merkle_tree.rs
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_network::{ 20 MainnetV0, 21 Network, 22 prelude::{TestRng, ToBits, Uniform}, 23 }; 24 use alphavm_console_types::Field; 25 26 use criterion::{BatchSize, BenchmarkId, Criterion}; 27 use std::collections::BTreeMap; 28 29 const DEPTH: u8 = 32; 30 const MAX_INSTANTIATED_DEPTH: u8 = 16; 31 32 const NUM_LEAVES: &[usize] = &[1, 10, 100, 1_000, 10_000, 100_000]; 33 const APPEND_SIZES: &[usize] = &[1, 10, 100, 1_000, 10_000, 100_000]; 34 const UPDATE_SIZES: &[usize] = &[1, 10, 100, 1_000, 10_000]; 35 36 /// Generates the specified number of random Merkle tree leaves. 37 macro_rules! generate_leaves { 38 ($num_leaves:expr, $rng:expr) => {{ (0..$num_leaves).map(|_| Field::<MainnetV0>::rand($rng).to_bits_le()).collect::<Vec<_>>() }}; 39 } 40 41 fn new(c: &mut Criterion) { 42 let mut rng = TestRng::default(); 43 // Accumulate leaves in a vector to avoid recomputing across iterations. 44 let leaves = generate_leaves!(*NUM_LEAVES.last().unwrap(), &mut rng); 45 for num_leaves in NUM_LEAVES { 46 // Benchmark the creation of a Merkle tree with the specified number of leaves. 47 c.bench_function(&format!("MerkleTree/new/{num_leaves}"), |b| { 48 b.iter(|| { 49 let _tree = MainnetV0::merkle_tree_bhp::<DEPTH>(&leaves[0..*num_leaves]).unwrap(); 50 }) 51 }); 52 } 53 } 54 55 fn append(c: &mut Criterion) { 56 let mut rng = TestRng::default(); 57 // Accumulate all leaves in a vector to avoid recomputing across iterations. 58 let leaves = generate_leaves!(*NUM_LEAVES.last().unwrap(), &mut rng); 59 // Generate all of the leaves that will be appended to the tree. 60 let new_leaves = generate_leaves!(*APPEND_SIZES.last().unwrap(), &mut rng); 61 // For each number of leaves to append, benchmark the append operation. 62 for num_leaves in NUM_LEAVES { 63 for num_new_leaves in APPEND_SIZES { 64 // Construct a Merkle tree with the specified number of leaves. 65 let merkle_tree = MainnetV0::merkle_tree_bhp::<DEPTH>(&leaves[..*num_leaves]).unwrap(); 66 c.bench_function(&format!("MerkleTree/append/{num_leaves}/{num_new_leaves}"), |b| { 67 b.iter_batched( 68 || merkle_tree.clone(), 69 |mut merkle_tree| { 70 merkle_tree.append(&new_leaves[..*num_new_leaves]).unwrap(); 71 }, 72 BatchSize::SmallInput, 73 ) 74 }); 75 } 76 } 77 } 78 79 fn update(c: &mut Criterion) { 80 let mut rng = TestRng::default(); 81 // Accumulate leaves in a vector to avoid recomputing across iterations. 82 let leaves = generate_leaves!(*NUM_LEAVES.last().unwrap(), &mut rng); 83 // For each number of leaves to update, benchmark the update operation. 84 for num_leaves in NUM_LEAVES { 85 // Construct a vector of (index, new_leaf) pairs to update the tree with. 86 // Note that we need to bound the number of updates since a large number of sequential singular updates to exceedingly long. 87 let updates = generate_leaves!(std::cmp::min(*UPDATE_SIZES.last().unwrap(), 10_000), &mut rng) 88 .into_iter() 89 .map(|leaf| { 90 let index: usize = Uniform::rand(&mut rng); 91 (index % num_leaves, leaf) 92 }) 93 .collect::<Vec<_>>(); 94 95 for num_new_leaves in UPDATE_SIZES { 96 // Construct a Merkle tree with the specified number of leaves. 97 let merkle_tree = MainnetV0::merkle_tree_bhp::<DEPTH>(&leaves[..*num_leaves]).unwrap(); 98 99 c.bench_function(&format!("MerkleTree/update/{num_leaves}/{num_new_leaves}"), |b| { 100 b.iter_batched( 101 || merkle_tree.clone(), 102 |mut merkle_tree| { 103 for (index, new_leaf) in updates.iter().take(*num_new_leaves) { 104 merkle_tree.update(*index, new_leaf).unwrap(); 105 } 106 }, 107 BatchSize::SmallInput, 108 ) 109 }); 110 } 111 } 112 } 113 114 fn update_many(c: &mut Criterion) { 115 let mut rng = TestRng::default(); 116 // Accumulate leaves in a vector to avoid recomputing across iterations. 117 let leaves = generate_leaves!(*NUM_LEAVES.last().unwrap(), &mut rng); 118 // For each number of leaves to update, benchmark the update operation. 119 for num_leaves in NUM_LEAVES { 120 // Generate all of the updates that will be applied to the tree. 121 // Note that we generate 2 * MAX_UPDATE_SIZE leaves to increase the number of unique of updates. 122 let mut updates = generate_leaves!(2 * *UPDATE_SIZES.last().unwrap(), &mut rng) 123 .into_iter() 124 .map(|leaf| { 125 let index: usize = Uniform::rand(&mut rng); 126 (index % num_leaves, leaf) 127 }) 128 .collect::<Vec<_>>(); 129 updates.sort_by_key(|(a, _)| *a); 130 updates.reverse(); 131 updates.dedup_by_key(|(a, _)| *a); 132 133 for num_new_leaves in UPDATE_SIZES { 134 // Construct a Merkle tree with the specified number of leaves. 135 let merkle_tree = MainnetV0::merkle_tree_bhp::<DEPTH>(&leaves[..*num_leaves]).unwrap(); 136 let num_new_leaves = std::cmp::min(*num_new_leaves, updates.len()); 137 let updates = BTreeMap::from_iter(updates[..num_new_leaves].iter().cloned()); 138 c.bench_function(&format!("MerkleTree/update_many/{num_leaves}/{num_new_leaves}",), |b| { 139 b.iter_batched( 140 || merkle_tree.clone(), 141 |mut merkle_tree| { 142 merkle_tree.update_many(&updates).unwrap(); 143 }, 144 BatchSize::SmallInput, 145 ) 146 }); 147 } 148 } 149 } 150 151 fn update_vs_update_many(c: &mut Criterion) { 152 let mut group = c.benchmark_group("UpdateVSUpdateMany"); 153 let mut rng = TestRng::default(); 154 // Accumulate leaves in a vector to avoid recomputing across iterations. 155 let max_leaves = 2usize.saturating_pow(MAX_INSTANTIATED_DEPTH as u32); 156 let leaves = generate_leaves!(max_leaves, &mut rng); 157 for depth in 1..=MAX_INSTANTIATED_DEPTH { 158 // Compute the number of leaves at this depth. 159 let num_leaves = 2usize.saturating_pow(depth as u32); 160 // Construct a Merkle tree with the specified number of leaves. 161 let tree = MainnetV0::merkle_tree_bhp::<DEPTH>(&leaves[..num_leaves]).unwrap(); 162 // Generate a new leaf and select a random index to update. 163 let index: usize = Uniform::rand(&mut rng); 164 let index = index % num_leaves; 165 let new_leaf = generate_leaves!(1, &mut rng).pop().unwrap(); 166 // Benchmark the standard update operation. 167 group.bench_with_input(BenchmarkId::new("Single", format!("{depth}")), &new_leaf, |b, new_leaf| { 168 b.iter_batched(|| tree.clone(), |mut tree| tree.update(index, new_leaf), BatchSize::SmallInput) 169 }); 170 // Benchmark the `update_many` operation. 171 group.bench_with_input( 172 BenchmarkId::new("Batch", format!("{depth}")), 173 &BTreeMap::from([(index, new_leaf)]), 174 |b, updates| b.iter_batched(|| tree.clone(), |mut tree| tree.update_many(updates), BatchSize::SmallInput), 175 ); 176 } 177 } 178 179 criterion_group! { 180 name = merkle_tree; 181 config = Criterion::default().sample_size(10); 182 targets = new, append, update, update_many, update_vs_update_many 183 } 184 criterion_main!(merkle_tree);