1use std::time::Instant;
  2
  3use clap::Parser;
  4use miden_crypto::{
  5    hash::rpo::{Rpo256, RpoDigest},
  6    merkle::{MerkleError, Smt},
  7    Felt, Word, ONE,
  8};
  9use rand_utils::rand_value;
 10
 11#[derive(Parser, Debug)]
 12#[clap(name = "Benchmark", about = "SMT benchmark", version, rename_all = "kebab-case")]
 13pub struct BenchmarkCmd {
 14    /// Size of the tree
 15    #[clap(short = 's', long = "size")]
 16    size: u64,
 17}
 18
 19fn main() {
 20    benchmark_smt();
 21}
 22
 23/// Run a benchmark for [`Smt`].
 24pub fn benchmark_smt() {
 25    let args = BenchmarkCmd::parse();
 26    let tree_size = args.size;
 27
 28    // prepare the `leaves` vector for tree creation
 29    let mut entries = Vec::new();
 30    for i in 0..tree_size {
 31        let key = rand_value::<RpoDigest>();
 32        let value = [ONE, ONE, ONE, Felt::new(i)];
 33        entries.push((key, value));
 34    }
 35
 36    let mut tree = construction(entries, tree_size).unwrap();
 37    insertion(&mut tree, tree_size).unwrap();
 38    proof_generation(&mut tree, tree_size).unwrap();
 39}
 40
 41/// Runs the construction benchmark for [`Smt`], returning the constructed tree.
 42pub fn construction(entries: Vec<(RpoDigest, Word)>, size: u64) -> Result<Smt, MerkleError> {
 43    println!("Running a construction benchmark:");
 44    let now = Instant::now();
 45    let tree = Smt::with_entries(entries)?;
 46    let elapsed = now.elapsed();
 47    println!(
 48        "Constructed a SMT with {} key-value pairs in {:.3} seconds",
 49        size,
 50        elapsed.as_secs_f32(),
 51    );
 52
 53    println!("Number of leaf nodes: {}\n", tree.leaves().count());
 54
 55    Ok(tree)
 56}
 57
 58/// Runs the insertion benchmark for the [`Smt`].
 59pub fn insertion(tree: &mut Smt, size: u64) -> Result<(), MerkleError> {
 60    println!("Running an insertion benchmark:");
 61
 62    let mut insertion_times = Vec::new();
 63
 64    for i in 0..20 {
 65        let test_key = Rpo256::hash(&rand_value::<u64>().to_be_bytes());
 66        let test_value = [ONE, ONE, ONE, Felt::new(size + i)];
 67
 68        let now = Instant::now();
 69        tree.insert(test_key, test_value);
 70        let elapsed = now.elapsed();
 71        insertion_times.push(elapsed.as_secs_f32());
 72    }
 73
 74    println!(
 75        "An average insertion time measured by 20 inserts into a SMT with {} key-value pairs is {:.3} milliseconds\n",
 76        size,
 77        // calculate the average by dividing by 20 and convert to milliseconds by multiplying by
 78        // 1000. As a result, we can only multiply by 50
 79        insertion_times.iter().sum::<f32>() * 50f32,
 80    );
 81
 82    Ok(())
 83}
 84
 85/// Runs the proof generation benchmark for the [`Smt`].
 86pub fn proof_generation(tree: &mut Smt, size: u64) -> Result<(), MerkleError> {
 87    println!("Running a proof generation benchmark:");
 88
 89    let mut insertion_times = Vec::new();
 90
 91    for i in 0..20 {
 92        let test_key = Rpo256::hash(&rand_value::<u64>().to_be_bytes());
 93        let test_value = [ONE, ONE, ONE, Felt::new(size + i)];
 94        tree.insert(test_key, test_value);
 95
 96        let now = Instant::now();
 97        let _proof = tree.open(&test_key);
 98        let elapsed = now.elapsed();
 99        insertion_times.push(elapsed.as_secs_f32());
100    }
101
102    println!(
103        "An average proving time measured by 20 value proofs in a SMT with {} key-value pairs in {:.3} microseconds",
104        size,
105        // calculate the average by dividing by 20 and convert to microseconds by multiplying by
106        // 1000000. As a result, we can only multiply by 50000
107        insertion_times.iter().sum::<f32>() * 50000f32,
108    );
109
110    Ok(())
111}