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(BenchmarkId::new("MerkleStore::with_merkle_tree", size), |b| {
351 b.iter_batched(
352 || leaves.iter().map(|v| v.into()).collect::<Vec<Word>>(),
353 |l| black_box(MerkleStore::new().with_merkle_tree(l)),
354 BatchSize::SmallInput,
355 )
356 });
357
358 group.bench_function(BenchmarkId::new("SimpleSmt::new", size), |b| {
359 b.iter_batched(
360 || {
361 leaves
362 .iter()
363 .enumerate()
364 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
365 .collect::<Vec<(u64, Word)>>()
366 },
367 |l| black_box(SimpleSmt::new(SimpleSmt::MAX_DEPTH).unwrap().with_leaves(l)),
368 BatchSize::SmallInput,
369 )
370 });
371
372 group.bench_function(BenchmarkId::new("MerkleStore::with_sparse_merkle_tree", size), |b| {
373 b.iter_batched(
374 || {
375 leaves
376 .iter()
377 .enumerate()
378 .map(|(c, v)| (c.try_into().unwrap(), v.into()))
379 .collect::<Vec<(u64, Word)>>()
380 },
381 |l| black_box(MerkleStore::new().with_sparse_merkle_tree(SimpleSmt::MAX_DEPTH, l)),
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::new().with_merkle_tree(mtree_leaves).unwrap();
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::new()
450 .with_sparse_merkle_tree(SimpleSmt::MAX_DEPTH, smt_leaves)
451 .unwrap();
452 let depth = smt.depth();
453 let root = smt.root();
454 let size_u64 = size as u64;
455
456 group.bench_function(BenchmarkId::new("SimpleSMT", size), |b| {
457 b.iter_batched(
458 || (rand_value::<u64>() % size_u64, random_word()),
459 |(index, value)| black_box(smt.update_leaf(index, value)),
460 BatchSize::SmallInput,
461 )
462 });
463
464 let mut store_root = root;
465 group.bench_function(BenchmarkId::new("MerkleStore", size), |b| {
466 b.iter_batched(
467 || (random_index(size_u64, depth), random_word()),
468 |(index, value)| {
469 // The MerkleTree automatically updates its internal root, the Store maintains
470 // the old root and adds the new one. Here we update the root to have a fair
471 // comparison
472 store_root = store.set_node(root, index, value).unwrap().root;
473 black_box(store_root)
474 },
475 BatchSize::SmallInput,
476 )
477 });
478 }
479}
480
481criterion_group!(
482 store_group,
483 get_empty_leaf_simplesmt,
484 get_leaf_merkletree,
485 get_leaf_path_merkletree,
486 get_leaf_path_simplesmt,
487 get_leaf_simplesmt,
488 get_node_merkletree,
489 get_node_of_empty_simplesmt,
490 get_node_simplesmt,
491 new,
492 update_leaf_merkletree,
493 update_leaf_simplesmt,
494);
495criterion_main!(store_group);