zx-verity provides an API for application components to read data from local storage. When retrieving data the integrity of the data is verified and causing reads to fail when the data has been modified or corrupted. zx-verity is based on a Merkle Tree, and is derived from a similar system in Chrome OS.
All of these implementations share the algorithm documented herein.
The merkle tree contains levels. A level is a row of the tree, starting at 0 and counting upward. Level 0 represents the level that contains hashes of chunks of the input stream.
Each level contains a number of hashes of the previous level. The hashes within a level are computed from 8kb blocks from the previous level (or data, if level 0), prepended with a block identity.
A block identity is the binary OR of the starting byte index of the block within the current level and the current level index, followed by the length of the block. For level 0, the length of the block is 8kb, except for the last block, which may be less than 8kb. All other levels use a length of 8kb, even when the last block is 0 padded.
Compute level 0 with the input data. Construct and compute subsequent levels using the previous level hashes as input data, until a level hashes contains exactly 32 bytes. This last level contains the root digest of the merkle tree.
As a special case, when there is no input data, implementations may need to handle the calculation independently. The digest of the empty input is simply the SHA-256 of 12 0 bytes, the block identity of a single 0 length block.
0xff - “oneblock”
0xff - “small”
0xff - “large”
0xff - “unaligned”
0xff0080 bytes filled with repetitions of
0xff0080 - “fuchsia”