Future of Stateles Ethereum- Core Protocol Research & Optimization in Verkle trees

Transcript

Okay, Akleen, you are now on stage. Um hey everyone, can everybody hear me okay? Uh need a quick confirmation. Yeah, we can hear you. Okay. Um yeah, I think I'm waiting for my peer to join uh the talk. Um let me just go quickly send him a text, but um he should be joining any minute. He already texted me if I'm finding the link on the email, but I will uh take a quick start with what we are trying to start today.

Um yeah, without wasting any time. So, good morning everyone. Um my name is Akleen Kaur. I'm a software development engineer at AWS. And um I'm here with Everton Fraga. Um he's here on the call and he's a senior solutions architect. Today, we're going to talk about something that directly affects each and every one of you in this room. And somebody like and people who totally care about Ethereum's road map towards straightless future. Um to do that, Ethereum is migrating towards Merkle trees and this is already talked about uh in the previous years at ECC. So, it's an amazing open source code and um yeah, we took a stab at it and wanted to find uh some performance

bottlenecks that we optimized upon. And uh finally, uh we invented something new. It's a fractional Merkle trees that we'll be talking about in this talk. And uh it gets us almost a 36 times uh end-to-end speed up in the overall execution. So, before I get into it, I will uh give the mic to Everton as he uh will talk about the introduction on what we do at AWS. Hey, how's it going everybody? Uh we're here for the speaking from the US. Unfortunately, we we couldn't be there. Uh we love to and and I I work on the global Web3 team at AWS.

And our mission is uh to build uh to build solutions and and partner with with great uh companies to to offer uh those solutions to to Web3 companies and to traditional uh FSI companies as well. Uh we we do believe on on on the mission of Web3 and decentralization um and and we basically uh are here to support the growth of of all the companies that that want to to do so. >> [snorts] >> Um We we're doing vast and a lot of uh projects and programs in the space. So, we have uh startup specific programs for Web3.

We have uh blockchain node um project. So, basically open source code that helps you accelerate the deployment of Ethereum uh nodes and and other uh protocols as well. And and we're always kind of growing and looking for opportunities uh to collaborate and push the user experience forward. Um so, and this kind of takes us to to this presentation where, you know, we we're always um looking for uh optimization everywhere. Uh I'm uh it's kind of obsessed about this.

And this takes us to this uh phenomenal presentation by Akleen. Yeah. Thank you, Everton. Um yeah, a quick introduction. I am based in Bay Area, California. Everton is based in uh the East Coast. Uh yeah, we are worked on time differences, but that did not stop the innovation that we bring to into this work. Um I am the founder of the Gator Blockchain Lab at the University of Florida. That gives me a lot of exposure with blockchain developments as open source. And uh we have uh I was also uh at ETHDenver uh at the Quantum Summit panel. So, um our concerns uh took some uh air around the ETHDenver

uh and uh around ETHDenver and that's where we started thinking more about some concrete problems that I will introduce towards uh the uh towards this presentation. So, quickly start getting started. We are very short on time, so I'll keep this very quick. Um so, uh I would like to introduce on since our work is mostly built on Merkle trees, I would like to start an introduction with what is exactly a Merkle tree because I'm not sure the people in this room how familiar they are with uh this pr- uh project. Um so, uh to ground everyone with a quick baseline, meet Alice. She, let's say, runs a light client a wallet on her phone and then she wants to verify that Bob's DeFi contract actually holds five ETH. That's before signing a

transaction. So, with today's Merkle Patricia trie, Alice needs a sibling hash on the path for the Bob's account up to the state root. And that's about 4 kilobytes of witness data per account. Every account she wants to verify adds another kilobyte. So, the proof size is actually scales logarithmically. Uh as the Ethereum proof grows, the as the Ethereum's uh tree size grows, the proof uh grows with it. So, for 1,000 accounts, that's nearly 4 megabytes and a lot of data. So, Merkle trees uh replace the hash ladder with a polynomial commitment and an inner product argument uh over the Bandersnatch curve. So, it's roughly 600 bytes total uh regardless of whether Alice is verifying one account or 1,000.

So, that's big O of one constant time uh verification. So, this is what actually makes the stateless Ethereum possible. So, instead of requiring one validator to hold the full state, Ethereum clients can verify blocks by only using the witnesses bundled in the block itself. So, we are building upon this foundation and uh offering some improvements. So, to define the problem, um so, let's use Alice again. She upgraded her home validator to use go-verkle. So, this is the Merkle trees implementation in go and uh her machine has 32 GB RAM and a fast NVMe, but her processes she is trying to process the same block you saw on the mainnet and that's, let's

say, between 18 to 19 million and uh a single block is 10,000 state updates. That's completely normal mainnet load, but um this takes about 550 seconds to process. So, Ethereum produces a new block every 12 seconds. Alice's node is 275 times too slow. So, this is for a small scale validator that does not have the access to a high power computation or a supercomputer or uh or cannot do a distributed uh networking parallel load. So, to consider this from the from the lens of a very small scale validator uh they are never able to catch up and are will fall I I will I tend to always fall

off the network. So, the memory is at uh a 20 GB peak your during the execution runtime when you're processing between uh blocks, let's say, between 18 to 19 million. So, the proofs that are coming out are roughly in the sizes of 3 kilobytes and this is not theoretical. This is what actually runs today. So, this is was our analysis from our benchmark tests uh that and our motivation behind this work because we wanted to bring down the proof size to 1.5 kilobytes. So, discussing the approach that we took, we found out four distinct um problems and performance bottlenecks, each compounding the other and through that

we could extrapolate a deeper architectural finding underneath all of them. So, uh for the bug one, uh we were we'll talk about phantom nodes. That's creation on delete That's creation on delete account where we saw a straight tree was silently bloating by 35%. The second was database compaction. The third is memory copy overhead that causes about 30,000 heap allocations per block. And the fourth is a cross-implementation correctness fix that I'll talk about uh in the subsequent slides. So, these four gave us some meaningful performance improvements, but our final work, fractional Merkle trees, is also is is what summarized our entire findings. So, uh let's uh jump into the phantom nodes

problem. So, let's consider a scenario that happens on the mainnet. Bob deploys a contract. Uh it self-destructs in the same transaction and Alice's node calls delete account on that address that never had a balance. So, before our fix, delete account always would call function get or create stem. That means it would create uh even address even an address that never existed. So, this would create a phantom node uh that would still stay in the tree even though the address balance of that account is set to zero. So, upon replaying 1 million mainnet blocks, that comes up to 350,000 of delete account calls and hitting an approximately 35% delete uh like deleted phantom nodes that still

exist in the uh block storage layer and that's 11.2 MB of wasted memory and 700 milliseconds of extra commitment computation per 1,000 blocks. So, this is this fic- this fix is a single uh check at the top of a delete account that if the stem doesn't exist, we do return immediately and that means that no node will be created and no commitment will be computed on top of uh this deleted node and that that that's how we start towards fixing to the tree bloat problem. The impact for this work was uh 100% of our phantom nodes were eliminated. The tree bloat was reduced from the existing current state today by 35%. So, uh this affects all the mainnet

workloads um and this one fix saved us 700 milliseconds per 1,000 blocks. That's a small number, but compacting it over network-wide, that sums up to larger time time saved. So, our problem uh our problem, too, is database compaction. So, for this enhancement, I want to bring about two parts of the problem. One was a latent panic that we observed, and the second was a key size problem. So, for latent panic, this happens during flushing commit Merkle nodes to LevelDB after every block verification. So, when a Merkle node gets flushed to the disk, its slot in memory is replaced with a hash node, a

sentinel that basically says that my child is on the disk. So, each node is keyed by its full banner banner wagon curve point. So, that's a 32-byte x coordinate and a 32-byte y coordinate, and that's 64 bytes in total. So, before our fix, the hash node implementation was a byte structure, and it would copy it would create a deep copy of this structure, and this mechanism would call a child commitment on it. So, the reason Alice's node did not crash at insert value at stem when the child commitment was called is because hash node would resolve to a real node before calling the child commitment, and this would just save the network from panicking,

but any change in the calling order can cause the network to panic. And this problem needed to be fixed. So, we fixed this structurally by implementing the hash node that now carries a 32-byte node reference and a cash commitment pointer. So, at the flush time, the commitment is already computed, and the cash pointer and and we fetch the data from the cash value at zero extra cost. So, overall, this eliminates about 1 second of hidden input output latency that previously attributed to state access overhead. And the key size problem solves solves the memory storage overhead by 50% as instead of using 64-byte keys, we

now use 32-byte keys. The usage of these 32-byte keys is primarily for SSTable Bloom filter, indexing block entries, and then causing exponential usage in the CPU capacity. So, this would in turn also save CPU costs because of using a lower byte key data DDB key. And this compaction is roughly saving us 15 to 30% throughput improvement in the database layer for fsync, memtable flushing, and lock contention functions.

Um then talking about our problem three, the back to Alice. So, here, let's consider when we are verifying a node using Bob's transaction, the proof comes as a flat byte buffer. Under the current Merkle tree code, deserializing each proof extracted three fields. One is a stem, that's 31 bytes static field, and then the x and y coordinate, that's 32 bytes each. So, by allocating new memory and copying each one, this is a total of 95 bytes copied per proof, and then this run across 10,000 proofs per block means nearly 30,000 heap allocations and 950

KB's of heap churn. So, Go's garbage collector sees 2 MB of short-lived objects and triggers three collection pauses timed right in the middle of block verification. So, deserialization alone is right now costing us 12 millisecond. So, our fix was to allocate the buffer once and hand out views into it using reference counted buffers. So, we allocate the buffer once when the proof arrives, and then a proof view is a lightweight structure with a pointer and an offset. So, using our stem x and y values slices sliced from the original buffer, we essentially don't have to copy anymore, and that causes no allocation, and then saves up about 100% of heap churn that is getting consumed.

This heap churn impact across 6,000 full nodes, that is roughly 7,200 blocks per day, is 829 GB. And this is 829 GB per node and 13.6 TB's across the network. So, that's the memory pressure that was silently degrading every validator's performance on every block that this problem fixes. Um our next problem is the So, before I jump into my next problem, I want to define currently, the Go Merkle and Rust Merkle

implementations don't match the proof verification. So, each must produce proof that can be verified by the other client since Ethereum does believe in a decentralized proof future across multiple Merkle implementations. So, the problem was that Go Merkle has one stem entry, and during block verification, so it uses a proof of absence construct a structure that proves if my if my stem is absent from the current state of the Merkle tree that I'm viewing. So,

So, the problem is that other stems that wire entries when multiple keys shared the same proof of absence, these proofs become structurally unverifiable from Rust Merkle because of using a vector instead of a hash map. So, for building extension list, this emits two entries. One is This is about 192 bytes. So, these Both of these two entries are mapped to the same proof of absence, and this in turn is called by a depth extension status function that finally approves if the stem is actually this is a correct proof that is submitted by the prover. So, in this

scenario, when block Bob deploys a contract with eight storage slots, this has never been written. So, we authored the first formal Merkle proof wire format as a part of this fix. That specification defines exactly what each implementation must send and expect. So, this class of ambiguity cannot reoccur. The fix was hash map with automatic deduplication and deterministic sort for canonical outputs to end to send end other stem entries in the wire format per missing key. So, even though the internal representation stays deduplicated, the honest trade-off is still a 35.5% larger proof since previously Go Merkle concatenated just one stem to proof of

absence proof, but now we are we are we are breaking down all the missing proof stems to the same proof of absence layer. That means larger computation over each stem and 33.5% overall larger proof size, but this is a correctness fix, not an optimization. So, it depends upon the developers and Ethereum community to finally adopt or not adopt this proposal, but I believe that the trade-off in the proof size is expected because of wanting cross-implementation compatibility, and that's essentially what we wanted to tackle for this problem.

Um this is a small compacted summary of all the optimization trade-offs. I'm going to quickly go over them. For processing time and peak memory and proof size, I still want to talk about them as we talk about Merkle trees, so I will skip that in this slide. Um we did achieve a 24 times faster deserializations in the problems I just mentioned, and a compaction a four times better DB compaction from our problem two. So, moving forward um with the actual main problem that I wanted to propose, that's we solve today So, the problem we are solving today is for Ethereum's high throughput scaling future with a much larger user base. So, a fundamental insight considering 200 million accounts

as a single monolithic structure, we can't process different accounts in parallel. They might share an ancestor node, but we can't keep it in cash because it's too many GB, and L3 cash is usually 64 MB's in the current hardware requirements. So, you can't split the commitment worker across cores, and that's like one global root. So, one global root causes this performance bottleneck because everything shares a state. So, every update touches the root path, and you cannot parallelize this computation. So, the working set never really truly fits in a CPU cache. So, updates are serial by design, and coming from a team like Elastic MapReduce at AWS,

performance optimization is our core tenant. So, I I'm going to propose, what if we don't use one giant tree? So, fractional Merkle trees is a partitioned state into 1,000 independent smaller trees called hyper trees, and each Each tree holds around like 200,000 accounts. So, a lightweight Merkle coordinator is using these 200,000 accounts as a small 200 MB structure instead of a 20 MB instead of 20 GB overall memory overhead, and then it is easily capable of fitting at least 32% of this 200 MB structure in an L3 cache today, but this problem is for the future, so do we do believe the hardware

computations might improve so that the full hyper tree can be >> you very much for your presentation. Uh maybe you can add a really, really quick conclusion so we won't get late to our schedule if it it's possible for you. Yeah, definitely. So, this is almost at the end of our presentation. I will quickly skip the breakthrough data structure. Our So, to share in a quick summary on why we are proposing fractional Merkle trees for combining Merkle trees and Verkle trees together.

We There are Our core tenant idea was using one coordinator root as a Merkle node and using hyper trees for as a Verkle tree representation. We did do a soundness and correctness proof on multiple benchmarks that revealed us that using hyper trees the entire state can be sharded in single computation in a single laptop instead of sharing it across the network. And we do not need to know the state of other partition that solves a lot of problem for access time and generating smaller proofs. We achieved a overall proof size of 1.5 kilobytes that we essentially targeted.

And we also achieved a faster computation from about 550 seconds to a 15-second proof verification. So, this is the high-level achievements of what we did with Verkle fractional Verkle trees. The code is already open source and is available in our GitHub repositories. So, feel free to look take a look at the GitHub repositories. This also deep thanks to Everton because he was always very readily available to review my work and help with guiding the direction for this framework. Also, I Thank you. Thank you very much for for

your time. Thank you for your great talk. And hopefully we will be here next year. We are really happy to have you here on HCC. So, thank you very much. May I have a round of applause for this one for us. Thank you. Thank you so much, HCC. Thank you a lot. See you next year. Bye-bye.