Protocol: Verkle Trees

[mratsim]

The Ethereum state will likely replace Merkle Trees by Verkle Trees for storage in the future.

• Paper: https://klein.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf
• Draft for EIP: https://notes.ethereum.org/uwK4EJypSHWyEZvivcYyJA

Simple Summary

Introduce a new Verkle state tree alongside the existing hexary Patricia tree. After the hard fork, the Verkle tree stores all edits to state and a copy of all accessed state, and the hexary Patricia tree can no longer be modified. This is a first step in a multi-phase transition to Ethereum exclusively relying on Verkle trees to store execution state.

Motivation

Verkle trees solve the key problem standing in the way of Ethereum being stateless-client-friendly: witness sizes. A witness accessing an account in today’s hexary Patricia tree is, in the average case, close to 3 kB, and in the worst case it may be three times larger. Assuming a worst case of 6000 accesses per block (15m gas / 2500 gas per access), this corresponds to a witness size of ~18 MB, which is too large to safely broadcast through a p2p network within a 12-second slot. Verkle trees reduce witness sizes to ~200 bytes per account in the average case, allowing stateless client witnesses to be acceptably small.

Articles:

• https://ethereum-magicians.org/t/proposed-verkle-tree-scheme-for-ethereum-state/5805
• https://dankradfeist.de/ethereum/2021/06/18/verkle-trie-for-eth1.html
• https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html
• https://vitalik.ca/files/misc_files/verkle.pdf
• https://blog.ethereum.org/2021/12/02/verkle-tree-structure/
  • Note: Ethereum proposal has extension nodes which differ from the paper verkle tries
    PoC / implementations:
• https://github.com/gballet/go-verkle
• https://github.com/gballet/zig-verkle
• https://github.com/ethereum/research/tree/master/verkle_trie
  Video / podcasts:
• https://www.youtube.com/watch?v=RGJOQHzg3UQ
• https://www.youtube.com/watch?v=f7bEtX3Z57o
• https://www.youtube.com/watch?v=1hTscLYsaIg
• https://www.youtube.com/watch?v=ik7xYCTC0B4

Prerequisite:

• Bandersnatch support
• KZG Polynomial Commitment #112
• Pedersen hash

[mratsim]

New developments Inner Product Argument instead of KZG:

• Bandersnatch impl notes https://hackmd.io/wliPP_RMT4emsucVuCqfHA?view
• Verkle Trees devlogs https://hackmd.io/@6iQDuIePQjyYBqDChYw_jg/B1rUOM9Zq