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

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)
      • GPU acceleration: ICICLE-STWO by Ingonyama
    • 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

Select a repo