Native Nova SHA256 bench

Context: See https://hackmd.io/0gVClQ9IQiSXHYAK0Up9hg?view= for previous Nova benchmarks, with more of a focus on recursion.

Hardware: Macbook Pro M1 Max (2021), 64GB memory.

Native Nova SHA256 benchmark with varying preimage.

Code: https://github.com/srinathsetty/Nova/blob/main/benches/sha256.rs

Comment

• Using native Nova and Bellperson SHA256, not via Nova Scotia
• Size is preimage for sha256, not proof size
• Constraints is per step (primary circuit), secondarty circuit is constant ~10k constraints
• A single fold, no recursion

Comparing with Celer Network Benchmarks:

• https://github.com/celer-network/zk-benchmark
• Hardware: MBP but M1 vs M1 Max, e.g. 16GB memory
• Starky also takes ~8s for 64KB preimage size (same)
• Halo2 and Plonky takes ~100s for ~8KB preimage size (100x faster)

Comparing with Nova Scotia SHA256:

• See https://hackmd.io/0gVClQ9IQiSXHYAK0Up9hg?view=
• Multiple SHA256 hashes (p=100), also single fold (k=1)
• Written in Circom
• 2.9m constraints
• 635ms for prove step (base case)
• If done recursively (e.g. 10 or 100 folds) then each recursive proof step is ~2s, x5 base case
  • appears to expand, from 1.3s to 3.1s - leak?

Comparing Halo2 SHA256 benchmarks:

• In varying preimage size case 8KB takes ~100s
• 8KB SHA256 takes ~3m constraints in R1CS
• For recursive hashing case ~3m constraints gives you 100 hashes in one fold
• With 100 hashes using lookup tables Halo2 takes ~1.6s
• I.e. a ~100x difference, which explains disparity

Tldr (tentative):

• Can reproduce Nova native benchmarks x100 faster than Plonky/Halo2 and on par with Starky
• For same number of constraints and no recursion prove step same prover speed for Nova Scotia and Nova
• Recursion overhead ~x5 more than base case in each step
• Lookup tables seems to have made Halo2 KZG x100 diff
• Using Circom toolchain takes long time to get many constraints (>3m) into circuit
• Doing 100 hashes in a circuit vs varying preimage size different problems

Things to follow up / answer:

1. Why and when would we not stick as much as possible into a single fold?
2. Reproduce preimage hash bench with Nova Scotia and e.g. rapidsnark toolchain
3. What would a better recursive benchmark look like that can't easily be solved with e.g. lookups?