smtree 0.1.2

SMTree is a flexible sparse tree accumulator that can support various tree types via traits for custom node-merging (i.e., Merkle tree hashes) and tree-padding logic. The api supports single and batch inclusion proofs and random sampling.
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

// Copyright (c) Facebook, Inc. and its affiliates.
//
// This source code is licensed under the MIT license found in the
// LICENSE file in the root directory of this source tree.

use std::cmp::Eq;
use std::collections::HashSet;
use std::fmt::Debug;
use std::time::Instant;

use criterion::{criterion_group, criterion_main, Criterion};

use smtree::pad_secret::ALL_ZEROS_SECRET;
use smtree::{
    index::TreeIndex,
    node_template::{HashNodeSmt, SumNodeSmt},
    traits::{Mergeable, Paddable, ProofExtractable, Rand, Serializable, TypeName},
    tree::SparseMerkleTree,
};

type SMT<P> = SparseMerkleTree<P>;

type List<P> = Vec<(TreeIndex, P)>;

pub fn bench_build<
    P: 'static + Mergeable + Paddable + ProofExtractable + Rand + TypeName + Clone + Default + Eq,
>(
    c: &mut Criterion,
) where
    <P as ProofExtractable>::ProofNode: Debug + Clone + Default + Eq + Mergeable + Serializable,
{
    let name = P::get_name();
    const LEAF_NUM: u64 = 1_000_000;
    const TREE_HEIGHT: usize = 256;
    c.bench_function(
        &format!(
            "Build SMT({}) from {} leaves of {}",
            TREE_HEIGHT, LEAF_NUM, name
        ),
        |b| {
            b.iter(|| {
                println!("Start!");
                let time = Instant::now();
                let mut list: List<P> = Vec::new();
                let mut set: HashSet<TreeIndex> = HashSet::new();
                let mut sum = P::default();
                for _i in 0..LEAF_NUM {
                    sum.randomize();
                    loop {
                        let mut idx = TreeIndex::zero(TREE_HEIGHT);
                        idx.randomize();
                        if !set.contains(&idx) {
                            list.push((idx, sum.clone()));
                            set.insert(idx);
                            break;
                        }
                    }
                }
                println!("Finish in {:?} ms", time.elapsed().as_millis());
                println!("Start!");
                let time = Instant::now();
                let mut tree = SMT::new(TREE_HEIGHT);
                tree.build(&list, &ALL_ZEROS_SECRET);
                println!("Finish in {:?} ms", time.elapsed().as_millis());
            })
        },
    );
}

pub fn bench_update<
    P: 'static + Mergeable + Paddable + ProofExtractable + Rand + TypeName + Clone + Default,
>(
    c: &mut Criterion,
) where
    <P as ProofExtractable>::ProofNode: Debug + Clone + Default + Eq + Mergeable + Serializable,
{
    const LEAF_NUM: u64 = 1_000_000;
    const TREE_HEIGHT: usize = 32;
    let name = P::get_name();
    c.bench_function(
        &format!(
            "Build SMT({}) from {} leaves of {} by updating each leaf",
            TREE_HEIGHT, LEAF_NUM, name
        ),
        |b| {
            b.iter(|| {
                println!("Start!");
                let time = Instant::now();
                let mut list: List<P> = Vec::new();
                let mut set: HashSet<TreeIndex> = HashSet::new();
                let mut sum = P::default();
                for _i in 0..LEAF_NUM {
                    sum.randomize();
                    loop {
                        let mut idx = TreeIndex::zero(TREE_HEIGHT);
                        idx.randomize();
                        if !set.contains(&idx) {
                            list.push((idx, sum.clone()));
                            set.insert(idx);
                            break;
                        }
                    }
                }
                println!("Finish in {:?} ms", time.elapsed().as_millis());
                println!("Start!");
                let time = Instant::now();
                let mut tree = SMT::new(TREE_HEIGHT);
                for item in list.iter() {
                    tree.update(&item.0, item.1.clone(), &ALL_ZEROS_SECRET);
                }
                println!("Finish in {:?} ms", time.elapsed().as_millis());
            })
        },
    );
}

criterion_group! {
    name = benches;
    config = Criterion::default().sample_size(10);
    targets =
              bench_build<SumNodeSmt>,
              bench_build<HashNodeSmt::<blake3::Hasher>>,
              bench_build<HashNodeSmt<blake2::Blake2b>>,
              bench_build<HashNodeSmt<sha2::Sha256>>,
              bench_build<HashNodeSmt<sha3::Sha3_256>>
}
criterion_main!(benches);