XMSS + minimal zkVM = lightweight PQ signatures, with unbounded aggregation
- branch main: optimized for prover efficiency
- branch lean-vm-simple: optimized for simplicity
Both versions will eventually merge into one.
- WHIR
- SuperSpartan, with AIR-specific optimizations developed by W. Borgeaud in A simple multivariate AIR argument inspired by SuperSpartan
- Univariate Skip
- Logup*
- ...
The VM design is inspired by the famous Cairo paper.
Benchmarks are performed on 2 laptops:
- i9-12900H, 32 gb of RAM
- mac m4 max
target ≈ 128 bits of security, currently using conjecture: 4.12 of WHIR, "up to capacity" (TODO: provable security)
Poseidon2 over 16 KoalaBear field elements.
RUSTFLAGS='-C target-cpu=native' cargo run --release -- poseidon --log-n-perms 20
The full recursion program is not finished yet. Instead, we prove validity of a WHIR opening, with 25 variables, and rate = 1/4.
- 1-to-1: Recursive proof of a single WHIR opening
- n-to-1: Recursive proof of many WHIR openings (≈ 8) (we report prover time per WHIR)
RUSTFLAGS='-C target-cpu=native' cargo run --release -- recursion --count 8
RUSTFLAGS='-C target-cpu=native' cargo run --release -- xmss --n-signatures 1775Trivial encoding (for now).
n = 2,000,000
FIB_N=2000000 RUSTFLAGS='-C target-cpu=native' cargo test --release --package lean_prover --test test_zkvm -- --nocapture -- test_prove_fibonacci --exact --nocapture
Proving time:
- i9-12900H: 2.0 s (1.0 MHz)
- mac m4 max: 1.2 s (1.7 MHz)
With conjecture "up to capacity", current proofs with rate = 1/2 are about ≈ 400 - 500 KiB, of which ≈ 300 KiB comes from WHIR.
- The remaining 100 - 200 KiB will be significantly reduced in the future (this part has not been optimized at all).
- WHIR proof size will also be reduced, thanks to merkle pruning (TODO).
Target: 256 KiB for fast proof, 128 KiB for slower proofs (rate = 1/4 or 1/8).