Benchmark Hash in SNARK

Use cases

• Aggregation for hash-based signature
  • Optimistic requirement: 500k hash/s ^[1]
• STARKed binary hash tree
  • Worst-case requirement: 100k hash/s ^[2]

Requirements

• Post-quantum friendly
• Provable soundness
• Not-too-complex to write spec

Benchmark candidates

• plonky3 - FRI + AIR
  • Blake3 circuit, Keccak circuit and Poseidon2 circuit are implemented
• stwo - FRI + AIR
  • Blake2s circuit and Poseidon2 circuit are implemented
• binius
  • Keccak circuit and Vision circuit are implemented
• hashcaster - GKR on binary field
  • Keccak circuit is implemented but no PCS connected yet
• expander - GKR
  • Keccak circuit and Poseidon circuit are implemented

Benchmarks

• Machine spec
  • CPU: i9-13900K
  • RAM: 64GB (2x Crucial DDR5 5600 32GB Dual Channel)
  • OS: Linux 5.15.0-124-generic x86-64
  • Env:
    • RAYON_NUM_THREADS: 4
• Code: https://github.com/han0110/bench-hash-in-snark/tree/3398a8c
• Output
  • perm: Number of permutations proving (210..20)
  • time: Average proving time of 10 samples
  • throughput: Average throughput of 10 samples (= perm / time)
  • proof_size: Average proof size of 10 samples
  • peak_memory: Peak memory usage measured by /usr/bin/time the proving command (if the process is killed due to OOM, the row will be filled with -)

plonky3

FRI parameter:

• Field size: 124 (degree-4 extension of 31-bits field)
• Rate: ¹/₂
• Number of query: 256
• Poseidon2 parameter (notation following https://eprint.iacr.org/2023/323.pdf)
  • \(n = 31 \ \ t = 16 \ \ d = 3 \ \ R_F = 8 \ \ R_P = 20\)
  • \(p = 2^{31} - 2^{24} + 1\) (KoalaBear)

To reproduce, get into the code repository and run:

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 ./bench.sh plonky3 blake3 $i
    RAYON_NUM_THREADS=4 ./bench.sh plonky3 keccak $i
    RAYON_NUM_THREADS=4 ./bench.sh plonky3 poseidon2 $i
done;
python3 render_table.py

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh plonky3 blake3 $i
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh plonky3 keccak $i
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh plonky3 poseidon2 $i
done;
python3 render_table.py

stwo

FRI parameter:

• Field size: 124 (degree-4 extension of 31-bits field)
• Rate: ¹/₂
• Number of query: 256
• Poseidon2 parameter (notation following https://eprint.iacr.org/2023/323.pdf)
  • \(n = 31 \ \ t = 16 \ \ d = 5 \ \ R_F = 8 \ \ R_P = 14\)
  • \(p = 2^{31} - 1\) (Mersenne31)

To reproduce, get into the code repository and run:

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 ./bench.sh stwo blake2s $i
    RAYON_NUM_THREADS=4 ./bench.sh stwo poseidon2 $i
done;
python3 render_table.py

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh stwo blake2s $i
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh stwo poseidon2 $i
done;
python3 render_table.py

binius

FRI parameter:

• Field size: 128
• Rate: ¹/₂
• Number of query: 241
• Provable soundness: 100-bits

To reproduce, get into the code repository and run:

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 ./bench.sh binius keccak $i
    RAYON_NUM_THREADS=4 ./bench.sh binius vision $i
done;
python3 render_table.py

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh binius keccak $i
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh binius vision $i
done;
python3 render_table.py

hashcaster

Since hashcaster only implements the PIOP part, the benchmark below uses Binius commitment scheme for it for completeness.

FRI parameter:

• Field size: 128
• Rate: ¹/₂
• Number of query: 241
• Provable soundness: 100-bits

To reproduce, get into the code repository and run:

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 ./bench.sh hashcaster keccak $i
done;
python3 render_table.py

expander

• Poseidon parameter (notation following https://eprint.iacr.org/2023/323.pdf)
  • \(n = 31 \ \ t = 16 \ \ d = 5 \ \ R_F = 8 \ \ R_P = 14\)
  • \(p = 2^{31} - 1\) (Mersenne31)

To reproduce, get into the code repository and run:

cd expander/circuit/
go run gf2_keccak.go
go run m31_poseidon.go
cd ../../
for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 ./bench.sh expander keccak $i
    RAYON_NUM_THREADS=4 ./bench.sh expander poseidon $i
done
python3 render_table.py

Possible further optimizations

• hashcaster
  • Use binius PCS on polyval field directly