fast-certs 🏎️🔒

Fast, non-ZK correctness certificates for rollups and computation.

This crate provides publicly verifiable proofs of correctness without zero-knowledge overhead.
If you need to prove correctness only (not secrecy), you can achieve orders of magnitude higher throughput than zkSNARKs or zkSTARKs — while retaining strong integrity guarantees.

Features

• Merkle proofs — compact membership certificates (O(log n)) over any dataset.
• Algebraic certificates — Fiat–Shamir–based linear checks (e.g. Freivalds’) for matrix multiplication, rollup state transitions, etc.
• Ethereum-style rollups — commit to pre-state, post-state, and transaction list, then prove correctness via a non-interactive linear check.
• Zero dependencies on trusted setup — proofs are derived deterministically via Fiat–Shamir over cryptographic hashes.
• Blazing-fast prover — no heavy crypto, just hashing and modular arithmetic.

Installation

Add to your Cargo.toml:

[dependencies]
fast-certs = "0.1.0"

Examples

Merkle Tree Membership

use fast_certs::merkle::MerkleTree;

let leaves: Vec<Vec<u8>> = (0..4).map(|i| format!("leaf-{i}").into_bytes()).collect();
let tree = MerkleTree::from_leaves(&leaves);
let root = tree.root().unwrap();

let proof = tree.prove(2).unwrap();
assert!(proof.verify(&leaves[2], &root));

Matrix Multiplication Certificate

use fast_certs::freivalds::*;

let a = Matrix::from_fn(4, 4, |i, j| ((3*i + j) as u64));
let b = Matrix::from_fn(4, 4, |i, j| ((2*i + 7*j) as u64));
let c = mat_mul(&a, &b);

let proof = prove_freivalds(&a, &b, &c);
assert!(verify_freivalds(&a, &b, &c, &proof));

Ethereum Rollup (example program)

We ship a demo under examples/eth_rollup.rs:

cargo run --example eth_rollup --release

This commits to:

• Pre-state balances (U256, Address)
• Transactions (from, to, value, nonce)
• Post-state balances

And produces a rollup proof:

• Merkle roots for pre-state, post-state, tx list
• Fiat–Shamir scalar check ensuring the state transition matches the tx batch

Benchmarks

We provide Criterion benchmarks under benches/.

Run:

cargo bench --bench eth_rollup_sig

Results (single-threaded, CPU-only, Rust)

• Peak throughput: ~574k TPS (small batches)
• Sustained throughput: >220k TPS (100k accounts, 20k txs)

Claim

Our rollup prover achieves ~500k TPS on commodity hardware (single-threaded, Rust, CPU-only). Even at 100k accounts and 20k transactions, throughput remains above 220k TPS. This demonstrates the power of non-ZK correctness-only certificates: blazing fast, scalable, and verifiable.

Roadmap / TODO

• Batch Merkle multiproofs for more compact decommitments
• Parallel Merkle construction (Rayon) for even higher TPS
• Optional k-round Fiat–Shamir checks for tunable soundness levels

License

Licensed under either of:

• Apache License, Version 2.0 (LICENSE-APACHE)
• MIT License (LICENSE-MIT)

at your option.

Acknowledgements

Inspired by:

• Freivalds’ algorithm for probabilistic verification
• Fiat–Shamir heuristic for removing interaction
• Ethereum rollup research — adapting proofs for practical scaling without ZK