Proposed Verkle tree scheme for Ethereum state

Proposed Verkle tree scheme for Ethereum state

This document describes a proposal for how concretely the Ethereum state can be represented in a Verkle tree.

See https://notes.ethereum.org/_N1mutVERDKtqGIEYc-Flw for notes of how Verkle tries work.

Desiderata

  • Short witness length for accounts or storage, even under “attack”. This necessitates:
    • An “extension node”-like scheme where the bulk of an address or storage key can be stored as part of a single node, instead of always going 32 layers deep
    • Hashing account addresses and storage keys to prevent attackers from filling the storage in locations that are close enough to each other that branches to them become very long without doing a very large amount of brute force computation
  • Maximum simplicity. Particularly, it would be ideal to be able to describe the result as a single Verkle tree
  • Forward-compatibility (eg. ability to add more objects into an account header in the future)
  • Code for an account should be stored in one or a few subtrees, so that a witness for many code chunks can be minimally sized
  • Frequently-accessed values (eg. balance, nonce) should be stored in one or a few subtrees, so that a witness for this data can be minimally sized
  • Data should be by default reasonably distributed across the entire state tree, to make syncing easier

Proposal

The proposed scheme can be described in two different ways:

  1. We can view it as a “tree of commitments” (so like the trie-of-tries in eth1 but where the bottom level is just a single layer), with two additional simplifications:
    • Only leaf nodes containing extended paths, no “internal” extension nodes
    • The leaves of the top trie are only commitments (of the same type as the commitments used in the tree), and not “a hash pointing to a header which contains two values, a bytearray and a tree” as is the status quo today
  2. We can view it as a single tree, where there are internal extension nodes but they can only extend up to the 31 byte boundary (tree keys MUST be 32 bytes long)

These two perspectives are completely equivalent. We will focus on (2) for the rest of the description, but notice that if you take perspective (1) you will get a design where each account is a subtree.

The Verkle tree structure used, from the first perspective, will be equivalent to the structure described here. From the second perspective, it would be equivalent to the structure described in that document, except that instead of (key, value) leaf nodes, there would be intermediary nodes that extend up to the 31 byte boundary (note: the last byte would be a separate commitment even if there’s only one member value that has the same first 31 bytes).

We define the spec by defining “tree keys”, eg. if we say that the tree key for storage slot Y of account X is some value f(X, Y) = Z, that means that when we SSTORE to storage slot Y in account X, we would be editing the value in the tree at location Z (where Z is a 32-byte value).

Note also that when we “store N at position P in the tree”, we are actually storing hash(N) % 2**255. This is to preserve compatibility with the current 32-byte-chunk-focused storage mechanism, and to distinguish “empty” from “zero” (which is important for state expiry proposals).

Header values

The tree keys for this data are defined as follows:

def get_basic_data_tree_key(address, i):
    assert 0 <= i < 256
    return address[:3] + hash(address + b'\x00')[:28] + bytes([i])
    
def get_tree_key_for_version(address):
    return get_basic_data_tree_key(address, 0)    
    
def get_tree_key_for_balance(address):
    return get_basic_data_tree_key(address, 1)
    
def get_tree_key_for_nonce(address):
    return get_basic_data_tree_key(address, 2)

# Backwards compatibility for EXTCODEHASH    
def get_tree_key_for_code_keccak(address):
    return get_basic_data_tree_key(address, 3)
    
# Backwards compatibility for EXTCODESIZE
def get_tree_key_for_code_size(address):
    return get_basic_data_tree_key(address, 4)

Code

def get_code_chunk_tree_key(address, chunk):
    chunk_hi = (chunk // 256).to_bytes(32, 'big')
    chunk_lo = bytes([chunk % 256])
    return address[:3] + hash(address + b'\x01' + chunk_hi)[:28] + chunk_lo

Chunk i contains a 32 byte value, where bytes 1…31 are bytes i*31...(i+1)*31 - 1 of the code (ie. the i’th 31-byte slice of it), and byte 0 is the number of leading bytes that are part of PUSHDATA (eg. if part of the code is ...PUSH4 99 98 | 97 96 PUSH1 128 MSTORE... where | is the position where a new chunk begins, then the encoding of the latter chunk would begin 2 97 96 PUSH1 128 MSTORE to reflect that the first 2 bytes are PUSHDATA).

Note that code chunks in the same size-256 (7936 byte) range are all part of a single commitment; this is an optimization to make code witnesses more efficient, as transactions typically access many different parts of a contract’s code at the same time.

Note also that this structure makes code function identically to storage, removing the barriers to drastically increasing maximum code size if we later desire to do this.

Storage

def get_storage_slot_tree_key(address, storage_key):
    s_key_hi = (storage_key // 256).to_bytes(32, 'big')
    s_key_lo = bytes([storage_key % 256])
    return address[:3] + hash(address + b'\x02' + s_key_hi)[:28] + s_key_lo

Note that storage slots in the same size-256 range (eg. 0…255, 1024…1279) are all part of a single commitment; this is an optimization to make witnesses more efficient when related storage slots are accessed together. If desired, this optimization can be exposed to the gas schedule, making it more gas-efficient to make contracts that store related slots together (however, Solidity already stores in this way by default).

1 Like

I don’t understand this part. This seems to suggests that we are not storing the value but the hash of the value? Which is confusing to me since hashing implies we can’t recover the original value?

The idea is that when you provide a witness, you would provide [[k1,v1], [k2,v2], [k3,v3]...] along with the witness, but then the Verkle tree witness verification algorithm instead takes in [[k1, hash(v1)], [k2, hash(v2)], [k3, hash(v3)]...]. This is perfectly safe and does not compromise on data availability or soundness or anything like that.

The only thing that we theoretically lose from this approach is that we can’t use algebraic mechanisms (algebraic PoCs or erasure coding) on the state, but we lost the ability to do that anyway when we decided to use Verkle trees, so it’s not really a loss.

1 Like

IIUC, we would logically store the hash in the tree for the purposes of generating the verkle commitment, but we would in practice store the original value in whatever on-disk key/value store is used.

This is exactly correct.

So calling SELFDESTRUCT would take O(num_used_slots) to clear them all out. The cleanest resolution to that problem is to say that we should disable SELFDESTRUCT before verkles go live. (which I’m in favor of doing anyway)

There’s a way to do it without that: have a “number of times self-destructed” counter in the state and mix it in with the address and storage key to compute the tree path. But that’s ugly in a different way, and yes, we should just disable SELFDESTRUCT.

So it seem like we either:

  • Get rid of SELFDESTRUCT which based on some recent discussion in ACD looks like it may be complex due to the interplay with CREATE2 and “upgradeable” contracts.
  • Keep SELFDESTRUCT but replace the actual state clearing with an alternate mechanism that just abandons the state. When combined with the state expiration schemes, this is effectively like deleting it since it will become inaccessible and eventually expire.
  • Keep SELFDESTRUCT and determine how we can clear the state in a manner that doesn’t have O(n) complexity.

Right, those are basically the three choices. My preference is strongly toward the first, and we acknowledge that upgradeable contracts through a full-reset mechanism were a mistake.

1 Like

:100:

… and if DELEGATECALL isn’t appealing enough as an upgrade mechanism, let’s figure out how to improve that. (rather than how to keep in-place contract morphing via SELFDESTRUCT).

I don’t quite understand how this proposal achieves this. The initial 3 bytes are taken directly from the account address. So if an account has a 1 GB storage tree, then the subtree starting with those three bytes will store that 1 GB of data, much more than 100 GB / 2^24 = ~ 6 kB that an average subtree at that level stores.

As you know, address[:3] guarantees deduplicatation of an account’s the first 3 witness chunks. So I think the motivation is to optimize witness size. So just a clever trick.

I was wondering: is there any reason not to do address[:2] or address[:4]? More generally, what is the motivation for the “reasonably distributed” property (edit: how does it make syncing easier edit2: and how does it trade-off with the “short witness length” property)?

It is clever to use hash(same thing) + bytes([i]), chunk_lo, or s_key_lo to keep related values as neighbors in the tree.

A further optimization: the account version/balance/nonce/codehash/codesize commitment can also store, for example, the first ~100 code chunks and the smallest ~100 storage keys. But this optimization adds complexity, so I won’t push it.

Is there a reason for s_key_hi to be a 32-byte integer? The most significant byte is always \x00, so it seems that it could be omitted.

@dankrad @poemm I’m not super attached to address[:3] specifically. There’s a tradeoff: address[:4] makes witnesses slightly smaller, but it makes data less well-distributed, as then it would be a 1/2**32 slice instead of a 1/2**24 slice that could have a large number of keys. Meanwhile address[:2] slightly reduces the witness size advantage, at the cost of improving distribution. It’s possible that the optimal thing to do is to just abandon the address[:x] thing entirely; it would not be that bad, because in a max-sized block the first ~1.5 bytes are saturated anyway, and it would make the even-distribution property very strong (only deliberate attacks could concentrate keys).

No big reason. I guess making it a 32-byte integer is slightly more standardized, as we have plenty of 256-bit ints but no other 248-bit ints. It doesn’t make a significant difference either way.