1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
use criterion::{Criterion, criterion_group, criterion_main};
use mt_rs::{
hasher::SHA256Hasher,
merkletree::MerkleTree,
proof::{DefaultProofer, Proofer},
};
use rand::{RngCore, rngs::OsRng};
use std::fs::{self, File};
use std::io::{BufWriter, Write};
use std::path::Path;
// Create files `filenames` with random data with a size of `size` MB.
fn setup_files(filenames: &Vec<String>, size: usize) -> std::io::Result<Vec<Vec<u8>>> {
for filename in filenames.iter() {
if !Path::new(filename).exists() {
let file = File::create(filename)?;
let mut writer = BufWriter::new(file);
let mut buffer = vec![0u8; 1024 * 1024]; // 1 MB buffer
// 1 MB * size = total bytes
for _ in 0..size {
// Fill buffer with random bytes
OsRng.fill_bytes(&mut buffer);
writer.write_all(&buffer)?;
}
writer.flush()?;
}
}
let files: Vec<Vec<u8>> = filenames
.iter()
.map(|filename| fs::read(filename).expect("file not found"))
.collect();
Ok(files)
}
fn cleanup_files(filenames: &Vec<String>) -> std::io::Result<()> {
for filename in filenames.iter() {
if Path::new(filename).exists() {
fs::remove_file(filename)?;
}
}
Ok(())
}
fn test_merkle_tree(files: &Vec<Vec<u8>>) {
let hasher = SHA256Hasher::new();
let tree = MerkleTree::new(hasher.clone(), files);
let proofer = DefaultProofer::new(&hasher, tree.leaves().clone());
let root = tree.root();
let root_hash = root.hash();
for i in 0..files.len() {
let proof = proofer.generate(i).expect("proof generation failed");
assert!(proofer.verify(&proof, &files[i], root_hash, &hasher));
}
}
/// Example of a MarkleTree with 512 nodes which use SHA256 algorithm to make hashes.
/// Each node has a size of 1024 bytes.
/// Also, it verifies each node path with a proofer O(n).
fn bench_large_merkle_tree_sha256(c: &mut Criterion) {
let filenames: Vec<String> = (1..=10).map(|i| format!("file-{i}.dat")).collect();
let mut group = c.benchmark_group("MerkleTree");
group.sample_size(10);
for size in [5, 10, 15] {
group.bench_function(
format!("MerkleTree creation and validation with 10 nodes and SHA256 algorithm. {size} MB per each file."),
|b| {
let files = setup_files(&filenames, size).expect("failed to allocate new files");
b.iter(|| {
test_merkle_tree(&files);
});
cleanup_files(&filenames).expect("failed to deallocate data");
},
);
}
group.finish();
}
criterion_group!(benches, bench_large_merkle_tree_sha256);
criterion_main!(benches);
|
