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