blockscout-verkle-tree

Module for visualizing Verkle tree proofs

Usage

cargo run --release

Service contains only one route: GET /blocks/{block_number}

• Service send a svg-image of verkle tree by block_number in condriua test-net

Theory

Verkle trie is quite similar to Modified Merkle Patricia Trie. To understand how this data structure works, let's look at each modification separately.

Merkle Tree

The binary tree that is used like hash function for any split data.
Recursively taking the hash function and concatenating, we get the Top Hash, which serves as a digital signature of the data.

The Merkle Proof requires storing a path for each leaf. This proof is used in Bitcoin blockchain (merkle_root in the header). But there is the main Merkle tree traversal problem: it is too expensive to store all the auth-paths in memory.

Wiki_ru. Algorithm complexity: O(ln(N)) (proof).

Trie

This is k-ary search tree. Also called prefix-tree for strings.

*Example for set of words: "A", "to", "tea", "ted", "ten", "i", "in", and "inn".inside *

Sample of Node struct:

template <class T>
class className {
    Node children[ALPHABET_SIZE];
    bool is_terminal;
    T value;
};

Algorithm complexity: O(N²) : create; O(m) : find, where m - lenght of word;

Patricia trie

This is a prefix tree in which prefixes are binary — that is, each key node stores information about one bit. In Ethereum the transition takes place according to the heximal number system (wich called nibble).

Modified Merkle Patricia Trie

Here it is. The main features that distinguish Ethereum from Bitcoin are implemented by realization of this data structure.
Modified Merkle Patricia Trie (MPT) provides opportunities to store account statuses, smart-contracts and almost anything dynamically stored data inside the blockchain.
There are a lot of optimizations which currently Ethereum use, I'll keep it out in context of this README.
You can find Ethereum docs about MPT here.
In short, we combine everything that we talked about above.
We dynamically store the key-value, and verify their authenticity with a digital signature at the root (as Merkle Tree).
Asymptotics of methods like in prefix tree. There are a few difficult parts in realization, but not critical (article with realization).

Verkle Tree

I find Vitalik 's article great for beginning.
Verkle Trees are very similar to Modified Merkle Patricia Trie. The main difference is complexity of cryptographic part.

There are the same constuction of tree: a leaf nodes with key-value, intermediate nodes with width number of children (in MPT is constantly 16). The main idea of creating this data structure is reduce the size of all data. Let's take a look at some pictures:

Nothing new for us yet, but let's see what will Merkle tree require for a single proof.

That's a lot of nodes! Meanwhile Verkle Tree require only 3 (!) nodes.

That's impressive! So, how it works?

Merkle tree and Merkle proof is algorithm that we can relate to vector commitment. And not to go into the depths of group theory, we can assume this is one of the easiest one. In turn, Verkle Tree use polynomial commitment.

Polynomial commitments let you hash a polynomial, and make a proof for the evaluation of the hashed polynomial at any point.

There are two the easiest polynomial commitment schemes: KZG commitmens, bulletproof-style commitments.

Using these schemes already have a big win, but the math we use here provide us opportunity to merge different proofs (like on the last picture).

Time Complexities (from this paper)

k here - is width. Because Verkle Tree doesn't have multiplier width - 1 while proof (we don't have to get sisters), proof will be much better.

Usefull links

I consider there's no point in implementation of verkle tree (i found it).
So, if someone comes back here in the future, I'll leave a bunch of links here, which helped me a lot.

links	description
crate-crypto/rust-verkle	Implementation of verkle tree in rust (special crate)
gballet/verkle-block-sample	Example of verklee proof in rust
condrieu	Testnet with usage of verkle tree
gballet/go-verkle	Test client of verkle tree in go
Ethereum Meeting	recording a meeting, where Vitalik talks about verkle tree (beginning)
Guillaume Ballet on ETH PRAGUE 2020	Speech by Guillaume Ballet about transition to verkle-networks
eth research	KZG commitments research
MIT paper	Intro-paper to verkle trees (beginning)
Vitalik's paper	Post a bit harder than previous (beginning)
verkle-trie-for-eth1	Post to read (beginning)
KZG commitments	Post about Kate commitments (some math)
Math	Elliptic Curve usage
@vbuterin/verkle_tree_eip	Post about work and influence of verkle tree