Understanding EIP-7864's Unified Binary Tree

Thanks to Ignacio Hagopian (EIP-7864 author) for a quick review of this article and the cover image features a tree from the Goerli Park.

Intro

Unlike Bitcoin, Ethereum includes something called "state root" in its current block's header. For being functional, it's not necessary to have a state root, since any new full node joining the network can sync and execute all blocks to arrive at the current state. However, running full-node is time and resource-consuming. As of Feb 2025, the Ethereum's current blockchain size is ~1500 GiB. Forget about mobile phones, even most laptops don't have that much space capacity. To make things worse, we also have many L2s. It's not practical for users to run full nodes for every network they use. Hence, almost every Ethereum or L2 user knowingly or unknowingly trusts a full-node RPC provider. If these providers give malicious responses, the user won't realize until money is lost.

That's why Ethereum, since its inception in mid-2015, came with a state root, a 32-byte value that is calculated by encoding the entire state using the Merkle Patricia Trie structure. This enables devices with limited storage/computation to still use Ethereum in a safe and trustless way.

However, MPT has many complexities like RLP and Extension Nodes which make writing zk constraints extremely challenging (was in development for about 2 years). Being a hex-ary trie, its proof size is quite huge, especially when required to supply multiple state proofs. Light clients also face an edge case while operating on a partial MPT.

Verkle tree solution was studied for the last few years and attempted to solve the above problems, however, it's not post-quantum safe. The security of hash functions is not proven to be affected by quantum computers. Hence, the hash-based Binary tree can be a promising solution.

Unified Binary Tree (UBT)

There are many technical details specified in the EIP-7864. This post is an informal attempt to specify the details one by one, such that it can be easy for an engineer to digest quickly.

Step 1 - Sparse Tree

Let's imagine a sparse merkle tree structure with 256 depth, meaning the number of leaves is $2^{256}$ . Each leaf stores a 256-bit value. This makes it like a mapping of uint256 to uint256, where we traverse down the tree by consuming a bit from the key.

In the following steps, we will make some modifications to the tree to arrive at the Binary Tree specified in EIP-7864.

Spoiler alert: the UBT is not sparse, it will be discussed later in Step 8.

Step 2 - Group every 256 leaves

In the MPT's Account trie, the leaf was an RLP byte string of tuple of the nonce, balance, code hash, and storage root. It's convenient to have these details together.

In our binary tree, how can we keep these related values together?

1. We can hash their RLP string and store it as the leaf value.
2. We can store related values in adjacent leaves in the merkle tree.

The first option adds an extra layer of hashing and increases complexity. The second option is simpler. Let's go!

To be able to store related items in adjacent leaves in a neat way, we can allocate adjacent groups of 256 leaves and call it "sub-tree". This means our original 256-bit key of the huge tree is split into two parts: 248-bit stem-key + 8-bit sub-key.

Note that from a structural perspective, there's no difference from our original 256-depth sparse merkle tree. We have simply grouped all the leaves of our massive tree into groups of 256 leaves. So it looks like we have a tree of 248-depth, and each of its leaves is an 8-depth sub-tree.

There are three types of sub-trees:

• Account sub-tree
• Storage sub-tree
• Code chunks sub-tree

All of these sub-trees are 8-depth, so they look the same. The only difference is the kind of data that is stored in the leaves.

Step 3 - Account sub-tree

Details of an account will be stored in a subtree. To reach that sub-tree for an account we need to convert a 20-byte address into a 31-byte key using the following logic:

fn address_to_key(address: [u8; 20]) -> [u8; 31] {
  let address: [u8; 32] = to_bytes_32(address);
  let tree_idx: [u8; 32] = [0u8; 32];

  // use first 31 bytes result of the hash
  let result: [u8; 32] = hash(concat(address, tree_idx));
  result[..31]
}

In a sub-tree there are 256 leaves. Every account has the following details:

• Nonce (8 bytes)
• Balance (16 bytes)
• Bytecode (dynamic, max length 24kb)
• Storage (dynamic, max count is very high)

Our goal is to somehow store it. Now nonce and balance could each take a leaf but each leaf size is 32 bytes. So to save proof cost, we can combine these details in a single leaf.

First leaf data layout

• 1 byte: Version byte
• 4 bytes: Reserved for future usage
• 3 bytes: code size
• 8 bytes: nonce
• 16 bytes: balance

Second leaf

• 32 bytes: Codehash

Rest of the leaves

• Third leaf to 64th leaf: Reserved for future usage.
• 65th leaf to 128th leaf: Reserved for Storage.
• 129th leaf to 256th leaf: Reserved for Bytecode chunks.

Step 4 - Storage sub-tree

Previously, there were MPTs inside MPTs (account trie contained storage trie). To open a storage slot, we had to open the account's storage root first, which adds proof size as well as extra work. In the Binary tree, we could avoid this by combining all key-value pairs in the single tree.

The first 64 storage slots are stored in the Account's sub-tree. The 65th leaf to 128th leaf is reserved for this purpose. The rest of the storage slots in groups of 256 are stored together in a deterministically random sub-tree calculated using the following logic.

def get_tree_key_for_storage_slot(address: Address32, storage_key: int):
    if storage_key < (CODE_OFFSET - HEADER_STORAGE_OFFSET):
        pos = HEADER_STORAGE_OFFSET + storage_key
    else:
        pos = MAIN_STORAGE_OFFSET + storage_key
    return get_tree_key(
        address,
        pos // STEM_SUBTREE_WIDTH,
        pos % STEM_SUBTREE_WIDTH
    )

This helps with giving state proof for Solidity arrays which start at a deterministically random slot and then all array elements are sequential. In the case of solidity mappings, it will store things in random leaves in our UBT, but if the solidity mapping points to a structure (e.g. mapping(address => Person)) then solidity lays out the structure contents sequentially, so we can make easy state proofs for that too.

Step 5 - Bytecode chunk sub-tree

Previously in MPT only codehash was present in the state. Opening a small part of bytecode through state proof meant providing an entire preimage of codehash which is lengthy. This is troublesome especially when we want to create block execution proof, a worse-case block would touch as many Ethereum accounts and we have to witness all bytecode when only a small portion of it is used, this causes a lot of hashing, creating a DoS vector for zk light clients.

In the new UBT, we want to improve this situation by placing the bytecode in the merkle tree, chunk by chunk in the leaves. So that zk light clients can expose sufficiently required code slices. The costs of CALL opcodes can also be updated to incentivize usage of less bytecode.

Bytecode in the worst case (24kb) will require 750+ leaves. So we need to allocate other sub-trees to be able to fill all the bytecode.

A naive approach can be to simply break bytecode into 32-byte chunks and place them in the merkle tree. However, note that bytecode can also contain push opcodes. So when you are given a 32-byte chunk from a huge bytecode, you are not sure if the first byte is an executable opcode or part of a push opcode.

To resolve this issue, we can simply allocate 1 byte in every chunk to store the number of bytes that are non-executable (part of the push opcode in the previous chunk).

Layout of chunk

• 1 byte: number of non-executable/push bytes at the begining of this chunk
• 31 bytes: raw bytecode

Example 1 - short bytecode

# raw bytecode len 3 bytes
345f55

# 1-byte num of non-exec bytes + 31-byte chunks
- 00345f5500000000000000000000000000000000000000000000000000000000

Example 2 - long bytecode

# raw bytecode len 64 bytes
5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b
5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b

# 1-byte num of non-exec bytes + 31-byte chunks
- 005b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b
- 005b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b
- 005b5b0000000000000000000000000000000000000000000000000000000000

Example 3 - long bytecode with push opcode

# raw bytecode len 64 bytes
5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b6911223344
5566778899aa5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b

# 1-byte num of non-exec bytes + 31-byte chunks
- 005b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b69112233
- 07445566778899aa5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b
- 005b5b0000000000000000000000000000000000000000000000000000000000

In the above example, we have a PUSH10 (0x69) in the first chunk whose push data is also going into the second chunk. The complete instruction looks like 69112233445566778899aa, however when we break it into 31-byte chunks we have 445566778899aa push bytes, hence we store 7 in the num of non-exec bytes.

The first 128 bytecode chunks are stored in the account sub-tree. The rest of the chunks in groups of 256 chunks are stored somewhere in the UBT.

def get_tree_key_for_code_chunk(address: Address32, chunk_id: int):
    return get_tree_key(
        address,
        (CODE_OFFSET + chunk_id) // STEM_SUBTREE_WIDTH,
        (CODE_OFFSET + chunk_id)  % STEM_SUBTREE_WIDTH
    )

Step 6 - Simplify the tree by hash function special case

Usually in a Merkle tree, the hash value of a node is the hash of the concatenation of its children.

top = hash(concat(A, B))

If you see the scale of our tree, most of it is going to be empty even after 100 years of production usage.

There will be a lot of hashing involved, we can add a special case - if both A and B are 0, then hash(concat(0, 0)) is 0.

This means if our tree is empty, its root is 0.

Similarly, if a leaf is non-zero, we can compute the hash of that section easily.

Also, note that the hash function is not yet finalized. People are waiting for the security analysis of poseidon2.

Step 7 - Empty node to further simplify tree

A naive approach for creating such a tree in memory will require about $10^{68}$ GB of memory.

To ghost the unused portions of the tree, we can introduce "Empty Node".

Interestingly, the usage of empty nodes to hide the section or actual full sections does not affect the state root.

Step 8 - Convert into a non-sparse tree to further simplify the tree

In a sparse merkle tree, the proof size is $O(logb(leaves_{max}))$ . In our tree where we have $2^{256}$ depth, we will have a very huge proof size i.e. 32 bytes x 256 = 8192 bytes.

Especially, when most of the leaves in our tree are going to be empty even after 1000 years of production usage. The ideal case would be to have the proof in $O(logb(leaves_{count}))$ .

We introduce a structure something called StemNode which is supposed to represent the 256 leaves of the sub-tree. It also stores the 31 bytes of the stem.

struct StemNode {
  stem: [u8; 31],
  leaves: [u256; 256],
}

The goal is to have a minimal amount of internal branching nodes. If there's just a single StemNode then we can place it directly.

Tree examples

Following is an empty tree:

Since there's nothing, the root node is EmptyNode and root hash is 0.

First insertion

Now we insert one element key=bytes32(1) and value=1.

Since we have one insertion, it creates a stem node with the stem as the first 31 bytes from the key, last 1 byte is used as the id in the stem node. In this case, our key=1 is broken down into stem=0 and id=1.

Second insertion

Now we insert one more element key = 1<<255 and value=1. This key is broken down into stem=1<<247 and id=0. We will now update the tree.

Third insertion

To show an insertion in existing stem node, let us insert key=0 value=4. Here key is broken down into stem=0 and id=0. As we walk down the tree, we arrive at a StemNode where stem is 0. So we update the value at id=0.

Fourth insertion

We can do additional insertion at key = 1<<253 and value=1 to see how internal nodes are created. This key is broken down into stem=1<<245 and id=0. We create minimum internal nodes as needed.

As we walk down the stem path, we arrive at a StemNode whose stem is 0 instead of 1<<245. So we refactor that section by adding some internal nodes and creating a new StemNode.

As you can see a node existed already on the left leg of the root. It was refactored down as needed using a minimal amount of internal branch nodes.

In the previous MPT specification, a field similar to stem existed called path in the branch, extension, and leaf nodes in MPT, however, it excluded the already consumed nibbles down in the path. So in the process when we have to refactor the tree, it changes the path, hereby changing the hash of the node, giving rise to some edge cases. It is great to see that in the UBT specification, the stem value is not affected by refactoring in placement as it's the full 31-byte key value.

Outro

As of Feb 2025, this proposal is in draft status. Unified Binary Tree is a step towards a quantum-safe and snarkified Ethereum. It also makes Ethereum's spec simpler and can work together with state-expiry EIP. It overall sounds beneficial to Ethereum, however making changes to Ethereum is not easy and we have to explore the challenges too.

To participate in the UBT discussion, you can use the thread at https://ethereum-magicians.org/t/eip-7864-ethereum-state-using-a-unified-binary-tree/22611/6.