# ZKEVM Proof System Customisation

Targets:

* __RU__: Rollup
* __VP__: Validity Proof

_List below is not ordered in any manner such as priority or difficulty_

## 1. Implement Linearization

Target: __RU__, __VP__

Currently linearization technique is not implemented in halo2. So it is required to to send all even fixed column evaluations to the prover. In order to reduce size of proof as well as verifier group operations. This can be done with two ways. We can customize prover after our circuits are finalized. And second is we can implement auto linearisation that would work with all any circuit.

## 2. BLS12 Integration for KZG

Target: __RU__, __VP__

> For __VP__ Why it is better to have pairing based proof system where we can use halo2 as is?

For __RU__: BLS12 support will even eventually arrive at EVM and we will probably have cheaper group and pairing operaitions than we have with BN256. However until then we are good with BN256.

## 3. Implement Z(X) Based Multiopen Strategy for KZG

https://hackmd.io/@tompocock/shplonk
https://zcash.github.io/halo2/design/proving-system/multipoint-opening.html

Target: __RU__, __VP__

For __RU__: In BN setting we try to avoid G2 operations so batch opening technique that takes place in plonk paper is probably the best. But there is a cool trick to validate G2 operations using pairing and G1 add and mul precompiles. We should calculate the trade off between adding few pairing terms and g1 operations to use Z(X) and multiopening without G2 operations.

## 4. EVM Compatible Transcript

Target: __RU__

* Add keccak256 and sha256. Currently we only have blake2 in halo2.
* Add uncompresed point read/write in order to avoid expensive point decompression in EVM.

## 5. EVM Verifier

Target: __RU__

After we our state and execution circuits are finalized we need to implement EVM verifier under KZG and BN254 setup. This would be probably much more specialized verifier than generic one in halo2 library.

## 6. FRI Integration

Target: __VP__

> Explain why?

## 7. KZG Integration

Target: __VP__, __RU__

We have added KZG multiopen to halo2 library that currently only supports BN256 curve.

https://github.com/kilic/halo2/tree/kzg

It needs to be merged with new updates in halo2 library.

## 8. Implement Semi-Recursive System

Target: __VP__, __RU__

I have just made up the term semi-recursive that defines a system where we verify some part of proof in a circuit and defer pairing out of the circuit to L1 for example. I think this is what aztec applies in their proof system.

Also Stark verifier approach is intoruced by Hermez https://youtu.be/17d5DG6L2nw?t=1764

If applied, we can reconsider Z(X) Based Multiopen Strategy for __RU__ since G2 ops are moved to the circuit.

## 9. Public Inputs

Figure out how to feed public inputs in verifier side.

There are two ways:

First is the how it is done in halo2 library:

__Prover__:

* sends evaluations of public input polynomial

__Verifier__:

1. commits to public input polynomial.
2. adds commitment to the transcript and squeeze the evaluation point
3. checks circuit equation with public input evaluations
4. checks the opening public input polynomial

This is efficient in recursion context (I think only for two layer) to avoid hashing many things in the circuit

And second way is closer to the plonk paper:

__Prover__:

* sends nothing about public inputs

__Verifier__:

1. adds public input values to the transcript and squeeze the evaluation point
2. calculates public input evaluations
3. checks circuit equation with public input evaluations

For second method see [experimental PR](https://github.com/zcash/halo2/pull/358/commits/5add9da7ebf3405adc8087071fe310790b80af25) in halo2 repo and see how to [calculate public input evals](https://github.com/kilic/halo2/commit/6ff719d8836381d44d4a866d2dd44300156762f6) with halo2 tooling.

This is efficient when we want to avoid group operations in verifier side