# MTC Pipeline (mtcbench)
End-to-end Merkle Tree Certificate pipeline: TBS cert issuance, log-entry
conversion, SHA-256 Merkle tree construction (O(N) bottom-up), O(N log N)
batch inclusion proof generation, checkpoint creation, standalone certificate
assembly and DER encoding, SQLite persistence, and proof verification.
All results are from: Lenovo ThinkPad P1 Gen 5, 12th Gen i7-12800H, 64 GB RAM,
Linux 6.15.8-200.fc42.x86_64. Release build, mimalloc global allocator, Rayon
thread pool (16 logical cores). Run date: 2026-04-09.
## Running the Benchmark
```bash
# OpenSSL backend (default)
cargo build --release -p synta-bench --features bench-mtc-sqlite --bin mtcbench
./target/release/mtcbench bench --sizes 1,2,4,8,16,32,64,128,256,512,1024 --algos sha256
./target/release/mtcbench bench --sizes 1,2,4,8,16,32,64,128,256,512,1024 --algos sha256 \
--ca-key-algo ml-dsa-65 --db mtcbench-mldsa65.sqlite
# NSS backend (cert_gen signing and verification route through NSS;
# Merkle tree operations are unaffected)
cargo build --release -p synta-bench --features bench-mtc-sqlite-nss --bin mtcbench
./target/release/mtcbench bench --sizes 1,2,4,8,16,32,64,128,256,512,1024 --algos sha256 \
--db mtcbench-nss.sqlite
./target/release/mtcbench bench --sizes 1,2,4,8,16,32,64,128,256,512,1024 --algos sha256 \
--ca-key-algo ml-dsa-65 --db mtcbench-nss-mldsa65.sqlite
```
## Results: ECDSA P-256
**Configuration:** SHA-256 Merkle hash; ECDSA P-256 CA and subscriber keys.
| `cert_gen` | 0.35 ms | 185 | 4.51 ms | 227 | 0.37 ms | 173 | 5.93 ms | 173 |
| `entry_convert` | 0.24 ms | 264 | 0.85 ms | 1,203 | 0.08 ms | 835 | 1.11 ms | 921 |
| `leaf_hash` | 0.04 ms | 1,724 | 0.10 ms | 9,961 | 0.02 ms | 3,118 | 0.15 ms | 6,952 |
| `db_insert_entries` | 0.37 ms | 171 | 1.45 ms | 705 | 0.11 ms | 606 | 1.34 ms | 767 |
| `tree_build` | 0.01 ms | 7,524 | 0.13 ms | 8,149 | 0.01 ms | 7,933 | 0.11 ms | 9,083 |
| `proof_gen_all` | 0.02 ms | 3,076 | 0.35 ms | 2,921 | 0.02 ms | 4,319 | 0.30 ms | 3,390 |
| `proof_gen_one` | 0.01 ms | 86 | 0.13 ms | 7.5 | 0.01 ms | 117 | 0.13 ms | 7.7 |
| `checkpoint_create` | 0.004 ms | 234 | 0.007 ms | 146 | 0.003 ms | 319 | 0.007 ms | 134 |
| `db_insert_checkpoint` | 0.03 ms | 33.8 | 0.02 ms | 48.1 | 0.01 ms | 70.5 | 0.02 ms | 58.7 |
| `proof_encode` | 0.15 ms | 429 | 0.41 ms | 2,501 | 0.30 ms | 211 | 0.47 ms | 2,177 |
| `db_insert_proofs` | 0.15 ms | 441 | 1.49 ms | 685 | 0.48 ms | 133 | 1.46 ms | 703 |
| `standalone_build` | 0.07 ms | 884 | 0.68 ms | 1,503 | 0.21 ms | 301 | 0.78 ms | 1,315 |
| `standalone_encode` | 0.06 ms | 997 | 0.50 ms | 2,032 | 0.16 ms | 403 | 0.69 ms | 1,476 |
| `db_insert_standalone` | 0.15 ms | 420 | 2.27 ms | 451 | 0.28 ms | 230 | 2.02 ms | 508 |
| `proof_verify_one` | 0.001 ms | 799 | 0.002 ms | 456 | 0.003 ms | 322 | 0.002 ms | 458 |
| `proof_verify_all` | 0.04 ms | 1,571 | 0.18 ms | 5,634 | 0.16 ms | 399 | 0.27 ms | 3,826 |
| `db_read_entries` | 0.05 ms | 2,502 | 0.23 ms | 9,040 | 0.09 ms | 1,532 | 0.24 ms | 8,551 |
| `db_read_standalone` | 0.06 ms | 1,985 | 0.79 ms | 2,602 | 0.09 ms | 1,418 | 1.20 ms | 1,707 |
## Results: ML-DSA-65
**Configuration:** SHA-256 Merkle hash; ML-DSA-65 CA and subscriber keys.
ML-DSA-65 certificates are ~5,521 bytes DER, roughly 8× larger than ECDSA P-256 (~700 bytes).
| `cert_gen` | 2.15 ms | 29.8 | 19.72 ms | 51.9 | 3.17 ms | 20.2 | 20.81 ms | 49.2 |
| `entry_convert` | 0.46 ms | 138 | 0.52 ms | 1,985 | 0.24 ms | 265 | 0.58 ms | 1,781 |
| `leaf_hash` | 0.08 ms | 851 | 0.10 ms | 10,421 | 0.07 ms | 863 | 0.08 ms | 13,117 |
| `db_insert_entries` | 0.20 ms | 321 | 2.58 ms | 396 | 0.13 ms | 502 | 2.34 ms | 437 |
| `tree_build` | 0.01 ms | 6,674 | 0.12 ms | 8,525 | 0.01 ms | 7,913 | 0.12 ms | 8,643 |
| `proof_gen_all` | 0.02 ms | 3,209 | 0.43 ms | 2,401 | 0.02 ms | 4,098 | 0.38 ms | 2,704 |
| `proof_gen_one` | 0.01 ms | 104 | 0.17 ms | 5.9 | 0.01 ms | 114 | 0.14 ms | 7.0 |
| `checkpoint_create` | 0.007 ms | 149 | 0.009 ms | 115 | 0.004 ms | 244 | 0.009 ms | 114 |
| `db_insert_checkpoint` | 0.03 ms | 34.1 | 0.04 ms | 24.8 | 0.02 ms | 63.5 | 0.03 ms | 31.5 |
| `proof_encode` | 0.19 ms | 330 | 0.52 ms | 1,971 | 0.10 ms | 618 | 0.35 ms | 2,949 |
| `db_insert_proofs` | 0.20 ms | 323 | 2.40 ms | 427 | 0.12 ms | 542 | 2.28 ms | 448 |
| `standalone_build` | 0.15 ms | 439 | 0.74 ms | 1,380 | 0.08 ms | 802 | 0.67 ms | 1,539 |
| `standalone_encode` | 0.15 ms | 428 | 0.73 ms | 1,399 | 0.12 ms | 556 | 0.73 ms | 1,399 |
| `db_insert_standalone` | 0.87 ms | 73.3 | 16.83 ms | 60.8 | 0.61 ms | 105 | 15.14 ms | 67.6 |
| `proof_verify_one` | 0.003 ms | 332 | 0.003 ms | 364 | 0.002 ms | 434 | 0.003 ms | 333 |
| `proof_verify_all` | 0.21 ms | 309 | 0.22 ms | 4,740 | 0.13 ms | 505 | 0.26 ms | 3,889 |
| `db_read_entries` | 0.05 ms | 2,695 | 0.22 ms | 9,506 | 0.06 ms | 2,385 | 0.22 ms | 9,353 |
| `db_read_standalone` | 0.13 ms | 993 | 1.94 ms | 1,053 | 0.17 ms | 753 | 2.12 ms | 964 |
## Algorithm Comparison: OpenSSL Backend (batch=1024)
Operations unaffected by key algorithm (SHA-256 Merkle operations):
| `leaf_hash` | 0.10 ms | 0.10 ms | identical: 32-byte SHA-256 hashes |
| `tree_build` | 0.13 ms | 0.12 ms | identical: operates on hash digests |
| `proof_gen_all` | 0.35 ms | 0.43 ms | variance from Rayon scheduling |
| `proof_verify_all` | 0.18 ms | 0.22 ms | Merkle hash chain only |
Operations affected by key algorithm:
| `cert_gen` | 4.51 ms | 19.72 ms | **4.4× slower** |
| `standalone_build` | 0.68 ms | 0.74 ms | 1.1× (larger TBS assembly) |
| `db_insert_standalone` | 2.27 ms | 16.83 ms | **7.4× slower** (8× larger DER blobs) |
| `db_read_standalone` | 0.79 ms | 1.94 ms | **2.5× slower** (I/O bound) |
| `db_insert_entries` | 1.45 ms | 2.58 ms | 1.8× slower (larger log entry DER) |
## NSS Backend: Impact on MTC Pipeline
Only `cert_gen` is affected by the crypto backend. All Merkle tree operations
(`leaf_hash`, `tree_build`, `proof_gen_all`, `proof_verify_all`) operate
entirely on 32-byte SHA-256 digests and are backend-agnostic.
| ECDSA P-256 — OpenSSL | 0.35 ms | 4.51 ms | — |
| ECDSA P-256 — NSS | 0.37 ms | 5.93 ms | **+1.3×** |
| ML-DSA-65 — OpenSSL | 2.15 ms | 19.72 ms | — |
| ML-DSA-65 — NSS | 3.17 ms | 20.81 ms | **+1.06×** |
The NSS overhead is substantially smaller in the MTC pipeline than in x509bench
because mtcbench `cert_gen` amortizes the per-signer key-import cost differently:
the CA signer is initialized once per batch run rather than once per certificate.
For ML-DSA-65, whose signing cost dominates (~90 µs/sign × 1024 = ~92 ms
single-threaded, parallelized to 19.72 ms), the PKCS#11 overhead is a minor
fraction of total batch time.
## Analysis
`tree_build`, `proof_gen_all`, and `proof_verify_all` are key-algorithm-agnostic:
they operate entirely on 32-byte SHA-256 hashes and run at the same speed
regardless of the certificate key type or crypto backend.
`cert_gen` is 4.4× slower with ML-DSA-65 because each certificate requires one
ML-DSA-65 signing operation (~800 µs on a single core), compared to ECDSA P-256
(~30 µs). Rayon parallelizes both, but ML-DSA-65 signing stresses the L2 cache
(large polynomial operations), limiting perfect scaling across all 16 cores.
`db_insert_standalone` and `db_read_standalone` are 7–10× slower because
ML-DSA-65 standalone DER blobs are approximately 8× larger than their ECDSA P-256
counterparts (~8 KB vs ~1 KB per entry). SQLite throughput degrades roughly
proportionally to row size for large BLOB inserts.
`tree_build` throughput increases from ~6.7 M/s (batch=64) to ~8.1–8.5 M/s
(batch=1024): larger trees amortize the per-tree constant setup cost over more nodes.
`proof_gen_all` uses the O(N log N) pre-built level walk —
one hash comparison per tree level per leaf — so per-cert cost stays roughly
constant regardless of batch size.
`proof_verify_all` throughput scales from ~310–1,571 K/s (batch=64) to
3,826–5,634 K/s (batch=1024) as Rayon parallelism amortizes the fixed
per-task overhead. Each Rayon task processes at least 8 proofs (`with_min_len(8)`)
to keep scheduling overhead below the SHA-256 compute time.
SQLite inserts use a single `prepare()` before the transaction loop so the
SQL parse cost is paid once per batch rather than once per row.