EIP-8364 SSZ compact multiproofs

No call decision · Scaling & data · EIP status Draft · created 2026-08-04

Defines a new encoding that compresses Merkle multiproofs into a bit string called a proof descriptor. A proof can be requested at roughly 2 bits per node, and the server can produce the proof with a single pass over the tree and no preprocessing.

Why it is needed

Ethereum summarizes data with a hash structure called a Merkle tree and uses Merkle proofs to confirm that some piece of data is genuine. The existing multiproof format for proving several nodes at once specifies the nodes to be proven as a list of generalized indices, and each index typically takes 2 to 8 bytes, which gets expensive when a different proof is requested dynamically each time. There is also a burden on the server side. Given a list of indices, the server has to separately compute the indices of the helper nodes needed for the proof and plan how to traverse the tree. This EIP's descriptor approach represents the shape of an entire proof at roughly 2 bits per node, and the server simply follows the descriptor bits, walking the tree once depth-first and emitting nodes in order. It is meant as a building block for protocols that dynamically exchange chosen proofs, such as light client protocols or proof-serving APIs.

What changes

Today

After EIP-8364

Who is affected

In depth

Structure of the proof descriptor

A multiproof is a set of N tree nodes combining the requested nodes and helper nodes with no distinction between them. No node is a descendant of another, and Merkleizing the whole set yields the tree root. The descriptor is built via a depth-first, left-first traversal starting at the root. If the visited node is a proof node, a 1 bit is written and no further descent happens. Otherwise a 0 bit is written and the traversal descends into the left child, then the right child. The result is N 1-bits and N-1 0-bits, for 2*N-1 bits total. In every proper prefix the count of 1-bits can never exceed the count of 0-bits, and across the whole string it exceeds it by exactly one, so the point where the count of 1-bits first exceeds the count of 0-bits is exactly the end. In other words, the descriptor marks its own end. In the original example, requesting a single generalized index 42 gives proof nodes in order 4, 20, 42, 43, 11, 3, and the descriptor is 00100101111, which serializes to 0x25e0.

Serialization and validity rules

When serializing, bits are filled starting from the most significant bit. Descriptor bit i is stored at bit 7 - i % 8 of byte i // 8, and 0 to 7 zero bits are appended for byte alignment. A valid descriptor must satisfy three conditions: it must have at least one 1-bit, there must be at most 7 0-bits after the last 1-bit, and reading from the start, the point where the count of 1-bits first exceeds the count of 0-bits must be exactly the last 1-bit. Implementations must reject descriptors that violate these. This rule ensures a valid descriptor has exactly one serialization, so there is no possibility of the same proof shape being represented by different bytes. The test cases' invalid examples are 0x00 (no 1-bit), 0x40 (traversal incomplete), 0xff (traversal ended at the first bit yet more 1-bits follow), and 0x25e000 (padding exceeds 7 bits).

Node ordering and descriptor computation

The N proof nodes are serialized in the order the traversal visits them, i.e., lexicographic order of the generalized indices' binary representations. The set of requested indices must not contain an ancestor of another requested index, since no pair in the proof node set may be in an ancestor-descendant relationship, and an ancestor's value is computed anyway in the course of verifying its descendant's proof. The reference implementation's compute_proof_indices sorts the union of the requested indices and the get_helper_indices result by their binary representations, and compute_proof_descriptor builds the descriptor by writing, for each index, as many 0-bits as the number of trailing zero bits in its binary representation, followed by its own 1-bit.

Root computation and verification

calculate_compact_multi_merkle_root replays the descriptor traversal. It consumes one bit per node visited: a 1-bit returns a proof node as-is, and a 0-bit combines the left and right partial results via hash(left + right). The hash function is the SHA-256 defined in the consensus spec. It asserts that the number of supplied nodes equals the count of 1-bits, and that when the traversal ends, the bits and nodes have been consumed exactly and completely. Verifiers must only use a descriptor if they derive it themselves from the generalized indices they intend to verify, or compare a peer-supplied descriptor against one derived that way and confirm it matches.

Design rationale

A list of generalized indices and the shape encoding carry the same information, but except for very sparse proofs the shape encoding is cheaper to transmit: roughly 2 bits per node including helper nodes, versus 2 to 8 bytes per requested index. For the server it is always cheaper. Since the descriptor bits are consumed in the same order as the depth-first traversal, no index arithmetic, helper index computation, or traversal planning is needed. The reason requested nodes and helper nodes are not encoded separately is that whoever built the descriptor already knows which nodes were requested, so the distinction would give neither side new information. SSZ Bitlist fills from the least significant bit and appends a length-marking 1-bit, but since the descriptor marks its own end such a bit is unnecessary, and the most-significant-bit-first approach lets the serialized bytes be read in traversal order. This encoding is byte-compatible with existing implementations and applies broadly to binary Merkle trees of arbitrary depth.

Security considerations

The descriptor length sets an upper bound on the resources consumed by proof processing. A 2*N-1 bit descriptor means exactly N nodes and N-1 internal hashes. Before allocating buffers or starting hashing, implementations must validate the descriptor, including the balance condition, confirm that the number of supplied nodes equals the 1-bit count, and impose a context-appropriate limit on descriptor length. Chain-shaped descriptors can push a naive recursive implementation to depth N, so this should be avoided by using iterative traversal or by capping recursion depth to the maximum tree depth possible in that context. Also, the descriptor does not prove the tree structure itself. A single bit does not say whether a node is a leaf or the root of an unexplored subtree. A 32-byte value alone cannot tell whether it is a piece of data or the hash of two children, so for fixed-shape SSZ types the index is statically determined, but for SSZ lists or progressive trees with varying depth, the shape of the structure must first be validated, for example through a length mix-in, before it can be interpreted as a specific leaf.

Current status

This EIP is a Draft-status Standards Track, Core proposal created on August 4, 2026. It defines a new format without changing existing data structures, serialization, or proof formats, so it has no effect on existing multiproof users. Since it is still at the draft stage, the specification content is subject to change.

Original EIP · ← EIPs