Skip to main content

proof_sizes/
proof_sizes.rs

1//! How small a Merkle branch is beside the list it stands in for.
2//!
3//! ```sh
4//! cargo run --release --example proof_sizes
5//! ```
6//!
7//! In a Merkle DAG, checking one child of a parent takes the parent's whole
8//! list of hashes. Here a parent's list is a Merkle tree of its own, so one
9//! child is checked with a branch of it. This prints both sizes, in bytes on
10//! the wire, for folders of ten to a million entries and for files of ten to
11//! half a million chunks. A file of half a million chunks is about a terabyte.
12
13use scionic_merkletree::{
14    Builder, Chunking, Entry, ExtraData, MemoryStore, Request, Responder, Result, Store, Stored,
15};
16
17/// How many bytes a store's holder answers a request with.
18fn answer_bytes(store: &MemoryStore, request: &Request) -> Result<usize> {
19    let mut bytes = 0;
20    Responder::new(store).answer(&request.encode(), &mut |frame| {
21        bytes += frame.len();
22        Ok(())
23    })?;
24    Ok(bytes)
25}
26
27fn row(count: usize, list: usize, branch: usize) {
28    let smaller = list as f64 / branch as f64;
29    println!("{count:>10}  {list:>12}  {branch:>8}  {smaller:>9.0}x");
30}
31
32fn main() -> Result<()> {
33    println!("One entry of a folder, by its name. Names are 16 bytes long.");
34    println!(
35        "{:>10}  {:>12}  {:>8}  {:>10}",
36        "entries", "whole list", "branch", "smaller by"
37    );
38    for count in [10_usize, 1_000, 10_000, 1_000_000] {
39        let store = MemoryStore::new();
40        let mut builder = Builder::new(&store, Chunking::fixed(16)?);
41        let file = builder.file_from_bytes(b"the same small file")?;
42        let entries = (0..count)
43            .map(|number| Entry::new(format!("file-{number:07}.bin"), file, ExtraData::new()))
44            .collect::<Result<Vec<_>>>()?;
45        let folder = builder.folder(entries)?;
46        let list = store
47            .get(Stored::FolderList, &folder.hash)?
48            .map_or(0, |list| list.len());
49        let request = Request::FolderName {
50            folder: folder.hash,
51            name: format!("file-{:07}.bin", count / 2),
52        };
53        row(count, list, answer_bytes(&store, &request)?);
54    }
55
56    println!();
57    println!("One chunk of a file, by its number.");
58    println!(
59        "{:>10}  {:>12}  {:>8}  {:>10}",
60        "chunks", "whole list", "branch", "smaller by"
61    );
62    for count in [10_usize, 1_000, 10_000, 500_000] {
63        // Chunks of one byte, so that a file of many chunks is small.
64        let store = MemoryStore::new();
65        let mut builder = Builder::new(&store, Chunking::fixed(1)?);
66        let bytes: Vec<u8> = (0..count).map(|at| (at % 251) as u8).collect();
67        let file = builder.file_from_bytes(&bytes)?;
68        let list = store
69            .get(Stored::FileList, &file.hash)?
70            .map_or(0, |list| list.len());
71        let request = Request::FileBranch {
72            file: file.hash,
73            start: (count / 2) as u64,
74            count: 1,
75        };
76        row(count, list, answer_bytes(&store, &request)?);
77    }
78    Ok(())
79}