miden-crypto/benches/store.rs
benches/store.rsRaw
1use criterion::{black_box, criterion_group, criterion_main, BatchSize, BenchmarkId, Criterion};
2use miden_crypto::{
3 hash::rpo::RpoDigest,
4 merkle::{
5 DefaultMerkleStore as MerkleStore, LeafIndex, MerkleTree, NodeIndex, SimpleSmt,
6 SMT_MAX_DEPTH,
7 },
8 Felt, Word,
9};
10use rand_utils::{rand_array, rand_value};
11
12/// Since MerkleTree can only be created when a power-of-two number of elements is used, the sample
13/// sizes are limited to that.
14static BATCH_SIZES: [usize; 3] = [2usize.pow(4), 2usize.pow(7), 2usize.pow(10)];
15
16/// Generates a random `RpoDigest`.
17fn random_rpo_digest() -> RpoDigest {
18 rand_array::<Felt, 4>().into()
19}
20
21/// Generates a random `Word`.
22fn random_word() -> Word {
23 rand_array::<Felt, 4>()
24}
25
26/// Generates an index at the specified depth in `0..range`.
27fn random_index(range: u64, depth: u8) -> NodeIndex {
28 let value = rand_value::<u64>() % range;
29 NodeIndex::new(depth, value).unwrap()
30}
31
32/// Benchmarks getting an empty leaf from the SMT and MerkleStore backends.
33fn get_empty_leaf_simplesmt(c: &mut Criterion) {
34 let mut group = c.benchmark_group("get_empty_leaf_simplesmt");
35
36 const DEPTH: u8 = SMT_MAX_DEPTH;
37 let size = u64::MAX;
38
39 // both SMT and the store are pre-populated with empty hashes, accessing these values is what is
40 // being benchmarked here, so no values are inserted into the backends
41 let smt = SimpleSmt::<DEPTH>::new().unwrap();
42 let store = MerkleStore::from(&smt);
43 let root = smt.root();
44
45 group.bench_function(BenchmarkId::new("SimpleSmt", DEPTH), |b| {
46 b.iter_batched(
47 || random_index(size, DEPTH),
48 |index| black_box(smt.get_node(index)),
49 BatchSize::SmallInput,
50 )
51 });
52
53 group.bench_function(BenchmarkId::new("MerkleStore", DEPTH), |b| {
54 b.iter_batched(
55 || random_index(size, DEPTH),
56 |index| black_box(store.get_node(root, index)),
57 BatchSize::SmallInput,
58 )
59 });
60}
61
62/// Benchmarks getting a leaf on Merkle trees and Merkle stores of varying power-of-two sizes.
63fn get_leaf_merkletree(c: &mut Criterion) {
64 let mut group = c.benchmark_group("get_leaf_merkletree");
65
66 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
67 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
68
69 for size in BATCH_SIZES {
70 let leaves = &random_data[..size];
71
72 let mtree_leaves: Vec<Word> = leaves.iter().map(|v| v.into()).collect();
73 let mtree = MerkleTree::new(mtree_leaves.clone()).unwrap();
74 let store = MerkleStore::from(&mtree);
75 let depth = mtree.depth();
76 let root = mtree.root();
77 let size_u64 = size as u64;
78
79 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
80 b.iter_batched(
81 || random_index(size_u64, depth),
82 |index| black_box(mtree.get_node(index)),
83 BatchSize::SmallInput,
84 )
85 });
86
87 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
88 b.iter_batched(
89 || random_index(size_u64, depth),
90 |index| black_box(store.get_node(root, index)),
91 BatchSize::SmallInput,
92 )
93 });
94 }
95}
96
97/// Benchmarks getting a leaf on SMT and Merkle stores of varying power-of-two sizes.
98fn get_leaf_simplesmt(c: &mut Criterion) {
99 let mut group = c.benchmark_group("get_leaf_simplesmt");
100
101 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
102 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
103
104 for size in BATCH_SIZES {
105 let leaves = &random_data[..size];
106
107 let smt_leaves = leaves
108 .iter()
109 .enumerate()
110 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
111 .collect::<Vec<(u64, Word)>>();
112 let smt = SimpleSmt::<SMT_MAX_DEPTH>::with_leaves(smt_leaves.clone()).unwrap();
113 let store = MerkleStore::from(&smt);
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, SMT_MAX_DEPTH),
120 |index| black_box(smt.get_node(index)),
121 BatchSize::SmallInput,
122 )
123 });
124
125 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
126 b.iter_batched(
127 || random_index(size_u64, SMT_MAX_DEPTH),
128 |index| black_box(store.get_node(root, index)),
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 const DEPTH: u8 = SMT_MAX_DEPTH;
140
141 // both SMT and the store are pre-populated with the empty hashes, accessing the internal nodes
142 // of these values is what is being benchmarked here, so no values are inserted into the
143 // backends.
144 let smt = SimpleSmt::<DEPTH>::new().unwrap();
145 let store = MerkleStore::from(&smt);
146 let root = smt.root();
147 let half_depth = DEPTH / 2;
148 let half_size = 2_u64.pow(half_depth as u32);
149
150 group.bench_function(BenchmarkId::new("SimpleSmt", DEPTH), |b| {
151 b.iter_batched(
152 || random_index(half_size, half_depth),
153 |index| black_box(smt.get_node(index)),
154 BatchSize::SmallInput,
155 )
156 });
157
158 group.bench_function(BenchmarkId::new("MerkleStore", DEPTH), |b| {
159 b.iter_batched(
160 || random_index(half_size, half_depth),
161 |index| black_box(store.get_node(root, index)),
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::from(&mtree);
181 let root = mtree.root();
182 let half_depth = mtree.depth() / 2;
183 let half_size = 2_u64.pow(half_depth as u32);
184
185 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
186 b.iter_batched(
187 || random_index(half_size, half_depth),
188 |index| black_box(mtree.get_node(index)),
189 BatchSize::SmallInput,
190 )
191 });
192
193 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
194 b.iter_batched(
195 || random_index(half_size, half_depth),
196 |index| black_box(store.get_node(root, index)),
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::<SMT_MAX_DEPTH>::with_leaves(smt_leaves.clone()).unwrap();
220 let store = MerkleStore::from(&smt);
221 let root = smt.root();
222 let half_depth = SMT_MAX_DEPTH / 2;
223 let half_size = 2_u64.pow(half_depth as u32);
224
225 group.bench_function(BenchmarkId::new("SimpleSmt", size), |b| {
226 b.iter_batched(
227 || random_index(half_size, half_depth),
228 |index| black_box(smt.get_node(index)),
229 BatchSize::SmallInput,
230 )
231 });
232
233 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
234 b.iter_batched(
235 || random_index(half_size, half_depth),
236 |index| black_box(store.get_node(root, index)),
237 BatchSize::SmallInput,
238 )
239 });
240 }
241}
242
243/// Benchmarks getting a path of a leaf on the Merkle tree and Merkle store backends.
244fn get_leaf_path_merkletree(c: &mut Criterion) {
245 let mut group = c.benchmark_group("get_leaf_path_merkletree");
246
247 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
248 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
249
250 for size in BATCH_SIZES {
251 let leaves = &random_data[..size];
252
253 let mtree_leaves: Vec<Word> = leaves.iter().map(|v| v.into()).collect();
254 let mtree = MerkleTree::new(mtree_leaves.clone()).unwrap();
255 let store = MerkleStore::from(&mtree);
256 let depth = mtree.depth();
257 let root = mtree.root();
258 let size_u64 = size as u64;
259
260 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
261 b.iter_batched(
262 || random_index(size_u64, depth),
263 |index| black_box(mtree.get_path(index)),
264 BatchSize::SmallInput,
265 )
266 });
267
268 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
269 b.iter_batched(
270 || random_index(size_u64, depth),
271 |index| black_box(store.get_path(root, index)),
272 BatchSize::SmallInput,
273 )
274 });
275 }
276}
277
278/// Benchmarks getting a path of a leaf on the SMT and Merkle store backends.
279fn get_leaf_path_simplesmt(c: &mut Criterion) {
280 let mut group = c.benchmark_group("get_leaf_path_simplesmt");
281
282 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
283 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
284
285 for size in BATCH_SIZES {
286 let leaves = &random_data[..size];
287
288 let smt_leaves = leaves
289 .iter()
290 .enumerate()
291 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
292 .collect::<Vec<(u64, Word)>>();
293 let smt = SimpleSmt::<SMT_MAX_DEPTH>::with_leaves(smt_leaves.clone()).unwrap();
294 let store = MerkleStore::from(&smt);
295 let root = smt.root();
296 let size_u64 = size as u64;
297
298 group.bench_function(BenchmarkId::new("SimpleSmt", size), |b| {
299 b.iter_batched(
300 || random_index(size_u64, SMT_MAX_DEPTH),
301 |index| {
302 black_box(smt.open(&LeafIndex::<SMT_MAX_DEPTH>::new(index.value()).unwrap()))
303 },
304 BatchSize::SmallInput,
305 )
306 });
307
308 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
309 b.iter_batched(
310 || random_index(size_u64, SMT_MAX_DEPTH),
311 |index| black_box(store.get_path(root, index)),
312 BatchSize::SmallInput,
313 )
314 });
315 }
316}
317
318/// Benchmarks creation of the different storage backends
319fn new(c: &mut Criterion) {
320 let mut group = c.benchmark_group("new");
321
322 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
323 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
324
325 for size in BATCH_SIZES {
326 let leaves = &random_data[..size];
327
328 // MerkleTree constructor is optimized to work with vectors. Create a new copy of the data
329 // and pass it to the benchmark function
330 group.bench_function(BenchmarkId::new("MerkleTree::new", size), |b| {
331 b.iter_batched(
332 || leaves.iter().map(|v| v.into()).collect::<Vec<Word>>(),
333 |l| black_box(MerkleTree::new(l)),
334 BatchSize::SmallInput,
335 )
336 });
337
338 // This could be done with `bench_with_input`, however to remove variables while comparing
339 // with MerkleTree it is using `iter_batched`
340 group.bench_function(BenchmarkId::new("MerkleStore::extend::MerkleTree", size), |b| {
341 b.iter_batched(
342 || leaves.iter().map(|v| v.into()).collect::<Vec<Word>>(),
343 |l| {
344 let mtree = MerkleTree::new(l).unwrap();
345 black_box(MerkleStore::from(&mtree));
346 },
347 BatchSize::SmallInput,
348 )
349 });
350
351 group.bench_function(BenchmarkId::new("SimpleSmt::new", size), |b| {
352 b.iter_batched(
353 || {
354 leaves
355 .iter()
356 .enumerate()
357 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
358 .collect::<Vec<(u64, Word)>>()
359 },
360 |l| black_box(SimpleSmt::<SMT_MAX_DEPTH>::with_leaves(l)),
361 BatchSize::SmallInput,
362 )
363 });
364
365 group.bench_function(BenchmarkId::new("MerkleStore::extend::SimpleSmt", size), |b| {
366 b.iter_batched(
367 || {
368 leaves
369 .iter()
370 .enumerate()
371 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
372 .collect::<Vec<(u64, Word)>>()
373 },
374 |l| {
375 let smt = SimpleSmt::<SMT_MAX_DEPTH>::with_leaves(l).unwrap();
376 black_box(MerkleStore::from(&smt));
377 },
378 BatchSize::SmallInput,
379 )
380 });
381 }
382}
383
384/// Benchmarks updating a leaf on MerkleTree and MerkleStore backends.
385fn update_leaf_merkletree(c: &mut Criterion) {
386 let mut group = c.benchmark_group("update_leaf_merkletree");
387
388 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
389 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
390
391 for size in BATCH_SIZES {
392 let leaves = &random_data[..size];
393
394 let mtree_leaves: Vec<Word> = leaves.iter().map(|v| v.into()).collect();
395 let mut mtree = MerkleTree::new(mtree_leaves.clone()).unwrap();
396 let mut store = MerkleStore::from(&mtree);
397 let depth = mtree.depth();
398 let root = mtree.root();
399 let size_u64 = size as u64;
400
401 group.bench_function(BenchmarkId::new("MerkleTree", size), |b| {
402 b.iter_batched(
403 || (rand_value::<u64>() % size_u64, random_word()),
404 |(index, value)| black_box(mtree.update_leaf(index, value)),
405 BatchSize::SmallInput,
406 )
407 });
408
409 let mut store_root = root;
410 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
411 b.iter_batched(
412 || (random_index(size_u64, depth), random_word()),
413 |(index, value)| {
414 // The MerkleTree automatically updates its internal root, the Store maintains
415 // the old root and adds the new one. Here we update the root to have a fair
416 // comparison
417 store_root = store.set_node(root, index, value.into()).unwrap().root;
418 black_box(store_root)
419 },
420 BatchSize::SmallInput,
421 )
422 });
423 }
424}
425
426/// Benchmarks updating a leaf on SMT and MerkleStore backends.
427fn update_leaf_simplesmt(c: &mut Criterion) {
428 let mut group = c.benchmark_group("update_leaf_simplesmt");
429
430 let random_data_size = BATCH_SIZES.into_iter().max().unwrap();
431 let random_data: Vec<RpoDigest> = (0..random_data_size).map(|_| random_rpo_digest()).collect();
432
433 for size in BATCH_SIZES {
434 let leaves = &random_data[..size];
435
436 let smt_leaves = leaves
437 .iter()
438 .enumerate()
439 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
440 .collect::<Vec<(u64, Word)>>();
441 let mut smt = SimpleSmt::<SMT_MAX_DEPTH>::with_leaves(smt_leaves.clone()).unwrap();
442 let mut store = MerkleStore::from(&smt);
443 let root = smt.root();
444 let size_u64 = size as u64;
445
446 group.bench_function(BenchmarkId::new("SimpleSMT", size), |b| {
447 b.iter_batched(
448 || (rand_value::<u64>() % size_u64, random_word()),
449 |(index, value)| {
450 black_box(smt.insert(LeafIndex::<SMT_MAX_DEPTH>::new(index).unwrap(), value))
451 },
452 BatchSize::SmallInput,
453 )
454 });
455
456 let mut store_root = root;
457 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
458 b.iter_batched(
459 || (random_index(size_u64, SMT_MAX_DEPTH), random_word()),
460 |(index, value)| {
461 // The MerkleTree automatically updates its internal root, the Store maintains
462 // the old root and adds the new one. Here we update the root to have a fair
463 // comparison
464 store_root = store.set_node(root, index, value.into()).unwrap().root;
465 black_box(store_root)
466 },
467 BatchSize::SmallInput,
468 )
469 });
470 }
471}
472
473criterion_group!(
474 store_group,
475 get_empty_leaf_simplesmt,
476 get_leaf_merkletree,
477 get_leaf_path_merkletree,
478 get_leaf_path_simplesmt,
479 get_leaf_simplesmt,
480 get_node_merkletree,
481 get_node_of_empty_simplesmt,
482 get_node_simplesmt,
483 new,
484 update_leaf_merkletree,
485 update_leaf_simplesmt,
486);
487criterion_main!(store_group);