1st Milestone

Status: Done

Goal: Implement a MVP Verkle Trie implementation for Besu

Dates: July-October 2023

Budget: 10K allocated, 12K consumed.

Summary

Current Merkle-Patricia Trie implementation in Besu: github repo

The implementation follows closely the current implementation of Merkle-Patricia Trie in Besu and is implemented in the Java language. It is more than an MVP as it includes several not so trivial optimisations already like extensions and computing commitments in batches. However, following current design structure maximises the chance of integrating well with the client.

Features

• Generic Implementation in both key and value types: SimpleVerkleTrie<K, V>
• Node interface, with 3 types of implems: BranchNode, LeafNode and NullNode.
• Usual mapping operations get/put/remove are implemented via Visitors Classes implementing PathNodeVisitor interface for extensibility.
• Trie-keys mapping is implemented according to the specs, effectively Pedersen Hashing address and indices.
• Implements simplest python ref implem of verkle commitments using pedersen-commitments wrapped from rust-verkle. Also follows the Visitor pattern.
• Implements store/retrieve to persist trie data to storage.
• Branches and Leaves support Extensions for efficiency. This requires more complex tree restructuration in PutVisitor (splitting) and RemoveVisitor (flattening).
• All operations have simple local tests, using a HashMap to mock storage.