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