Applications of Data Structures in real world

Published in

The Symposium

4 min readJul 21, 2021

By Tisha Chawla & Shubh Mittal

Supply chain management was virtually unknown a decade back, yet today it attracts the attention of senior-level managers across a broad spectrum of companies and industries. Over the years it has evolved to maximize service for all the involved nodes while effectively minimizing system huge costs. The idea that has driven this concept is inventory optimization and network. Supply chains are increasingly dependent on the efficient movement and analysis of immense amounts of data. The complexity involved in managing that data can be staggering. As a result, more and more companies are turning to an efficient data structure.

Verkle Trees

Verkle Trees, a data structure combines the advantages of trees and cryptographic accumulators.

Verkle Tree is a bandwidth-efficient alternative to Merkle Trees that uses Vector Commitments rather than cryptographic hash functions.

In the Merkle tree, every external node is labeled with the cryptographic hash of a data block, and every internal node is labeled with the cryptographic hash of the labels of its successor nodes. This data structure with branching factor k achieves O(kn) construction time and O(log k n) membership proof-size. This means that the branching factor, k, offers a tradeoff between computational power and bandwidth. The depth of the tree is independent of the reduction time and depends only on the branching factor. Better vector commitments change this equation, each level only needs a constant size proof, so the extra factor of d-1 disappears.

Methods

The aim is to see the efficacy of a new data structure, Verkle Trees, which decreases the bandwidth required for Merkle Trees.

Using elliptic curves and polynomial math to create a data structure where the inclusion of any k of n values can be proven with a single (~48 byte) witness. The primary objective is to reduce the membership proof size. This will increase the computational power required to update a Merkle Tree relative to that required to compute and update a Merkle Tree. The Verkle Tree is a k-ary tree, where k is the branching factor of the tree. The branching factor, k, determines the proper gap between computational power and bandwidth that a k-ary Verkle Tree provides us.

It is followed by computing Vector Commitments up the tree over previously computed commitments until the computation of the root commitment.

A Verkle Tree with K=3

An Algorithmic Approach to Verkle Trees

Assuming that key and value are known (they need to be provided in any witness scheme), then for every inner node that the key path crosses, incorporate the commitment to that node to the proof. For instance, let’s assume we want to prove the leaf 0101 0101 1010 1111 -> 1213, then we have to give the commitment to Node A and Node B, as the path goes through these nodes. We don’t have to give the Root itself because it is known to the verifier.

Then adding a proof for each internal node, that proves that the hash of the child is a correct reveal of the commitment. So the proofs in this example would consist of three evaluation proofs:

Proof that the hash of key and value of the node 0101 0101 1010 1111 -> 1213 is the evaluation of the commitment of Internal node B at the index 1010
Proof that the root of Internal node B is the evaluation of the commitment of Internal node A at the index 0111
Proof that the root of Internal node A is the evaluation of the Root commitment at the index 0101

Here KZG proofs can be compressed using different schemes to a small constant size, so given any number of inner nodes, the proof can be done using a small number of bytes. Even better, given any number of leaves to prove, one only needs this small size proof to prove them together.

Results

Merkle Trees, which are exceptionally fast and can be computed in O(n) time. Unfortunately, their proof size of O(log2 n) is very huge and can be costly in terms of bandwidth.

Due to this disadvantage, we briefly turned to k-ary trees, but their proofs are actually even larger than Merkle Trees, O(k logk n). Vector Commitment Schemes decrease the proof size down to a constant, O(1), but this comes at the cost of O(n² ) computation to construct the Vector Commitment, which is too expensive. However, The k-ary Verkle Tree takes only O(kn) time to construct. Moreover, its proof size is only O(log k n), a factor of O(log2k) times lesser than the Merkle Tree’s membership proofs. This is an advantage as it allows the reduction of bandwidth at an unreasonable increase in computational power. We know that bandwidth is cheaper than computational power. If we set k = 512, we achieve a 9 times reduction in proof size, and thus bandwidth, at the cost of a 512 increase in computational power. If less computational power is desired, k can be decreased. The value of k varies depending on the environment-specific optimization between bandwidths.

In Conclusion, Verkle Trees are a potential replacement for Merkle Trees for many applications. Due to the variable branching factor, k, Verkle Trees can be adapted to satisfy different criteria. In the future, Verkle Trees will be further optimized by implementing them in parallel.

Applications of Data Structures in real world

Verkle Trees

Methods

An Algorithmic Approach to Verkle Trees

Results

References

Written by CollabProject