I've been building a bare-metal no_std Rust kernel as an independent project, and I'd like feedback on its file-integrity mechanism.
Most integrity schemes (fs-verity, dm-verity, IMA) verify a file once — at load, or when a page is first read from storage — then trust the cached copy. That leaves a gap: if something corrupts the in-memory page after the check (a DMA-capable peripheral, a kernel bug, rowhammer), later reads return tampered bytes as authentic.
Re-hashing the whole file on every read closes the gap but scales with file size — reading 4 bytes of a 4 MiB file re-hashes all 4 MiB, which blows a sub-millisecond budget on edge hardware.
What I did instead:
Split each file into fixed 4 KiB blocks, each with a stored BLAKE3 leaf hash.
A ranged read verifies only the blocks it touches, so per-read cost is Θ(bytes read) rather than Θ(file size).
A lazily-recomputed Merkle root over the leaves bounds write cost (one block hash + a deferred root update, instead of a full rehash).
On real hardware (an x86-64 laptop and an ARM64 phone via Termux), block-level verification stays roughly constant — ~2.7 µs on x86-64, ~3.65 µs on ARM64 — across the whole 4 KiB–4 MiB range, while whole-file verification grows into milliseconds.
Repo (kernel + benchmark harness): I'll drop the link in a reply below.
Two things I'm genuinely unsure about and would value opinions on:
BLAKE3 SIMD in a no_std kernel. I'm running it in portable mode in-kernel right now. Is wiring up the SIMD path worth it on a bare-metal target, or more trouble than it's worth?
Constant-time leaf comparison. I accumulate per-byte differences without early exit to avoid a timing side channel on the verify path. Reasonable instinct here, or unnecessary?
Happy to go into the VFS hook or the lazy-Merkle update if anyone's interested.
This boundary will exist no matter what integrity scheme you use, because there will always be some interval after a value's integrity is checked but before that value is used in further computation. Your scheme pushes that boundary downstream a bit, so that the memory corruption you're concerned about detecting will be detected if it happens before your OS hands a page off to the userspace program that requested it, but cosmic rays and RAM defects care not for the OS/userspace split and can still corrupt data after it's in the userspace program's care.
If your OS is designed for an environment where memory corruption is common enough that repeatedly re-checking the data while it's in memory is a useful operation, then that risk needs to be accounted for in each program that runs on your OS, as well as in the OS itself, unfortunately. However, for most systems, the primary source of storage errors isn't memory corruption, but rather storage corruption, which is actually addressed if data is validated as it's copied from storage into memory.
You're right, and that's a fair correction — this moves the check-to-use boundary downstream rather than eliminating it. Corruption after the OS hands the page to userspace is outside what this catches, and you're correct that for most systems storage corruption is the dominant concern, which load-time/page-in verification already addresses.
The narrower case I'm targeting is the window where a page stays cache-resident and trusted across many reads after its initial check — e.g. the page-cache tampering class (Dirty Pipe, Copy Fail) where on-disk data is untouched but the cached copy is altered, so storage-boundary checks see nothing. Re-verifying on each read shrinks that specific window; it doesn't extend the guarantee into userspace, and I shouldn't imply it does. Appreciate you drawing the boundary precisely — I'll tighten how I frame the scope. Meanwhile, can you help?
Yeah — ZFS (and Btrfs) are the canonical precedent for block-level Merkle integrity, and the lazy root-update pattern is very much in that lineage. Thanks for the link, the Internals-for-Interns writeup looks great. The piece I'm exploring that differs is doing the verification inline on every read in a small no_std kernel, rather than at the storage/checksum layer — but the data structure owes a lot to that prior work. Appreciate the pointer. It will be great if you visit the codebase and help.
If you don't want to use SIMD, you should consider Skein, possibly round reduced. IIRC it's faster than Blake on 64-bit CPUs when SIMD isn't used. I think ZFS chose Skein for that reason.
For the “verify arbitrary blocks against a root without rehashing the whole file” part, it may be worth looking at Bao before building a custom tree format.
Bao is BLAKE3-based verified streaming, by one of the BLAKE3 authors, and it is aimed at exactly this kind of problem: encode the file once, then verify a byte range, or “slice,” against the root hash by checking only the relevant leaf data and the path back up the tree. That is very close to the data structure you are describing, with a lot of the details already worked out.
The reason it fits nicely is that BLAKE3 is already a binary Merkle tree internally over 1 KiB chunks. So if your verification block size is aligned and is a multiple of 1 KiB, each block can line up with a subtree of the hash you are already computing. You do not need a totally separate tree layer. If the block size is unaligned, you start crossing chunk boundaries and lose some of that advantage.
A concrete shape could be:
cache the interior node hashes
verify a page on read by hashing the leaf and walking up to the trusted root
on write, rehash the leaf, mark the path dirty, and recompute the root lazily
That lines up well with the lazy-update idea scottmcm mentioned.
On the Skein vs BLAKE3-without-SIMD question, I would probably weight that less heavily for this access pattern than for bulk hashing. If you are verifying one page per read, the cost is one leaf hash plus log(n) parent compressions, not full-file throughput where SIMD width dominates. BLAKE3’s portable backend should be fine at that granularity, and you get the tree structure essentially for free. With Skein, you would still need to build and maintain the Merkle layer yourself.