Proof format

Overview

We distinguish three kinds of proof steps: Branch, Fork and Leaf. Each step contains a skip value which corresponds to the length of the common prefix at that particular level.

Since the prefix is a portion of the path (itself obtained by hashing the key), we need not to provide the whole prefix. The length is sufficient to recover it.

Note also that the Fork and Leaf steps may seem like an optimization when looking only at the proof from an inclusion perspective; but they are actually necessary steps to verify insertion and deletion proofs (which verifies the proof from an exclusion standpoint, and thus require the full neighbor when there's only one).

Branch

The most common case encountered for every level that has 3+ nodes (or 2+ neighbors depending how you look at it). The neighbors array is an array of 4 * 32 = 130 bytes which corresponds to 4 hash digests.

These 4 digests are in reality a Merkle proof of a tiny binary Sparse-Merkle Tree of size 16 corresponding to all the nodes at that branch arranged according to their nibble (0 leftmost, f rightmost).

• The first 32 bytes of the neighbors array is the root hash of the top-most neighbor sub-tree containing 8 nodes.

• The last 32 bytes of the neighbors array is the direct neighbor of the node if any, or a null hash (32 times 0 bits).

To recover the hash of a Branch level, we must compute the following:

blake2b_256(prefix | sparse_merkle_root([node, ...neighbors]))

where sparse_merkle_root denotes the Merkle root hash obtained from arranging the 16 nodes by their nibbles as described, using null hashes for absent neighbors.

Fork

A Fork is a special Branch case where there's only one neighbor which is not a Leaf.

The step contains the full neighbor's preimage, as well as the nibble at which it sits. From there, we can recover the hash of a Fork level by computing:

blake2b_256(prefix | sparse_merkle_root([node, blake2b_256(neighbor.prefix | neighbor.root)]))

The neighbor.nibble indicates the location of the neighbor in the Sparse Merkle Tree, whereas the one from the node being proved is given by its path at that particular location.

Leaf

A Leaf is a special Branch case where there's only one neighbor which is a leaf of the trie.

The key and value corresponds to the hash digests of the neighbor's key and value respectively. Note that while we provide the full key, the proof only truly requires a suffix of the key up to the moment it separates from the node's path. The first bits of the keys are thus usually ignored and are only kept to make the proof more convenient to generate.