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 = 63u8;
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(63)
107 .unwrap()
108 .with_leaves(smt_leaves.clone())
109 .unwrap();
110 let store = MerkleStore::new()
111 .with_sparse_merkle_tree(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 = 63u8;
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(63)
220 .unwrap()
221 .with_leaves(smt_leaves.clone())
222 .unwrap();
223 let store = MerkleStore::new()
224 .with_sparse_merkle_tree(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(63)
299 .unwrap()
300 .with_leaves(smt_leaves.clone())
301 .unwrap();
302 let store = MerkleStore::new()
303 .with_sparse_merkle_tree(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(63).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| black_box(MerkleStore::new().with_sparse_merkle_tree(l)),
386 BatchSize::SmallInput,
387 )
388 },
389 );
390 }
391}
392
393/// Benchmarks updating a leaf on MerkleTree and MerkleStore backends.
394fn update_leaf_merkletree(c: &mut Criterion) {
395 let mut group = c.benchmark_group("update_leaf_merkletree");
396
397 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
398 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
399
400 for size in BATCH_SIZES {
401 let leaves = &random_data[..size];
402
403 let mtree_leaves: Vec<Word> = leaves.iter().map(|v| v.into()).collect();
404 let mut mtree = MerkleTree::new(mtree_leaves.clone()).unwrap();
405 let mut store = MerkleStore::new().with_merkle_tree(mtree_leaves).unwrap();
406 let depth = mtree.depth();
407 let root = mtree.root();
408 let size_u64 = size as u64;
409
410 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
411 b.iter_batched(
412 || (random_index(size_u64), random_word()),
413 |(index, value)| black_box(mtree.update_leaf(index, value)),
414 BatchSize::SmallInput,
415 )
416 });
417
418 let mut store_root = root;
419 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
420 b.iter_batched(
421 || (random_index(size_u64), random_word()),
422 |(index, value)| {
423 // The MerkleTree automatically updates its internal root, the Store maintains
424 // the old root and adds the new one. Here we update the root to have a fair
425 // comparison
426 store_root = store
427 .set_node(root, NodeIndex::new(depth, index), value)
428 .unwrap();
429 black_box(store_root)
430 },
431 BatchSize::SmallInput,
432 )
433 });
434 }
435}
436
437/// Benchmarks updating a leaf on SMT and MerkleStore backends.
438fn update_leaf_simplesmt(c: &mut Criterion) {
439 let mut group = c.benchmark_group("update_leaf_simplesmt");
440
441 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
442 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
443
444 for size in BATCH_SIZES {
445 let leaves = &random_data[..size];
446
447 let smt_leaves = leaves
448 .iter()
449 .enumerate()
450 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
451 .collect::<Vec<(u64, Word)>>();
452 let mut smt = SimpleSmt::new(63)
453 .unwrap()
454 .with_leaves(smt_leaves.clone())
455 .unwrap();
456 let mut store = MerkleStore::new()
457 .with_sparse_merkle_tree(smt_leaves)
458 .unwrap();
459 let depth = smt.depth();
460 let root = smt.root();
461 let size_u64 = size as u64;
462
463 group.bench_function(BenchmarkId::new("SimpleSMT", size), |b| {
464 b.iter_batched(
465 || (random_index(size_u64), random_word()),
466 |(index, value)| black_box(smt.update_leaf(index, value)),
467 BatchSize::SmallInput,
468 )
469 });
470
471 let mut store_root = root;
472 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
473 b.iter_batched(
474 || (random_index(size_u64), random_word()),
475 |(index, value)| {
476 // The MerkleTree automatically updates its internal root, the Store maintains
477 // the old root and adds the new one. Here we update the root to have a fair
478 // comparison
479 store_root = store
480 .set_node(root, NodeIndex::new(depth, index), value)
481 .unwrap();
482 black_box(store_root)
483 },
484 BatchSize::SmallInput,
485 )
486 });
487 }
488}
489
490criterion_group!(
491 store_group,
492 get_empty_leaf_simplesmt,
493 get_leaf_merkletree,
494 get_leaf_path_merkletree,
495 get_leaf_path_simplesmt,
496 get_leaf_simplesmt,
497 get_node_merkletree,
498 get_node_of_empty_simplesmt,
499 get_node_simplesmt,
500 new,
501 update_leaf_merkletree,
502 update_leaf_simplesmt,
503);
504criterion_main!(store_group);