EIP-8364: SSZ Compact Multiproofs

Abstract

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.

Motivation

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:

• Bandwidth: each generalized index requires a varint or fixed-width unsigned integer, typically two to eight bytes. The proof descriptor requires 2 * N - 1 bits, where N is the total number of proof nodes — the requested indices and all helper indices together.
• Server preprocessing: to serve a request expressed as generalized indices, a server must compute the helper indices and plan an efficient traversal of its tree. A server handling a descriptor performs no preprocessing: the descriptor bits directly drive a depth-first traversal that emits the proof nodes in order.

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.

Specification

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.

Proof Descriptor

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:

• If the visited node is one of the N proof nodes, emit a 1 bit and do not descend further.
• Otherwise (the node has a descendant among the proof nodes), emit a 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:

• it contains at least one 1 bit,
• at most seven 0 bits follow the final 1 bit, and
• reading from the first bit, the count of 1 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.

Proof Node Ordering

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.

Example

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.

    descriptor bits          generalized indices

        0                            1
       / \                          / \
      0   1                        2   3
     / \                          / \
    1   0                        4   5
       / \                          / \
      0   1                       10   11
     / \                          / \
    1   0                       20   21
       / \                          / \
      1   1                       42   43
      ^                            ^

The descriptor bitlist is 00100101111 and serializes, with five padding bits, to 0x25e0.

Computing a Proof Descriptor

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.

def compute_proof_indices(indices: Sequence[GeneralizedIndex]) -> Sequence[GeneralizedIndex]:
    all_indices = set(get_helper_indices(indices)).union(indices)
    # sort in depth-first, left-to-right traversal order
    return sorted(all_indices, key=bin)

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:

def compute_proof_descriptor(indices: Sequence[GeneralizedIndex]) -> bytes:
    bitstring = ''
    for index in compute_proof_indices(indices):
        bitstring += '0' * (len(bin(index)) - len(bin(index).rstrip('0'))) + '1'

    # append zero bits to byte-align the descriptor
    if len(bitstring) % 8 != 0:
        bitstring += '0' * (8 - len(bitstring) % 8)

    return int(bitstring, 2).to_bytes(len(bitstring) // 8, byteorder='big')

Validating a Descriptor

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:

def compute_bits_from_proof_descriptor(descriptor: bytes) -> Sequence[bool]:
    bitstring = ''.join(['{0:08b}'.format(byte) for byte in descriptor])
    assert '1' in bitstring
    last_one_index = bitstring.rindex('1')
    assert len(bitstring) - last_one_index <= 8

    zeros_minus_ones = 0
    bits = []
    for i in range(last_one_index + 1):
        bit = bool(int(bitstring[i]))
        bits.append(bit)
        if bit:
            zeros_minus_ones -= 1
        else:
            zeros_minus_ones += 1
        assert (zeros_minus_ones < 0) == (i == last_one_index)
    return bits

Root Calculation and Verification

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):

def calculate_compact_multi_merkle_root(nodes: Sequence[Bytes32], descriptor: bytes) -> Root:
    bits = compute_bits_from_proof_descriptor(descriptor)
    assert len(nodes) == sum(bits)
    ptr = [0, 0]  # [bit_index, node_index]
    root = calculate_compact_multi_merkle_root_inner(nodes, bits, ptr)
    assert ptr[0] == len(bits)
    assert ptr[1] == len(nodes)
    return root

def calculate_compact_multi_merkle_root_inner(nodes: Sequence[Bytes32],
                                              bits: Sequence[bool],
                                              ptr: List[int]) -> Bytes32:
    bit = bits[ptr[0]]
    ptr[0] += 1
    if bit:
        node = nodes[ptr[1]]
        ptr[1] += 1
        return node
    else:
        left = calculate_compact_multi_merkle_root_inner(nodes, bits, ptr)
        right = calculate_compact_multi_merkle_root_inner(nodes, bits, ptr)
        return hash(left + right)

def verify_compact_merkle_multiproof(nodes: Sequence[Bytes32],
                                     descriptor: bytes,
                                     root: Root) -> bool:
    return calculate_compact_multi_merkle_root(nodes, descriptor) == root

Rationale

Shape Encoding vs Index Lists

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.

Uniform Node Encoding

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.

Relation to SSZ Bitlist

SSZ 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.

Generality

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.

Backwards Compatibility

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.

Test Cases

Valid descriptors:

Invalid descriptors, which fail the validity rules in the Specification:

Reference Implementation

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.

Security Considerations

Resource Exhaustion

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.

The Descriptor Does Not Prove Tree Structure

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

Copyright and related rights waived via CC0.