verkle-tree 0.1.0

A Rust implementation of Verkle Trees, a powerful upgrade to Merkle Trees that offers improved efficiency and reduced proof sizes. This crate provides a robust, performant, and easy-to-use library for creating, manipulating, and verifying Verkle Trees.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#[cfg(test)]
mod tests {

    use crate::VerkleTree;
    use ark_bls12_381::Fr as F;
    use rand::{prelude::SliceRandom, Rng};

    #[test]
    fn test_build_tree() {
        let (tree, _, _, _) = build_verkle_tree();
        assert!(
            tree.root_commitment().is_some(),
            "Failed building verkle tree"
        );
    }

    #[test]
    fn test_generate_proof() {
        let (tree, datas, length, width) = build_verkle_tree();
        let mut rng = rand::thread_rng();
        let ranom_index = rng.gen_range(0..=length * width);
        let random_point = datas[ranom_index];
        let proof = tree.generate_proof(ranom_index, &random_point);
        assert!(proof.is_ok(), "Proof Generation failed");
    }

    #[test]
    fn test_generate_invalid_proof() {
        let (tree, datas, length, width) = build_verkle_tree();
        let mut rng = rand::thread_rng();
        let ranom_index = rng.gen_range(0..=length * width);
        let fake_point = F::from(rng.gen_range(-100..=100));
        let proof = tree.generate_proof(ranom_index, &fake_point);
        assert!(
            proof.is_err(),
            "Should not be able to generate a valid proof"
        );
    }

    #[test]
    fn test_verify_proof() {
        let (tree, datas, length, width) = build_verkle_tree();
        let mut rng = rand::thread_rng();
        let ranom_index = rng.gen_range(0..=length * width);
        let random_point = datas[ranom_index];
        let proof = tree.generate_proof(ranom_index, &random_point).unwrap();
        let verification = tree.verify_proof(&proof);

        assert!(verification, "Given point should generate a valid proof");
    }

    #[test]
    fn test_invalid_proof_verification() {
        let (tree, _, _, _) = build_verkle_tree();
        let (invalid_tree, datas, length, width) = build_verkle_tree();
        let mut rng = rand::thread_rng();
        let ranom_index = rng.gen_range(0..=length * width);
        let random_point = datas[ranom_index];
        let proof = invalid_tree.generate_proof(ranom_index, &random_point);
        let verification = tree.verify_proof(&proof.unwrap());

        assert_eq!(verification, false, "Should not accept invalid proof");
    }

    fn build_verkle_tree() -> (VerkleTree, Vec<F>, usize, usize) {
        let mut rng = rand::thread_rng();
        let width = rng.gen_range(2..=20);
        let length = rng.gen_range(2..=20);
        println!("Generating tree with length {} and width {}", length, width);
        let datas = generate_random_vec(length * width);
        (VerkleTree::new(&datas, width).unwrap(), datas, width, length)
    }

    fn generate_random_vec(length: usize) -> Vec<F> {
        let mut rng = rand::thread_rng();
        println!("Generating vector with length: {}", length);
        (0..length)
            .map(|_| F::from(rng.gen_range(-100..=100)))
            .collect()
    }
}