EIP-3102 Binary trie structure

No call decision · Scaling & data · EIP status Stagnant · created 2020-09-01

A proposal to merge the account trie and storage trie into one, convert the hexary structure into a binary structure, and replace the hash function with blake2b to reduce proof size.

Why it is needed

Ethereum's current state storage structure is a hexary tree called the Merkle Patricia Trie (MPT). A hexary tree has the advantage of shallow depth, meaning fewer hash computations, but in practice disk access has proven to be a bigger bottleneck than hashing. Because of this, clients are moving away from storing every internal node on disk, instead storing only values flatly and recomputing internal nodes as needed. There is also demand for making stateless verification, confirming state via proofs without downloading blocks, easier to use, and binary trees have proofs roughly 4x smaller than hexary trees, which favors this goal. On top of this, the MPT carries a lot of complex machinery, such as RLP encoding and optimizations that embed small nodes into their parent, which creates a high risk of bugs, and the disk space saved by those optimizations is only about 1MB, negligible compared to the roughly 300GB needed for a full sync.

What changes

Today

After EIP-3102

Who is affected

In depth

Trie structure and nodes

The trie is made up of nodes N=(N_l, N_r, N_p, N_v). N_l and N_r are the hashes of the left and right children respectively, with empty_hash (the hash of the empty string) used when a child is absent. N_p is an optional prefix, a bit string shared by all keys beneath this node. N_v is the value, present only on leaf nodes. A node whose children are both empty_hash is a leaf, all others are internal nodes. The 'leaf marker' bit present in the old MPT is removed, replaced by treating childless nodes as leaves.

Account fields and key structure

Each field of account A=(A_b, A_n, A_c, A_s) forms its key by taking the first 254 bits of hash(A_a) (hash(A_a)[0..253]) and appending 2 bits. Balance A_b is ...++0b00, nonce A_n is ...++0b01, code A_c is ...++0b10, and storage root A_s is ...++0b11. Storage slot k is located via ...++0b11++hash(k). If EIP-2926 is applied, A_c becomes the root of a Merkle tree formed by splitting code into chunks, and code chunk c is accessed via ...++0b10++u256(c). The text notes that if more fields are needed at the account level, the third bit can be reserved for future use.

Merkleization (hashing) rule

A node without a prefix is hashed as internal_hash = hash(left_child_hash || right_child_hash), leaf_hash = hash(hash(key) || hash(leaf_value)). A node with a prefix converts the path length from the root to that node (path_length) into a u256, prepends it, and hashes again: internal_hash_with_prefix = hash(u256(path_length-1) || internal_hash), and leaf_hash_with_prefix follows the same pattern. A leaf's value is always stored as hash(value), to account for cases like code that exceed 32 bytes.

Why blake2b was chosen as the hash function

A binary tree has roughly 4x more nodes than a hexary tree, which means that many more hashing operations. To offset this performance cost, blake2b was chosen over keccak256 for its speed. BLAKE3 is faster, but at the time of writing there was no official golang implementation, which was judged a security risk, so blake2b was adopted instead.

Why a binary tree was chosen over a hexary one

For a tree with N leaves and k children per node, the average proof (branch) length is roughly 32*(k-1)*log(N)/log(k) bytes, and this expression is minimized at k=2. Comparing at N=2^24, it is 768 bytes at k=2, 1152 bytes at k=4, 1792 bytes at k=8, and 2880 bytes at k=16. The original reason for using a hexary structure was to reduce the number of disk reads, but it turns out that even a binary tree can be 'mimicked' at the database layer in the same way, so that reasoning no longer holds. It is also noted that Eth2 (the consensus layer) plans to widely use binary trees, which is an additional compatibility advantage.

Why path length is used instead of the prefix bit string

To reduce the complexity of byte manipulation, hashing a node with a prefix uses only the bit length of the path from the root to that node (path length), not the prefix bit string itself. It is explained that using the path length from the root instead of the prefix length has the advantage that deleting a single leaf does not require rehashing the sibling node.

Merging the account and storage tries

Since clients are trending toward storing keys and values in a 'flat' database, the account's address hash is prepended to each storage slot key so that all of an account's data is grouped together on disk, and the account trie and storage trie were merged into one to also simplify the proof structure.

Transition risk and current status

The text explicitly states that a hard fork is required to move to this structure, and notes that converting all state to the new structure during the transition is heavy work, which could create an incentive for some clients to delay the switch, potentially lowering network security around the transition point. It mentions EIP-2584 as a proposed transition procedure for this purpose. This EIP's status is Stagnant, meaning it is not currently being actively worked on.

Original EIP · ← EIPs