## Beam call #2: post quantum signature aggregation
---
## Benchmark hash in snark
- Plonky3 looks most promising, on a modern CPU (e.g. i9-13900K, M3 Max), it can do:
- 1.75 - 2 M/s $\text{poseidon2}_{t16}$ permutations on KoalaBear.
- 30 K/s blake3 permutations and 4 K/s keccak256 permutations, tho both look far from poseidon2 but the current designs are purely arithmetic, no lookup is adopted yet, so perhaps there is still room to improve.
- Stwo also performs well and is close to Plonky3.
- Binius performs a bit worse than Plonky3 and Stwo on traditional hash function on CPU.
- Hashcaster looks also promising, it can do 60 K/s keccak256 permutations, and it also has much room to improve.
- Expander didn't provide PCS a month ago, but now it seems to have Orion supported, need to revisit and benchmark.
- More details in https://hackmd.io/@han/bench-hash-in-snark.
---
## Hashcaster exploration work
- **Efficient boolean formula verification**
- Hashcaster's `boolcheck` protocol verifies quadratic Boolean formulas using polynomial coordinates.
- **Core techniques**
- Frobenius theory: Uses Frobenius automorphisms to efficiently extract packed field elements.
- 4 Russians method: Speeds up structured matrix-vector computations, crucial for efficient multi-opening verifications.
- **Results**
- Highly efficient proving system for Keccak combining `boolcheck` with classical small field sumcheck
- Still too slow in terms of throughput when compared to Poseidon results.
---
## Hash-based signature aggregation
- First attempt using existing zkVM (SP1 and OpenVM), the performance looks not good even with precompile.
- Second attempt using OpenVM's prover (based on Plonky3) which supports lookup additionally, currently we can aggregate 2.5 K signatures per second, but proof is large (> 3 MB).
- Optimizations we plan to try:
- For proving speed (ideally 10 K/s sig agg):
- A simpler prover to reduce overhead, and use GKR LogUp.
- Optimize AIR traces to reduce the area.
- For proof size (ideally 128KiB):
- Adopt merkle proof reduction tricks (shared cap, higher folding arity)
- Rearrange the AIR traces to reduce number of columns.
- Adopt STIR to reduce number of queries.
- More details in
- Global approach: https://hackmd.io/@han/hash-sig-agg
- Circuit gadgets: https://hackmd.io/@tcoratger/SyWbmVPckx
---
## Specialized minimal VM for signature aggregation
- **Our criteria for a Minimal VM:**
- Ultra-simple & secure
- High performance
- Flexible arithmetization
- **Explorations:**
- Binius M3 arithmetization – Bidirectional data stream without temporal constraints.
- SP1 recursion proving system – Seamless recursion inside the main VM.
- Cairo proof recursion – Language-level provability with strong benchmarks:
- Stwo proving record: 500K Poseidon hashes/sec ([StarkWare](https://starkware.co/blog/starkware-new-proving-record/))
- GPU acceleration: ICICLE-STWO by [Ingonyama](https://x.com/Ingo_zk/status/1887580350940954965)
- Jolt VM – Lookup & sumcheck-based, <25K LOC, highly maintainable & auditable.
- OpenVM – Open-source, modular zkVM framework:
- Extensible ISA for seamless VM extensions (Poseidon2).
- Built on Plonky3 for efficient crypto layer.
---
## Ideas we want to explore
- GKR style provers
- Polyhedra ref: https://medium.com/polyhedra-network/expander-still-the-worlds-fastest-zk-prover-6aa5fd428609
- 2.16 million Poseidon hashes per second (HPS)
- WHIR:
- Ref: https://gfenzi.io/papers/whir/
- Very fast verification
- Reduce proof size
- More explorations over binary field techniques
- CPU performance for recursion
- Hash explorations
<style>
.reveal {
font-size: 24px;
}
</style>
{"title":"beam call #2","contributors":"[{\"id\":\"a2e46ed4-c239-4200-8a19-4298a4d866c0\",\"add\":6898,\"del\":3054}]","description":"Plonky3 looks most promising, on a modern CPU (e.g. i9-13900K, M3 Max), it can do:"}