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 mut store = MerkleStore::new();
70 store.extend(mtree.inner_nodes());
71 let depth = mtree.depth();
72 let root = mtree.root();
73 let size_u64 = size as u64;
74
75 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
76 b.iter_batched(
77 || random_index(size_u64, depth),
78 |index| black_box(mtree.get_node(index)),
79 BatchSize::SmallInput,
80 )
81 });
82
83 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
84 b.iter_batched(
85 || random_index(size_u64, depth),
86 |index| black_box(store.get_node(root, index)),
87 BatchSize::SmallInput,
88 )
89 });
90 }
91}
92
93/// Benchmarks getting a leaf on SMT and Merkle stores of varying power-of-two sizes.
94fn get_leaf_simplesmt(c: &mut Criterion) {
95 let mut group = c.benchmark_group("get_leaf_simplesmt");
96
97 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
98 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
99
100 for size in BATCH_SIZES {
101 let leaves = &random_data[..size];
102
103 let smt_leaves = leaves
104 .iter()
105 .enumerate()
106 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
107 .collect::<Vec<(u64, Word)>>();
108 let smt = SimpleSmt::new(SimpleSmt::MAX_DEPTH)
109 .unwrap()
110 .with_leaves(smt_leaves.clone())
111 .unwrap();
112 let mut store = MerkleStore::new();
113 store.extend(smt.inner_nodes());
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 mut store = MerkleStore::new();
182 store.extend(mtree.inner_nodes());
183 let root = mtree.root();
184 let half_depth = mtree.depth() / 2;
185 let half_size = 2_u64.pow(half_depth as u32);
186
187 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
188 b.iter_batched(
189 || random_index(half_size, half_depth),
190 |index| black_box(mtree.get_node(index)),
191 BatchSize::SmallInput,
192 )
193 });
194
195 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
196 b.iter_batched(
197 || random_index(half_size, half_depth),
198 |index| black_box(store.get_node(root, index)),
199 BatchSize::SmallInput,
200 )
201 });
202 }
203}
204
205/// Benchmarks getting a node at half the depth on SMT and Merkle stores of varying power-of-two
206/// sizes.
207fn get_node_simplesmt(c: &mut Criterion) {
208 let mut group = c.benchmark_group("get_node_simplesmt");
209
210 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
211 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
212
213 for size in BATCH_SIZES {
214 let leaves = &random_data[..size];
215
216 let smt_leaves = leaves
217 .iter()
218 .enumerate()
219 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
220 .collect::<Vec<(u64, Word)>>();
221 let smt = SimpleSmt::new(SimpleSmt::MAX_DEPTH)
222 .unwrap()
223 .with_leaves(smt_leaves.clone())
224 .unwrap();
225 let mut store = MerkleStore::new();
226 store.extend(smt.inner_nodes());
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 mut store = MerkleStore::new();
262 store.extend(mtree.inner_nodes());
263 let depth = mtree.depth();
264 let root = mtree.root();
265 let size_u64 = size as u64;
266
267 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
268 b.iter_batched(
269 || random_index(size_u64, depth),
270 |index| black_box(mtree.get_path(index)),
271 BatchSize::SmallInput,
272 )
273 });
274
275 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
276 b.iter_batched(
277 || random_index(size_u64, depth),
278 |index| black_box(store.get_path(root, index)),
279 BatchSize::SmallInput,
280 )
281 });
282 }
283}
284
285/// Benchmarks getting a path of a leaf on the SMT and Merkle store backends.
286fn get_leaf_path_simplesmt(c: &mut Criterion) {
287 let mut group = c.benchmark_group("get_leaf_path_simplesmt");
288
289 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
290 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
291
292 for size in BATCH_SIZES {
293 let leaves = &random_data[..size];
294
295 let smt_leaves = leaves
296 .iter()
297 .enumerate()
298 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
299 .collect::<Vec<(u64, Word)>>();
300 let smt = SimpleSmt::new(SimpleSmt::MAX_DEPTH)
301 .unwrap()
302 .with_leaves(smt_leaves.clone())
303 .unwrap();
304 let mut store = MerkleStore::new();
305 store.extend(smt.inner_nodes());
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(BenchmarkId::new("MerkleStore::extend::MerkleTree", size), |b| {
351 b.iter_batched(
352 || leaves.iter().map(|v| v.into()).collect::<Vec<Word>>(),
353 |l| {
354 let mtree = MerkleTree::new(l).unwrap();
355 black_box(MerkleStore::new().extend(mtree.inner_nodes()));
356 },
357 BatchSize::SmallInput,
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(BenchmarkId::new("MerkleStore::extend::SimpleSmt", size), |b| {
376 b.iter_batched(
377 || {
378 leaves
379 .iter()
380 .enumerate()
381 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
382 .collect::<Vec<(u64, Word)>>()
383 },
384 |l| {
385 let smt = SimpleSmt::new(SimpleSmt::MAX_DEPTH).unwrap().with_leaves(l).unwrap();
386 black_box(MerkleStore::new().extend(smt.inner_nodes()));
387 },
388 BatchSize::SmallInput,
389 )
390 });
391 }
392}
393
394/// Benchmarks updating a leaf on MerkleTree and MerkleStore backends.
395fn update_leaf_merkletree(c: &mut Criterion) {
396 let mut group = c.benchmark_group("update_leaf_merkletree");
397
398 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
399 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
400
401 for size in BATCH_SIZES {
402 let leaves = &random_data[..size];
403
404 let mtree_leaves: Vec<Word> = leaves.iter().map(|v| v.into()).collect();
405 let mut mtree = MerkleTree::new(mtree_leaves.clone()).unwrap();
406 let mut store = MerkleStore::new();
407 store.extend(mtree.inner_nodes());
408 let depth = mtree.depth();
409 let root = mtree.root();
410 let size_u64 = size as u64;
411
412 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
413 b.iter_batched(
414 || (rand_value::<u64>() % size_u64, random_word()),
415 |(index, value)| black_box(mtree.update_leaf(index, value)),
416 BatchSize::SmallInput,
417 )
418 });
419
420 let mut store_root = root;
421 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
422 b.iter_batched(
423 || (random_index(size_u64, depth), random_word()),
424 |(index, value)| {
425 // The MerkleTree automatically updates its internal root, the Store maintains
426 // the old root and adds the new one. Here we update the root to have a fair
427 // comparison
428 store_root = store.set_node(root, index, value).unwrap().root;
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(SimpleSmt::MAX_DEPTH)
453 .unwrap()
454 .with_leaves(smt_leaves.clone())
455 .unwrap();
456 let mut store = MerkleStore::new();
457 store.extend(smt.inner_nodes());
458 let depth = smt.depth();
459 let root = smt.root();
460 let size_u64 = size as u64;
461
462 group.bench_function(BenchmarkId::new("SimpleSMT", size), |b| {
463 b.iter_batched(
464 || (rand_value::<u64>() % size_u64, random_word()),
465 |(index, value)| black_box(smt.update_leaf(index, value)),
466 BatchSize::SmallInput,
467 )
468 });
469
470 let mut store_root = root;
471 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
472 b.iter_batched(
473 || (random_index(size_u64, depth), random_word()),
474 |(index, value)| {
475 // The MerkleTree automatically updates its internal root, the Store maintains
476 // the old root and adds the new one. Here we update the root to have a fair
477 // comparison
478 store_root = store.set_node(root, index, value).unwrap().root;
479 black_box(store_root)
480 },
481 BatchSize::SmallInput,
482 )
483 });
484 }
485}
486
487criterion_group!(
488 store_group,
489 get_empty_leaf_simplesmt,
490 get_leaf_merkletree,
491 get_leaf_path_merkletree,
492 get_leaf_path_simplesmt,
493 get_leaf_simplesmt,
494 get_node_merkletree,
495 get_node_of_empty_simplesmt,
496 get_node_simplesmt,
497 new,
498 update_leaf_merkletree,
499 update_leaf_simplesmt,
500);
501criterion_main!(store_group);