In a [previous post](https://hackmd.io/8woMcS19StGGSYrz_Wl6yg?view), I described a compact storage layout for the (non-historical) Ethereum world state that's highly compact, which could be leveraged by full nodes (not archival nodes).
To facilitate that storage, as well as an efficient Ethereum EVM in general, we need some runtime components. The main component, described in this document, provides an efficient way to buffer, chain, compare, merge and discard modifications made to the world state.
## Challenges
### Block finalization
With [BART](https://hackmd.io/8woMcS19StGGSYrz_Wl6yg?view), we only save one world state. Problem is, what is the state of Ethereum? It's not straightforward to answer. At any given moment, blocks are being produced and appended to the block chain. However, blocks might be invalid and be discarded. Or, there might be competing blocks (especially in proof-of-work networks), or competing chains of blocks.
The network eventually settles "disputes" and chooses "winning" blocks. But during that time, we can't be certain a block will eventually make it to the finalized Ethereum world state. If we were to persist the state changes made by a block and it would later be discarded by the network, it would be too late for us; we couldn't restore the database to its previous state, since we only store one state.
### Competing chains
Competing blockchains also pose a performance challenge. These chains will keep producing blocks at the regular interval (e.g. 12 seconds), and their respective world state will keep diverging. To process/validate them all, we have to keep track of these ever-widening world states, and need to be able to efficiently switch between these states to validate their respective blocks. Once a block or chain "wins", we need to discard the data from the other chains.
### In-memory transactionality
Even for purely in-memory modifications, we sometimes need a kind of "transaction" that allows us to roll back changes in case of failure.
For example, blocks contain transactions, some of which are contract calls, but not every call succeeds. Calls could fail due to gas fees being insufficient, or various other reasons. In which case all state modifications performed by the contract are discarded. But all previous modifications made by successful transactions in that block are kept.
Similarly, a contract may call another contract which may fail. The caller can recover and continue execution. All modifications done by the failing contract are discarded.
Or sometimes we might like to use such a transaction for isolation, with no intent on "commiting" it. For example, when evaluating an `eth_call` RPC message, we execute an arbitrary contract with arbitrary parameters for debugging purposes, and don't wish to persist the modifications, not even in memory.
### Querying the last 128 world states
Full Ethereum nodes are expected to provide a set of RPC APIs that can be used to query the 128 recent world states. Since we only persist one world state, we can't use the database to fulfill that requirement.
## Buffering
We solve these challenges by buffering modifications. We don't persist them into the database straight away. We wait till we're certain we won't have to undo them. In the case of blocks on the blockchain, and of competing blockchains, we wait till a block is *finalized*.
For in-memory changes, we wait till a contract call is successful before applying its state modifications to the in-memory state.
We call such a buffer a *diff layer*.
## Diff layer requirements
So what would a diff layer look like? We want such a layer to:
* Be stack-able on top of a previous layer, e.g. the changes made by the previous block
* Allow several *sibling* layers to stack on top of one, i.e. support diverging state changes, as occurs with competing blockchains
* Support efficient lookup of an Account across all stacked diff layers (along a single chain)
* Have a low cost for spinning up a new diff layer and stacking it
* Have a low cost for discarding a diff layer (rollback)
* Have a low cost for switching between diff layers
* Provide a "flattened view" of stacked diff layers in order to facilitate Accounts range scans, e.g. to support incoming Snap Sync requests. Every layer should provide its own flattened view, since Snap Sync is performed as per the state at a specific point in time (i.e. specific block).
* Provide an efficient way to collect Merkle and Verkle Proofs for all the tree layers from an account to the root, which could span over separate diff layers.
## Diff layers using account lookup tables
A straightforward approach would be to use maps (or hash tables) between keys (being paths in the Merkle Patricia Tree, or Verkle Tree) and accounts. For example, imagine we have this *base layer*:
```
(base)
0x12345 ⟶ Account1 (balance= 1, nonce= 2)
0x6789a ⟶ Account2 (balance=67, nonce= 1)
0xbcdef ⟶ Account3 (balance=10, nonce=43)
```
Now imagine we have a *top layer* stacked on top of the base one:
```
(top)
0x6789a ⟶ Account2 (balance=72, nonce= 1)
0x8b7c6 ⟶ Account4 (balance=20, nonce= 1)
```
### Fetching a value
If we want to obtain the blanace of `Account4` from the top diff layer, one map lookup would be enough; the balance is 20. Same for `Account2`.
But if we want to obtain the balance of `Account1` or `Account3`, we wouldn't find them in the top diff layer, and would have to look up the base layer.
Since we intend to have around 128 diff layers (to support queries of recent world states, as per the Ethereum requirements for a full node), we might need to perform 128 map lookups, which isn't negligible.
### Enumerating accounts
Now what if we want to enumerate all accounts, in lexicographical order, as per their state in the top diff layer? We'd expect:
```
0x12345 ⟶ Account1 (balance= 1, nonce= 2)
0x6789a ⟶ Account2 (balance=72, nonce= 1)
0xbcdef ⟶ Account3 (balance=10, nonce=43)
0x8b7c6 ⟶ Account4 (balance=20, nonce= 1)
```
First off, to support that, the maps would have to be sorted, meaning a lookup and insertion time of O(log(N)). That's typically slower than a hash map lookup, making 128 lookups across all diff layers even more painful.
Second, we would have to merge the 128 diff layers into a flat structure, starting from the base layer, such that the top layer is merged last and overrides previous ones. This is a very expensive operation.
Another way would be to maintain such a flat view whenever a modification is made in a diff layer, but this needs to be done for every diff layer, and the flat view of the previous layer needs to be copied over to the new one. Very expensive too.
Yet another way would be to iterate all diff layers in parallel, such that at every step we find the account with the lowest lexicographical ID and return it, then increment that specific iterator. In case two or more iterators denote the same account, take the one from the higher diff layer. This is expensive as well.
### Merkle & Verkle proofs
A proof is comprised of the Merkle hashes of all nodes from the root down to and including the Account node, including the hashes of all their sibling nodes. For Verkle trees, a single proof is generated for each node from the root to the Account.
Account lookup tables don't hold tree data. If we wanted to generate a proof, we'd have to apply all the modifications in a diff layer and all its base layers to a Merkle or Verkle tree with a partial view of the full world state, then compute and obtain the proof.
We need to do that anyway to persist diff layers, however if we want to support providing proofs at arbitrary diff layers, each layer should have its own copy of the tree. Which is, well, expensive.
### Further complications
Things get even more hairy when we consider Account deletions. We'd have to store the fact that an account was deleted in a diff layer. Either by having a separate table for these, or denoting it by another way (e.g. holding a null account).
Besides accounts, we also need to track changes to accounts' own storage trees.
## Diff layers using stacked trees
There is another way to represent diff layers that solves the issues mentioned above, provides much better performance and has a lower memory footprint. It's achieved by holding a Merkle or Verkle tree structure, with some twists.
Let's start by an example. For simplicity, we'll be using a tree with a branching factor of 2 and depth of 3 (versus Merkle's branching factor of 16, and Verkle's branching factor of 256).
```graphviz
digraph {
node [shape=record style=rounded margin="0.2,0.07"]
root [label="{Root branch|{<child0>0|<child1>1}}" width=3];
branch0 [label="{Branch 0x0|{<child0>0|<child1>1}}" width=2];
branch1 [label="{Branch 0x1|{<child0>0|<child1>1}}" width=2];
account00 [label="{Account 0x00|Balance: 0}"];
account10 [label="{Account 0x10|Balance: 2}"];
account11 [label="{Account 0x11|Balance: 6}"];
root:child0 -> branch0;
root:child1 -> branch1;
branch0:child0 -> account00
branch1:child0 -> account10
branch1:child1 -> account11
}
```
Every branch has two children, at offsets 0 and 1, though some children might not be present. Nodes are identified by their path down the tree, e.g. the path `0x11` leads to Account `0x11`.
## Stacking a diff
Now let's assume we increased account `0x11`'s balance from 6 to 8. We perform that in a separate diff layer (highlighted in <span style="color: #a00">red</span>). That diff layer has a special property: it will contain the modified account along with its parent nodes, but it will hold direct memory pointer references into the previous diff layer for any other node that was not modified (see dotted <span style="color: #777">gray</span> arrows).
```graphviz
digraph {
graph [nodesep="0.8"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph base {
node [group=base]
root [label="{Root branch (base diff)|{<child0>0|<child1>1}}"]
branch0 [label="{Branch 0x0|{<child0>0|<child1>1}}"]
branch1 [label="{Branch 0x1|{<child0>0|<child1>1}}"]
account00 [label="{Account 0x00|Balance: 0}"]
account10 [label="{Account 0x10|Balance: 2}"]
account11 [label="{Account 0x11|Balance: 6}"]
root:child0 -> branch0
root:child1 -> branch1
branch0:child0 -> account00
branch1:child0 -> account10
branch1:child1 -> account11
}
subgraph top {
node [group=top color="#aa0000" fontcolor="#aa0000"]
edge [color="#aa0000"]
root_ [label="{Root branch (top diff)|{<child0>0|<child1>1}}"]
branch1_ [label="{Branch 0x1|{<child0>0|<child1>1}}"]
account11_ [label="{Account 0x11|Balance: 8}"]
root_:child0 -> branch0 [style="dashed" color="#cccccc"]
root_:child1 -> branch1_
branch1_:child0 -> account10 [style="dashed" color="#cccccc"]
branch1_:child1 -> account11_
}
}
```
Now let's say we're increasing account `0x00`'s balance from 0 to 100, in a separate diff layer (highlighted in <span style="color: #77f">blue</span>) stacked on top of the one that's stacked on top of the base layer:
```graphviz
digraph {
graph [nodesep="0.8"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph base {
node [group=base]
root [label="{Root branch (base diff)|{<child0>0| <child1>1}}"]
branch0 [label="{Branch 0x0|{<child0>0|<child1>1}}"]
branch1 [label="{Branch 0x1|{<child0>0|<child1>1}}"]
account00 [label="{Account 0x00|Balance: 0}"]
account10 [label="{Account 0x10|Balance: 2}"]
account11 [label="{Account 0x11|Balance: 6}"]
root:child0 -> branch0
root:child1 -> branch1
branch0:child0 -> account00
branch1:child0 -> account10
branch1:child1 -> account11
}
subgraph middle {
node [group=middle color="#aa0000" fontcolor="#aa0000"]
edge [color="#aa0000"]
root_ [label="{Root branch (middle diff)|{<child0>0| <child1>1}}"]
branch1_ [label="{Branch 0x1|{<child0>0|<child1>1}}"]
account11_ [label="{Account 0x11|Balance: 8}"]
root_:child0 -> branch0 [style="dashed" color="#cccccc"]
root_:child1 -> branch1_
branch1_:child0 -> account10 [style="dashed" color="#cccccc"]
branch1_:child1 -> account11_
}
subgraph top {
node [group=top color="#0000aa" fontcolor="#0000aa"]
edge [color="#0000aa"]
root__ [label="{Root branch (top diff)|{<child0>0| <child1>1}}"]
branch0__ [label="{Branch 0x0|{<child0>0|<child1>1}}"]
account00__ [label="{Account 0x00|Balance: 100}"]
root__:child0 -> branch0__
root__:child1 -> branch1_ [style="dashed" color="#cccccc"]
branch0__:child0 -> account00__
}
}
```
## Efficient lookup across layers
To look up an account, we start from the desired diff layer root, and walk down the tree. No matter the amount of diff layers, we'll always reach the account in as many hops as the depth of the tree. Note that a diff layer might point to a node belonging to a layer further back than its immediate base layer (not shown in the example).
Assuming a Markle tree with a typical depth of ~10, looking up an account across any number of diff layers is probably faster than a single lookup in a hash table (which necessitates hashing the whole 32-bytes key, looking up a bucket, iterating its list and comparing the key to the item(s) in the list). And even more so for a Verkle tree with a depth of ~5.
## Labeling nodes by their diff layer
If we wanted to answer the question "Has the top diff layer modified account `0x10`?" in our example, it's actually not easy to answer. If we were to walk down the tree from the top layer, the first stop would be at Branch `0x1` in the middle layer, then the account `0x10` in the base layer. It's obvious when looking at the color-coded example, but the implementation has no way of knowing whether a node is a direct descendant of a particular diff layer, other than trying to walk down all other diff roots to ascertain they don't reach that node, which is expensive.
The same problem arises if we attempt to serialize a specific diff layer; during traversal we'd scan nodes from base layers as well.
To solve that, we need an easy way to tell if a node belongs to a certain layer. There are multiple ways to achieve that. We choose to have nodes store an integer "diff height" counter, which can also be used to handle a separate concern not described here (cache expiration).
Here's the previous example with the diff height annotation:
```graphviz
digraph {
graph [nodesep="0.8"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph base {
node [group=base]
root [label="{Root branch (base diff)|Diff height: 0|{<child0>0|<child1>1}}"]
branch0 [label="{Branch 0x0|Diff height: 0|{<child0>0|<child1>1}}"]
branch1 [label="{Branch 0x1|Diff height: 0|{<child0>0|<child1>1}}"]
account00 [label="{Account 0x00|Diff height: 0|Balance: 0}"]
account10 [label="{Account 0x10|Diff height: 0|Balance: 2}"]
account11 [label="{Account 0x11|Diff height: 0|Balance: 6}"]
root:child0 -> branch0
root:child1 -> branch1
branch0:child0 -> account00
branch1:child0 -> account10
branch1:child1 -> account11
}
subgraph middle {
node [group=middle color="#aa0000" fontcolor="#aa0000"]
root_ [label="{Root branch (middle diff)|Diff height: 1|{<child0>0|<child1>1}}"]
branch1_ [label="{Branch 0x1|Diff height: 1|{<child0>0|<child1>1}}"]
account11_ [label="{Account 0x11|Diff height: 1|Balance: 8}"]
root_:child0 -> branch0 [style="dashed" color="#cccccc"]
root_:child1 -> branch1_ [color="#aa0000"]
branch1_:child0 -> account10 [style="dashed" color="#cccccc"]
branch1_:child1 -> account11_ [color="#aa0000"]
}
subgraph top {
node [group=top color="#0000aa" fontcolor="#0000aa"]
root__ [label="{Root branch (top diff)|Diff height: 2|{<child0>0|<child1>1}}"]
branch0__ [label="{Branch 0x0|Diff height: 2|{<child0>0|<child1>1}}"]
account00__ [label="{Account 0x00|Diff height: 2|Balance: 100}"]
root__:child0 -> branch0__ [color="#0000aa"]
root__:child1 -> branch1_ [style="dashed" color="#cccccc"]
branch0__:child0 -> account00__ [color="#0000aa"]
}
}
```
## Competing chains
We can stack multiple diff layers on top of a base layer. Meaning, we can support arbitrary chains of diffs.
In the following example, let's assume we have a fork in the blockchain. The base block (0) is in the middle, and contains two accounts with a balance of 100. Chain A (highlighted in <font color="008800">green</font> on the left) contains two blocks (1 and 2), each of which drains one of the accounts. Chain B (highlighted in <span style="color: #77f">blue</span> on the right) contains two blocks (1 and 2), each of which increments the balance of an account.
```graphviz
digraph {
graph [nodesep="0.5"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph a2 {
node [group=a2 color="#008800" fontcolor="#008800"]
edge [color="#008800"]
a2root [label="{Chain A block 2|Diff height: 2|{<child0>0|<child1>1}}"]
a2branch1 [label="{Branch 0x1|Diff height: 2|{<child0>0|<child1>1}}"]
a2account11 [label="{Account 0x11|Diff height: 2|Balance: 0}"]
a2root:child1 -> a2branch1
a2branch1:child1 -> a2account11
}
subgraph a1 {
node [group=a1 color="#008800" fontcolor="#008800"]
edge [color="#008800"]
a1root [label="{Chain A block 1|Diff height: 1|{<child0>0|<child1>1}}"]
a1branch1 [label="{Branch 0x1|Diff height: 1|{<child0>0|<child1>1}}"]
a1account10 [label="{Account 0x10|Diff height: 1|Balance: 0}"]
a1root:child1 -> a1branch1
a1branch1:child0 -> a1account10
a2branch1:child0 -> a1account10 [style="dashed" color="#cccccc"]
}
subgraph base {
node [group=base]
root [label="{Base block 0|Diff height: 0|{<child0>0| <child1>1}}"]
branch1 [label="{Branch 0x1|Diff height: 0|{<child0>0|<child1>1}}"]
account10 [label="{Account 0x10|Diff height: 0|Balance: 100}"]
account11 [label="{Account 0x11|Diff height: 0|Balance: 100}"]
root:child1 -> branch1
branch1:child0 -> account10
branch1:child1 -> account11
a1branch1:child1 -> account11 [style="dashed" color="#cccccc"]
}
subgraph b1 {
node [group=b1 color="#000088" fontcolor="#000088"]
edge [color="#000088"]
b1root [label="{Chain B block 1|Diff height: 1|{<child0>0|<child1>1}}"]
b1branch1 [label="{Branch 0x1|Diff height: 1|{<child0>0|<child1>1}}"]
b1account10 [label="{Account 0x10|Diff height: 1|Balance: 200}"]
b1root:child1 -> b1branch1
b1branch1:child0 -> b1account10
b1branch1:child1 -> account11 [style="dashed" color="#cccccc"]
}
subgraph b2 {
node [group=b2 color="#000088" fontcolor="#000088"]
edge [color="#000088"]
b2root [label="{Chain B block 2|Diff height: 2|{<child0>0|<child1>1}}"]
b2branch1 [label="{Branch 0x1|Diff height: 2|{<child0>0|<child1>1}}"]
b2account11 [label="{Account 0x11|Diff height: 2|Balance: 200}"]
b2root:child1 -> b2branch1
b2branch1:child0 -> b1account10 [style="dashed" color="#cccccc"]
b2branch1:child1 -> b2account11
}
}
```
Notice how both chain A and B have a diff layer at diff height 1, and at diff height 2. We must not stack a diff layer on top of another one with the same diff height, otherwise we couldn't tell their nodes apart. But this can't happen, since these layers belong to separate chains.
## Copy-on-write
Let's get back to our first example and explore how a diff layer is built, step by step. First, we *shallow clone* the base layer's root node. Meaning, we create an in-memory copy of the node object. That copy has the same pointers to its children as the original object; we don't *deep clone* the tree. However, we do increment its *diff height* counter. It's now the top diff layer.
```graphviz
digraph {
graph [nodesep="0.8"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph base {
node [group=base]
root [label="{Root branch (base diff)|Diff height: 0| {<child0>0|<child1>1}}"]
branch0 [label="{Branch 0x0|Diff height: 0|{<child0>0| <child1>1}}"]
branch1 [label="{Branch 0x1|Diff height: 0|{<child0>0| <child1>1}}"]
account00 [label="{Account 0x00|Diff height: 0|Balance: 0}"]
account10 [label="{Account 0x10|Diff height: 0|Balance: 2}"]
account11 [label="{Account 0x11|Diff height: 0|Balance: 6}"]
root:child0 -> branch0
root:child1 -> branch1
branch0:child0 -> account00
branch1:child0 -> account10
branch1:child1 -> account11
}
subgraph top {
node [group=top color="#aa0000" fontcolor="#aa0000"]
root_ [label="{Root branch (top diff)|Diff height: 1| {<child0>0|<child1>1}}"]
root_:child0 -> branch0 [style="dashed" color="#cccccc"]
root_:child1 -> branch1 [style="dashed" color="#cccccc"]
// Force graphviz to align root_ in its own "column"
fake1 [style = invis]
fake2 [style = invis]
root_ -> fake1 [style = invis]
fake1 -> fake2 [style = invis]
}
}
```
Our aim is to increment account `0x11`'s balance from 6 to 8. We need to clone all nodes leading to it, including the account. The next step is to inspect the child at offset `1`. Did we already clone it? We check its diff height. It's 0, not 1, meaning it's not "owned" by the top diff layer. We shallow clone it as well, and increment its diff height:
```graphviz
digraph {
graph [nodesep="0.8"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph base {
node [group=base]
root [label="{Root branch (base diff)|Diff height: 0| {<child0>0|<child1>1}}"]
branch0 [label="{Branch 0x0|Diff height: 0|{<child0>0| <child1>1}}"]
branch1 [label="{Branch 0x1|Diff height: 0|{<child0>0| <child1>1}}"]
account00 [label="{Account 0x00|Diff height: 0|Balance: 0}"]
account10 [label="{Account 0x10|Diff height: 0|Balance: 2}"]
account11 [label="{Account 0x11|Diff height: 0|Balance: 6}"]
root:child0 -> branch0
root:child1 -> branch1
branch0:child0 -> account00
branch1:child0 -> account10
branch1:child1 -> account11
}
subgraph top {
node [group=top color="#aa0000" fontcolor="#aa0000"]
root_ [label="{Root branch (top diff)|Diff height: 1| {<child0>0|<child1>1}}"]
branch1_ [label="{Branch 0x1|Diff height: 1|{<child0>0| <child1>1}}"]
root_:child0 -> branch0 [style="dashed" color="#cccccc"]
root_:child1 -> branch1_ [color="#aa0000"]
branch1_:child0 -> account10 [style="dashed" color="#cccccc"]
branch1_:child1 -> account11 [style="dashed" color="#cccccc"]
// Force graphviz to align root_ in its own "column"
fake [group=top style = invis]
branch1_ -> fake [style = invis]
}
}
```
Now we inspect the cloned node's own child at offset `1`. Its diff height is 0 too, meaning we need to shallow clone it as well (and increment the clone's diff height). This is the account we were looking for, so once cloned, we can increment its balance:
```graphviz
digraph {
graph [nodesep="0.8"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph base {
node [group=base]
root [label="{Root branch (base diff)|Diff height: 0| {<child0>0|<child1>1}}"]
branch0 [label="{Branch 0x0|Diff height: 0|{<child0>0| <child1>1}}"]
branch1 [label="{Branch 0x1|Diff height: 0|{<child0>0| <child1>1}}"]
account00 [label="{Account 0x00|Diff height: 0|Balance: 0}"]
account10 [label="{Account 0x10|Diff height: 0|Balance: 2}"]
account11 [label="{Account 0x11|Diff height: 0|Balance: 6}"]
root:child0 -> branch0
root:child1 -> branch1
branch0:child0 -> account00
branch1:child0 -> account10
branch1:child1 -> account11
}
subgraph top {
node [group=top color="#aa0000" fontcolor="#aa0000"]
edge [color="#aa0000"]
root_ [label="{Root branch (top diff)|Diff height: 1| {<child0>0|<child1>1}}"]
branch1_ [label="{Branch 0x1|Diff height: 1|{<child0>0| <child1>1}}"]
account11_ [label="{Account 0x11|Diff height: 1|Balance: 8}"]
root_:child0 -> branch0 [style="dashed" color="#cccccc"]
root_:child1 -> branch1_
branch1_:child0 -> account10 [style="dashed" color="#cccccc"]
branch1_:child1 -> account11_
}
}
```
Notice how we never modify a node from a base layer; we always clone them first. This approach is called *copy on write*.
## Deleting an account
In the example above, if we were to delete account `0x11` instead of incrementing its balance, all we'd have to do is modify its parent node to not have a child at offset `1`, like so:
```graphviz
digraph {
graph [nodesep="0.8"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph base {
node [group=base]
root [label="{Root branch (base diff)|{<child0>0| <child1>1}}"]
branch0 [label="{Branch 0x0|{<child0>0|<child1>1}}"]
branch1 [label="{Branch 0x1|{<child0>0|<child1>1}}"]
account00 [label="{Account 0x00|Balance: 0}"]
account10 [label="{Account 0x10|Balance: 2}"]
account11 [label="{Account 0x11|Balance: 6}"]
root:child0 -> branch0
root:child1 -> branch1
branch0:child0 -> account00
branch1:child0 -> account10
branch1:child1 -> account11
}
subgraph top {
node [group=top color="#aa0000" fontcolor="#aa0000"]
root_ [label="{Root branch (top diff)|{<child0>0| <child1>1}}"]
branch1_ [label="{Branch 0x1|{<child0>0|<child1>1}}"]
root_:child0 -> branch0 [style="dashed" color="#cccccc"]
root_:child1 -> branch1_ [color="#aa0000"]
branch1_:child0 -> account10 [style="dashed" color="#cccccc"]
// Force graphviz to align root_ in its own "column"
fake [group=top style = invis]
branch1_ -> fake [style = invis]
}
}
```
(Note that for simplicity, we've been ignoring the way Merkle and Verkle trees are encoded. If that were a MPT tree, the branch we just modified would need to have been converted into an *exension node*, since it's left with a single child. Similarly, branch `0x0` would have been an exstension node to begin with.)
If we were to delete account `0x10` as well, the parent branch would've been left with no children and should be *pruned*. Meaning, we'd detach it from its own parent, the root branch of the top diff, like so:
```graphviz
digraph {
graph [nodesep="0.8"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph base {
node [group=base]
root [label="{Root branch (base diff)|{<child0>0| <child1>1}}"]
branch0 [label="{Branch 0x0|{<child0>0|<child1>1}}"]
branch1 [label="{Branch 0x1|{<child0>0|<child1>1}}"]
account00 [label="{Account 0x00|Balance: 0}"]
account10 [label="{Account 0x10|Balance: 2}"]
account11 [label="{Account 0x11|Balance: 6}"]
root:child0 -> branch0
root:child1 -> branch1
branch0:child0 -> account00
branch1:child0 -> account10
branch1:child1 -> account11
}
subgraph top {
node [group=top color="#aa0000" fontcolor="#aa0000"]
root_ [label="{Root branch (top diff)|{<child0>0| <child1>1}}"]
root_:child0 -> branch0 [style="dashed" color="#cccccc"]
// Force graphviz to align root_ in its own "column"
root_:child1 -> branch1 [style = invis]
fake1 [group=top style = invis]
fake2 [group=top style = invis]
root_ -> fake1 [style = invis]
fake1 -> fake2 [style = invis]
}
}
```
## Enumeration & Snap Sync support
Since diff layers have the same structure as the world state, we can stack them on top of that state. In the following example, we use the world state as the "base" layer, then stack diff layers that perform an account addition, deletion, and modification:
```graphviz
digraph {
graph [nodesep="0.4"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph base {
node [group=base]
root [label="{Root branch (world state)|{<child0>0|<child1>1}}"]
branch1 [label="{Branch 0x1|{<child0>0|<child1>1}}"]
account10 [label="{Account 0x10|Balance: 2}"]
account11 [label="{Account 0x11|Balance: 6}"]
root:child1 -> branch1
branch1:child0 -> account10
branch1:child1 -> account11
}
subgraph addition {
node [group=addition color="#008800" fontcolor="#008800"]
edge [color="#008800"]
root_ [label="{Root branch (addition)|{<child0>0| <child1>1}}"]
branch0_ [label="{Branch 0x0|{<child0>0|<child1>1}}"]
account00_ [label="{Account 0x00|Balance: 3}"]
root_:child0 -> branch0_
root_:child1 -> branch1 [style="dashed" color="#cccccc"]
branch0_:child0 -> account00_
}
subgraph deletion {
node [group=deletion color="#aa0000" fontcolor="#aa0000"]
edge [color="#aa0000"]
root__ [label="{Root branch (deletion)|{<child0>0| <child1>1}}"]
branch1__ [label="{Branch 0x1|{<child0>0|<child1>1}}"]
root__:child0 -> branch0_ [style="dashed" color="#cccccc"]
root__:child1 -> branch1__
branch1__:child1 -> account11 [style="dashed" color="#cccccc"]
}
subgraph modification {
node [group=modification color="#0000aa" fontcolor="#0000aa"]
edge [color="#0000aa"]
root___ [label="{Root branch (modification)|{<child0>0| <child1>1}}"]
branch1___ [label="{Branch 0x1|{<child0>0|<child1>1}}"]
account11___ [label="{Account 0x11|Balance: 0}"]
root___:child0 -> branch0_ [style="dashed" color="#cccccc"]
root___:child1 -> branch1___
branch1___:child1 -> account11___
}
}
```
To enumerate accounts in lexicographical order at a specific diff layer, all we need to do is traverse the tree starting from the diff layer's root, depth-first. This would yield the following account ⟶ balance pairs, for each of the layers:
```
World state:
0x10 ⟶ 2
0x11 ⟶ 6
After addition:
0x00 ⟶ 3
0x10 ⟶ 2
0x11 ⟶ 6
After addition and deletion:
0x00 ⟶ 3
0x11 ⟶ 6
After addition, deletion and modification:
0x00 ⟶ 3
0x11 ⟶ 0
```
Naturally, we couldn't have the whole world state in memory; we'd only have a partial view of that world state (a sort of a cache). This will be described in a subsequent post.
### Proofs
For Merkle trees, branch nodes are expected to contain the Merkle hash of their children, whether these children are loaded in memory or not. Thus, if we modify a child in a branch, we can compute that child's new hash and, along with the the other pre-computed hashes, can compute the branch's new hash. Same for extension nodes.
For Verkle trees, there's no need for a branch to hold its children commitments. It's enough to compute a modified child's commitment and (sort of) use the "delta" between the child't old and new commitment to update the parent branch's own commitment.
Meaning, we can compute the updated hash / commitment of individual diff layers, and can readily serve Merkle / Verkle proofs for any account in any diff layer.
One thing to keep in mind is that Merkle hashes and Verkle commitments need to be computed by the order of the stacking of layers.
## Account storage
For the purpose of diffs, we can model the account storage as a sub-tree underneath the account node. Here's an example account with a couple of storage slots (highlighted in <font color="#a36824">brown</font>), and a diff layer that modifies one of the slots:
```graphviz
digraph {
graph [nodesep="0.8"]
node [shape=record style=rounded margin="0.2,0.07"]
subgraph base {
node [group=base]
root [label="{Root branch (base diff)|{<child0>0| <child1>1}}"]
branch1 [label="{Branch 0x1|{<child0>0|<child1>1}}"]
account10 [label="{Account 0x10|Balance: 2}}"]
root:child1 -> branch1
branch1:child0 -> account10
node [color="#a36824" fontcolor="#a36824"]
edge [color="#a36824"]
sroot [label="{Storage root branch|{<child0>0|<child1>1}}"]
sbranch1 [label="{Branch 0x1|{<child0>0|<child1>1}}"]
sleaf10 [label="{Leaf 0x10|Value:\n0x107ea351890f9701}"]
sleaf11 [label="{Leaf 0x11|Value:\n0x3cfb3345841c9c24}"]
account10 -> sroot
sroot:child1 -> sbranch1
sbranch1:child0 -> sleaf10
sbranch1:child1 -> sleaf11
}
subgraph top {
node [group=top color="#008800" fontcolor="#008800"]
edge [color="#008800"]
root_ [label="{Root branch (base diff)|{<child0>0| <child1>1}}"]
branch1_ [label="{Branch 0x1|{<child0>0|<child1>1}}"]
account10_ [label="{Account 0x10|Balance: 2}}"]
root_:child1 -> branch1_
branch1_:child0 -> account10_
sroot_ [label="{Storage root branch|{<child0>0|<child1>1}}"]
sbranch1_ [label="{Branch 0x1|{<child0>0|<child1>1}}"]
sleaf11_ [label="{Leaf 0x11|Value:\n0x753b16aadeef8515}"]
account10_ -> sroot_
sroot_:child1 -> sbranch1_
sbranch1_:child0 -> sleaf10 [style="dashed" color="#cccccc"]
sbranch1_:child1 -> sleaf11_
}
}
```
That way we can conveniently deal with all modifications in a single data structure. Note that the storage root might be a leaf, not necessarily a branch.
## Performance characteristics
The stacked diffs presented here are technically a *directed acyclic graph*. I prefer the term *stacked trees* since it conveys the notion of directionality; a top layer can access a base layer, but not vice versa.
Here's a summary of the performance characteristics of this approach. The depth of a Merkle tree should be around ~10 (as of 2024), and of a Verkle tree around ~5. For account storage, add another ~3 levels, depending on the size of that account's storage.
| Operation | Cost | Notes |
| -------- | -------- | -------- |
| New diff layer | O(1) | Clone base layer's root node; one memory allocation |
| Switch layers | O(1) | Look up a layer's root node by some identifier; hash table lookup |
| Discard layer with N nodes | O(N) | O(1) to stop referencing the layer's root node; the runtime Garbage Collector does the rest (O(N)) |
| Modify an account value | O(tree depth) | Copy-on-write of nodes on the path to the account |
| Account lookup inside layer | O(tree depth) | Pointer dereferences + integer comparisons as per tree depth |
| Account lookup across stacked layers | O(tree depth) | Pointer dereferences as per tree depth |
| Account storage slot lookup across stacked layers | O(tree depth + ~3) | Pointer dereferences |
| Traverse N consecutive accounts across stacked layers | O(N * tree depth) | Traversing tree depth first |
| Generate Merkle/Verkle proof for account | O(tree depth) | Pointer dereferences as per tree depth; excluding cost of generating proofs |
## Limitations
* Once a diff layer is stacked on another, the base layer must not be modified.
Sign in with Wallet
Connect another wallet