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