---
eip: 8297
title: Partitioned Binary Tree
description: Switch Ethereum state tree to a partitioned binary tree
author: Vitalik Buterin (@vbuterin), Guillaume Ballet (@gballet), Dankrad Feist (@dankrad), Ignacio Hagopian (@jsign), Kevaundray Wedderburn (@kevaundray), Tanishq Jasoria (@tanishqjasoria), Gajinder Singh (@g11tech), Danno Ferrin (@shemnon), Piper Merriam (@pipermerriam), Gottfried Herold (@GottfriedHerold), Wei Han Ng (@weiihann), Carlos Perez (@CPerezz)
discussions-to: https://ethereum-magicians.org/t/eip-8297-partitioned-binary-tree/28776
status: Draft
type: Standards Track
category: Core
created: 2026-06-11
---

## Abstract

Introduce a new binary state tree to replace the hexary Patricia tries. Account
and storage tries are merged into a single tree with variable-length,
prefix-free keys that also holds contract code. Account data is broken into
independent leaves grouped under a shared key prefix to provide locality.

The tree is partitioned into zones. The first byte of every key is a zone
identifier that labels the category of state the key holds: account headers,
contract code, or storage. Account headers and code take fixed low zones,
storage takes a fixed high zone, and the remaining zones are reserved for
future categories.

Note: the hash function used in this draft is not final. The reference
implementation uses BLAKE3 to reduce friction for clients experimenting with this
EIP, but the choice remains open.

## Motivation

Ethereum's long-term goal is to let blocks be proved with validity proofs so chain
verification is as simple and fast as possible. Part of this work consists of proving the
state read during EVM execution.

The Merkle Patricia Trie (MPT) is unfriendly to validity proofs: it uses RLP for
node encoding, Keccak for hashing, is a "tree of trees", and does not allow for the efficient proving of segments of bytecode. It also produces large Merkle proofs. As an example, the account trie today reaches a maximum depth of about 12, so a
branch at that depth is `15 * 32 * 12 = 5760` bytes: 15 sibling hashes of
32 bytes at each of the 12 levels. From a worst-case block perspective, spending all
`60M` gas to touch a single byte of many distinct account codes, none of which is
chunked, needs `60M/2400 * (12*480 + 64k) ≈ 1.8GB`. Here `2400` is the cheapest gas
to touch a fresh account, the [EIP-2930](./eip-2930.md) access-list address cost
(a cold access under [EIP-2929](./eip-2929.md) costs `2600`); `12*480` is the
branch to that account; and `64k` is the [EIP-7954](./eip-7954.md) 64 KiB code size
limit that must be revealed in full to prove any single byte of code that is
not chunked.

A binary tree shrinks regular Merkle proofs, because proof size scales with
`siblings * log_arity(N)` and arity 2 minimizes it. Switching from Keccak to a more
proving-friendly hash improves circuit performance.

Partitioning the tree into zones adds two properties on top of a flat unified
tree:

**Structural boundaries.** A key prefix of a known length is always the root of
a known category: the zone byte identifies account headers, code, or storage;
within storage, `key_hash(address)` identifies one account's bucket. Protocols
can reference these key-space regions as commitments without a side structure.
Because the tree compresses shared prefixes (see "Tree structure"), a boundary
does not always correspond to a distinct node at a fixed depth, but the region
of keys it owns is exact. This is what later proposals for state expiry and
partial statelessness build on.

**Code deduplication.** Code is content-addressed by code hash rather than by
account, so thousands of contracts deployed from the same factory share their
code leaves instead of each storing a copy.

## 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](https://www.rfc-editor.org/rfc/rfc2119) and [RFC 8174](https://www.rfc-editor.org/rfc/rfc8174).

### Notable changes from the hexary structure

- The account and storage tries are merged into a single tree.
- RLP is no longer used.
- The account's code is chunked and included in the tree.
- Account data (balance, nonce, first storage slots) is co-located to reduce
  branch openings.
- Code is content-addressed rather than keyed by account, so contracts with
  identical bytecode share it.

### Tree structure

The tree stores key-value entries where the key is a non-empty,
variable-length byte string of at most `MAX_KEY_LENGTH` bytes (see
"Maximum key length") and the value is 32 bytes. Keys MUST be prefix-free:
no key in the tree may be a prefix of another key in the tree. Computing
the root rejects keys that violate either constraint.

![Tree structure diagram](../assets/eip-8297/diagram.png)

There are two node types:

- `LeafNode` has `key` (the complete key) and `value` (32 bytes).
- `BranchNode` has `prefix` (a bit string, possibly empty), `left`, and
  `right`.

There is no separate extension node. A `BranchNode`'s `prefix` carries the
run of bits shared by every key below it that are not already consumed by
an ancestor.

A `BranchNode` MUST have two non-empty children: a prefix shorter than the
true shared run would leave the keys still agreeing at the next bit,
emptying one side, which is not a valid `BranchNode`. This forces every
prefix to be exactly the shared run, so each key/value set has exactly one
valid tree.

A `LeafNode` commits its complete key rather than a suffix relative to its
position in the tree, so its meaning never depends on where it sits;
splitting or merging branches elsewhere never changes an unrelated leaf's
hash.

```python
def _bytes_to_bits(data: bytes) -> list[int]:
    return [(byte >> (7 - i)) & 1 for byte in data for i in range(8)]

class LeafNode:
    def __init__(self, key: bytes, value: bytes):
        self.key = key
        self.value = value

class BranchNode:
    def __init__(self, prefix: list[int], left: "BinaryNode", right: "BinaryNode"):
        self.prefix = prefix
        self.left = left
        self.right = right

BinaryNode = LeafNode | BranchNode

def binarize(entries: dict[bytes, bytes], depth: int) -> BinaryNode:
    assert len(entries) > 0
    if len(entries) == 1:
        ((key, value),) = entries.items()
        return LeafNode(key, value)

    bits = {key: _bytes_to_bits(key) for key in entries}

    split = depth
    while True:
        # A key that runs out of bits while still grouped with others is
        # a prefix of theirs.
        for key_bits in bits.values():
            assert split < len(key_bits), "keys are not prefix-free"
        if len({key_bits[split] for key_bits in bits.values()}) > 1:
            break
        split += 1

    left = {k: v for k, v in entries.items() if bits[k][split] == 0}
    right = {k: v for k, v in entries.items() if bits[k][split] == 1}
    prefix = next(iter(bits.values()))[depth:split]
    return BranchNode(prefix, binarize(left, split + 1),
                      binarize(right, split + 1))
```

### Node merkelization

Define tags `LEAF_TAG = 0x00` and `BRANCH_TAG = 0x01`. `H` is the tree's
32-byte hash function, the same function as `key_hash` (see the note in
the Abstract).

`encode_bit_prefix` packs a bit string for hashing as a two-byte big-endian
bit count followed by the bits themselves, most significant bit first,
zero-padded to a byte boundary:

```python
def encode_bit_prefix(prefix: list[int]) -> bytes:
    assert len(prefix) < 2**16, "prefix exceeds encodable bit count"
    packed = bytearray((len(prefix) + 7) // 8)
    for i, bit in enumerate(prefix):
        packed[i // 8] |= bit << (7 - i % 8)
    return len(prefix).to_bytes(2, "big") + bytes(packed)
```

Merkelize each node type as:

- `leaf_hash = H(LEAF_TAG || key || value)`
- `branch_hash = H(BRANCH_TAG || encode_bit_prefix(prefix) || left_hash || right_hash)`
- The hash of an empty tree is `[0x00] * 32`

```python
def merkelize(node: BinaryNode) -> bytes:
    if isinstance(node, LeafNode):
        return H(bytes([LEAF_TAG]) + node.key + node.value)
    return H(
        bytes([BRANCH_TAG])
        + encode_bit_prefix(node.prefix)
        + merkelize(node.left)
        + merkelize(node.right)
    )
```

The state root of a key/value set is then:

```python
def state_root(entries: dict[bytes, bytes]) -> bytes:
    for key, value in entries.items():
        assert 1 <= len(key) <= MAX_KEY_LENGTH, "key length out of range"
        assert len(value) == 32, "value must be 32 bytes"
    if len(entries) == 0:
        return b"\x00" * 32
    return merkelize(binarize(entries, 0))
```

### Insertion and deletion

A mutation is an update to the entry set: insertion, which sets a key's
value, or deletion, which removes the key. Both are generic over the value
space. The tree has no distinguished value that means absence: any 32-byte
value may be stored, and only the presence of a key distinguishes it from
an absent one. The root after a mutation is `state_root` of the resulting
entry set.

An implementation that maintains the tree incrementally rather than
rebuilding it MUST still produce that root. For deletion this means
restoring the canonical form: removing a key leaves its parent branch with
a single child, which MUST take that branch's place. A surviving `LeafNode`
is promoted unchanged, since it commits its complete key. A surviving
`BranchNode` takes the parent's prefix, followed by the bit that selected
it, followed by its own prefix. Only the direct parent can be left with one
child, so the merge is bounded to one level, and it inverts the split that
insertion performs.

### Maximum key length

`MAX_KEY_LENGTH = 8192` bytes. The bound comes from the branch prefix encoding:

- `encode_bit_prefix` stores a branch's bit count in two bytes, so the
  largest representable prefix is `2**16 - 1 = 65535` bits.
- A branch's prefix is the run of bits its keys agree on, ending just
  before the first bit where they diverge.
- Two distinct keys of `L` bytes (`8*L` bits) must differ in at least one
  bit, so the longest run they can share is `8*L - 1` bits: agreement on
  everything except the final bit.
- To encode this, we require `8*L - 1 <= 65535`, giving `L <= 8192`.

Keys longer than `MAX_KEY_LENGTH` MUST be rejected. Enforcing this on
every key, rather than only inside `encode_bit_prefix`, keeps the bound a
stated property of every key instead of a failure that depends on which
other keys happen to be present: a key longer than `MAX_KEY_LENGTH` is not
itself invalid until a second key shares enough of its prefix to overflow
the count field.

### Zones

The first byte of every key is the zone identifier `Z`.

| Zone `Z`      | Category                                    |
| ------------- | -------------------------------------------- |
| `0x00`        | Account headers                             |
| `0x01`        | Code chunks (content-addressed)             |
| `0x02`-`0xFE` | Reserved for future categories              |
| `0xFF`        | Storage                                     |

New categories MUST be allocated from `0x02`-`0xFE` and MUST keep their
keys mutually prefix-free (see "Tree embedding").

### Tree embedding

All state is embedded into the single key/value space. Data accessed
together is co-located under one shared key prefix ("stem") to reduce
branch openings. The account header holds an account's basic data, code
hash or delegation, and first 64 storage slots under keys sharing one header
stem. Code is not in the header; it lives in `CODE_ZONE`, content-addressed
(see "Code").

| Parameter               | Value |
| ----------------------- | ----- |
| BASIC_DATA_LEAF_KEY     | 0     |
| CODE_HASH_LEAF_KEY      | 1     |
| DELEGATION_LEAF_KEY     | 2     |
| HEADER_STORAGE_OFFSET   | 64    |
| HEADER_STORAGE_SLOTS    | 64    |
| STEM_SUBTREE_WIDTH      | 256   |
| ACCOUNT_ZONE            | 0x00  |
| CODE_ZONE               | 0x01  |
| STORAGE_ZONE            | 0xFF  |
| ACCOUNT_KEY_LENGTH      | 34    |
| CODE_KEY_LENGTH         | 34    |
| STORAGE_KEY_LENGTH      | 66    |

It is a required invariant that `HEADER_STORAGE_OFFSET + HEADER_STORAGE_SLOTS
<= STEM_SUBTREE_WIDTH`.

Every key produced by this embedding has a length fixed by its zone:
`ACCOUNT_KEY_LENGTH`, `CODE_KEY_LENGTH` and `STORAGE_KEY_LENGTH` for the
account, code and storage zones respectively.

Fixing one length per zone is what keeps keys prefix-free within a zone, since
a shorter key of the same zone would otherwise be a proper prefix of a longer one.
Keys of different zones already differ in their first byte. Implementations MUST assert the length of every key they construct.

Addresses are passed as `Address32`. Convert a legacy address by prepending
12 zero bytes:

```python
def address20_to_address32(address: Address) -> Address32:
    return b'\x00' * 12 + address
```

A key is built from a zone byte, a hash-derived tree position, and a
sub-index byte. The zone byte and the tree position together are a key's
stem:

```python
def key_hash(inp: bytes) -> bytes32:
    return blake3(inp).digest()

def get_tree_key(zone: int, tree_position: bytes, sub_index: int) -> bytes:
    return bytes([zone]) + tree_position + bytes([sub_index])
```

### Header values

The account header's stem is in `ACCOUNT_ZONE` and is keyed by the
address alone, so each account has exactly one header stem.

```python
def get_tree_key_for_header(address: Address32, sub_index: int) -> bytes:
    key = get_tree_key(ACCOUNT_ZONE, key_hash(address), sub_index)
    assert len(key) == ACCOUNT_KEY_LENGTH
    return key

def get_tree_key_for_basic_data(address: Address32):
    return get_tree_key_for_header(address, BASIC_DATA_LEAF_KEY)

def get_tree_key_for_code_hash(address: Address32):
    return get_tree_key_for_header(address, CODE_HASH_LEAF_KEY)
```

`version`, `balance`, `nonce`, and `code_size` are packed big-endian in the value
at `BASIC_DATA_LEAF_KEY`:

| Name        | Offset | Size |
| ----------- | ------ | ---- |
| `version`   | 0      | 1    |
| `code_size` | 4      | 4    |
| `nonce`     | 8      | 8    |
| `balance`   | 16     | 16   |

Bytes 1 through 3 are reserved. The 4-byte `code_size` holds values up to `2^32 - 1`
bytes, far beyond any foreseeable contract size limit. Packing these fields into one
leaf needs one branch opening instead of three or four, which lowers gas and
simplifies witness generation.

Setting any header field also sets `version` and the three reserved bytes to
zero. `code_hash` and
`code_size` are set on contract or EOA creation; the code hash leaf of an
account with no code holds the Keccak hash of empty bytecode, unaffected by
this EIP's choice of merkelization hash (see "Backwards Compatibility").

The header sub-indices in use are `BASIC_DATA_LEAF_KEY`, `CODE_HASH_LEAF_KEY`,
`DELEGATION_LEAF_KEY`, and
`HEADER_STORAGE_OFFSET`..`HEADER_STORAGE_OFFSET + HEADER_STORAGE_SLOTS - 1`.
No key defined by this EIP resolves to any other sub-index; the remaining
sub-indices are reserved for future header fields (see "Storage layout").

### Delegation

An account whose code is an [EIP-7702](./eip-7702.md) delegation indicator, the
23 bytes `0xef0100 || target`, holds it in its header stem rather than as code:

```python
def get_tree_key_for_delegation(address: Address32):
    return get_tree_key_for_header(address, DELEGATION_LEAF_KEY)
```

The value is the indicator followed by nine zero bytes, and `code_size` is 23.
Such an account has no `CODE_ZONE` leaves and no `code_hash` leaf, since this
leaf determines both the code and its hash: a code read takes the first
`code_size` bytes and `EXTCODEHASH` hashes them. Being delegated and holding
contract code are mutually exclusive, so every account that exists holds
exactly one of the `CODE_HASH_LEAF_KEY` and `DELEGATION_LEAF_KEY` leaves. An
authorization to the zero address clears the delegation, replacing this leaf
with a `code_hash` leaf holding the hash of empty bytecode and zeroing
`code_size`.

An indicator cannot be deployed as contract code and none predates the ban
([EIP-3541](./eip-3541.md)), so an account holds one only by delegation.

### Code

Every code chunk lives in `CODE_ZONE`, content-addressed by `code_hash` so
contracts with identical bytecode share leaves. An aligned range of
`STEM_SUBTREE_WIDTH` chunks sharing one `tree_index` is a code group; its
chunks share a stem and differ only in the sub-index byte. No code chunk is
keyed by address.

```python
def get_tree_key_for_code_chunk(code_hash: bytes32, chunk_id: int):
    tree_index = chunk_id // STEM_SUBTREE_WIDTH
    sub_index  = chunk_id %  STEM_SUBTREE_WIDTH
    key = get_tree_key(
        CODE_ZONE, key_hash(code_hash + tree_index.to_bytes(32, "big")), sub_index
    )
    assert len(key) == CODE_KEY_LENGTH
    return key
```

Chunk `i` stores a 32-byte value where bytes 1..31 are the i'th 31-byte slice of the
code and byte 0 is the number of leading bytes that are PUSHDATA. For example, if
code is `...PUSH4 99 98 | 97 96 PUSH1 128 MSTORE...` where `|` begins a new chunk, the latter chunk begins `2 97 96 PUSH1 128 MSTORE`, recording that its first 2 bytes are PUSHDATA.

```python
PUSH_OFFSET = 95
PUSH1 = PUSH_OFFSET + 1
PUSH32 = PUSH_OFFSET + 32

def chunkify_code(code: bytes) -> Sequence[bytes32]:
    if len(code) % 31 != 0:
        code += b'\x00' * (31 - (len(code) % 31))
    bytes_to_exec_data = [0] * (len(code) + 32)
    pos = 0
    while pos < len(code):
        if PUSH1 <= code[pos] <= PUSH32:
            pushdata_bytes = code[pos] - PUSH_OFFSET
        else:
            pushdata_bytes = 0
        pos += 1
        for x in range(pushdata_bytes):
            bytes_to_exec_data[pos + x] = pushdata_bytes - x
        pos += pushdata_bytes
    return [
        bytes([min(bytes_to_exec_data[pos], 31)]) + code[pos: pos+31]
        for pos in range(0, len(code), 31)
    ]
```

A chunk encodes to 32 zero bytes when its 31 code bytes are all `0x00` and
byte 0's PUSHDATA count is zero too, as in a run of `STOP` or a zero-filled
data region. Zero bytes that continue PUSHDATA from an earlier chunk do not
qualify, since byte 0 then records the continuation. Such a zero chunk is
absent from the tree like any other zero value (see "Zero values and
deletion"). Chunk presence therefore does not delimit a contract's code: the
chunk count is `ceil(code_size / 31)`, and an absent chunk reads back as the
32 zero bytes it would have held, so the EVM cannot distinguish the two. A
contract whose code is entirely zeros has no code leaves at all and is still
distinguished from an account with no code by `code_size` and `code_hash`. A
witness proves such a chunk absent where it would otherwise prove its value.

### Storage

Storage slots 0 through 63 live in the account header's stem at
sub-indices `HEADER_STORAGE_OFFSET`..`HEADER_STORAGE_OFFSET +
HEADER_STORAGE_SLOTS - 1`. Slots 64 and above live in the storage zone.

A storage key's stem begins with the storage zone byte, followed by its
tree position: two full hash digests.

`key_hash(address)` places all of an account's overflow storage under
one shared prefix.

An aligned range of `STEM_SUBTREE_WIDTH` slots sharing one `tree_index`
is a storage group; its slots share a stem and differ only in the
sub-index byte. `key_hash(address || tree_index)` spreads the account's
storage groups within that bucket. The second digest is bound to the
address as well as `tree_index` (see "Security Considerations").

```python
def storage_tree_position(address: Address32, tree_index: int) -> bytes:
    prefix = key_hash(address)
    suffix = key_hash(address + tree_index.to_bytes(32, "big"))
    return prefix + suffix

def get_tree_key_for_storage_slot(address: Address32, storage_key: int):
    if storage_key < HEADER_STORAGE_SLOTS:
        return get_tree_key_for_header(address, HEADER_STORAGE_OFFSET + storage_key)
    tree_index = storage_key // STEM_SUBTREE_WIDTH
    sub_index  = storage_key %  STEM_SUBTREE_WIDTH
    key = get_tree_key(
        STORAGE_ZONE, storage_tree_position(address, tree_index), sub_index
    )
    assert len(key) == STORAGE_KEY_LENGTH
    return key
```

Group 0 is the exception: slots 0..63 live in the header, so its
storage-zone leaves are slots 64..255 only. Adjacent slots, common in
mappings and arrays, share a group.

### Zero values and deletion

Mapping zero to absence belongs to the state transition function, which
MUST resolve a write of 32 zero bytes to a deletion rather than an insertion:

```python
def state_write(entries: dict[bytes, bytes], key: bytes, value: bytes) -> None:
    if value == b"\x00" * 32:
        entries.pop(key, None)
    else:
        entries[key] = value
```

Writing zero to an absent key is therefore a no-op, no key in the state's
tree holds 32 zero bytes, and reading an absent key yields zero. Zero and
absent are the same state and commit to the same root, as in the MPT (see
"Collapsing zero and absent").

Deleting an account ([EIP-161](./eip-161.md) state clearing, or
`SELFDESTRUCT` in the transaction that created the account, per
[EIP-6780](./eip-6780.md)) MUST remove its header leaves and its storage
leaves. Its code is content-addressed and may be shared with other accounts,
so its `CODE_ZONE` leaves MUST be removed only if no account in the
resulting state has the same `code_hash`, and MUST be kept otherwise.

The MPT checked `storage_root` to decide whether an address has non-empty
storage (i.e., the that condition [EIP-7610](./eip-7610.md) checks before contract
creation). This tree has no such node, and thus the address has non-empty storage
exactly when a leaf exists at one of its header sub-indices
`HEADER_STORAGE_OFFSET`..`HEADER_STORAGE_OFFSET + HEADER_STORAGE_SLOTS - 1`
or anywhere in its storage bucket.

### Fork

Activation and the migration of existing MPT state into this tree are
specified in [EIP-8347](./eip-8347.md). Migration happens off the
consensus-critical path in every case: a node either converts the state
itself at a finalized anchor block, or downloads a snapshot and verifies
it against the anchor's state root. The converted state is caught up to
the chain head by replaying Block-Level Access Lists, and the tree
becomes the canonical state commitment at a single coordinated hard
fork.

## Rationale

This EIP defines the tree; it does not define how existing state is converted to it. Migration is specified in [EIP-8347](./eip-8347.md): the MPT state is
converted offline and the tree activates fully populated at the fork.

### Single tree with zones

A single key/value tree is simpler to work with than a tree of tries: database
access, caching, syncing, and proof code all operate on one abstraction, and
witness gas rules are clearer. Placement is hash-derived at every level: stems
scatter uniformly within their zone, and an account's storage groups scatter
uniformly within its bucket, so the tree stays balanced up to the deliberate
shared prefixes, which compression folds away (see "Tree depth").

Zones add structure without giving up that balance. Each zone is a
self-contained key-space region, so a node can sync, prove, or expire one
category without touching the rest. Because no leaf stores a `storage_root`,
an account's nonce in the account zone and one of its slots in the storage
zone are independent writes. The root recomputes in one bottom-up pass and
the two branches meet near the root. This admits parallelism across zones,
across accounts within a zone, and across stems within an account.

### Storage layout

Storage is the largest state category by a wide margin and the most
frequently proven, so its bucket assignment gets the strongest available
guarantee: the full `key_hash(address)` digest gives each account its own
storage bucket, with negligible chance of two accounts sharing one; the
bucket is the unit later expiry and partial-statefulness schemes can
prune or sync.
Binding the group-spreading digest to the address as well as `tree_index`
restricts the grinding analyzed in "Security Considerations" to the
attacker's own bucket.

Within the header stem, `HEADER_STORAGE_OFFSET` sits on a power-of-two
boundary: with `HEADER_STORAGE_SLOTS = 64`, the header slots are exactly
the sub-indices whose two leading bits are `01`, so the whole range hangs
off a single branch and a witness touching several header slots shares one
path down to it. The sub-indices between `CODE_HASH_LEAF_KEY` and
`HEADER_STORAGE_OFFSET` are reserved for future header fields. The
reservation is free, since absent keys occupy no nodes, and a field
allocated there shares the leading `00` bits with the basic data and code
hash leaves that every account access already reads, placing it on the
branch a witness for those leaves already opens.

### Content-addressed code

Keying code by `code_hash` rather than by account lets all contracts with
identical bytecode share leaves. Most deployed contracts repeat a small number of
templates, so this removes a large amount of duplicate code from the state. For
the same reason, a block witness contains at most one copy of a shared chunk, no
matter how many contracts touch it. Sharing is also why account deletion checks
before removing a chunk (see "Zero values and deletion").

That check is decidable from the transaction alone. A code leaf is present
exactly while some account has that contract code, and [EIP-161](./eip-161.md)
clearing reaches only accounts with no code, so an account with code is deleted
only by `SELFDESTRUCT` in the transaction that created it. A leaf that predates
the transaction is therefore held by an account the transaction cannot delete
and stays; a leaf the transaction inserted is held only by accounts the
transaction wrote that code to, and goes when none of them remain. Neither case
reads state older than the transaction, so no reference count over the state is
needed.

An account can replace a delegation indicator but never contract code, which
is why indicators are not kept as code (see "Delegation"). Whether another
account still delegates to the same target is answerable neither from the
transaction nor from a witness, since a shared leaf is byte-identical whether
one account holds it or a million; it would need a reference count over the
whole state, kept correct across restart, snap sync and reorgs. A later change
that lets a live account replace code in `CODE_ZONE` would have to say how the
check stays local.

An indicator takes its own sub-index rather than sharing the code-hash leaf the
account never needs at the same time, because telling the two apart by their
leading bytes would let an attacker grind code whose hash begins `0xef0100` and
have the contract read as a delegation.

Keeping a prefix of the code in the account header instead would avoid that
check, but it would key that prefix by address, so the templates above would
each store one copy per deployment: the duplication this zone exists to
remove. That reasoning does not extend to a delegation indicator, which is 23
bytes and replaces the code-hash leaf the account would hold anyway.

### SNARK friendliness and post-quantum security

The design avoids RLP and the MPT's variable-arity branching. The dominant
factor, though, is the merkelization hash, which should be efficient in and
out of circuit. The choice is open, with candidates:

1. **BLAKE3**: good native performance, reasonable in-circuit, well-studied,
   currently used in the reference implementation.
2. **Keccak**: already in Ethereum, well-studied, less efficient to prove.
3. **Poseidon2**: strong in-circuit performance, security analysis ongoing through
   the Ethereum Foundation (EF) cryptography initiative, needs extra specification for field encoding.

Because the tree depends only on a hash function and not on elliptic curves, it
remains secure against quantum adversaries; Verkle's curve-based stack does not,
and NIST guidance calls for retiring elliptic-curve cryptography by 2030.
Progress in proving systems suggests pre-state and post-state proofs can be
generated fast enough, matching Verkle's main advantage.

### Arity-2

Binary tries minimize witness size. In an `N`-element tree with `k` children per
node, the average branch is roughly `32 * (k-1) * log(N) / log(k)` bytes, minimized
at `k = 2`. For `N = 2**24`:

| `k` | Branch length (chunks) | Branch length (bytes) |
| --- | ---------------------- | ---------------------- |
| 2   | 24                     | 768                    |
| 4   | 36                     | 1152                   |
| 8   | 56                     | 1792                   |
| 16  | 90                     | 2880                   |

### Tree depth

The proposed design avoids a full-depth Sparse Merkle Tree (SMT), which
helps reduce the hashing load in proving systems, currently a throughput
bottleneck on commodity hardware.

A `BranchNode`'s prefix exists because storage buckets manufacture long
shared runs: every one of an account's overflow storage groups shares the
same `key_hash(address)`, up to 256 bits. Without compression this would
produce long chains of branch nodes with a single occupied child. Folding
the shared run into the branch's prefix (see "Tree structure") collapses
each such chain to one node, which is also what bounds the proof-size cost
of grinding a set of groups in "Security Considerations".

### Collapsing zero and absent

Collapsing zero and absent keeps the root a function of the state alone and
not of the writes that produced it, as in the MPT. A client's flat state can
keep representing zero as the absence of a record, a tree rebuilt from a
state dump reproduces the root, a test fixture can express any pre-state,
and a tree converted from the MPT, which carries no record of slots cleared
before the fork, agrees with one maintained incrementally across it. Zero
also has a single representation at the proof layer.

The rule sits in the state transition function and leaves the tree generic,
which is the MPT's split: the trie is defined over arbitrary key/value pairs
with no distinguished value, and the storage trie holding only non-zero
slots is a property of how state maps into it rather than of the trie. Keeping
the layers apart means the tree can be specified, tested, and reused without
carrying a rule that belongs to the EVM's value semantics, and a client is
free to spell a zero write as an explicit delete or as a write its own tree
layer collapses, since only the resulting entry set is committed. Zero is the
trigger because the EVM has no other spelling of "unset": a storage slot is a
256-bit word that reads as zero before it is ever written, and `SSTORE` of
zero is how a contract clears one.

Accounts need no existence marker under this rule, so `version` stays zero
as in [EIP-7864](./eip-7864.md). The only account whose `BASIC_DATA` is all
zero is the empty account of [EIP-161](./eip-161.md), with zero nonce, zero
balance and no code, which the EVM cannot distinguish from a nonexistent
account and which state clearing deletes when it is touched.

The rule applies to code chunks too, which are the one value in this tree
whose zero encoding carries meaning rather than being the natural spelling of
"unset" (see "Code"). Exempting them would make the rule depend on the key
rather than the value. With all code in `CODE_ZONE` the exemption would at
least fall on a zone boundary rather than on a sub-index range, but it still
buys nothing: `code_size` already delimits the code and an absent chunk reads
as the zeros it would have held. Nor does it buy a smaller state, since an
exemption stores only leaves whose contents are already implied by
`code_size`.

The alternative, a zero-valued leaf that stays in the tree and is distinct
from an absent key, is what a multi-tree state expiry design requires, where
"absent" means the latest version of the object may be in an older tree.
Expiry on this tree instead marks an expired region with a stub introduced
at the expiry fork (see "State expiry").

The cost is deletion logic in clients that maintain the tree incrementally,
and re-paying state-creation gas for a slot that is cleared and later
rewritten. The merge that deletion requires is bounded to one level and
inverts the split insertion already performs (see "Insertion and deletion").
The gas asymmetry is a pricing question, better answered in the gas schedule
than by holding roughly a hundred bytes of consensus state for every slot
ever created.

### State expiry

Per-account and per-bucket expiry is a natural operation on the zone
topology. The storage bucket keyed by `key_hash(address)` roots one
account's storage in the common case. Record its hash and prune below it.
The account header's stem expires the account's core data, hot storage and
delegation in one step. Content-addressed code needs reference counting or
deferral to a state sweep, since its leaves may be shared and a sweep has no
transaction to reason from. Resurrection re-attaches a subtree consistent
with the recorded commitment. The mechanism itself is left to a separate EIP.

## Backwards Compatibility

The main breaking change is that the tree structure change breaks in-EVM
verification of MPT state proofs. Post-fork state roots commit to the new
tree, so contracts that verify proofs against them must adopt the new
tree's proof format.

This EIP does not change the gas schedule.

The change is invisible to the EVM. Contracts address storage by 256-bit slot
numbers through `SLOAD` and `SSTORE` and never see tree keys. Key derivation runs
inside the client, below the EVM, exactly as the MPT already hashes slot keys and
addresses. No contract, Solidity, or Yul code changes.

`EXTCODEHASH` is unaffected. The account's code hash is a Keccak hash
regardless of the tree's own merkelization hash, held in the `code_hash` leaf
or, for a delegated account, computed from the delegation leaf.

## Test Cases

The hash function is not fixed, so digests cannot be pinned. The
deterministic parts of the derivation are given as vectors. `H(x)` is the
full 32-byte digest of `x`.

Account header, `BASIC_DATA` of address `A`:

```
key    = 0x00 || H(A) || 0x00
length = 1 + 32 + 1 = 34 bytes
```

Delegation of address `A` to target `T`:

```
sub_idx = DELEGATION_LEAF_KEY = 2 (0x02)
key     = 0x00 || H(A) || 0x02
length  = 34 bytes
value   = 0xef0100 || T || 0x00 * 9
```

Storage slot `storage_key = 5` of address `A` (in the header, since 5 < 64):

```
sub_idx = HEADER_STORAGE_OFFSET + 5 = 69 (0x45)
key     = 0x00 || H(A) || 0x45
length  = 34 bytes
```

Storage slot `storage_key = 1000` (in the storage zone, since 1000 >= 64):

```
tree_index = 1000 // 256 = 3
sub_idx    = 1000 %  256 = 232 (0xE8)
key        = 0xFF || H(A) || H(A || 3) || 0xE8
length     = 1 + 32 + 32 + 1 = 66 bytes
```

Code chunk `chunk_id = 5` of bytecode with hash `C`:

```
tree_index = 5 // 256 = 0
sub_idx    = 5 %  256 = 5 (0x05)
key        = 0x01 || H(C || 0) || 0x05
length     = 34 bytes
```

Code chunk `chunk_id = 300` of the same bytecode:

```
tree_index = 300 // 256 = 1
sub_idx    = 300 %  256 = 44 (0x2C)
key        = 0x01 || H(C || 1) || 0x2C
length     = 34 bytes
```

`A || 3` and `C || 1` denote `A` (respectively `C`) concatenated with the
32-byte big-endian encoding of the integer.

## Security Considerations

A collision means two distinct items derive the same key.

Keys contain three hash-derived components:

- `key_hash(address)`: both the account stem and the storage bucket.
- `key_hash(address || tree_index)`: the storage suffix.
- `key_hash(code_hash || tree_index)`: the code stem.

Each is a full 256-bit digest, so any collision costs about `2^128`
birthday work, far beyond reach. Keys of different zones differ in their
first byte and cannot collide at all.

**Content-addressed code.** Two contracts with identical bytecode share
code-zone leaves by design, which is deduplication, not a collision. Two
distinct bytecodes mapping to the same stem would need a 256-bit
collision, on Keccak for `code_hash` or on `key_hash(code_hash ||
tree_index)`, either of which is infeasible.

**Sub-index.** The sub-index is a direct mapping rather than a hash:
`HEADER_STORAGE_OFFSET + storage_key` in the header, `storage_key %
STEM_SUBTREE_WIDTH` in the storage zone, and `chunk_id % STEM_SUBTREE_WIDTH`
in the code zone. Two distinct keys share a
sub-index only if they also share a stem, in which case they are
the same item, so no collision is possible between distinct items.

**Grinding.** `key_hash(address || tree_index)` places a storage group in
its account's bucket, and `tree_index` comes from the slot number. An
attacker chooses slots freely: directly in their own contract, or through
mapping keys in any contract that hashes them into slots.

Grinding for digests that share `k` leading bits would deepen the tree. Without
compression that buys a `k`-node chain for about `2^(k/2)` work.

Compression folds the run into one `BranchNode` prefix of about `k/8`
bytes (see "Tree depth"), and `d` real extra nodes cost about `2^d` work.
The address in the digest stops cross-contract reuse, so a slot set found by
grinding for one contract is random in every other.

**Preimage.** Every node's hash preimage begins with a one-byte tag
(`LEAF_TAG` or `BRANCH_TAG`) distinguishing the two node types, and a
`BranchNode`'s prefix carries an explicit bit count.
This makes the mapping from logical node to preimage injective; no leaf and branch
preimage can coincide, and no two prefixes of different bit length pack to
the same bytes.

## Copyright

Copyright and related rights waived via [CC0](../LICENSE.md).