The Verge in a nutshell:
- Replaces the state Merkle tree with a Verkle tree...
- ...which allows for builders to attach Verkle proofs to their blocks...
- ...allowing validators to statelessly verify blocks.
What does this word salad mean?
First, some context:
(2/28)
- Replaces the state Merkle tree with a Verkle tree...
- ...which allows for builders to attach Verkle proofs to their blocks...
- ...allowing validators to statelessly verify blocks.
What does this word salad mean?
First, some context:
(2/28)
A lot of information goes into the block header of a block...
...including something called the *stateRoot*, defined as:
- the hash...
- of the root node...
- of the state Merkle tree...
- after all the transactions included in the block have been executed.
(3/28)
...including something called the *stateRoot*, defined as:
- the hash...
- of the root node...
- of the state Merkle tree...
- after all the transactions included in the block have been executed.
(3/28)
This stateRoot encapsulates the *entire state* of the system: account balances, contract storage, contract code, etc.
OK, let's break that definition down.
First off, what's hashing?
(4/28)
OK, let's break that definition down.
First off, what's hashing?
(4/28)
Hashing converts an input of any size to an output of a fixed size, called a *hash*, by running that input through a cryptographic ‘hash function’.
This fixed size output is crucial when considering Ethereum’s limited block sizes.
Great, so what are Merkle trees then?
(5/28)
This fixed size output is crucial when considering Ethereum’s limited block sizes.
Great, so what are Merkle trees then?
(5/28)
An example Merkle tree is shown here.
Data chunks at the leaf nodes (i.e. ends) of the tree are hashed.
Pairs of these hashes are then combined and hashed again until only one hash remains - the root hash at the top.
Why is this structure useful?
(6/28)
Data chunks at the leaf nodes (i.e. ends) of the tree are hashed.
Pairs of these hashes are then combined and hashed again until only one hash remains - the root hash at the top.
Why is this structure useful?
(6/28)
The Merkle tree structure allows for Merkle proofs. These prove that a piece of data is contained within the tree.
The structure of the tree determines the information required for the proof, which allows someone else to verify this proof against the public root hash.
(7/28)
The structure of the tree determines the information required for the proof, which allows someone else to verify this proof against the public root hash.
(7/28)
With a Merkle tree structure, not much additional data is required for the proof, reducing proof size.
In the proof shown here for '64', only hashes from 3 *sister nodes*, shown in yellow, are needed to recreate the root hash.
These proofs are also called *witnesses*.
(8/28)
In the proof shown here for '64', only hashes from 3 *sister nodes*, shown in yellow, are needed to recreate the root hash.
These proofs are also called *witnesses*.
(8/28)
Ethereum's state Merkle tree is a particular kind called a *Merkle Patricia Tree* (MPT).
These use properties of the underlying data chunks to determine how to structure the tree.
In the example shown here, the tree is structured based on shared prefix characters.
(9/28)
These use properties of the underlying data chunks to determine how to structure the tree.
In the example shown here, the tree is structured based on shared prefix characters.
(9/28)
The data in the leaf nodes of Ethereum's state MPT consist of key-value mappings, where the keys are ‘0x’ addresses and the values are account balances, contract storage, contract code, etc.
Shared prefix characters from the keys create the tree structure.
(10/28)
Shared prefix characters from the keys create the tree structure.
(10/28)
There is only one global state MPT, which needs to update over time to reflect the changes coming from the new transactions in every block.
These could be changes to existing accounts, as well as the creation of new accounts.
(11/28)
These could be changes to existing accounts, as well as the creation of new accounts.
(11/28)
The MPT data structure allows us to quickly calculate the new root hash in a new block after these operations, but without recomputing the entire tree.
In the example shown here, updating the stateRoot requires a limited number of hashes from the previous block's tree.
(12/28)
In the example shown here, updating the stateRoot requires a limited number of hashes from the previous block's tree.
(12/28)
To verify a new stateRoot, validating full nodes need to store a local copy of the state for up to the most recent 128 blocks;
and then use this whilst executing all transactions in a new block to ensure the calculated stateRoot matches the one in the block header.
(13/28)
and then use this whilst executing all transactions in a new block to ensure the calculated stateRoot matches the one in the block header.
(13/28)
Whilst MPTs are great, it turns out there is an even more efficient and effective form of them that requires even fewer hashes for proofs and updates: Verkle trees!
And these Verkle trees in turn can help reduce the need for validating full nodes to locally store state.
(14/28)
And these Verkle trees in turn can help reduce the need for validating full nodes to locally store state.
(14/28)
In MPTs, the proof of any given leaf node consists of the entire set of sister nodes (e.g. red nodes show in the image for the proof of '4ce').
Therefore, as MPT width increases, proof size increases.
But: Verkle trees get *smaller* proofs as width increases!
How?
(15/28)
Therefore, as MPT width increases, proof size increases.
But: Verkle trees get *smaller* proofs as width increases!
How?
(15/28)
In Verkle proofs, sister nodes are NOT required for the proof - just the hashes on the path to the leaf node itself with a ‘little bit extra (🤏)’.
So, what’s this 🤏?
It can get quite technical; there are two implementations.
(16/28)
So, what’s this 🤏?
It can get quite technical; there are two implementations.
(16/28)
1. 🤏 as multiple additional proofs using vector commitments
Imagine a hash function that hashes a list of values (z1, z2, …, zn), and outputs a vector commitment, C.
For a given C and zi, we can make a short proof that proves the value at the i'th position is zi.
(17/28)
Imagine a hash function that hashes a list of values (z1, z2, …, zn), and outputs a vector commitment, C.
For a given C and zi, we can make a short proof that proves the value at the i'th position is zi.
(17/28)
1. cont.
These short additional proofs replace the function of the sister nodes, confirming child node positions with respect to their parent nodes.
It is visualised below, showing how a few short additional proofs link each commitment in the path to the next.
(18/28)
These short additional proofs replace the function of the sister nodes, confirming child node positions with respect to their parent nodes.
It is visualised below, showing how a few short additional proofs link each commitment in the path to the next.
(18/28)
2. 🤏as a single additional proof using a polynomial commitment
Vector commitments are hashes of a list.
Polynomial commitments are hashes of *polynomials*, and make a proof for the evaluation of the hashed polynomial at *any* point.
(19/28)
Vector commitments are hashes of a list.
Polynomial commitments are hashes of *polynomials*, and make a proof for the evaluation of the hashed polynomial at *any* point.
(19/28)
2. cont.
Instead of requiring an additional proof for each commitment along the path, only a *single* fixed-size additional proof is needed that proves *all* parent-child links between *all* commitments along the paths from each leaf node to the root.
Powerful stuff.
(20/28)
Instead of requiring an additional proof for each commitment along the path, only a *single* fixed-size additional proof is needed that proves *all* parent-child links between *all* commitments along the paths from each leaf node to the root.
Powerful stuff.
(20/28)
This 2nd implementation allows proof sizes to decrease by 20-30x vs the MPTs that Ethereum uses today, and is the one being proposed for the Verge itself.
These Verkle proofs will also remove the need for validating full nodes to store a local copy of the state. How so?
(21/28)
These Verkle proofs will also remove the need for validating full nodes to store a local copy of the state. How so?
(21/28)
Well, Ethereum is aiming for *weak statelessness*, whereby storing the state locally is no longer required by full nodes to validate a block, but it is required by full nodes which build the block.
What would this mean for builders?
(22/28)
What would this mean for builders?
(22/28)
Builders, under proposer-builder separation, should be well suited to handle both the size of the state and its growth over time.
They will use the state to generate Verkle proofs for the parts of the state being read or affected by the transactions in that block.
(23/28)
They will use the state to generate Verkle proofs for the parts of the state being read or affected by the transactions in that block.
(23/28)
These proofs, which prove the values of the state that have been accessed by the builder, will be included in the block.
A validating full node will then verify that the state changes are valid by using these proofs to recreate the stateRoot from the block header.
(24/28)
A validating full node will then verify that the state changes are valid by using these proofs to recreate the stateRoot from the block header.
(24/28)
Enabling statelessness will:
- remove the need for validators to locally store state, & therefore...
- reduce full node space requirements, which should...
- encourage more people to run full nodes and increase decentralisation.
Good stuff all around.
(25/28)
- remove the need for validators to locally store state, & therefore...
- reduce full node space requirements, which should...
- encourage more people to run full nodes and increase decentralisation.
Good stuff all around.
(25/28)
Implementing Verkle trees is difficult as would involve transitioning the state tree in-place using temporary overlay trees.
Implementing *state expiry* (from the Purge) at the same time, which involves creating a new state tree every year, would circumvent this.
(26/28)
Implementing *state expiry* (from the Purge) at the same time, which involves creating a new state tree every year, would circumvent this.
(26/28)
Further detail and explanation around what you've read above can be found in my Substack post accompanying this thread:
(27/28)
himesh.substack.com/p/after-the-me…
(27/28)
himesh.substack.com/p/after-the-me…
Meanwhile, my earlier threads & Substack post on Part 1 of this series, covering the Surge 🌊, can be found here:
(28/28)
(28/28)
https://twitter.com/himeshdoteth/status/1557638869381566466
That's a wrap!
If you enjoyed this thread:
1. Follow me @himeshdoteth for more of these
2. RT the tweet below to share this thread with your audience
🖖
If you enjoyed this thread:
1. Follow me @himeshdoteth for more of these
2. RT the tweet below to share this thread with your audience
🖖
https://twitter.com/himeshdoteth/status/1572561609280688130
• • •
Missing some Tweet in this thread? You can try to
force a refresh
