This EIP introduces a compact encoding for Merkle multiproofs. A multiproof of N tree nodes is encoded as a proof descriptor, a bitlist of 2 * N - 1 bits describing the shape of the proof as a traversal of the Merkle tree, followed by the N nodes in traversal order. The descriptor encodes requested nodes and helper nodes uniformly.
The descriptor doubles as a request format: a client can describe an arbitrary multiproof to a server in roughly two bits per node, and the server can produce the proof in a single descriptor-guided traversal of its tree, without computing helper indices.
The existing multiproof format identifies the proven nodes by a list of generalized indices, which are convenient for identifying individual tree nodes but inefficient when used directly to request multiproofs dynamically:
2 * N - 1 bits, where N is the total number of proof nodes — the requested indices and all helper indices together.The descriptor also frames the response: the number of 1 bits determines the exact number of proof nodes, and verification is a linear-time traversal of the bits and nodes.
This format is a building block for protocols and APIs that serve dynamically-chosen proofs, such as light client protocols and proof-serving endpoints.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 and RFC 8174.
This specification extends the Simple Serialize (SSZ) Merkle proof specification and reuses its definitions of GeneralizedIndex and get_helper_indices. The hash function is SHA-256, as defined in the consensus specifications.
A multiproof is a set of N tree nodes — requested nodes and helper nodes, treated uniformly — such that no node is a descendant of another and, together, the nodes merkleize to the root of the tree.
The proof descriptor is a bitlist constructed by a depth-first, left-to-right traversal from the root of the tree:
N proof nodes, emit a 1 bit and do not descend further.0 bit, then traverse its left child followed by its right child.The resulting bitlist has exactly N 1 bits and N - 1 0 bits, 2 * N - 1 bits in total. Because every proper prefix of the bitlist contains at most as many 1 bits as 0 bits, while the full bitlist contains one more 1 bit than 0 bits, the descriptor is self-delimiting: the traversal ends at the first bit position where the count of 1 bits exceeds the count of 0 bits.
When serialized, descriptor bits are packed most-significant-bit first: bit i of the descriptor is stored at bit 7 - i % 8 of byte i // 8. Between zero and seven 0 bits are appended for byte alignment.
A serialized descriptor is valid if and only if:
1 bit,0 bits follow the final 1 bit, and1 bits first exceeds the count of 0 bits exactly at the final 1 bit.Implementations MUST reject invalid descriptors. These rules also make the encoding canonical: every valid descriptor has exactly one serialization, so a given proof shape is not byte-malleable.
The N proof nodes are serialized in the order the traversal above visits them: depth-first, left to right. Equivalently, they are ordered lexicographically by the binary representations of their generalized indices.
A multiproof for generalized index 42 consists of proof nodes at generalized indices 4, 20, 42, 43, 11 and 3, in proof node order. The figure below shows the descriptor bit emitted at each visited node (left) and the corresponding generalized indices (right); subtrees below proof nodes are not visited and are not shown. The ^ marks the requested index.
The descriptor bitlist is 00100101111 and serializes, with five padding bits, to 0x25e0.
The set of proof node indices for a set of requested generalized indices is the union of the requested indices and their helper indices, sorted in traversal order. The requested indices MUST NOT contain an index that is an ancestor of another requested index: a proof node set contains no descendant pairs, and an ancestor's value is computed anyway while verifying its descendant's proof.
The descriptor is computed from the sorted indices. Each proof node contributes one 0 bit for each internal node of which it is the leftmost descendant among the proof nodes — one per trailing zero bit of its generalized index — followed by its own 1 bit:
The following function validates a serialized descriptor and returns its bits, up to and including the final 1 bit. Each assert identifies a condition under which the descriptor MUST be rejected:
The root of a compact multiproof is calculated by replaying the descriptor traversal, consuming one descriptor bit per visited node and one proof node per 1 bit. A verifier MUST derive the descriptor from the generalized indices it intends to verify, or check a supplied descriptor for equality against one so derived (see Security Considerations):
A list of generalized indices and a shape encoding carry the same information. For all but the sparsest proofs the shape encoding is cheaper to transmit — about two bits per proof node, helpers included, versus two to eight bytes per requested index — and it is strictly cheaper to serve: the descriptor bits are consumed in the same order as a depth-first tree traversal, so a proof server needs no index arithmetic, helper index computation, or traversal planning. The canonical node ordering also removes any ambiguity in proof node serialization.
The party that constructs a descriptor derives it from the generalized indices it wants proven, so it already knows which proof nodes it requested and which are helpers. Encoding the distinction would add complexity and bits without adding information for either party.
BitlistSSZ Bitlist[N] serialization packs bits least-significant first and appends a sentinel 1 bit to delimit the list length. The descriptor is already self-delimiting, so a sentinel is redundant, and the most-significant-first packing keeps the serialized bytes readable in traversal order. This encoding is also byte-compatible with existing implementations of this format.
The descriptor encodes the shape of an arbitrary binary tree, so the format applies to any binary Merkle tree with arbitrary leaf depths, including the progressive tree shapes introduced in EIP-7916.
This EIP defines a new proof format and modifies no existing data structure, serialization, or proof format. Existing producers and consumers of generalized-index multiproofs are unaffected.
Valid descriptors:
| Requested indices | Proof node order | Descriptor bits | Serialized |
|---|---|---|---|
[1] | [1] | 1 | 0x80 |
[2] | [2, 3] | 011 | 0x60 |
[10, 11] | [4, 10, 11, 3] | 0010111 | 0x2e |
[42] | [4, 20, 42, 43, 11, 3] | 00100101111 | 0x25e0 |
Invalid descriptors, which fail the validity rules in the Specification:
| Serialized | Reason |
|---|---|
0x00 | no 1 bit |
0x40 | traversal incomplete: 1 bits never outnumber 0 bits |
0xff | traversal ends at the first bit, but further 1 bits follow |
0x25e000 | more than seven padding bits after the final 1 bit |
The Python functions in the Specification section are the reference implementation. They are directly executable when combined with the helper functions of the SSZ Merkle proof specification.
The descriptor length bounds all resources needed to process a proof: a descriptor of 2 * N - 1 bits describes exactly N proof nodes and N - 1 internal hashing steps. Implementations are expected to validate a descriptor (including the balance condition) before allocating proof-sized buffers or performing hashing, to check that the number of supplied proof nodes equals the number of 1 bits (as the reference functions do), and to enforce context-appropriate limits on descriptor length. Naive recursive implementations can be driven to a recursion depth of N — linear in the descriptor length — by a chain-shaped descriptor; an iterative traversal, or a recursion bound set to the maximum plausible tree depth of the context, avoids this.
A 1 bit terminates the traversal at a node without revealing whether that node is a leaf or the root of an unexplored subtree. A verifier is expected to derive the descriptor from the generalized indices it intends to verify — or check a supplied descriptor for equality against one so derived — rather than trusting a peer-supplied descriptor as a statement about the structure or contents of the tree. In particular, matching a known root only proves that the supplied nodes occupy the tree positions described by the descriptor; it proves nothing about which positions the consumer should have queried.
This mitigation is only as strong as the verifier's knowledge of the tree's shape. A 32-byte node value does not reveal whether it is a data chunk or the hash of two children, so knowing the correct generalized indices requires knowing the shape of the tree at those positions. For fixed-shape SSZ types the relevant generalized indices are static and known in advance; for variable-size structures — SSZ lists, or progressive trees whose depth grows with element count — the consumer also needs to verify the structure's shape (for example, via the SSZ length mix-in) before interpreting a proof node as a particular leaf.
Copyright and related rights waived via CC0.