Rust implementation of Verkle tree verifiable by PlonK. The circuit implementation of Verkle tree verification is here.
Original Golang implementation is in crate-crypto/go-ipa and gballet/go-verkle.
This library uses alt-BabyJubjub BN128 instead Bandersnatch as the elliptic curve for commitments.
This is not an attempt to further speed up the creation or verification of Verkle tree proofs. The project is positioned as a groundwork for constructing Verkle tree proofs verifiable by PlonK and for making verification of Layer 2 transactions more efficient.
rustup override set nightly
cargo --version # >= 1.56.0VerkleTreeWith32BytesKeyValue is the 32 bytes key-value storage with G1Affine-valued commitments.
See also sample code about how to use this library.
use franklin_crypto::bellman::bn256::G1Affine;
use verkle_tree::bn256_verkle_tree::proof::VerkleProof;
use verkle_tree::bn256_verkle_tree::VerkleTreeWith32BytesKeyValue;VerkleTreeWith32BytesKeyValue::new() returns a tree consisting of only one root node with no children.
let domain_size = 256;
let committer = IpaConfig::new(domain_size);
let mut tree = VerkleTreeWith32BytesKeyValue::new(committer);VerkleTreeWith32BytesKeyValue::insert() inserts (key, value) entry in given Verkle tree.
This method updates the entry to the new value and returns the old value,
even if the tree already has a value corresponding to the key.
let old_value: Option<[u8; 32]> = tree.insert(key, value);VerkleTreeWith32BytesKeyValue::remove() remove the entry corresponding to key in given Verkle tree.
If the tree does not have a value corresponding to the key, this method does not change the tree state.
let old_value: Option<[u8; 32]> = tree.remove(&key);VerkleTreeWith32BytesKeyValue::get() fetch the value corresponding to key in given Verkle tree.
The maximum time it takes to search entries depends on the depth of given Verkle tree.
let stored_value: Option<&[u8; 32]> = tree.get(&key);VerkleTreeWith32BytesKeyValue::compute_digest() computes the digest of given Verkle tree.
let digest: Fr = tree.compute_digest()?;VerkleProof::create() returns the inclusion/exclusion proof and its auxiliary data.
If keys includes one key, elements.zs[i] is a child index of the internal node
corresponding the key prefix of length i, and elements.ys[i] is the value of that child.
If keys includes two or more keys, compute elements.zs and elements.ys for each key,
and concatenate them.
let (proof, elements) = VerkleProof::create(&mut tree, &keys)?;
let zs = elements.zs;
let ys = elements.ys;under development
EncodedVerkleProof::encode() returns a Verkle proof in an serializable form.
It omits duplications and elements that can be calculated from other elements.
let encoded_proof = EncodedVerkleProof::encode(&proof);under development
EncodedVerkleProof::decode() returns a Verkle proof in an easy-to-calculate form.
zs and ys can be restored from proof.
let (proof, zs, ys) = encoded_proof.decode()?;VerkleProof::check() returns the validity of given inclusion/exclusion proof.
The verification does not use elements.fs, which has information on all child nodes.
let domain_size = 256;
let committer = IpaConfig::new(domain_size);
let is_valid: bool = VerkleProof::check(&proof, &zs, &ys, &committer)?;The transcript is the object storing all commitments which a prover should submits to a verifier and generating challenges (= pseudo-random variables) on behalf of the verifier. Generating challenges uses Poseidon hash function for low-cost PlonK proofs.
We choose Alt-BN128 (a.k.a. BN254) curve in our implementation for use with Ethereum Solidity. We need this elliptic curve to do the inner product proof.
A tree data structure consists of the set called nodes. Each node consist of a value and a list of reference to other nodes called children. No reference is duplicated. There is only one node in a tree that is not referenced by any other node. This is called the root.
Verkle tree is a type of prefix tree, where each node correspond to a key prefix, i.e. the first few bytes of the key, and refers to nodes corresponding to a prefix that is one character longer than its own prefix. There are two types of nodes in the case of Verkle trees: internal and leaf. Each internal node has 256 children and a digest of its subtree. Each leaf node has no children and a digest of the suffix tree, which is a data structure storing multiple entries corresponding to a key prefix.
A similar data structure is Merkle tree, but the difference between these is in the way their commitments are computed.
If you would like to know more, please refer to Vitalik Buterin's post.
Example:
cargo test -- test_encode_verkle_proof --nocapture
cat test_cases/case1/proof.json{
"multi_proof": {
"ipa": {
"l": [
"0x373ae8f856e37542cda7561dc507ddf3a7ac666fb163e908d093fda016bd328a",
"0x1d764657384e62b0e9b70d00d140cc13d885b8831355e7f3fb708f2b47be2604",
"0x47ed7f94b6263630d585b4bb8070bb066aa74e9b1ee068d28c6b0dfef61b4d01",
"0x363cf2f487193e12d57f5034b64a46dd7ce360b157b8c69cb39d5e9cde553714",
"0xcab992777bd368c4fbb0372127f623dd803bf2830d69c620a6042b153e2d9727",
"0xa9f01ce3441b121dc8bb75860eebac6a49b96001462a92a18e511c151501c6a8",
"0xaddbaffbf6a28fad5f8d050be6d884aa68705421fdd345bb83296adc5ee2d602",
"0x0d57a8821d9771380ef72b743304f3b0b960b59b7683f95a0434bf95d4cc6093"
],
"r": [
"0x2ff4547fface585e095bf1eae305fa07b5e2b6b1692d17c1d7f964b2b1794181",
"0x447165ae6c16b23540c07d3f0a93d92be37e90030c3b80e7fce16f9671890aa8",
"0x39625eb44c1b211eced15ba93f2c901eadb1a32e0b5a0d0c4987b8d7d60c9b2f",
"0x572729372ccd211f3073a3535e5c5590e38173ce0071d9ce55f67fccbedb4415",
"0x5ebcd74626a3923034ec66bd0b7f7908fb6a6ff3fb1aa9dde6273684ec13bb16",
"0x8e859d69cc0e4cb297acf8ac8b3af292d3d9e1de3ddc5734400769565ce3d088",
"0x0b474fd0dc097920ec9642f1dbcfa3f840b7da6fe25c496c05aa181fad2632aa",
"0xd8f52ca54bf344b80d7b5268b46a49fa3b633b51ed1277d49da429d4176dd41e"
],
"a": "0x1e7caca7461a0200b57594e57db4a4bc33526f80a2757a6f6d93bb2e54364059"
},
"d": "0x406cbde73c39a688977004d833d80105f19c058698f4e69c8b7427af1858e1a4"
},
"keys": [
"0xfea400000000000000000000000000000000000000000000000000000000650d",
"0x11a400000000000000000000000000000000000000000000000000000000670d",
"0xfda400000000000000000000000000000000000000000000000000000000670d",
"0xfea400000000000000000000000000000000000000000000000000000000670d",
"0xff00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
],
"values": [
"0x0000000000000000000000000000000000000000000000000000000000000000",
"0x0000000000000000000000000000000000000000000000000000000000000000",
"0x0000000000000000000000000000000000000000000000000000000000000000",
"0x8800000000000000000000000000003cc10000000000000000000000000000eb",
"0x0000000000000000000000000000000000000000000000000000000000000000"
],
"extra_data_list": [
"0x1000000000000000000000000000000000000000000000000000000000000000",
"0x1200000000000000000000000000000000000000000000000000000000000000",
"0x1300000000000000000000000000000000000000000000000000000000000000",
"0x1400000000000000000000000000000000000000000000000000000000000000",
"0x09ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
],
"commitments": [
"0x548597525b0dcb2c046411b7f4d7ce5a2f89a5c2b74fd25de157034296e30ca2",
"0x522a1a4b4989ba0d40f3087753aa85c29dce891816215036855c11b77362199c",
"0x8d6606735e3b17c30992ec1646dbe6c01e37ed37b60cedfc19cb773d1c14890a",
"0x421e3f1467b697029ce8b8ab9b50667233fa198d6df465364345b444feb12889",
"0x421e3f1467b697029ce8b8ab9b50667233fa198d6df465364345b444feb12889",
"0x9b9704755f28a84eca03566db4dbdf43f0a045e95df2fe400eee6cdcf9eaf227"
]
}NOTE: This Verkle proof has 5 keys, but a capacity of about 32 keys
(to be precise, it can contain 256 commitments before encoding).
The size of multi_proof is constant within that capacity.