# ZK Deep Dive
Created on: 31 July 2023
Author: akashin @ NEAR
Related: [zkwasm sync](https://hackmd.io/MTmmOMOxShaMqMi83bxzRQ)

---

### Theory
- [Gentle intro to SNARKs](https://www.di.ens.fr/~nitulesc/files/Survey-SNARKs.pdf)
- ZK MOOC: https://zk-learning.org/
- KZG commitments: https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html
- Plonk: https://eprint.iacr.org/2019/953.pdf

### Tutorials
- ZK VMs (Polygon Miden): https://www.youtube.com/watch?v=GRFPGJW0hic
- Building opcode compatible zk EVMs: https://www.youtube.com/watch?v=Crzw7ccuHd0

### ZK EVM Materials
- Dev guide: https://zkevm.polygon.technology/docs/introduction
- Spec: https://zkevm.polygon.technology/introduction
- End-to-end life of a transaction: https://zkevm.polygon.technology/docs/protocol/l2-transaction-cycle-intro/
- Proof aggregation: https://github.com/0xPolygonHermez/zkevm-techdocs/blob/main/proof-recursion/v.1.1/proof-recursion.pdf
- ZK Assembly docs: https://github.com/0xPolygonHermez/zkevm-techdocs/blob/main/zkevm-architecture/v.1.1/zkevm-architecture.pdf
- Running a verifier: https://github.com/0xPolygonHermez/zkevm-contracts/blob/main/verifyMainnetDeployment/verifyMainnetProofVerifier.md
- ZK EVM ROM: https://github.com/0xPolygonHermez/zkevm-rom

### PIL
- Tech document: https://github.com/0xPolygonHermez/zkevm-techdocs/blob/main/pil/v.1.0/pil.pdf
- Example programs: https://github.com/0xPolygonHermez/zkevm-proverjs/tree/main/pil
- Compiler: https://github.com/0xPolygonHermez/pilcom
- PIL2 presentation: https://docs.google.com/presentation/d/13nb9Zx1yHTrrXYfowSJZh8bJi0P3Ku7iuOjWmI9Fg-8/edit?usp=sharing

## Meetup topics

#### Modifying the PIL and Processor
> E.g. let's try to add one more register.
> Or let's add a new circuit for hash function like SHA256

#### Benchmarking and profiling proofs
> How do I find out why the proof generation is slow?

#### What can we do with "Compiler JIT bombs"?
> Smart contracts that deliberately try to exploit the prover and increase the proof generation time
> See https://docs.google.com/presentation/d/1n75Mo09HmyruV5S7q0cHWuq-UorrvdG1bRAYTNydBcY/edit#slide=id.g672d2eff65ef7faa_0

#### PIL2 Deep Dive/Future of proving speed
> How can we support large computations (10^8 execution steps)?
> How does the proving time depend on the number of rows/steps in the execution trace?

#### NEAR Contract Runtime overview
> How we pre-process contracts
> The diagram here: https://nomicon.io/RuntimeSpec/Components/

#### How we collaborate going forward
> The focus of NEAR team
> The focus of Polygon team

## Questions

#### ✅ How expensive (how many steps) is it to access external state (e.g. ETH state)?
> What does it depend on? How does size of key and value influence this?
> Can we use Merkle inclusion proofs or do we need to use something ZK-specific?

#### ✅ How can we implement WASM indirect function calls?

Is there a way to find out the current location in the program and JUMP to it?

- Yes, we can use `@label` to get the address of the label and store it in a variable, e.g.:

@label => RR

#### ✅ How will WASM foreign (host) function calls work?
> All functions are described in https://nomicon.io/RuntimeSpec/Components/BindingsSpec/, and they fall into the following categories:
> - [Pure math functions](https://nomicon.io/RuntimeSpec/Components/BindingsSpec/MathAPI): sha256, sha512, keccak256, keccak512
> - [Execution context functions](https://nomicon.io/RuntimeSpec/Components/BindingsSpec/ContextAPI): E.g. `signer_account_id`, `block_index`, `storage_usage`, `gas_used`
> - "Input functions": `input`, `read_register`, `storage_read`
> - "Output functions": `value_return`, `panic`, `log`, `promise_create`, `storage_write`
>
> Implementation: https://github.com/near/nearcore/blob/master/runtime/near-vm-runner/src/logic/logic.rs
>
> - How hard would it be to implement each category?
> - Can we have an escape hatch for things that we haven't implemented yet?

Likely need a dedicated state machine for math functions.

From point of PIL, don't need to implement it, but need to verify it.
E.g. division is hard to compute but easy to verify.

#### ❓ What does the verifier of the proof gets as an input?
> How about recursive proofs?

Previous proof and commitment to the history?

#### ✅ How relevant is the ZK-WASM work from DelphinusLab?
> https://delphinuslab.com/zk-wasm/

- Need to check if this is compatible
- Need to check when will this be production ready

Likely to be used as an inspiration

#### ✅ What are Publics `x` and Privates `w` in case of EVM computation?

Publics would be the old and new state root, transaction root.
Privates would be the actual list of transactions, the execution trace.

#### ✅ How long does the proof generation usually take? What does it depend on?
> - Input size? Transaction complexity? State witness size?
> - What happens during 30 mins of verification [described here](https://zkevm.polygon.technology/docs/protocol/transaction-execution/#verification-on-layer-1)?

Proof generation until recursion is 2.5 minutes for a batch. (Faster CPU on machine -> Faster proof).
Each batch contains many Ethereum transactions. Has limited number of ZK Counters. Related to the number of the rows in the PIL.
A single 256 bit operation - 16 rows (CYCLES?).
Resource consumption depends on the included transactions.
Proving time does not depend on how many transactions are in the batch.

Aggregation of proofs between batches take 15-20 seconds

Final aggregated proof translated into SNARK.

Ethereum has 30M Gas limit. There are limits per operation time.
Dynamic proofs will allow to process larger.

#### ✅ How is well-formedness/validity of transactions proven?
> The parts that happen outside of WASM VM, e.g. signature validation, balance checks, WASM syntax and limits checks.

Needs to be expressed as ZK circuit. E.g. this is done for consensus rules of Ethereum.

#### ✅ What is the number of rows in PIL (2^10 in pil.pdf)?
> - Does it limit the max possible size of the program?
> - How do you select this number?

First, you could define number of rows in PIL1 and PIL2, in PIL1 only has one number of rows but in pil2 you could decide for each subproof how many rows want. In production, with PIL1 we have 2^23 rows. This number of rows determines how many resources (arithmetics, binaries, keccaks) we have.

We select this number considering size, cost, time, etc.. In PIL2 with vadcops you could divide the zkevm in some subproofs (as state machines). Each subproof has one or more numbers of rows (for example, S (2^16), M(2^23), XL(2^25),...) but not only this, you could aggregate subproofs of same or different size.

For example, I need more than 2^24 rows of binary (2^24 + 2^15), I have some options:
1 subproof of XL (51% of use)
3 subproofs of size M (67% use)
2 subprofs of size M + 1 subproof of size S (99% use).

#### ✅ How does zkASM relate to PIL?
> Is it built on top of it?

With zkASM generates columns (pols) of ROM, these cols are used in constraints of PIL to verify the program trace. We could make a specific meeting to show you some examples of this.
Really zkasmcom is a tool to generate the ROM fixed cols (constant pols), but you could generate these cols by hand but it would be very tedious and complex (label, variable addresses, etc..). The zkasm makes the ROM more readable and auditable.

#### ✅ What is in the output of PIL compilation?
> What is in the file `out.pil.json`?

Constraints in a convenient format? (https://zkevm.polygon.technology/docs/zkProver/overview#microprocessor-state-machines)

#### ✅ What is [Bridge's Global Exit Merkle Tree](https://zkevm.polygon.technology/docs/protocol/transaction-batching#globalexitroot)?

Should be answered in https://zkevm.polygon.technology/docs/protocol/exit-tree