miden-crypto/benches/store.rs
benches/store.rsRaw
1use criterion::{black_box, criterion_group, criterion_main, BatchSize, BenchmarkId, Criterion};
2use miden_crypto::merkle::{MerkleStore, MerkleTree, NodeIndex, SimpleSmt};
3use miden_crypto::Word;
4use miden_crypto::{hash::rpo::RpoDigest, Felt};
5use rand_utils::{rand_array, rand_value};
6
7/// Since MerkleTree can only be created when a power-of-two number of elements is used, the sample
8/// sizes are limited to that.
9static BATCH_SIZES: [usize; 3] = [2usize.pow(4), 2usize.pow(7), 2usize.pow(10)];
10
11/// Generates a random `RpoDigest`.
12fn random_rpo_digest() -> RpoDigest {
13 rand_array::<Felt, 4>().into()
14}
15
16/// Generates a random `Word`.
17fn random_word() -> Word {
18 rand_array::<Felt, 4>().into()
19}
20
21/// Generates an index at the specified depth in `0..range`.
22fn random_index(range: u64, depth: u8) -> NodeIndex {
23 let value = rand_value::<u64>() % range;
24 NodeIndex::new(depth, value).unwrap()
25}
26
27/// Benchmarks getting an empty leaf from the SMT and MerkleStore backends.
28fn get_empty_leaf_simplesmt(c: &mut Criterion) {
29 let mut group = c.benchmark_group("get_empty_leaf_simplesmt");
30
31 let depth = SimpleSmt::MAX_DEPTH;
32 let size = u64::MAX;
33
34 // both SMT and the store are pre-populated with empty hashes, accessing these values is what is
35 // being benchmarked here, so no values are inserted into the backends
36 let smt = SimpleSmt::new(depth).unwrap();
37 let store = MerkleStore::from(&smt);
38 let root = smt.root();
39
40 group.bench_function(BenchmarkId::new("SimpleSmt", depth), |b| {
41 b.iter_batched(
42 || random_index(size, depth),
43 |index| black_box(smt.get_node(index)),
44 BatchSize::SmallInput,
45 )
46 });
47
48 group.bench_function(BenchmarkId::new("MerkleStore", depth), |b| {
49 b.iter_batched(
50 || random_index(size, depth),
51 |index| black_box(store.get_node(root, index)),
52 BatchSize::SmallInput,
53 )
54 });
55}
56
57/// Benchmarks getting a leaf on Merkle trees and Merkle stores of varying power-of-two sizes.
58fn get_leaf_merkletree(c: &mut Criterion) {
59 let mut group = c.benchmark_group("get_leaf_merkletree");
60
61 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
62 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
63
64 for size in BATCH_SIZES {
65 let leaves = &random_data[..size];
66
67 let mtree_leaves: Vec<Word> = leaves.iter().map(|v| v.into()).collect();
68 let mtree = MerkleTree::new(mtree_leaves.clone()).unwrap();
69 let store = MerkleStore::from(&mtree);
70 let depth = mtree.depth();
71 let root = mtree.root();
72 let size_u64 = size as u64;
73
74 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
75 b.iter_batched(
76 || random_index(size_u64, depth),
77 |index| black_box(mtree.get_node(index)),
78 BatchSize::SmallInput,
79 )
80 });
81
82 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
83 b.iter_batched(
84 || random_index(size_u64, depth),
85 |index| black_box(store.get_node(root, index)),
86 BatchSize::SmallInput,
87 )
88 });
89 }
90}
91
92/// Benchmarks getting a leaf on SMT and Merkle stores of varying power-of-two sizes.
93fn get_leaf_simplesmt(c: &mut Criterion) {
94 let mut group = c.benchmark_group("get_leaf_simplesmt");
95
96 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
97 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
98
99 for size in BATCH_SIZES {
100 let leaves = &random_data[..size];
101
102 let smt_leaves = leaves
103 .iter()
104 .enumerate()
105 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
106 .collect::<Vec<(u64, Word)>>();
107 let smt = SimpleSmt::with_leaves(SimpleSmt::MAX_DEPTH, smt_leaves.clone()).unwrap();
108 let store = MerkleStore::from(&smt);
109 let depth = smt.depth();
110 let root = smt.root();
111 let size_u64 = size as u64;
112
113 group.bench_function(BenchmarkId::new("SimpleSmt", size), |b| {
114 b.iter_batched(
115 || random_index(size_u64, depth),
116 |index| black_box(smt.get_node(index)),
117 BatchSize::SmallInput,
118 )
119 });
120
121 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
122 b.iter_batched(
123 || random_index(size_u64, depth),
124 |index| black_box(store.get_node(root, index)),
125 BatchSize::SmallInput,
126 )
127 });
128 }
129}
130
131/// Benchmarks getting a node at half of the depth of an empty SMT and an empty Merkle store.
132fn get_node_of_empty_simplesmt(c: &mut Criterion) {
133 let mut group = c.benchmark_group("get_node_of_empty_simplesmt");
134
135 let depth = SimpleSmt::MAX_DEPTH;
136
137 // both SMT and the store are pre-populated with the empty hashes, accessing the internal nodes
138 // of these values is what is being benchmarked here, so no values are inserted into the
139 // backends.
140 let smt = SimpleSmt::new(depth).unwrap();
141 let store = MerkleStore::from(&smt);
142 let root = smt.root();
143 let half_depth = depth / 2;
144 let half_size = 2_u64.pow(half_depth as u32);
145
146 group.bench_function(BenchmarkId::new("SimpleSmt", depth), |b| {
147 b.iter_batched(
148 || random_index(half_size, half_depth),
149 |index| black_box(smt.get_node(index)),
150 BatchSize::SmallInput,
151 )
152 });
153
154 group.bench_function(BenchmarkId::new("MerkleStore", depth), |b| {
155 b.iter_batched(
156 || random_index(half_size, half_depth),
157 |index| black_box(store.get_node(root, index)),
158 BatchSize::SmallInput,
159 )
160 });
161}
162
163/// Benchmarks getting a node at half of the depth of a Merkle tree and Merkle store of varying
164/// power-of-two sizes.
165fn get_node_merkletree(c: &mut Criterion) {
166 let mut group = c.benchmark_group("get_node_merkletree");
167
168 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
169 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
170
171 for size in BATCH_SIZES {
172 let leaves = &random_data[..size];
173
174 let mtree_leaves: Vec<Word> = leaves.iter().map(|v| v.into()).collect();
175 let mtree = MerkleTree::new(mtree_leaves.clone()).unwrap();
176 let store = MerkleStore::from(&mtree);
177 let root = mtree.root();
178 let half_depth = mtree.depth() / 2;
179 let half_size = 2_u64.pow(half_depth as u32);
180
181 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
182 b.iter_batched(
183 || random_index(half_size, half_depth),
184 |index| black_box(mtree.get_node(index)),
185 BatchSize::SmallInput,
186 )
187 });
188
189 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
190 b.iter_batched(
191 || random_index(half_size, half_depth),
192 |index| black_box(store.get_node(root, index)),
193 BatchSize::SmallInput,
194 )
195 });
196 }
197}
198
199/// Benchmarks getting a node at half the depth on SMT and Merkle stores of varying power-of-two
200/// sizes.
201fn get_node_simplesmt(c: &mut Criterion) {
202 let mut group = c.benchmark_group("get_node_simplesmt");
203
204 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
205 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
206
207 for size in BATCH_SIZES {
208 let leaves = &random_data[..size];
209
210 let smt_leaves = leaves
211 .iter()
212 .enumerate()
213 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
214 .collect::<Vec<(u64, Word)>>();
215 let smt = SimpleSmt::with_leaves(SimpleSmt::MAX_DEPTH, smt_leaves.clone()).unwrap();
216 let store = MerkleStore::from(&smt);
217 let root = smt.root();
218 let half_depth = smt.depth() / 2;
219 let half_size = 2_u64.pow(half_depth as u32);
220
221 group.bench_function(BenchmarkId::new("SimpleSmt", size), |b| {
222 b.iter_batched(
223 || random_index(half_size, half_depth),
224 |index| black_box(smt.get_node(index)),
225 BatchSize::SmallInput,
226 )
227 });
228
229 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
230 b.iter_batched(
231 || random_index(half_size, half_depth),
232 |index| black_box(store.get_node(root, index)),
233 BatchSize::SmallInput,
234 )
235 });
236 }
237}
238
239/// Benchmarks getting a path of a leaf on the Merkle tree and Merkle store backends.
240fn get_leaf_path_merkletree(c: &mut Criterion) {
241 let mut group = c.benchmark_group("get_leaf_path_merkletree");
242
243 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
244 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
245
246 for size in BATCH_SIZES {
247 let leaves = &random_data[..size];
248
249 let mtree_leaves: Vec<Word> = leaves.iter().map(|v| v.into()).collect();
250 let mtree = MerkleTree::new(mtree_leaves.clone()).unwrap();
251 let store = MerkleStore::from(&mtree);
252 let depth = mtree.depth();
253 let root = mtree.root();
254 let size_u64 = size as u64;
255
256 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
257 b.iter_batched(
258 || random_index(size_u64, depth),
259 |index| black_box(mtree.get_path(index)),
260 BatchSize::SmallInput,
261 )
262 });
263
264 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
265 b.iter_batched(
266 || random_index(size_u64, depth),
267 |index| black_box(store.get_path(root, index)),
268 BatchSize::SmallInput,
269 )
270 });
271 }
272}
273
274/// Benchmarks getting a path of a leaf on the SMT and Merkle store backends.
275fn get_leaf_path_simplesmt(c: &mut Criterion) {
276 let mut group = c.benchmark_group("get_leaf_path_simplesmt");
277
278 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
279 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
280
281 for size in BATCH_SIZES {
282 let leaves = &random_data[..size];
283
284 let smt_leaves = leaves
285 .iter()
286 .enumerate()
287 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
288 .collect::<Vec<(u64, Word)>>();
289 let smt = SimpleSmt::with_leaves(SimpleSmt::MAX_DEPTH, smt_leaves.clone()).unwrap();
290 let store = MerkleStore::from(&smt);
291 let depth = smt.depth();
292 let root = smt.root();
293 let size_u64 = size as u64;
294
295 group.bench_function(BenchmarkId::new("SimpleSmt", size), |b| {
296 b.iter_batched(
297 || random_index(size_u64, depth),
298 |index| black_box(smt.get_path(index)),
299 BatchSize::SmallInput,
300 )
301 });
302
303 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
304 b.iter_batched(
305 || random_index(size_u64, depth),
306 |index| black_box(store.get_path(root, index)),
307 BatchSize::SmallInput,
308 )
309 });
310 }
311}
312
313/// Benchmarks creation of the different storage backends
314fn new(c: &mut Criterion) {
315 let mut group = c.benchmark_group("new");
316
317 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
318 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
319
320 for size in BATCH_SIZES {
321 let leaves = &random_data[..size];
322
323 // MerkleTree constructor is optimized to work with vectors. Create a new copy of the data
324 // and pass it to the benchmark function
325 group.bench_function(BenchmarkId::new("MerkleTree::new", size), |b| {
326 b.iter_batched(
327 || leaves.iter().map(|v| v.into()).collect::<Vec<Word>>(),
328 |l| black_box(MerkleTree::new(l)),
329 BatchSize::SmallInput,
330 )
331 });
332
333 // This could be done with `bench_with_input`, however to remove variables while comparing
334 // with MerkleTree it is using `iter_batched`
335 group.bench_function(BenchmarkId::new("MerkleStore::extend::MerkleTree", size), |b| {
336 b.iter_batched(
337 || leaves.iter().map(|v| v.into()).collect::<Vec<Word>>(),
338 |l| {
339 let mtree = MerkleTree::new(l).unwrap();
340 black_box(MerkleStore::from(&mtree));
341 },
342 BatchSize::SmallInput,
343 )
344 });
345
346 group.bench_function(BenchmarkId::new("SimpleSmt::new", size), |b| {
347 b.iter_batched(
348 || {
349 leaves
350 .iter()
351 .enumerate()
352 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
353 .collect::<Vec<(u64, Word)>>()
354 },
355 |l| black_box(SimpleSmt::with_leaves(SimpleSmt::MAX_DEPTH, l)),
356 BatchSize::SmallInput,
357 )
358 });
359
360 group.bench_function(BenchmarkId::new("MerkleStore::extend::SimpleSmt", size), |b| {
361 b.iter_batched(
362 || {
363 leaves
364 .iter()
365 .enumerate()
366 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
367 .collect::<Vec<(u64, Word)>>()
368 },
369 |l| {
370 let smt = SimpleSmt::with_leaves(SimpleSmt::MAX_DEPTH, l).unwrap();
371 black_box(MerkleStore::from(&smt));
372 },
373 BatchSize::SmallInput,
374 )
375 });
376 }
377}
378
379/// Benchmarks updating a leaf on MerkleTree and MerkleStore backends.
380fn update_leaf_merkletree(c: &mut Criterion) {
381 let mut group = c.benchmark_group("update_leaf_merkletree");
382
383 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
384 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
385
386 for size in BATCH_SIZES {
387 let leaves = &random_data[..size];
388
389 let mtree_leaves: Vec<Word> = leaves.iter().map(|v| v.into()).collect();
390 let mut mtree = MerkleTree::new(mtree_leaves.clone()).unwrap();
391 let mut store = MerkleStore::from(&mtree);
392 let depth = mtree.depth();
393 let root = mtree.root();
394 let size_u64 = size as u64;
395
396 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
397 b.iter_batched(
398 || (rand_value::<u64>() % size_u64, random_word()),
399 |(index, value)| black_box(mtree.update_leaf(index, value)),
400 BatchSize::SmallInput,
401 )
402 });
403
404 let mut store_root = root;
405 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
406 b.iter_batched(
407 || (random_index(size_u64, depth), random_word()),
408 |(index, value)| {
409 // The MerkleTree automatically updates its internal root, the Store maintains
410 // the old root and adds the new one. Here we update the root to have a fair
411 // comparison
412 store_root = store.set_node(root, index, value).unwrap().root;
413 black_box(store_root)
414 },
415 BatchSize::SmallInput,
416 )
417 });
418 }
419}
420
421/// Benchmarks updating a leaf on SMT and MerkleStore backends.
422fn update_leaf_simplesmt(c: &mut Criterion) {
423 let mut group = c.benchmark_group("update_leaf_simplesmt");
424
425 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
426 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
427
428 for size in BATCH_SIZES {
429 let leaves = &random_data[..size];
430
431 let smt_leaves = leaves
432 .iter()
433 .enumerate()
434 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
435 .collect::<Vec<(u64, Word)>>();
436 let mut smt = SimpleSmt::with_leaves(SimpleSmt::MAX_DEPTH, smt_leaves.clone()).unwrap();
437 let mut store = MerkleStore::from(&smt);
438 let depth = smt.depth();
439 let root = smt.root();
440 let size_u64 = size as u64;
441
442 group.bench_function(BenchmarkId::new("SimpleSMT", size), |b| {
443 b.iter_batched(
444 || (rand_value::<u64>() % size_u64, random_word()),
445 |(index, value)| black_box(smt.update_leaf(index, value)),
446 BatchSize::SmallInput,
447 )
448 });
449
450 let mut store_root = root;
451 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
452 b.iter_batched(
453 || (random_index(size_u64, depth), random_word()),
454 |(index, value)| {
455 // The MerkleTree automatically updates its internal root, the Store maintains
456 // the old root and adds the new one. Here we update the root to have a fair
457 // comparison
458 store_root = store.set_node(root, index, value).unwrap().root;
459 black_box(store_root)
460 },
461 BatchSize::SmallInput,
462 )
463 });
464 }
465}
466
467criterion_group!(
468 store_group,
469 get_empty_leaf_simplesmt,
470 get_leaf_merkletree,
471 get_leaf_path_merkletree,
472 get_leaf_path_simplesmt,
473 get_leaf_simplesmt,
474 get_node_merkletree,
475 get_node_of_empty_simplesmt,
476 get_node_simplesmt,
477 new,
478 update_leaf_merkletree,
479 update_leaf_simplesmt,
480);
481criterion_main!(store_group);