## Current benchmark

| | [Scroll](https://github.com/scroll-tech/halo2-snark-aggregator) | [PSE](https://github.com/han0110/plonk-verifier) |
| --------------------------------------------- | --------------------------------------------------------------- | ---------------------------------------------------------------- |
| **Circuit** | | |
| Ec scalar mul <small>(row)</small> | 83501 | 70804 |
| Multi ec scalar mul <small>(row)</small> | ? | 27333 (<small>^10933055/₄₀₀</small>) |
| Maximum columns | ? | 4549 (<small>^2²⁷/₂₉₅₀₀</small>) ¹ |
| **Solidity** | | |
| Aggregation verification <small>(gas)</small> | 1058k ² | 570k ³ |

<div class="table-footnote">

1. Using plookup instead of builtin subset argument, we can manage to constrain the aggregation circuit's degree to 3, so we can have maximum circuit size 2²⁷ on BN254. Considering other overheads (e.g. transcript), in PSE I try to measure it with 29500 as amortized column cost.
2. 1058k is taken from the git commit message of [`56b47fe`](https://github.com/scroll-tech/halo2-snark-aggregator/commit/56b47fed4d21e342d781b531174a73c1f535bc36) on 07/05.
3. 570k has zk disabled and plookup instead of subset argument, but hasn't included other public inputs (e.g. txs and block). This cost (570363 to be precise) could be further split into 3 parts (the less Rest means the less overhead):
<br>
| | Gas | Percentage |
| ----------------------- | ------------------------------- | ---------- |
| Intrinsic + Calldata | 82488 (21000+4032\*15.25) | 14.46% |
| EcMul + EcAdd + Pairing | 443300 (52\*6100+52*250+113100) | 77.72% |
| Rest | 44575 | 7.82% |

</div>

## Feature

- [ ] 1. Challenge API ([under review](https://github.com/zcash/halo2/pull/593))
- [ ] 2. Optional ZK ([wip](https://github.com/privacy-scaling-explorations/halo2/pull/76))
- [ ] 3. Zigzag grand-product (nth <span class="highlight">2. Optional ZK</span>) [^zigzag-trick]
- [ ] 4. Zigzag plookup argument (needs <span class="highlight">1. Challenge API</span>, nth <span class="highlight">3. Zigzag grand-product</span>)
- [ ] 5. Fflonk
- [ ] 6. Low hanging fruits
- [ ] Evaluate instance column directly ([implemented](https://github.com/han0110/halo2/commit/190c7c9687c0880a04600665fe8e39a61b9ccade))
- [ ] Remove the extra ec scalar mul in current SHPLONK implementation by using ascending power instead of descending ([implemented](https://github.com/privacy-scaling-explorations/halo2/pull/84/commits/ad53e9824eaaabf71f2e41763f1f63aad225f87b))

[^zigzag-trick]: See [this note](https://hackmd.io/KEOGZeaWQle9-Y8cNwR5rQ?view) for more information about zigzag trick.

## Target

### Constraint system

To get rid of undesired overhead, the ideal constraint system for ZKEVM is to have:

- <span class="highlight">2. Optional ZK</span>

For FSM-like circuits (EVM, State, Bytecode, etc...), it saves 1 degree and will be beneficial for circuits that have so many state (especially EVM circuit).

- <span class="highlight">3. Zigzag grand-product</span>

In general it saves evaluations, with <span class="highlight">2. Optional ZK</span> it saves 1 degree and then saves grand-product polys.

- <span class="highlight">4. Zigzag plookup argument</span>

When lookup to the same table, plookup is more efficient than builtin subset argument, it save permuted table polys and evaluations.

### Aggregation circuit

TODO

### Solidity verifier

Currently `MainGate` + `RangeChip` with zk disabled costs ~570k gas to verify. If we need multiple pairs of `MainGate` + `RangeChip` to make aggregation circuit capable to aggregate all circuits, we can simply add another layer of `MainGate` + `RangeChip` to aggregate the aggregation circuit, to make solidity verifier cost to be always ~570k.

If we want to further lower ~570k down to smaller number, we can finally add another aggregation cirucit that uses <span class="highlight">5. Fflonk</span> protocol, and it should be reduce roughly to ~300k.

{%hackmd C0hM4L6mT9-5XXfjBXmAxA %}

<style>
.highlight {
font-size: 75%;
font-weight: bold;
background-color: #eac545;
padding: 0.2em 0.5em;
margin: 0;
border-radius: 0.25em
}
</style>