Pedersen-commitment based verkle trees using the ed25519 elliptic curve.
learn about verkle trees here: https://vitalik.ca/general/2021/06/18/verkle.html
Techniques used in this software:
The verkle tree has a radix of 256. So, if there are N elements in the tree, then a proof for a single element would be log_256(N) steps long. If you are proving more than one thing, then they share steps. So if you are proving 1000 things, the proof is more like 1000*(log_256(N) - 1) steps long. For each step we need to store a 32 byte compressed elliptic curve point.
We also need to store some fixed sized data.
There are 2 different formats for the proofs. Sometimes we want the proof to be very small, and are willing to put extra effort in. In that case, we use the bullet proof method, and the extra data is only 17 elliptic curve points, each 32 bytes. So, 544 bytes total.
If we want to generate the proof very quickly, we can skip the bullet proof step, and the proof ends up being longer. It needs to have 256 finite field elements, each 32 bytes long. So, 8192 bytes total.
If the Tree has N elements, and you want to prove M of them.
Fast: 8192 + (32 * M * (log_256(N) - 1)).
Small: 544 + (32 * M * (log_256(N) - 1)).
Small proofs are usually better if we are proving many things, and fast proofs are usually better if we are proving very few things.
In the context of a blockchain, we use the fast proofs for light nodes, and the small proofs in blocks.
units are in microseconds (millionths of a second) unless otherwise specified.
finite field speed tests: fr:test(8).
(if you run this test several times, it speeds up. I think there is some caching involved.)
multiplication: 0.1
subtraction: 0.08
additions: 0.1
elliptic point multiplication speed test ed:test(6).:
for unsimplified points: 230
for simplified points: 220
chain, we use the fast proofs for light nodes, and the small proofs in blocks.
elliptic point doubling speed test ed:test(17). : 0.9
elliptic point doubling speed test ed:test(18). : 1.15
proving 3 things. test_trie:test(1).
load 10 000 elements: 2.36 seconds
make a small proof: 0.97 seconds
verify the small proof: 0.2 seconds
make a fast proof: 0.075 seconds
verify the fast proof: 0.066 seconds
Load a db with 10 000 elements, and prove 3000 of them with a small proof. test_trie:test(3).
loading the db: 6.0 seconds
making the proof: 2.1 seconds
verifying the proof: 0.55 seconds
calculating the root hash after the update: 3.3 seconds
storing the updated data in the database: 0.35 seconds
You need to install erlang first to use this database.
To run the software: start
to turn off the software, and save everything
verkle_sup:stop(ID).
where ID is the name of the database (this allows for multiple databases.)
The test database is trie01.
To create a new database.
verkle_sup:start_link(ID).
The verkle tree is a database that stores key-value pairs. Keylength is the number of bytes in a key. Size is the number of bytes in a value. ID is the id of this database, so you can have more than one of these databases at the same time.
Each element stored in the verkle tree can also store some meta data that is not a part of the consensus state.
To store data in your database. You want to store some key-value pairs. First, each key-value pair needs to be packaged into a leaf.
Leaf = leaf_verkle:new(Key, Value, Meta).
Key, Value, and Meta are binaries.
for example: Leaf = leaf_verkle:new(<<1:256>>, <<2:256>>, 0).
Once you have a list of leaves, you can store them in the database like the following:
{Loc2, _, _} = store_verkle:batch([Leaf], 1, ID).
Loc is the pointer to your current database. The number 1 is a pointer to your database when it is empty. Loc2 is a pointer to your database once it is filled with data.
Now lets make a proof of some of the data from the database.
SmallProof = get_verkle:batch([<<1:256>>], Loc2, ID, small).
Where Keys is a list of the keys of the leaves that you want to prove. This is a small proof, that means we use the bullet proof technique to compress the final size of the proof. This is what block producers do to help keep the size of blocks small. You can also make fast proofs, that are a little bigger, but much faster to create.
if you want to make the fast version of the proof:
FastProof = get_verkle:batch([<<1:256>>], Loc2, ID, fast).
Now lets verify the proofs.
{true, Leaves, _} = verify:proof(SmallProof, CFG).
{true, Leaves, _} = verify:proof(FastProof, CFG).
When you verify the proof, it returns a list of all the leaves that this proof proves.
To do integration tests: test_verkle:test().
There is a benchmark tool: benchmark:doit().
The cryptography stuff is tested with: crypto_tests:doit(0).
Many modules have their own unit tests. They are located at the bottom of the page in the same module that they are testing.
Here is a calculator to get an idea for how much it should cost to do different things with the verkle tree and libraries.
https://docs.google.com/spreadsheets/d/1740XUDJ89aSRE-4HBD44brjGake_MRAqC4YF7YcEScE/edit
inner product argument bullet proofs: https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html
polynomial multiproofs: https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html
Ed25519 https://en.wikipedia.org/wiki/EdDSA#Ed25519
It is defined like this.
The prime for the finite field: q = 2^255 - 19
Curve equation: -x^2 + y^2 = 1 - ((121665/121666) * x^2 * y^2 )
These are the algorithms we can use for operations on the elliptic curve: http://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
ed25519 elliptic curve algorithms for elliptic curve operations in C.
multi exponentiation with bucket method. precomputed multi exponentiation with bucket method.
bulletproofs inner product using pedersen commitments. polynomials in evaluation format. polynomials multiproofs.