# Fuchsia Merkle Roots

[Merkle Trees][merkletree] are used in various places in the Fuchsia ecosystem,
including the [FAR Archive Format][far], the Blob Storage Filesystem, and the
[Package Manager][pm].

In [Zircon][zircon] `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][merkletree], and is derived from a similar
system in [Chrome OS][dmverity].

All of these implementations share the algorithm documented herein.

## Parameters of the Merkle Tree

 * Block size: 8kb, 0 padded.
 * Root digest size: 32 bytes.
 * Hash algorithm: SHA-256.
 * Block digest computation: SHA-256(u64(offset | level) + u32(length) + data)

## Definitions

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.

## Computation of a level

 1. Initialize the level with an index, an offset starting at 0, and an empty
    list of hashes.
 2. For each 8kb (or remainder of) of input, compute the next block identity by
    taking the binary OR of the level index and the current offset, followed
    by the length of the input.
 3. Init a SHA-256 digest, append to it the identity, the input, and if the
    input is shorter than 8kb, a pad of 0 up to 8kb.
 4. Append the output of the digest to the level's list of hashes. Increment
    the offset by the input length.
 5. Repeat 1-4 until all input is consumed.
 6. If the length of hashes is 32, finish.
 7. If the length of hashes is not 8kb aligned, 0 fill up to an 8kb
    alignment and compute more levels until there is a root level containing a
    single 32 byte digest.

## Computation of a root digest

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.

## A note about the empty digest

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.

## Example values

 * The empty digest:
 `15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b`
 * 8192 bytes of `0xff` - "oneblock"
 `68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737`
 * 65536 bytes of `0xff` - "small"
 `f75f59a944d2433bc6830ec243bfefa457704d2aed12f30539cd4f18bf1d62cf`
 * 2105344 bytes of `0xff` - "large"
 `7d75dfb18bfd48e03b5be4e8e9aeea2f89880cb81c1551df855e0d0a0cc59a67`
 * 2109440 bytes of `0xff` - "unaligned"
 `7577266aa98ce587922fdc668c186e27f3c742fb1b732737153b70ae46973e43`
 * `0xff0080` bytes filled with repetitions of `0xff0080` - "fuchsia"
 `2feb488cffc976061998ac90ce7292241dfa86883c0edc279433b5c4370d0f30`


[merkletree]: https://en.wikipedia.org/wiki/Merkle_tree "Merkle Tree"
[dmverity]: https://www.chromium.org/chromium-os/chromiumos-design-docs/verified-boot "Chrome OS Verified Boot"
[far]: /docs/development/source_code/archive_format.md "Archive Format"
[pm]: /src/sys/pkg/bin/pm/README.md "Package Manager"
[zircon]: /zircon/README.md "Zircon"