1  // Copyright (c) 2019-2025 Alpha-Delta Network Inc.
 2  // This file is part of the alphavm library.
 3  
 4  // Licensed under the Apache License, Version 2.0 (the "License");
 5  // you may not use this file except in compliance with the License.
 6  // You may obtain a copy of the License at:
 7  
 8  // http://www.apache.org/licenses/LICENSE-2.0
 9  
10  // Unless required by applicable law or agreed to in writing, software
11  // distributed under the License is distributed on an "AS IS" BASIS,
12  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  // See the License for the specific language governing permissions and
14  // limitations under the License.
15  
16  #[macro_use]
17  extern crate criterion;
18  
19  use alphavm_console_algorithms::Sha3_256;
20  use alphavm_console_collections::kary_merkle_tree::KaryMerkleTree;
21  use alphavm_console_network::{
22      MainnetV0,
23      prelude::{TestRng, ToBits, Uniform},
24  };
25  use alphavm_console_types::Field;
26  
27  use criterion::Criterion;
28  
29  const DEPTH: u8 = 8;
30  const ARITY: u8 = 8;
31  
32  /// Generates the specified number of random Merkle tree leaves.
33  macro_rules! generate_leaves {
34      ($num_leaves:expr, $rng:expr) => {{ (0..$num_leaves).map(|_| Field::<MainnetV0>::rand($rng).to_bits_le()).collect::<Vec<_>>() }};
35  }
36  
37  fn new(c: &mut Criterion) {
38      let mut rng = TestRng::default();
39  
40      // Initialize the hashers.
41      let path_hasher = Sha3_256::default();
42      let leaf_hasher = Sha3_256::default();
43  
44      // Determine the number of leaves to benchmark.
45      let max_num_leaves = (ARITY as u32).pow(DEPTH as u32);
46      const RATIO: u32 = 4;
47  
48      // Accumulate leaves in a vector to avoid recomputing across iterations.
49      let leaves = generate_leaves!(max_num_leaves, &mut rng);
50      for ratio in 0..=RATIO {
51          let num_leaves = max_num_leaves * ratio / 4;
52          // Benchmark the creation of a KaryMerkle tree with the specified number of leaves.
53          c.bench_function(&format!("KaryMerkleTree/new/{num_leaves} ({}% full)", ratio as f64 * 100f64 / 4f64), |b| {
54              b.iter(|| {
55                  let _tree = KaryMerkleTree::<_, _, DEPTH, ARITY>::new(
56                      &leaf_hasher,
57                      &path_hasher,
58                      &leaves[0..num_leaves as usize],
59                  )
60                  .unwrap();
61              })
62          });
63      }
64  }
65  
66  fn verify(c: &mut Criterion) {
67      let mut rng = TestRng::default();
68  
69      // Initialize the hashers.
70      let path_hasher = Sha3_256::default();
71      let leaf_hasher = Sha3_256::default();
72  
73      // Determine the maximum number of leaves.
74      let max_num_leaves = (ARITY as u32).pow(DEPTH as u32);
75      // Initialize the leaves.
76      let leaves = generate_leaves!(max_num_leaves, &mut rng);
77  
78      // Initialize the tree.
79      let tree = KaryMerkleTree::<_, _, DEPTH, ARITY>::new(&leaf_hasher, &path_hasher, &leaves).unwrap();
80      let proof = tree.prove(0, &leaves[0]).unwrap();
81  
82      // Benchmark the verification a KaryMerkle tree proof.
83      c.bench_function("KaryMerkleTree/verify", |b| {
84          b.iter(|| {
85              assert!(proof.verify(&leaf_hasher, &path_hasher, tree.root(), &leaves[0]));
86          })
87      });
88  }
89  
90  criterion_group! {
91      name = kary_merkle_tree;
92      config = Criterion::default().sample_size(10);
93      targets = new, verify
94  }
95  criterion_main!(kary_merkle_tree);