Hash Trees and the Root of Trust in a Checksummed Filesystem

A checksum stored beside its block protects that block against damage that occurs after the write. It does not protect the checksum. If an attacker or a fault can modify both the block and the value recorded for it, verification succeeds and proves nothing. The gap is closed by making the checksum of one block part of the verified content of another, recursively, until the chain terminates at a single value that is trusted by some other means. That construction is a hash tree, and the choice of what to trust at the top is where the design problems live.

From independent checksums to a chain

Consider a filesystem where every data block has a checksum recorded in the block pointer that names it, and every metadata block likewise. Verification of a data block requires reading its pointer, which requires reading the parent block, which requires verifying the parent against the grandparent’s pointer. Follow that to its conclusion and every verification terminates at the root block, whose checksum is recorded nowhere within the tree.

This is the same structure as a Merkle tree, and it has the same property: a single trusted root value authenticates the entire contents. Changing any block changes its checksum, which changes the pointer to it, which changes the parent’s contents and therefore the parent’s checksum, and so on up to the root. An adversary who wants to substitute one block without detection must produce a chain of consistent changes all the way to the root, which requires either forging the hash function or replacing the root.

Two consequences follow immediately, and both are useful in ordinary operation as well as under attack. Verification is incremental: a read of one block verifies only the path from the root to that block, which for a tree of depth three or four is a handful of checksums rather than a full scan. And a failure localises: the point in the path where verification first fails identifies the level at which the damage occurred, which distinguishes a corrupted data block from a corrupted pointer from a corrupted interior node.

ZFS’s tree of block pointers is exactly this. The uberblock, at the top, holds the root block pointer; the root’s checksum is in the uberblock; every other block’s checksum is in the pointer that names it. Reading a file walks from the uberblock down through indirect blocks to the data, verifying each block as it is read. The depth is bounded by the block size and the pointer size: a 128 KiB block holding 128-byte block pointers addresses 1024 children, so three levels address 2^30 blocks and four address 2^40 — enough for a petabyte-scale pool at 128 KiB per block.

The root and what it means to trust it

The root of a hash tree is a single value, and the security of everything below it reduces to the question of how that value is obtained. Three answers are in use, and they correspond to three different threat models.

The root is read from the same medium it authenticates. This is ZFS’s arrangement: the uberblock is stored in a small ring of locations at the start of each vdev, each copy carrying its own checksum, and the pool is mounted by selecting the uberblock with the highest transaction group among those that verify. The chain is self-consistent but not anchored — a fault or an attacker that rewrites the uberblock and the entire tree consistently is undetectable from within. What makes this acceptable is that the threat model is accidental corruption, not a determined adversary with write access to the raw device. Against the first, the ring of redundant uberblocks with independent checksums is strong; against the second, it is not a defence at all.

The root is passed to the kernel from outside the medium. This is dm-verity’s arrangement: the hash tree is built over the data at image-creation time, the root hash is computed and signed or recorded separately, and the kernel is given the root hash as a parameter when the device is configured. Verification of any block then terminates at a value the kernel already knows, so an attacker who modifies the image on disk cannot make it verify. The trust anchor has moved from the storage to the boot configuration, which is the right place when the storage is not trusted — a downloaded image, a read-only system partition, a container layer.

The root is signed and the signature verified against a key in hardware. This is the arrangement for measured boot and for encrypted volumes whose header carries a signed manifest. It is the strongest anchor and the most operationally expensive, because key rotation and revocation become filesystem concerns.

/* Walking a hash tree: verify each level before trusting what it names. */
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

struct hnode { uint64_t addr; uint32_t len; uint8_t digest[32]; };

void sha256(const void *buf, size_t len, uint8_t out[32]);   /* FIPS 180-4 */
/* Returns the child covering leaf_addr; reads only an already verified node. */
int lookup_child(const uint8_t *node, uint32_t len, uint64_t leaf_addr,
                 struct hnode *out);

int verified_read(int fd, const struct hnode *root, uint64_t leaf_addr, void *out)
{
    struct hnode cur = *root;
    for (;;) {
        uint8_t *buf = malloc(cur.len);
        uint8_t got[32];
        if (!buf) return -1;
        if (pread(fd, buf, cur.len, cur.addr) != (ssize_t)cur.len) {
            free(buf);
            return -2;
        }
        sha256(buf, cur.len, got);
        if (memcmp(got, cur.digest, 32) != 0) {
            free(buf);
            return -3;                 /* this level is damaged; stop here */
        }
        if (cur.addr == leaf_addr) {
            memcpy(out, buf, cur.len);
            free(buf);
            return 0;
        }
        struct hnode child;
        if (!lookup_child(buf, cur.len, leaf_addr, &child)) {
            free(buf);
            return -4;
        }
        free(buf);
        cur = child;                   /* only reached when the parent verified */
    }
}

The property that matters in that loop is that cur is only advanced after the current level verifies. A corrupted interior node cannot redirect the walk to an arbitrary leaf, because the walk stops at the corrupted node. This is the structural difference between a hash tree and a checksum table: a table lookup by address trusts the address, while a tree walk verifies the path that produced it.

What the tree costs, and where the cost falls

The storage overhead of a hash tree is the size of the interior nodes. For a hash tree over 4 KiB blocks with SHA-256, one interior node holds 128 hashes of 32 bytes, so a single node covers 512 KiB of data: the hash level adds one part in 128, about 0.8 percent, to the protected image, and each level above it adds a negligible further amount. A 1 GiB image therefore carries roughly 8 MiB of hash blocks. ZFS’s interior nodes are larger relative to the data they cover, because a block pointer is 128 bytes and holds far more than a checksum: at a 128 KiB block size, pointer storage costs roughly one part in a thousand per level of the tree.

The read cost is depth. A verified read of one block touches one node per level, so a tree of depth four performs five reads instead of one. On a cached filesystem this is nearly free, because interior nodes are hot. On a cold one it multiplies the random-read count by the depth, which is why deep trees with small blocks are a bad combination: 4 KiB blocks with 128-byte pointers give only 32 children per node, and a terabyte filesystem needs six levels. Large blocks amortise the depth, which is the same argument that drives block size in copy-on-write designs generally.

The write cost is the reason hash trees pair naturally with copy-on-write. Updating one leaf changes its parent, which changes the grandparent, up to the root — so a single 4 KiB write to a deep tree rewrites one node per level plus the root. An in-place filesystem cannot do this without a journal covering the whole path; a copy-on-write filesystem does it by allocating new nodes and switching the root pointer, which is atomic and requires no journal at all. The tree structure and the update strategy are not independent choices.

Verification is not authentication

A hash tree built with CRC32C detects accidental damage along the whole path, and it is not an authentication structure. CRC is linear, so an adversary who knows the polynomial can compute a modified block whose CRC is unchanged, and can do so at every level of the tree consistently. The chain does not add security against a forger; it adds localisation and incremental verification, which are worth having on their own.

For an authentication guarantee the hash function must be collision-resistant, and the root must be anchored outside the adversary’s reach. Both conditions are needed. A SHA-256 tree whose root is read from the same disk is a strong integrity check against media faults and a weak one against tampering, because the attacker replaces the root along with everything else. A CRC tree with an externally anchored root detects nothing an attacker does, because the attacker can forge each level.

The distinction shows up in how these systems are deployed. dm-verity uses SHA-256 and an external root because its purpose is to make a read-only image tamper-evident on a device the attacker may control. ZFS uses Fletcher-4 or a selected hash depending on configuration, with a self-stored root, because its purpose is to make a large writable pool resilient to hardware faults. Neither is a weaker version of the other; they answer different questions, and checksum strength and what CRC32C and SHA-256 each guarantee covers the function-level reasoning that separates them.

Where the chain stops being enough

Two limits are worth stating because they bound what any tree can claim.

The tree authenticates content, not freshness. An attacker who can restore an older, internally consistent version of the entire tree — an old root and all its blocks — presents a state that verifies perfectly and is simply out of date. Defending against rollback requires a counter or a monotonic value outside the tree, which is why ZFS records a transaction group number in the uberblock and why the mount logic prefers the highest one that verifies. That preference is a freshness check, not a cryptographic one; an attacker who can write an uberblock with an arbitrarily high transaction group defeats it.

The tree authenticates what was written, not what should have been written. A bug that computes the wrong data and the matching checksum produces a tree that verifies end to end. No structure built from self-consistent checksums can catch that class, and it is the reason the remaining exposure sits above the filesystem, in the path between the application’s buffer and the block the filesystem wrote — the boundary that end-to-end protection information and the checksum boundary examines.