leanMultisig

Minimal hash-based zkVM, targeting recursion and aggregation of hash-based signatures, for a Post-Quantum Ethereum.

Documentation: PDF

Proving System

• multilinear with WHIR, allowing polynomial stacking (reducing proof size)
• SuperSpartan, with AIR-specific optimizations
• Logup, with a system of buses similar to OpenVM

The VM design is inspired by the famous Cairo paper.

Security

123 bits of security. Johnson bound + degree 5 extension of koala-bear -> no proximity gaps conjecture. (TODO 128 bits? this would require hash digests bigger than 8 koala-bears).

Benchmarks (Slightly outdated, new benchmarks incoming)

Machine: M4 Max 48GB (CPU only)

Benchmark	Current	Target
Poseidon2 (16 koala-bears)	560K Poseidon2 / s	n/a
2 -> 1 Recursion	1.15 s	0.25 s
XMSS aggregation	554 XMSS / s	1000 XMSS / s

Expect incoming perf improvements.

To reproduce:

• cargo run --release -- poseidon --log-n-perms 20
• cargo run --release -- recursion --n 2
• cargo run --release -- xmss --n-signatures 1350

Proof size

WHIR intial rate = 1/4 -> proof size ≈ 225 KiB. (150 KiB with rate 1/16, and < 100 KiB is possible with poximity gaps conjecture + rate 1/16).

(TODO: remaining optimization = 2024/108 section 3.1)

Credits

• Plonky3 for its various performant crates
• whir-p3: a Plonky3-compatible WHIR implementation
• Whirlaway: Multilinear snark for AIR + minimal zkVM