B Merkle Tree
The growth in popularity of the blockchain execution layer has pushed the storage layer to the forefront of research and development. As more transactions and data can be pushed through decentralized consensus systems, the problem of maintaining and storing the results of the execution layer in a trustless distributed data network has been pushed to authenticated indices, like the Patricia Merkle trie. The implementation of these indices has enormous impacts on the efficiency of storage, retrieval, and verification of data being requested from the blockchain.
Authenticated Indexes are the foundation of the Blockchain data layer
In the process of scaling up the execution layer of blockchain, it is important to select an effective indexing method. This method serves as the data store for the blockchain and is responsible for data storage and operation.
- Index Scaling and Performance: the rate at which the index scales with regards to the size of the witnesses, the amount of data that is stored, and the time it takes to perform data structure operations (e.g. insert, get, remove, range).
- Authentication operations: comprised of witness verification, the time to update the authenticated structure, and the time it takes to verify the witness. It is also necessary to determine what specific types of witnesses can be generated. Witnesses can be generated for a time Verification size, Update time, Proof Verification time
- Feature extensibility: while less defined, the greater the performance and flexibility of the data structure the easier it is to extend the feature set to include: partitioning multi-layer queries, and light client adaptations.
Examples
- Patricia Merkle Trie
- Verkle trie (q-ary trie)
- IAVL tree
Taking a traditional approach with a B-tree
B tree is a self-balancing tree used in many database systems. It splits nodes to accommodate the efficient height. B-trees, and their close cousin the B+ tree, are used as a preferred indexing system in document and relational databases like Postgres and MongoDB. They provide indexing structures for queries between ranges, which can be extended for use in high-level relational queries.
Using Polynomial Commitments with a B Merkle tree
The B Merkle Tree (BMT) represents the next step for constant-sized authenticated data stores for the blockchain. The B Merkle tree utilizes a polynomial commitment scheme for intranode proofs, similar to the Verkle tree, but takes into account self-balancing in order to provide efficient updates and proofs.
The B Merkle tree uses constant-sized internode witnesses by using vector commitments. The structure resembles a B-tree and can be updated as such.
Intranode proofs can track the ordering of the key elements and can be updated dynamically to include an ordered set of elements within each node. B-Merkle tree combines intranode proofs in a recursive manner similar in nature to Verkle tree.
Index functionality
The structure of the B-Merkle tree enables it to generate and verify witnesses to the same operations as those found in the B-tree itself. This means that it has the capacity for proofs of range, removal, along with get, and insertion of elements.
Furthermore, these proofs can be done with constant, with regards to the number of elements in the tree (as opposed to log(N)(log(M)).
- Insertion
- Get
- Removal
- Range
Comparisons
While current methods for Merkle structures have intra-node proofs that are linear in size to the branching factor of the trie itself, there are q-ary Merkle prefix trees, like the Verkle tree, that provide constant sized intranode proofs that provide constant size regardless of the branching factor. These intra-node proofs utilize mercurial commitment schemes that are positionally binding, but that are bounded in the number of elements that can be accumulated. Despite the benefit that is attained with these prefix structures, they are still implemented as tries, which means that their proof sizes are based on the size of the key, instead of the number of elements.
This results in a lower proof size for the BMT as the total number of elements increases.
Building Authenticated databases
Traditional blockchain approaches use authenticated indexes that are built on top of primitive databases, like LevelDB or RocksDB, this improves the time to a Proof-of-Concept for the data index, but it sacrifices performance by building a datastore on top of another data store, this increases the number of data accesses, and reduces the functionality of the data structure when measured against that of traditional databases.
In order to adapt to the requirements of the future, it is necessary for authenticated data structures to form the indexes the base of the next generation of decentralized databases, Since the B Merkle tree builds on the structures that are currently being used in traditional databases, it is possible to adapt current implementations of databases to incorporate the B Merkle tree.
Extensions and Benefits
With the incorporation of higher-level database logic, it is possible to utilize the B Merkle tree to its full potential. We will discuss these benefits in further detail in the next step.
- Multi-layer range proofs and High-level queries: the B Merkle tree provides efficient proofs of range, which when extended with boolean logic and set operations can provide concise proofs for high-level filters, and queries on relational data sets.
- Partitioning and Light-client: a reduction in the size of the proofs, and ease of self-balancing enable the B Merkle tree to provide an efficient light client solution for large data stores.
References
- B Merkle Tree: https://arxiv.org/pdf/2006.01994.pdf
- Verkle Tree: Verkle trees
- Vitaliks Blog on Verkle tree: https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf
