Ethereum mainnet - Analysis of MPT depth and VKT locality optimization in block executions

This document provides summarized information about mainnet transaction execution state trie access for the Merkle Patricia Storage Trees, and on-the-fly analysis of future Verkle Tree branch locality for the same access patterns.

Context and reason for this work

Previously, we did a static analysis of the Merkle Patricia Tree depth of the Ethereum mainnet network. This was useful to understand the depth of the State Trie and have a distribution of depths for the Storage Trees.

What’s important to note about static analysis is that it isn’t factor in the frequency at which each contract is accessed in the actual usage of the network.

For example, if 99.99% of the contract Storage Trees have a tree depth of 1, and 0.01% have a depth of 10, we can’t conclude that most Ethereum clients will have to deal with trees of depth 1. This can happen because the most accessed contract is probably the one with more storage; this isn’t a rule, but it makes sense. In our example, if 99% of the transactions target 0.01% of the contracts, the real access depth is closer to ~10 and not ~1.

This work aims to collect Storage Tree average depth access on real transactions while they’re being executed in a real client (i.e: in our case Geth).

Additionally, we’ll simulate how a Verkle Trie design decision to optimize for access locality would work in the same access patterns. While we analyze the actual transaction storage slot accesses, we’d map how these behave on Verkle Trie branch accesses. We’ll explain more about this later.

Methodology

To achieve this goal, I built a Go native Geth tracer, which allows hooks into different parts of the execution pipeline.

In particular, we can re-execute previous transactions and capture a particular opcode (i.e: SSTORE and SLOAD) that is being executed. Armed with this possibility, we can load the storage trie and calculate the depth of the accessed branch.

Moreover, since the storage slot is present in the EVM stack at the point SSTORE and SLOAD are executed, we can read this value. This means that we have the preimage of the Storage Trie key, which allows us to calculate the stem corresponding to the storage slot in the future Verkle Trie migration.

With this, we can simulate the branch accesses in the Verkle Trie and analyze how many accesses for a branch are:

• First-time access: A branch is accessed in the VKT for the transaction.
• Hot access: a second or further access to a previously read branch in the VKT for the transaction.
• Free access: this is a special case of hot access where the storage slot is less than 64, since these are optimized in a special stem that is always loaded for the transaction, so it doesn’t incur in First-time access.

If the above sounds a bit cryptic, I’d highly recommend reading EIP-4762: Statelessness gas cost changes and the *Layout of the verkle tree* section from the Verkle Tree blog post.

The analysis stack is formed by:

• The custom Geth native tracer, which enables calling debug_traceTransaction(..., "treeAccessLogger") for a custom tracer to get raw data about storage slot access for MPT depth and VKT branch access.
• A custom tool trace-depth that continuously calls this new tracer from the Geth node and saves the data in SQLite while the Geth node continues to execute blocks. The same tool provides flag -results to create the summary of the collected data.

With a Geth node synced to mainnet, we can run the enhanced version from the first bullet, with the trace-depth as a sidecar process.

Note that this work is trying to do the VKT branch access analysis without a Geth node with access to any existing Keccak preimages. This is why we “simulate” the VKT branch access on-the-fly since we can pull the “preimage” from the EVM stack while the transaction is executed. There’s no migrated VKT tree in the Geth node since we don’t have the information to do that!

Results

Here we present the results generated by running the analysis stack and getting the automatic result summary from trace-depth. Later, I’ll explain in more detail what each field of the summary means.

-- Summary --
Block range: [16348389, 16356771] (8383 total blocks)
Total txns: 1183641

Total read/write accesses: 25865749
MPT average depth is: 5.04

Top 20 contracts with the most accesses:
        Contract 0xc02aaa39b223fe8d0a0e5c4f27ead9083c756cc2
                Read/Write slot accesses: 1633727 (6.32%)
                MPT Avg. read/write access depth: 6.92
                VKT Reads branch accesses: 0.04% free, 66.24% hot, 33.72% cold
                VKT Writes branch accesses: 0.00% free, 33.89% hot, 66.11% cold
        Contract 0x06450dee7fd2fb8e39061434babcfc05599a6fb8
                Read/Write slot accesses: 1501938 (5.81%)
                MPT Avg. read/write access depth: 7.62
                VKT Reads branch accesses: 54.28% free, 31.23% hot, 14.49% cold
                VKT Writes branch accesses: 25.59% free, 58.75% hot, 15.66% cold
        Contract 0xdac17f958d2ee523a2206206994597c13d831ec7
                Read/Write slot accesses: 1398251 (5.41%)
                MPT Avg. read/write access depth: 6.93
                VKT Reads branch accesses: 54.61% free, 3.88% hot, 41.51% cold
                VKT Writes branch accesses: 0.00% free, 4.39% hot, 95.61% cold
        Contract 0xa0b86991c6218b36c1d19d4a2e9eb0ce3606eb48
                Read/Write slot accesses: 1275505 (4.93%)
                MPT Avg. read/write access depth: 6.82
                VKT Reads branch accesses: 10.10% free, 39.67% hot, 50.23% cold
                VKT Writes branch accesses: 0.09% free, 9.98% hot, 89.93% cold
        Contract 0x00000000006c3852cbef3e08e8df289169ede581
                Read/Write slot accesses: 709661 (2.74%)
                MPT Avg. read/write access depth: 7.21
                VKT Reads branch accesses: 15.52% free, 43.33% hot, 41.15% cold
                VKT Writes branch accesses: 37.26% free, 31.66% hot, 31.08% cold
        Contract 0x000000000000ad05ccc4f10045630fb830b95127
                Read/Write slot accesses: 513161 (1.98%)
                MPT Avg. read/write access depth: 6.35
                VKT Reads branch accesses: 24.09% free, 56.13% hot, 19.79% cold
                VKT Writes branch accesses: 29.26% free, 31.71% hot, 39.03% cold
        Contract 0x42dc0cecefbaf8e81d631a75fa212510c347f66b
                Read/Write slot accesses: 314540 (1.22%)
                MPT Avg. read/write access depth: 4.89
                VKT Reads branch accesses: 35.73% free, 12.57% hot, 51.70% cold
                VKT Writes branch accesses: 10.43% free, 7.48% hot, 82.10% cold
        Contract 0x000000000000aaeb6d7670e522a718067333cd4e
                Read/Write slot accesses: 270848 (1.05%)
                MPT Avg. read/write access depth: 4.56
                VKT Reads branch accesses: 0.00% free, 42.69% hot, 57.31% cold
                VKT Writes branch accesses: 0.00% free, 9.45% hot, 90.55% cold
        Contract 0x2b591e99afe9f32eaa6214f7b7629768c40eeb39
                Read/Write slot accesses: 222207 (0.86%)
                MPT Avg. read/write access depth: 6.67
                VKT Reads branch accesses: 3.52% free, 5.54% hot, 90.95% cold
                VKT Writes branch accesses: 21.38% free, 17.21% hot, 61.40% cold
        Contract 0x44e94034afce2dd3cd5eb62528f239686fc8f162
                Read/Write slot accesses: 143861 (0.56%)
                MPT Avg. read/write access depth: 6.04
                VKT Reads branch accesses: 6.06% free, 79.79% hot, 14.15% cold
                VKT Writes branch accesses: 47.21% free, 8.59% hot, 44.19% cold
        Contract 0xcb323294d1cfb4547126b0e299af2e1fab7f1943
                Read/Write slot accesses: 139639 (0.54%)
                MPT Avg. read/write access depth: 4.88
                VKT Reads branch accesses: 30.80% free, 16.70% hot, 52.50% cold
                VKT Writes branch accesses: 4.21% free, 23.73% hot, 72.06% cold
        Contract 0x5a98fcbea516cf06857215779fd812ca3bef1b32
                Read/Write slot accesses: 133654 (0.52%)
                MPT Avg. read/write access depth: 6.55
                VKT Reads branch accesses: 8.47% free, 81.94% hot, 9.60% cold
                VKT Writes branch accesses: 0.00% free, 6.76% hot, 93.24% cold
        Contract 0x5f8c3af28b7af2fd628f9ccd14d12570da0715ae
                Read/Write slot accesses: 128564 (0.50%)
                MPT Avg. read/write access depth: 4.32
                VKT Reads branch accesses: 24.00% free, 50.59% hot, 25.41% cold
                VKT Writes branch accesses: 11.83% free, 40.16% hot, 48.01% cold
        Contract 0x7db5af2b9624e1b3b4bb69d6debd9ad1016a58ac
                Read/Write slot accesses: 120187 (0.46%)
                MPT Avg. read/write access depth: 5.41
                VKT Reads branch accesses: 42.20% free, 52.41% hot, 5.39% cold
                VKT Writes branch accesses: 53.68% free, 11.48% hot, 34.84% cold
        Contract 0xcfc19e20d0a7c57b7bfa18c74179de576cd29ecb
                Read/Write slot accesses: 117295 (0.45%)
                MPT Avg. read/write access depth: 3.86
                VKT Reads branch accesses: 45.97% free, 42.18% hot, 11.85% cold
                VKT Writes branch accesses: 27.86% free, 9.96% hot, 62.18% cold
        Contract 0x88e6a0c2ddd26feeb64f039a2c41296fcb3f5640
                Read/Write slot accesses: 107145 (0.41%)
                MPT Avg. read/write access depth: 5.85
                VKT Reads branch accesses: 68.41% free, 17.62% hot, 13.97% cold
                VKT Writes branch accesses: 83.88% free, 9.09% hot, 7.03% cold
        Contract 0x769272677fab02575e84945f03eca517acc544cc
                Read/Write slot accesses: 99990 (0.39%)
                MPT Avg. read/write access depth: 4.54
                VKT Reads branch accesses: 0.03% free, 46.05% hot, 53.92% cold
                VKT Writes branch accesses: 0.00% free, 20.04% hot, 79.96% cold
        Contract 0xc9aa0d98a7d7899f7ef6daa0e7482e3c4e4f140b
                Read/Write slot accesses: 96017 (0.37%)
                MPT Avg. read/write access depth: 4.24
                VKT Reads branch accesses: 56.18% free, 24.01% hot, 19.81% cold
                VKT Writes branch accesses: 11.50% free, 6.15% hot, 82.35% cold
        Contract 0x74312363e45dcaba76c59ec49a7aa8a65a67eed3
                Read/Write slot accesses: 94583 (0.37%)
                MPT Avg. read/write access depth: 6.42
                VKT Reads branch accesses: 12.14% free, 33.29% hot, 54.57% cold
                VKT Writes branch accesses: 70.11% free, 0.00% hot, 29.89% cold
        Contract 0x5954ab967bc958940b7eb73ee84797dc8a2afbb9
                Read/Write slot accesses: 93651 (0.36%)
                MPT Avg. read/write access depth: 5.38
                VKT Reads branch accesses: 35.68% free, 42.58% hot, 21.73% cold
                VKT Writes branch accesses: 20.17% free, 21.95% hot, 57.89% cold

Summary output description

Let’s explain what the summary is showing.

Header

-- Summary --
Block range: [<start>, <end>] (<numBlocks> total blocks)
Total txns: <totalTxns>

Total read/write accesses: <totalReadWriteAccesses>
MPT average depth is: <avgMPTDepth>

• <start> and <end> describe which Ethereum mainnet blocks were analyzed which generated these results. <numBlocks> = <end>-<start>+1
• <totalTxns> are the total number of transactions executed in the analyzed block range.
• <totalReadWriteAccess> is the total SSTORE and SLOAD opcodes analyzed in the block range (i.e: every storage slot read/write access).
• <avgMPTDepth> is the average depth of a Storage Trie branch access. Every branch access depth was logged and averaged with the total number of branch accesses.

Contract summary

Contract <contractAddr>
        Read/Write slot accesses: <readWriteSlotAccesses> (<percOfTotal>)
        MPT Avg. read/write access depth: <MPTAvgDepth>
        VKT Reads branch accesses: <readFree>% free, <readHot>% hot, <readCold>% cold
        VKT Writes branch accesses: <writeFree>% free, <writeHot>% hot, <writeCold>% cold

• <contractAddr> is the address of the contract.
• <readWriteSlotAccesses> is the total number of read/write storage slot accesses for this contract in the analyzed block range.
• <percOfTotal> is the % of read/write storage slots compared to the total analyzed in the block range. This factor sorts results. So, the top in the list is the contract that did more read/write storage slot accesses.
• <MPTAvgDepth> has the same semantics described in the Header section but is scoped to this contract.
• <(read|write)Free> indicates the % of read/write branch access for a storage slot <64.
• <(read|write)Cold> indicates the % of read/write branch accesses for a storage slot ≥64 that have accessed a VKT stem for the first time in the transaction execution.
• <(read|write>Hot> indicates the % of read/write branch access for a storage slot ≥64 for a stem that has been previously accessed (i.e., previous cold access for that stem has happened).

Note that <(read|write)Cold> accesses can provide insight into WITNESS_BRANCH_COST and SUBTREE_EDIT_COST.

Conclusion

If we compare the static results from this live mainnet analysis, we can see that the true MPT depth access is way higher than expected. This makes intuitive sense since the most popular contracts probably have a reasonable amount of storage data.

This work also provides interesting results about how the Verkle Triee locality optimization made in the design plays out on real contract executions (no testnets, nor fake contracts).

This could provide insight data to refine EIP-4762 and to the owners of contracts on what they might expect regarding future gas cost changes.

To potentially improve the usefulness in this regard, we can think of further iterations of this work, for example:

• Consider counting count how many “first time” VKT leaf access happen to have some intuition around CHUNK_EDIT_COST.
• Instead (or apart from) showing the percentages of VKT branch accesses, we could show the average first-time accesses per contract (e.g: contract X has Y branch cold accesses per transaction). This can help estimate future gas costs since using % in summary only describes “access patterns”.
• Consider if we could also count CHUNK_FILL_COST situations in the access patterns.