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