MerkleBloom

Rust implementation of Forget-Me-Not (FMN) trees with sparse Bloom-Merkle filters and a key-transparency (KT) wrapper. This is the code used to produce the benchmark figures in the paper — the library lives in rust/, the driver binaries are in rust/src/bin/, and the data used to create the figures in the paper are in rust/results/.

Repository layout

• rust/ — the crate. All real code lives here.
  • rust/src/ — library modules: bloom.rs, fmn.rs, proofs.rs, key_transparency.rs, scenario.rs, virtual_latest/.
  • rust/src/bin/ — driver binaries and the JSON suite configs they consume.
  • rust/benches/bench.rs — Criterion micro-benchmarks.
  • rust/tests/ — integration tests.
  • rust/fixtures/ — pre-generated forests (gitignored; rebuild with gen_fixtures).
  • rust/data/ — WhatsApp activity CSVs (feb_1_2026.csv, oct_1_2025.csv) consumed by kt_compare.
  • rust/results/ — CSVs we ship and reference in the paper.
• python/ — plotting scripts that turn the CSVs in rust/results/ into the paper's figures, plus python/requirements.txt.

Prerequisites

• A recent Rust toolchain (cargo, edition 2021).
• All commands below assume the working directory is rust/ unless stated otherwise.
• Always pass --release. Debug builds of the Bloom-filter code are unusably slow.

Quick start: fixtures + quick_bench

These benchmark were optimized for testing during development on a M4 Macbook Air with 16GB of RAM.

cd rust
cargo run --bin gen_fixtures --release
cargo run --bin quick_bench --release

gen_fixtures writes pre-built forests to rust/fixtures/ (see rust/src/bin/gen_fixtures.rs). The defaults are the paper parameters m=27 k=2 lam=256; override with -- --m N --k N --lam N.

quick_bench (rust/src/bin/quick_bench.rs) loads the fixtures and prints three tables: prove_latest / verify_latest timings, epoch-merge construct/verify timings, and a multi-epoch scenario sweep. It uses paper params m=27 k=2 lam=256.

Reproducing the CSVs in rust/results/

Each CSV maps to a single command. All commands assume cwd = rust/. Where a suite JSON's built-in csv field doesn't already point at results/<name>.csv, the command uses --csv to override (see virtual_bench.rs).

figure2.csv (Figure 2)

Assumes access to significnat memory resources (128GB) and a long-running computation (12ish hours).

cargo run --bin virtual_bench --release -- \
  --config src/bin/figure2_singletree_suite.json \
  --csv results/figure2.csv

ef_size_sweep.csv (Figure 3)

cargo run --bin ef_size_sweep --release

Writes the hardcoded path results/ef_size_sweep.csv. No prerequisites. Sweeps Elias-Fano-encoded sparse Bloom sizes across m ∈ {26..29} and n ∈ {2^5 .. 2^16}, 100 trials each.

kt_compare_feb_verify.csv (Figure 5, left)

cargo run --bin kt_compare --release -- \
  --input data/feb_1_2026.csv \
  --output results/kt_compare_feb_verify.csv \
  --verify

--verify populates the verify_ms column. The output file supports resume — the binary reads already-written rows and skips completed epochs.

kt_compare_oct_verify.csv (Figure 5, right)

cargo run --bin kt_compare --release -- \
  --input data/oct_1_2025.csv \
  --output results/kt_compare_oct_verify.csv \
  --verify

latest_virtual_m27.csv (Figure 6, Teal)

Note: There are two configuration JSON files for generating this data: either latest_virtual_suite.json or latest_virtual_suite_deep.json. The former assumes about 128GB of RAM while the later assumes at least 300GB of RAM (we ran it on a machine with 500GB of RAM, but didn't reach full utilization). There is no configuration to run this on a small machine. The former completed in about 24-36 hours, while the later completed in 8 hours.

# For 128GB of RAM:
cargo run --bin latest_virtual_bench --release -- \
  src/bin/latest_virtual_suite.json

# For 300+GB of RAM:
cargo run --bin latest_virtual_bench --release -- \
  src/bin/latest_virtual_suite_deep.json

No matter the configuration used, this script supports resuming on crash by default.

latest_virtual_m28.csv (Figure 6, Orange)

See warning about memory usage and runtimes above.

# For 128GB of RAM:
cargo run --bin latest_virtual_bench --release -- \
  src/bin/latest_virtual_suite_m28.json

# For 300+GB of RAM:
cargo run --bin latest_virtual_bench --release -- \
  src/bin/latest_virtual_suite_m28_deep.json

monitoring.csv and monitoring-worstcase.csv (Figure 7)

Two separate suite files, one per CSV. The average case sweeps sizes 7.2M … 1.07G leaves; the worst case sweeps powers of two minus one (16383 … 1073741823 leaves). --csv is overridden so both land in results/:

# Average case:
cargo run --bin virtual_bench --release -- \
  --config src/bin/figure6_monitoring_suite.json \
  --csv results/monitoring.csv

# Worst case:
cargo run --bin virtual_bench --release -- \
  --config src/bin/figure6_monitoring_suite_worst_case.json \
  --csv results/monitoring-worstcase.csv

Generating the paper figures

Once the CSVs above exist in rust/results/, the Python scripts under python/ turn them into the PDFs (and one LaTeX table) used in the paper. All commands below assume cwd = <repo root>.

Create a virtualenv and install the plotting dependencies:

python3 -m venv .venv
source .venv/bin/activate
pip install -r python/requirements.txt

Then run any of the five scripts. Each reads the relevant CSV from rust/results/ and writes its output(s) to figures/:

python python/generate_singletree_results.py     # figure2.csv → singletree_proof_size.pdf
python python/generate_ef_size_sweep.py          # ef_size_sweep.csv → ef_size_sweep.pdf
python python/generate_kt_comparison.py          # kt_compare_oct_verify.csv → kt_comparison_{feb,oct}.pdf
python python/generate_monitoring_results.py     # monitoring{,-worstcase}.csv → monitoring_benchmark_size.pdf
python python/generate_latest_results.py         # latest_virtual_m{27,28}.csv → latest_benchmark_size.pdf

Other entry points

• cargo test --release — integration tests in rust/tests/.
• cargo bench — Criterion micro-benchmarks (rust/benches/bench.rs) at smaller params m=20 k=2 lam=256.
• Optional Cargo features (see rust/Cargo.toml): zstd-compression, snappy-compression, trace-prove, verify-timing. These were used during development.