# Benchmarking mv-lookup vs halo2-lookup (based on Keccak circuit)

## Code

Source code repository: github.com/aleph-zero-foundation/zkevm-circuits, branch `mv-comparison` ([direct link](https://github.com/aleph-zero-foundation/zkevm-circuits/tree/mv-comparison)).

Beneath it uses a bit modified `halo2_proofs` library from github.com/aleph-zero-foundation/halo2:
- branch `pse-mvlookup` uses mv lookup mechanism in the PLONK prover
- branch `halo2-lookup` uses standard halo2 lookup mechanism in the PLONK prover

## Benchmarking

We compare both mechanism under two configurations:
- 12 rows per round
- 25 rows per round

Every experiment was run 10 times.

Measurements:
- time of key generation
- time of the first phase of proving (prover-type-independent)
- time of the second phase of proving (commiting, prover-type-dependent)
- counting MSMs and FFTs during the first phase of proving

Benchmarking machine: AWS EC2 t3.2xlarge (8vCPUs, 32GB memory).

## Results

MSM count
| | Halo2 | MV | Ratio | Speedup |
| -------- | ------- | ----- | ------ | ------- |
| 12 rows | 576 | 332 | ~57.6% | x1.73 |
| 25 rows | 301 | 179 | ~59.5% | x1.68 |

First phase time (s)
| | Halo2 | MV | Ratio | Speedup |
| -------- | ------ | ---- | ------ | ------- |
| 12 rows | 105 | 64 | ~61% | x1.64 |
| 25 rows | 53 | 40 | ~75.5% | x1.33 |

Whole procedure time (s)
| | Halo2 | MV | Ratio | Speedup |
| -------- | ------ | ---- | ------ | ------- |
| 12 rows | 133 | 96 | ~72% | x1.39 |
| 25 rows | 82 | 77 | ~94% | x1.06 |

## Raw (average) results

### Halo2 / 12 rows

MSM_COUNTER: {32768: 576}
FFT_COUNTER: {32768: 572, 131072: 573}

key_generation: 3274.1ms
second phase reached after: 108185.1ms
whole process: 133206.5ms

### Halo2 / 25 rows

MSM_COUNTER: {32768: 301}
FFT_COUNTER: {32768: 297, 131072: 298}

key_generation: 2395.9ms
second phase reached after: 55114.2ms
whole process: 82336.8ms

### MV / 12 rows

MSM_COUNTER: {32768: 332}
FFT_COUNTER: {32768: 327, 131072: 328}

key_generation: 3346.8ms
second phase reached after: 67830.1ms
whole process: 95565.9ms

### MV / 25 rows

MSM_COUNTER: {32768: 179}
FFT_COUNTER: {32768: 174, 131072: 175}

key_generation: 2816.6ms
second phase reached after: 42131.6ms
whole process: 77106.7ms