# Nova benchmarks summarization

Here's a list of some of the benchmarks we've been taking to better understand how Nova performs vs other proof systems.

*NOTE: Disclaimer - these benchmarks are preliminary and should be taken with a grain of salt. Some shortcuts were taken as these were done and we want to check the correctness of these calculations before being 100% confident in them.*

## Pure hashing

### Nova

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

| Size | Constraints | Time |
| ---- | ----------- | ----- |
| 64B | 55k | 53ms |
| 128B | 82k | 59ms |
| 256B | 135k | 77ms |
| 512B | 242k | 106ms |
| 1KB | 456k | 182ms |
| 2KB | 883k | 320ms |
| 4KB | 1.7m | 521ms |
| 8KB | 3.4m | 1s |
| 16KB | 6.8m | 1.9s |
| 32KB | 13.7m | 4.1s |
| 64KB | 27.4m | 7.7s |

### All
| Size | Constraints | Nova Time | Starky Time | Halo2 Time |
| ---- | ----------- | ----- | ----- | ----- |
| 64B | 55k | 53ms ||
| 128B | 82k | 59ms ||
| 256B | 135k | 77ms ||
| 512B | 242k | 106ms ||
| 1KB | 456k | 182ms ||
| 2KB | 883k | 320ms ||
| 4KB | 1.7m | 521ms ||
| 8KB | 3.4m | 1s || ~100s(**wo lookup**) ~1.6s(**lookup**) |
| 16KB | 6.8m | 1.9s ||
| 32KB | 13.7m | 4.1s ||
| 64KB | 27.4m | 7.7s | 8s (Memory 16GB) |

## Recursive hashing

Recursively hashing of SHA256 $k$ times. That is, computations of the form $h(h(h(h(h(x)))))$.

This also show how doing many recursives hashes in a single fold in Nova improves performance. That is, turning expression above into:

$$h(h(h(x))) \text{(d times)}\rightarrow h(h(h(x))) \text{(d times)} \rightarrow \dots$$

With the same number of recursive hashes, just batching more in a single fold.

Rationale: Similar to https://github.com/celer-network/zk-benchmark but doing hashing recursively to take advantage of Nova+IVC.

Code: https://github.com/privacy-scaling-explorations/nova-bench

#### Proving systems

| Framework | Arithmetization | Algorithm | Curve | Other |
|------------------|-----------------|-----------|--------|--------------|
| Circom (snarkjs) | R1CS | Groth16 | Pasta | |
| Nova (seq) | Relaxed R1CS | Nova | Pasta | |
| Nova (par) | Relaxed R1CS | Nova | Pasta | parallel PoC |
| Halo2 | Plonkish | KZG | BN254 | |

### Prover time

#### Powerful laptop

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

| k | Circom | Nova (total) d=1 | Nova (step sum) d=1 | Halo 2 (KZG) |
|-------|--------|------------------|---------------------|--------------|
| 1 | 0.3s | **0.2s** | **0.1s** | **0.8s** |
| 10 | 7.3s | 2.4s | 1.2s | 0.8s |
| 100 | 62s | 24s | 12.5s | 1.6s |
| 1000 | - | 240s | 125s | 25s |

#### Powerful server

Hardware: Server with 72 cores and ~350GB RAM.

| k | Nova d=1 | Nova d=10 | Nova d=100 | Nova d=100 par | Halo 2 (KZG) |
|---------|----------------|-----------|-------------|----------------|--------------|
| 100 | 19s | 3.6s | - | - | 2.5s |
| 1000 | 190s | 36s | 26.5s | 28.5s | 41.6s |
| 10000 | 1900s | 360s | **265s** | **226s** | **389.1s** |
| 100000 | 19000s | | | | ? |

### Memory usage and SRS

#### Powerful server

Hardware: Server with 72 cores and ~350GB RAM

| k | Nova (seq) d=1 | Halo 2 (KZG) | Nova (par PoC) |
|---------|-----------------|--------------|-------------|
| 100 | 1.6GB | 3.7GB | 9GB |
| 1000 | 1.6GB | 32GB | 244GB |
| 10000 | 1.6GB | 245GB | OOM |
| 100000 | 1.6GB | ? | ? |

### Conclusion

Based on the above we draw the following conclusions:

1. **Nova is memory-efficient.** For large circuits this matters a lot, where Circom and Halo2 both require a big SRS and run out of memory. This is especially important in low-memory environments.
2. **R1CS vs Plonkish matters a lot.** Plonkish with lookup tables leads to a much faster prover time for Halo2 (KZG) with e.g. SHA256 recursive hashing for d=1. This motivates work on alternative folding schemes, such as Sangria.
3. **Be mindful of constraints vs recursion overheard.** For SHA256 and d=1 the number of constraints isn't big enough (~30k) compared to recursive overhead (~10k) to see huge performance gains. As we increase to d=10 and d=100 we see how Nova starts to perform better than Halo 2 (KZG). This suggests that we want to use somewhat large circuits for Nova folding.
4. **For large circuits, Nova appears to be faster than Halo2 (KZG)**. We see that even with less than perfect parallelization, we get ~35% improvement over Halo2 for 10 000 recursive hashes.
5. **For pure and small circuits** Nova appears to be faster than Halo2, for Halo2 can not take adavantages of lookup.

## reference
https://hackmd.io/0gVClQ9IQiSXHYAK0Up9hg?view=
https://hackmd.io/u3qM9s_YR1emHZSg3jteQA