# ZKEVM Meeting Notes

Call link: https://ethereumfoundation.zoom.us/j/96738752557?pwd=eUVMZEdwSS9IcEtJVmVRU3JrWVJHUT09

## 24th Dec 2021

### Attendants

Han, Shin , Chih-Cheng

### Updates

- Shin
- intro assembly to field arithm (in review by Onur)
- prover function optimization (Bretch proposed an )
- working on FFT, comparing algo
- Han
- impl CALL and
- refactor the sepc of the state circuit with mainly rationale https://hackmd.io/VCGteyZEQFKUjHA_A72f1Q
- sorting account address
- call context or tx access list
- miha
- MPT
- finished the refacoritng rm nibbles
- rebase branch to to use new applyzkp halo2 version
- impl supoprt for adding new leaf to tree (current has updating only)
- impl support for adding leaf to a branch that has 2 leaves
- cc
- merged

Edu has been on state circuit busmapping too

## 17th Dec 2021

### Attendants

Han, Barry W, Miha S, Edu, Shin, Thore H, Marios, Chih-Cheng, Onur, YingTong

### Updates

- Shin
- assemply on field arithmetics
- cc
- working with Carlos on refactoring state input
- wokring on flags to enabling a chip
- Marios
- Devops group:
- VPN account working. access to our private network
- EVM circuit benchs
- TODO: thore reach out to jamie for Marios repo access
- Carlos
- intermediate chips copy the states.
- benchmarks on shin's PR
- Edu
- merge the integration test with Geth
- merge PR that using CIB
- reviewing Carlos's pr on bench
- meeting with Han to learn requirement for the circuit input
- working on BEGIN_TX
- Han
- Working on the `CALL`
- fullfill Call context on busmapping
- RETURN and REVERT https://github.com/han0110/zkevm-specs/tree/feature/return-and-revert
- Onur
- BigInt construction.
- Created some edge cases.
- Point assertion: if some point is on cureve or not
- 100k rows for a single ECC mul
- miha
- MPT
- refacotr to remove nibbles
- looking into Halo2 rm poly extension domain

YT: We have CI bench on upstream Halo2 https://github.com/zcash/halo2/pull/421

Edu: concern using Github CI, since it runs on different server everytime. We might lose consistency

### Discusion

#### Missing piece of working POC

- need EVM with CALL and RETURN

#### Fetch upstream again

- Assign cell would be convenient
- Onur can look into it again

#### Periodically Benchmark ?

#### next 2 Call

24th optional
31th cancel

#### License

YT: extrmemly optimistic. expect Jan under MIT

## 10th Dec 2021

### Attendants

Han, Barry W, Miha S, Edu, Shin, Thore H, Marios, Chih-Cheng

### Updates

- Shin
- integration testing in container
- introduce Assembly to speedup Mulmod arith in fft
- ext team reported some issue
- Edu
- Spent time on learning plonk and halo2
- Continued Shin's Geth integration.
- Move all the code to deploy contract and transaction from TS to Rust.
- We can run Geth in dev mode, we can do in reproducible manner
- use rust RPC to get it working
- future work:
- use geth to generate circuit input
- operation in state circuit
- preparing integration test with CIB
- creating a coordinator
- cc
- Keccak base conversion config
- han
- impl CALL https://github.com/han0110/zkevm-specs/blob/feature%2Fcall-and-stop/src/zkevm_specs/evm/execution/call.py and markdown spec is WIP
- impl STOP. multi step involved
- scroll propose a note https://hackmd.io/kHUvMYrcTlqaHm_0nvrE7A?view
- miha
- generalization of leaves
- RLP has 2 or 3 bytes metadata
- move to extension nodes, adding new storage slot. The proof is differnet in left/right proof.
- Marios
- almost done syncing geth archival node.
- next: debug mode in Geth
- devops: a security group/ template for everyone to deploy a secure instances

Carlos and Onur didn't make it today
- carlos
- Filed two issues for keccack which I started to impl already and that are needed for the entire keccak.
- Would be nice if CC could address them for Rho and Pi
- onur
- I was half offline this week but I worked on some edge cases in non-native implementation regarding ranges and lazy reductions. I'm about to finalize it then get back to ecc multiplication.

### Discussion

#### Prover rotation optimization

Caching to reduce memory

only an issue, no PR yet. https://github.com/zcash/halo2/issues/418

Put some bench in CI to tell if we have regression

#### Multi-step opcode

## 3rd Dec 2021

### Attendants

Han, Barry W, Miha S, Edu, Kev W, Shin, Thore H, Carlos P, Marios, Onur, Chih-Cheng

### Updates

- Shin
- geth integration PR
- memory consumption?
- cc
- base converion circuits for keccak
- edu
- updated busmpaing CIB generates more fields required by the circuit
- progress in integration test: helping Shin for RPC method for geth
- onur
- edge cases big integer arithmetics
- ECC adding (double/add merged)
- progressing on scaler multiplication
- WF formula that aztec use?
- cp
- keccak integration
- WIP PR rebased to main
- refactor the configs
- han
- rebased PR to main
- complete begin tx impl
- spec is ready too
- marios
- AWS for POC
- have few geth nodes syncing
- miha
- tranistion from storage to state trie
- RLP for nonce and balance. Iterate 32 columns
- RLC

### Discussion

#### Bench EVM circuit

500k gas in 10 hrs

## 26th Nov 2021

### Attendants

Han, Barry W, Miha S, Edu, Kev W, Shin, Thore H, Carlos P, Marios, Onur

### Updates

- Shin
- Benchmark and docker
- Edu
- Add missing fields of witness in `bus-mapping`
- Key value DB in `bus-mapping` for querying intermidiate state when parsing trace
- Carlos
- Put everything together of keccak circuit
- Test passing iota and absorb
- Onur
- ECDSA implementation
- Han
- Add missing table and partially integrate with `bus-mapping` for EVM circuit in [#PR196](https://github.com/appliedzkp/zkevm-circuits/pull/196)
- Refactor and remove partially impmeneted execution result in zkevm-spec [#PR52](https://github.com/appliedzkp/zkevm-specs/pull/52)
- Miha
- Random linear combination in MPT circuit

### Discussion

## 19th Nov 2021

### Attendants

Chih-Cheng L, Han, Barry W, Miha S, Edu, Shin, Carlos P, Marios, Onur.

### Updates

- Shin
- evm and prover container
- next week
- benchmark
- Edu
- all opcode implemented in circuit are also implemented busmapping
- error evm
- balance check
- address check
- Carlos
- keccak
- need to conditional activate absorb
- busmapping
- jsonrpc call
- eip1186 support eth get proof
- Marios
- investigate node sync
- cc
- rho gate bench
- rho gate debugging
- Onur
- shplonk
- prepared a toy implementation
- looking into ECC and wrong field
- ECDSA
- impl ECC API
- Han
- add missing part in evm circuit
- begin_tx implmentatation
- Miha
- RLC on branch
- Compression
### Discussion

#### How many opcodes do we able to process?

#### Columns are expensive in ECC, probably need to simplify keccak somehow

MPT now have the most columns

#### Checking state change in busmapping

## 12th Nov 2021

### Attendants

Chih-Cheng L, Han, Barry W, Miha S, Edu, Kev W, Shin, Thore H, Carlos P, Mary M, YingTong L.

### updates

- Shin
- lookup2
- cc
- rho gate merged
- updated keccak cost analysis
- carlos
- keccak
- mixing config
- supporting lookup advice column in halo2
- PR open https://github.com/appliedzkp/halo2/pull/5
- reviewed PR for edu and cc
- onboard Mario:
- RPC endpoint, throughput, prover, optimized the code
- edu
- completed the refactoring of busmapping.
- made a split for the type received from geth
- use the web3 crate (use the primitive types)
- han
- CALL spec
- found an issue in PUSH https://hackmd.io/U9KZb94nSfOdsdsKVOfH5A?view
- miha
- mpt branch
- stuck on some issue of lookup and random linear combination

### follow up

- ~~shin talk to yt and onur on the proposal to implemnt kzg as independent crate instead of maininting a full halo2 fork.~~
- license

### Discussion

#### Change to halo2 libarary API, KZG

yt: prefer using beta version halo2

#### Prover complexity

yt: haven't estimated for proof size

barry: how to convert rows and columns into proving time

#### Milestone

targeting a simple transfer

## 5th Nov 2021

### Attendants

Chih-Cheng L, Han, Barry W, Miha S, Edu, Kev W., Shin, Thore H.

### updates

- Onur
- Implemented `assert_zero`, `is_zero` and `assert_equal`, `is_equal` `assert_not_equal`, `division` and `inversion` constaints for the base field.
- Started to implement ecc operations:
- Addition, doubling and conditional brancing where we need to constrain doubling instead of additional f point_a = point_b.
- Also unimplemented ecc traits are added. Now ecdsa and recursion can be implemeted with these.
- Scroll Tech team pushed their [first PR](https://github.com/kilic/halo2wrong/pull/4) to wrong field repo for division and inversion operations in non native field
- Also today started to revisit shplonk to make it g2 free and see if it is worth to use eventually.
- CC
- rho gate ready for review
- next week: keccak cost
- Barry
- ext contributor on ECDSA trait
- Edu
- laying out the structure for building the circuit input.
- Circuit input builder
- before: trace from Geth
- after: from block take each of tx, and get each of steps.
- challenge
- can't get the storage operation
- concepts
- Context:
- for example address of the storage operation
- output of the circuit builder
- web3 types
- we can use the web3 crate for web3 types
- Shin
- working on KGZ branch
- proposal to implement kzg as independent crate instead of maintaining a full halo2 fork.
- Han
- transaction part
- review scroll's JUMP and CALLDATALOAD
- Miha
- MPT circuit
- looking into the contraint of branch hashing

### Discussion

#### if random linear combination on 532 bytes unsafer than 32 bytes (bytes are all range checked to fit 8-bit)?

barry, kev: don't think so. (consult Mary on this)

#### How do we measure the cost of the circuit?

We know the

- number of roots of unity we need to use

depends on the custom gate we are using.
degree of the equation n -> 16n

#### fflonk

2 pairings + scaler* n_customgates

### follow up

- slow testing https://github.com/zcash/halo2/issues/398
- calldata compression (public input)
- no progress this week
- ECDSA
- external team is on it
- license
- monthly release
- do one for opcode progress last month

## 29th Oct 2021

### Attendants

Chih-Cheng L, Han, Barry W, Miha S, Onur K, Edu, Ying Tong

### updates

- cc
- progress in rho steps
- next week: action on keccak cost again
- edu
- PR refacoter in busmpaping side to easyly writing new opcode
- introduce a new concept: context
- converting busmapping into circuit input builder: a new struct. a new pr coming
- onur
- kzg pr, keccak pr
- yt suggested to change trait bound
- draft on verifier cost on kzg and G2 free setup https://hackmd.io/2Fg8SREJSTG3rymPqixogg?view#Cost-analysis
- maximum value support
- no update from Xin
- Kev and recursion: no update
- han
- reviewing PR
- think about opcode loading. got some feedback on Call from scroll team
- miha
- witness generator and circuit
- look into halo2

### Discussion

#### When is a good time to work on ECDSA component?

onur: after Onur and Xin prepare the trait

barry: need to find someone on it

#### CALLDATACOPY proposal from scroll team

han: I think taht's good

In `CALLDATACOPY` draft https://hackmd.io/@gaswhat/SyfGp9_UF there are some questions in the end that might need some more thought and feedback.

#### MPT

miha: keccak will be the dominating factor of cost

#### License

yt: no update

## 22th Oct 2021

### Attendants

Chih-Cheng L, Han, Barry W, Miha S, Onur K, Edu, Ying Tong, Thore, Carlos P, Kev W.

### updates

- cc
- progress in keccak rho gate: assign region, unblocking the integration work.
- closing stale spec issues
- edu
- Bus mapping.
- preparing a doc: Witness generation flow https://hackmd.io/eAXcIw_sRjK7hP-NSGEJUg?both
- han
- Finished the EVM PR, ready for review. https://github.com/appliedzkp/zkevm-specs/pull/52
- A md spec for that EVM PR too. https://hackmd.io/1RXDCPagQNOAT04yA_zPKA
- cp
- go traces for tests.
- keccak PR for Xi and iota merged. On putting all together now
- figuring a archtecture for RPC client
- onur
- keccak transcript for halo2, ready for review
- PR for kzg https://github.com/appliedzkp/halo2/pull/1
- (Xin is working on MUL)
- miha
- MPT PR https://github.com/appliedzkp/zkevm-circuits/pull/132

### Agenda

#### Proof aggreation circuit, cost analysis. This affects whether we go copy-constain-heavy layout or custom-gate-heavy layout (cc)

onur: Primitive not completed yet. No spec yet, need to think about it more.

Can make a draft how to veryfy kzg in circuit, and it could tell us more about the aggreation circuit.

barry: can we create a crate for an example?

Onur: it's doable. need a small spec. recursion circuit depends on gates, columns of other circuit. It could out of halo2 lib.

We can do auto-generated aggregated circuit. take keys as input

YT: we don't verify things in the circuit yet.

YT: aggregation circuit === verifyer circuit? Onur: yes

kev: is the strategy that Hermez use in the cost reduction trick used here?

cp: they use FRI outside.
kev: use groth16 to verify STARK

#### 2 epic size PRs to review (probably need to assign someone for reviewing them)

- https://github.com/appliedzkp/halo2/pull/1 (YT)
- https://github.com/appliedzkp/zkevm-specs/pull/52 (invite ext team to help reviewing)

#### Toughts on busmapping (Edu)

now: taking tx -> trace steps
future: taking block(s) -> txs -> trace steps

#### Do we require recursion for the proof to be cheap (kev)

barry: recursion is for proof but not for call and txs

#### Proof for multiple blocks? (CP)

barry: don't think we are likely do to multiple blocks

han: multiple blocks more complexity, need to think more ...

#### Licence update?

YT: no

#### communication with ext team

cc: improve spec writing

barry: do they need to spec something on busmapping?
cp: don't think so

## 15th Oct 2021

Attendants: Chih-Cheng L, Han, Barry W, Miha S, Onur K, Edu, Ying Tong, Thore, Mary M. Carlos P.

### updates

- cc
- WJ hello world
- onur
- ecc, doubling, addition, group operation
- edu
- merged pull request SLOAD, busmapping. #116
- reviewed a PR from Brecht #91
- Carlos
- keccak, xi, iota13, and iota9. absorb should be done soon
- onboard rahul on busmapping
- call context part
- Han
- figuring out the CALL. spec PR on EVM circuit #52
- Miha
- reviewing
- impl MPT circuit. Concerned about the layout a bit.

### Agenda

- strategy for maintaining the KZG fork
- move to azkp repo
- constantly merge upstream https://die-antwort.eu/techblog/2016-08-git-tricks-for-maintaining-a-long-lived-fork/
- remaining issues:
- [easy] replace blake with keccak
- ~~[medium] halo2's public inputs are committed at verifier side~~
- proof aggregation circuit: to handle many columns and custom gates

#### Issue of Mockprover long testing time.
https://github.com/zcash/halo2/issues/377

#### Chance to contribute back to halo2

gadgets and abstractions we do

#### MPT trade off

#### Are we plaining for audit some later day?

Bary: yes

yt: zcash has gone thoruhg 1 round of ext audit. Some bug are not obvous to anyone. Some part of rust outside of the circuit (has type check), and some inside the circuit (has no types enforced). Can consider an internal audit.

cp: need an example of the bug (https://github.com/zcash/orchard/pull/209)

barry: any idea how to setup an audit process.

yt: pairing review. 2 peopl reviewing a pr they don't write. best with spec.

barry: on going process?

yt: post merged review on PR that hasn't changed much.

yt: fun friday that I can do anything on friday.

#### license

yt: cautions optimistic on MIT but don't know when

#### What's the aggregator circuit

yt: Does aggregator circuit need to do wrong field aggregation?
onur: yes

circuit aggregated bn point in bn scalar field.

### Action

- edu
- figuring out the archtecute for busmapping. We now only consider the traces, but we need to consider tx too.
- carlos
- keep helping on the keccak
- studying call and delegate call, and execution.
- cc
- the halo2 fork and probably pairing fork
- yt
- share the auditted bug example https://github.com/zcash/orchard/pull/209

write down some thing about aggregator circuit

## 8th Oct 2021

Attendants: Chih-Cheng L, Han, Barry W, Miha S, Onur K, Edu, Kev, Ying Tong, Thore

### Updates

- edu:
- sload and sstore opcode for busmapping
- cc:
- slow progress in keccak rho steps
- reviewed the BYTE opcode/sepc and circuit.
- carlos
- keccak xi steps
- onur
- non-native field. EC operations
- next week: doubling
- exponentiation
- endomorphism
- exponentiation + endomorphism
- han
- digging into tx and call
- self-destruct
- write some python code to see if those are runnable
- miha
- MPT
- working on a conceptual circuit implementation

### Discussion

#### Verifier cost of the column

onur: more columns means we have more commitments to open
yt: need to fact check this and get back

#### EC operations

yt: ochard has EC gadgets, why don't we use those?
onur: Because we need non-native EC gadgets. We can't use those gates, since we are using bn254

#### Proofs

aggegrating proofs
recursion: efficient but preventing paralleling

Aztec style recursion, that can be checked with 1 pairing and works in evm

#### Miha's update on MPT

>A bit of an update on mpt: in https://github.com/miha-stopar/mpt/blob/main/witness/witness_test.go there are a couple of examples how to generate witnesses and also the simulation of constraints.
> I think this approach should cover all scenarios - we first get the proofs via RPC eth_getProof for the storage slots that are going to be modified. For all the modifications, we then maintain the state internally and are getting the proofs from this internal state.
> The code is based on https://github.com/geohot/cannon and a fix from Han (https://github.com/geohot/cannon/commit/a15f4a34e4b6cf75574742c24e4176fb36f6e70a).
> At first I tried to maintain internally only the trie, but it makes it easier to have a statedb too. So, the approach is now using statedb as a wrapper around the trie and we are making modification via statedb. Quite some properties and functions in statedb and trie have been made public to enable modifications.
> When thinking about the witness generation some problems appeared but then I realized these could be solved by changing the approach of proof verification from bottom->top to top->bottom. This is actually the approach that geth VerifyProof is using and it makes some other things easier too, I will update the documentation in the next days (but the circuit layout doesn't change much actually).
> Bottom line, I think I can now actually start developing the circuit. In parallel, I will be writing the tests and verifications in Go like the ones mentioned above (BTW, the most complete test until now is TestStateUpdateOneLevel) and will then use the same data for the circuit tests.

edu: why not use JS tracer?
han: JS tracer can't access the MPT trace

barry: how to consume keccak hash?
miha:

yt: how does MPT interact with EVM circuit
barry: throguh bus mapping
yt: so it's separate

#### RLP encoding

barry: are there other place we need to use it?
miha: outside the storage? I plan to inlcude RLP, and it is in doc already

#### dev tool

separate generic and zkevm specific one.
constraint builder need to be aware of max degree
impl Expression

#### How many circuit we have?

wrong field
EVM circuit
MPT circuit
keccak proof
EC verification

We can optimize how many proof/circuits we want

#### Do we have constant column that's not affecting degree?

han: can we have some columns that's constant
yt: it's called the "instance column". There's an API to let you assign absolute row. https://github.com/zcash/halo2/blob/main/src/circuit.rs#L185 assign_advice_from_instance

han: is there a way to avoid degree counting in halo2?
yt:

#### licensing update

yt: no. expect to have updates 1 week from now

## 1st Oct 2021

Attendants: Carlos P, Chih-Cheng L, Han, Barry W, Miha S, Mary M, Onur K, Edu

### Updates

- cc:
- Keccak, theta step, testing cases ready for review.
- cp:
- refactor of the memoery to byte basis.
- Testing tool for the opcode implementaion.
- reviewing serveal prs, tooling for trace generator.
- talk to han on call context and storage.
- put edu up to speed with busmapping and parsing.
- onur:
- test passing for big integer mul, add, reduction circuits. https://github.com/kilic/halo2wrong
- cost analysis for each operations. for example big integer mul 34 rows
- han:
- playing with evm
- write down evm circuit with python code.
- miha:
- debuging and styding geth.
- provide witness generator for MPT

### Discussion

#### Outsourcing busmapping to external contributors?

#### Add release flow

To make sure witness generation

#### Estimation bignumber mul in EC mul?

5 mul 1m row?

how many for recursion?
each column brings an addition and multiplication
multiplication is the bottleneck.

#### mm: vitalik has a proposal of poly commitment that hides the index.

barry: the current project is scalabitly focus than privacy. But mostly because compatebilty issue

#### miha: Issue of getting MPT witness from Geth

han: has rust trie impl and use Geth to get intermeidate state and let rust lib to generate intermeidate witness
miha: need to maintain a moduele to communicate Geth to provide primage
barry: should geth maintain this? han: probably geth team not intersted
barry: eta for the module? miha: try to estimate next week.

#### miha: MPT: RLP encoding layout

miha: Circuit become over 100 columns, not sure if that's ok.
need to write down more details to have better estimation

### Next steps

- cc: add tags and release flow
- onur: on group operations.

### Communication to external team

- share onur's update. Check with them on the comparison of two methods
- issue on the long witness generation time.
- solution 1: need to disable that test.
- solution 2: out source the CI to powerful machine

## 24th Sep 2021

Attendants: Carlos P, Ying T, Chih-Cheng L, Han, Barry W, Miha S, Kevaudray W,

### Updates

cc: keccak
carlos: parsing more information from geth trace including call context, storage.
onur: non-native field, aztec approach https://github.com/kilic/wrong
han: state circuit and evm circuit. storage and access list need to revert
miha: merged the state circuit. on merkle tree, debugging geth.

### Discussion

#### Merkle proof

Might need to implement the tree in rust.

#### Do we want to enforce a memory hard upper bound 2**24?

so that memory is more friendly in the circuit. We can have 3 bytes in mem key

sounds reasonable to all

## 17th Sep 2021

Attendants: Carlos P, Ying T, Chih-Cheng L, Han, Barry W, Miha S, Kevaudray W,

### Updates

cc: review PR, slow progress in keccak
carlos: ...sorry missed...
han: investigate bytecode circuit
miha: review code. MPT tree updated doc. Setting some test in OpenEthereum to get some witness.

Manage external team's expectation

- circuit/lookup would be the same
- rest of the crate would be changing

- spec first approach

licences: nothing conclusive now

## 9th Sep 2021

Attendants: Chih-Cheng L, Han, Barry W, Miha S, Kevaudray W, Thore H, Rahul B S, Mary M,

### Updates

- Rahul: complete the conversion table for keccak. looking into the sponge part.
- cc: keccak theta step, pi step, xi step done. Working on the rho part.
- han: working on the specing part, especially the busmapping part
- Miha: MPT circuit: https://hackmd.io/CDmIbMafR5SLnHlCIXxE3A?view .

#### Onur

Updated range proof of an integer limb with an overflow value. So we can prove for example 67 bit value in (16+16+16+16+3) fashion where 3 is the overflow value. such feature is required to constain reduction.

Btw I'm following 4 width standart plonk gate rather than using too much customization.

Mul, add, sub, reduction methods are structurally done but still not tested. And for 2 days I'm having challenges with rust compiler :/

Next week I'll be on a kind of a vacation but my laptop will be with me and try to finalize non native field and start its documentation.

Also following https://github.com/xgaozoyoe/halo2ecc/ repo and hopefully the join next call today.

## 3th Sep 2021

Attendants: Chih-Cheng L, Han, Barry W, Onur K, Carlos P, Thore H, Miha S, Mary M, Kevaudray W,

### Updates

- cc: add detail steps for theta rho and xi on the keccak spec. add cost estimation for keccak. https://hackmd.io/sK7v0lr8Txi1bgION1rRpw
- Carlos: Execution trace parsing from geth in bus mapping.
- Onur: Non-native field implementation in halo2: https://github.com/kilic/wrong.
- Miha: Patricia trie and storage in bus mapping.
- Han: trait with examples. Write push opcode. Next step: code initialization. Can start the opcode implemnetation one by one.
- kev:

code initialization is another gadget to implement. It determines wether to process ETH balance directly or to process bytecode first.

Busmapping crate needs refactor because some fields are still missing.

Can start out source opcdoes to external contributors

kev: looked into the stark video. starkware: readonly model. plookup argument is simpler. high level opcdoes called builtin

barry: on multiple-opcdoe circuit approach.

license issue

Our alternatives:
- exsting zkevm code use halo2 API + onur kzg + rewrite a constraint system with similar api to halo2
- build another halo2.0

license that zkevm should use:
- choose either license MIT or apache

## 27th Aug 2021

Attendants: Chih-Cheng L, Han, Ying T, Barry W, Onur K, Rahul B S, Carlos P, Thore H, Miha S,

### Updates

- Rahul, cc: Keccak256
- Onur: modulo arithmetics and group arithmetics. eta a week or 10 days
- Carlos P: bus mapping was merged. Check the implementation of the range proof.
- Han: opcode gadget check. Move on to busmapping part
- Miha: state circuit. all issue addressed. integrating the state circuit with the Carlos's new busmapping api. implementing the push opcode (generic to 1~32). the tricky part is to get the push argument from the next part of the bytecode.

Carlos: Adding representation of memory. memory is worked with 32 bytes word. unaligment for 8 bits.
do all the call context in the storage

discussion on push opcode https://hackmd.io/uQJV4yyQSPufUahr0UkAtw#PUSH

busmapping parsing question:
parse the geth debug_trace API directly

licence question: no progress. zcash still in internally debate

where to put the opcode traits? In crate busmapping or zkevm-circuit?

Thore: what would be a good description of the task for testing focus dev?

### plans for next week

- Rahul, cc: continue on the keccak. Rahul on lookup table. cc on sponge
- Carlos: move to the memory issues
- Miha: continue on the state circuit. Merge with bus lookup. finalize push opcode
- Han: integrate the busmapping. Create an issue and add some geth debug_trace API examples

## 20th Aug 2021

Attendants: Chih-Cheng L, Han, Ying T, Barry W, Onur K, Rahul B S, Carlos P, Thore H, Kevaudray W, Miha S,

### Updates

Han, Rahul, CC: keccak tables and optimization tricks
Onur: Multiplication
Carlos, YingTong, Han: Busmapping API. Range proof
Han: write the spec and the trait. State proof and the evm proof
Miha: state proof. have storage. closing to finish

### Discussion

EDDSA:

Would the future CALL implementation changing the bussmapping API alot?

To only future proof thing we consider now is we implment the memory as a byte array

storeage reuse?

1559:
Implemnting 1559 in the L2 makes less sense.

License discussion on Halo2:
YT: halo2 has no consensus yet. There's a time pressure (testnet end aug, early sep) to cut a release on Halo2, but they can't release until figuring out the license.

Barry: BOSL no definition of deivitive work is. Unclear how legal system deal with it.

### Next step

Rahul and CC: Continue on the keccak front
Miha: finish the state circuit, move to EVM circuit
Carlos: waiting the review of bussmaping API. meanwhile looking into range circuit or look into halo2 API or Merkle Patricia Tree
Onur: Multiplication on G1 operations
Han: focus on Trait and provide example. Explain Line by line if people need that

## 13th Aug 2021

Attendants: Chih-Cheng L, Han, Ying T, Barry W, Onur K, Rahul B S, Mary M, Carlos P, Thore H, Vitalik, Kevaudray W

### Updates

CC: Updated documentation.

Barry: Wrote some issues in the EVM spec.

Rahul: Figuring out keccak.

Carlos: Looking at mulmod for Bus mapping.

Onur: Public inputs. Is efficient in recursion context because avoids too much hashing. We can hash public inputs into the transcript directly.

Miha: Close to having first op code implementation

Han: Will be easier to break up opcodes and combine them into a single EVM circuit at the end.

Kev: TinyRAM exploring for optimisations.

### Discussion
Current plan is to try and get documentation to a level where we can outsource some of the work.

https://github.com/appliedzkp/zkevm-specs/issues

Barry also defined a milestone to unblock the opcode outsourcing https://github.com/appliedzkp/zkevm-specs/milestone/1

Haven't made a lot of progress with storage yet.

Rahul will continue with the rotations. CC will define multiplication property. Onur will look at range proofs. Miha will finalise state circuit PR - then could try to help with EVM circuit.

https://hackmd.io/CUWxTKjwS1OKm-ZPIOa76w?view#9-Public-Inputs

https://drive.google.com/file/d/1wlA_4KJRwyj5DkgD-0Lv5Kr_wnE3VcJN/view

Halo2 does have custom constraints outside of the circuit.

Progress on multiple calls: when a call happens enter initialisation section. Check if receiver has code to execute. If yes store in state circuit. https://hackmd.io/GT5-oa__SbedW1W2o4YJBw

## 6th Aug 2021

Attendants: Chih-Cheng L, Kevaudray W, Han, Ying T, Barry W, Onur K, Rahul B S, Mary M, Thore H

### Updates

CC: keccak circuit and addition circuit. Improved some examples and comments on spec to improve readability.

Rahul: Looking into rotations in keccak. Technique to switch to sparse form. Looking into matterlabs code.

CPerrez: Bus mapping field trait does not support hash. Should have byte arrays.

Han: Can start to have table for EVM circuit.

Ying Tong: Add mapping almost done. Will wait for bus mapping before completing. Bus mapping compression can use Halo2 backend to do compression for us. Check lookup-table commitment is the same. Will look at if we also need same randomness.

Onur: Keeping up with Zcash updates. Need to keep number of public inputs small. Want better resources for multiplying two numbers in the wrong field.

### Discussion

Error handling: allow prover to prove that there was an error code.

Kaccak uses sha3 not sha256 so cannot use Halo implementation.

Q: Can't we have a new type in the bus mapping? Ying Tong has a preference for new types over blocks of bytes.
A: Does not obviously make a difference. But can make a wrapper.

In EVM circuit have slot to check all sorts of operations. To call gadget ask for location and return constraint expression. Doesn't need to know layout. Op code decides how many witness values to use.

Helpers to help people write gadgets. Later can adjust slot size. Layout could change a lot in future so abstraction would be good for us.

>> Want better resources for multiplying two numbers in the wrong field.
Look at matterlabs code.
https://github.com/matter-labs/franklin-crypto/tree/dev/src/plonk/circuit/bigint

https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1108.md
https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1108.md

## 30th July 2021

Attendants: Miha S, Chih-Cheng L, Kevaudray W, Han, Ying T, Barry W, Onur K, Rahul B S, Mary M, Vitalik B, Thore H

### Updates

Onur: put Zcash team updates to KZG. There are things to do KZG side. Need spot for non-fixed columns in tables.

Barry: might need to do proof verification inside the zkp.
Would need to implement bigint arithmetic inside the circuit.
We do 2^256 so have to split up the integers anyway. Currently done in bytes.

CC: working on keccak. Found note by Georgios about shipwreck. Georgios designed an arithmetic sum. Figuring out how to do this. https://hackmd.io/xfgP5_uMTZyaEJJG4EJoRQ

YingTong: Bytewise addition. Going okay but have run out of memory with 2^17 table.

Miha: State circuit. Improved padding. Padded rows are not checked for constraints. Refactored state circuit a bit. Storage circuit and merkle tree.

### Discussion

Degree of lookup needs to be the same as number of rows in circuit.
Easy to pad KZG commitments.
Hard to pad FRI commitments.
Got to think of someway to tag input to random linear combination.

Can we pad the input to values that will always be true?
Yes we are doing this.

Can we do 128 bit limbs? Use a smaller table to pretend like you have a bigger table. Seems likely to be a component of the limb approach.

Will the cost of creating the table be a problem going forward?
It might be with dev tooling.

A memory address is 256 bits? There are two kinds of memory mstore8 which stores a byte and mstore which stores 32 mstore8's.

https://hackmd.io/@arielg/B13JoihA8
https://hackmd.io/Np7RwnpyQiaAzxB8HjqFkw

How do we store accounts in layer 1 contract? Just store the root.

Merkle patricia tree. Proofs could be dynamic length. Can't imagine what the circuit would be like.

When doing coopying constraints hard to know what do change dynamically.
Hard to know when to stop doing the copy constraint.

Plonk proving system. Prover loads in state. Op codes are also loaded in. Prove state that prover put in + op codes were correctly executed. Then we have another proof that checks that the state the prover put in are correct.

Need to change how we process public inputs because otherwise too expensive to put on chain.
Aztec verifies stuff that goes inside the pairings are correct inside the circuit.
Halo2 uses cycles so is different.

## 23th July 2021

Attendants: Miha S, Chih-Cheng L, Kevaudray W, Han, Ying T, Barry W, Onur K, Carlos P, Rahul B S,

### Updates

cc:pyspecs

- Word encoding and commitment check https://github.com/appliedzkp/zkevm-specs/pull/12
- Comparator https://github.com/appliedzkp/zkevm-specs/pull/8
- Addition https://github.com/appliedzkp/zkevm-specs/pull/11
- WIP keccak256

Onur:
- plonk
- proof system customization

YingTong:

- Halo2 changes upstream. bumped the halo2 commit.
- changes we want
- introduce a convenitnt new API change.
- selector optimization change: some manual code become automatic
- changes we dont want:
- introduced blinding facctor in advices column
- change lookup table to only allowed fixed column, need to undo that. We want to use public input as the table

barry: we don't need zk in this project. we want to do other project might need zero knowledge

kev: adding zk should not be too much hussle. Can do it in downstream lib.

yingtong: why zcash's want only fixed poly?
small table need to fill 2*25 rows in that column

onur: do we need to populate the table at the verifier side?
yingtong: yes

yingtong: a tag
global counter is a tag already

barry: maybe gc would not be an ideal tag

Carlos:
- rust implementation of bus mapping
- need to fix the implmentation and add some tests next week

keys for storage
carlos: for mem max size shoudn't be greater than usize.
barry: shuond be limited by the gas

yingtong: why we need keccak for evey storage trie?
carlos:
barry : if we want to store 1, we have a key value keccak(1): 1.

carlos: this is not blocker, but we have some design space.
han: many
yt: can we use keccak as public input, hash outside the circuit in l1 evm.
barry: that would work, but costs us 1 hash in evm for ebery stack rw.
kev: switch public input to private input
key: hash all hashes together, 1 l1evm hash
barry: don't think that helps

Han:
- extend call context spec. Try to create concrete example. But the file is too big
- evm error not cause by the revert

han: evm could allow chlid revert but parent still work.
barry: ideally we want to support this behavior. encode stack check if that's underflow or overflow

barry: another approach make it impossible to underflow or overflow so no edge cases to worry. but we want to do zkrollup that works so like evm.

Rahul:
- Jump Jumpi and jumpdest spec

Rahul:
CP: next gc and pc
Rahul: destination pc,
han: think we have access to next gc and pc

Miha:
- Memory circuit is reviewable.
- fixed column is not in the verifying key. fixed now.
- want to work on stack circuit

barry: stack and memeory should be similar except of the mstore8
han: do we do bytearry or kv for memory
barry: have to do bytearry to support 8 bits

Rahul: is there a fast is_zero comparator of 32 bytes?
barry: the commitment of U256 0 is zero. Just check the commitment is 0

barry: busmapping includes compressed form. How is compressed form represented.
Han: We have multiple random number r to avoid collision

kev: high level primitive you need. for example kv update. dictionary
yingtong: global 8 bit lookup table

transformation function from U256 -> FieldElement

barry: let prover witness the dictionary. check the degree

prover at each row would check a k and v.

key: block 500, prover want to prove the previous
barry:

## 16th July 2021
Attendants: Miha S, Chih-Cheng L, Kevaudray W, Han, Ying T, Barry W, Mary M, Onur K, Thore H.

### Updates

Onur: integrated KZG and the tests pass. Prover is done as well. Next step to make it compatible. Look at how we hash common inputs: change hash to sha256. Use uncompressed points so that we don't need to decompress inside zkp or EVM.

Barry: Looked at calls. Maintaining variables between calls. Different stack in different memory. Last thing to look at is storage. Cleaned up book that CC shared.

CC: Converting 256 bits to 8 bits. Then aggregate with carry bit. Different comparitors are different lookup tables. Currrent maximum is 2^16.

https://hackmd.io/EEPhKWgWSTCZ54ihCRqkhQ?both

Ying Tong: Some similarity to Comparitor. Lookup tables will be pretty different. In process of writing. Currently 10% done.

Miha: Memory circuit. Can reuse Han's gadget to avoid having q memory column. The q memory column would need additional constraints. One concern still bothering: as it is implemented now the prover can put init rows in random positions. There is no way to check if init rows are somewhere in the middle.

### Discussion

Q: Size of FFT, is it 8n?

A: Depends on how you define your circuit.

Q: When should we fork Halo2?

A: Recently Halo2 added loads of blinding factors and we don't need that. We want an API change. Now would be a good time to fork.
https://github.com/kilic/halo2/tree/kzg

Q: Changed commitments to Lagrange coefficients. Concern about this last week. What are the concerns. Are there documents?

A: Only concern is dividing polynomial by something that vanishes on the domain then will get an error. Dankrad has a document to get around this. Can't use anyway as there are G2 operations in the EVM that we would like to avoid.

Q: Could we use Splonk.
https://eprint.iacr.org/2020/081.pdf
https://hackmd.io/@tompocock/shplonk

Can reduce gas costs either with zkrollup or proof of validity for Ethereum. In short or medium term would be good to get gas cost benchmarks for informed decision making.

Can use recursion and Halo2 stuff. Makes sense to avoid recursion if possible because we might want to upgrade to FRI and recursion with FRI might be tricky.

Q: Can init rows be inserted in memory circuit?

A: Fixed column assignments are done at keygen and cannot be changed at proving time

Might need to specify can only do memory once.

We witness bus mapping polynomial. Prover can put anything in bus mapping. Decompression step = random linear combination of all elements of the polynomial. Includes global counter etc. Translate commitment to values inside commitment. Live in circuit identically.

We must limit degree of bus mapping and check every element of the bus mapping.

Need to guarantee elements checked across EVM proof and memory proof are the same. We check this in circuit and in EVM. We have range proof in L1 EVM and a range constraint in L2 EVM circuit. Check 100 elements and polynomial commitment only has 100 elements and thus checks must be the same.

Must check uniqueness i.e. that the bus mapping only has unique elements. This is why we need the global counter.

Want to do a call opcode which will be complicated. Should we wait until add circuit is finished? No, it should be okay to do this in parallel.

A lot of the call is already speced out but there are some details that need fixing.

Q: How much will subset argument cost in KZG? We have a lot of lookup on different column. Will it blow up proof size?

A: KZG should not change depending on size of circuit. In the Halo2 IPA the proof size will change but not in KZG.

There is a sha256 implementation in Halo2. Uses lookup tables heavily. 16bit table. Could fit 33 rounds. 2100 rows. Don't do ECDSA verification. https://zcash.github.io/halo2/design/gadgets/sha256/table16.html

Aztec and matterlabs may have implemented ECDSA verification.

Q: What is the conversation regarding bigger curves?

A: We're doing everything decompressed anyway. Limits our directions. Can't do proof of validity for EVM because would need to be off-chain.

### Next Steps

Get gas cost benchmarks.

Miha: Plan to finish memory circuit constraints in open PR. Will try to work on stack circuit together with Han and Ying Tong.

CC: Write about arithmetic. Implement keccak hash in Halo2.

## 9th July 2021
Attendants: Miha S, Chih-Cheng L, Kevaudray W, Han, Ying T, Carlos P, Barry W, Mary M, Rahul B S, Onur K, Thore H.

### Updates
*Onur* KZG stuff is okay. Currently working on multi-opening techniques. Exploring Halo2 library. Some efficiency issues with being too generic. In standard Plonk e.g. suggests to do not send evaluations of selector polynomials to the verifier, but in Halo2 we do send these. Want to finish this integration.

*Barry* What sort of accumulator. Can use Merkle trees or Verkle trees. Verkle trees looks like 400,000 gas. Caveat is that we have to account for reverts. Possibly less if we batch the pairings.

How to do calls. Seems simple. Most difficult thing is call data copy and return data copy. Might need too change the way we define our call ID. Random linearisation of previous call ID? Need to write up as currently doesn't make sense.

*Miha* Memory circuit pull constraints. Did some cleaning. Looking into Han's code for global counter. Making it more efficient with Plookup range techniques. Upper bound on global counter is 10,000. 10,000 seems a little too small. Maybe 2^16 elements?

Does not yet have a good grasp of how the memory circuit talks to the EVM circuit.

*CC and Carlos* Some small progress in the tests. Have not added global counter.

### Discussions
Need to decide when to optimise the verifier. Could be done after we know the full verifier. Would prefer to know gas costs as we're going rather than at the end.

Could get some average numbers because Noir has a verifier contract.

Would like to have a verifier for the different gadgets we're making to confirm that it won't be too high.

What is the linearization polynomial that Halo2 doesn't use. Method to avoid giving out evaluations of selector polynomials. Can significantly reduce proof size. It should be possible to use but not sure about the Halo2 abstraction. Not straightforward to do it in an automatic way. Not a blocker if we don't apply. Will explore when we come to it.

https://hackmd.io/4CRf1sYOSUiqka-FFhzvnw

A selector polynomial is a thin wrapper around a binary column.

What do we think about 400,000 gas to simplify the circuit? These are back of the envelope calcutions based on the cost of a block. This might be halfed if BlS12 precompile makes pairings cheaper.

How would circuit constraints look. Kate commitment -> Plookup key value mapping -> EVM circuit initialise them to being loaded value -> something about the key, key that we're loading to element it's stored in in memory like circuit. Key to index to value. As the circuit goes on write and read as we do in memory, but also need to queue-up "unwrite" in case of revert.

Whenever we have a stake load we incur some cost in the EVM but the cost should be small. A bit scary. Feels like state-proof is the blocker so there are benefits in improving that at the cost of more gas. We already have limit on number of operations you can do in a block so this might help.

Global counter is now unique.

Q: Add op code in EVM proof. Will need a bus mapping with op that uses an add code. Does the current example have that?

A: Basic things are storing, mstore and mload, push to stack. All of these things do entail additions, so yes, if you need them you will find them.

Is idea of removing some things from bus mapping so we have one thing for bus mapping and one for op codes. Not clear if this helps us or not.

Q: How do we see the bus mapping working? How do we accumulate bus mapping into a digest? The bus mapping could be sent between circuits so the digest is the public input.

A: We generate the digest as a witness and we verify in circuit. PC that contains all of the bus mapping elements. Bus mapping is random linear combination. Polynomial is passed from one to the other.

Don't need variable bus mapping length? What we want is uniqueness guarantee. The number of bus mapping entries up to the max of the global counter. Can use global counter as witness to tell to add bus mapping entry into the digest up to maximum degree of the global counter.

Concern. Bus memory mapping with memory read and state read but then need to verify both in EVM proof and we can only verify one at a time.

Add will cost 3 rows in a slot. Slot will cost 100 rows in the circuit. Can verify too much if we have 2^28 circuit size limit.

Q: Difference between a slot and a row?

A: A slot contains multiple rows. A slot contains 0 to 255 op codes that we are going to verify. There is a fixed column to read. Up to a slot could have 1000 rows to a single slot.

https://hackmd.io/q8EhMIp_TimpPWWFXtwOVw

3 plookups to load variables. 32 plookups * 2 to decompress. 32 plookups for the addition. 32 more for the compression. Gives us 131 constraints. 250,000 adds.

### TODOs:
How many op-codes in an average Ethereum block?

Combine all documents into a single place or spec. Could use a hackmd book or could gradually move documents to the spec repository. https://hackmd.io/@liangcc/zkvmbook/https%3A%2F%2Fhackmd.io%2F%40liangcc%2Fzkvmbook%2Fedit%3Fedit

## 2nd July 2021
Attendants: Miha Stopar, Chih-Cheng L, Han, Kevaudray W, Han, Thore H, Onur K, Ying T, Carlos P, Barry, Mary M.

### Updates

*Barry:* Thinking about variable with bus mapping. Can we make our slots smaller. How big can our custom constraints be? Are we concerned about verifier costs for high custom constraints?

How to do calls? Have not figured out yet.

Copy constraints. Copy constraints are being set in bus mapping. Can the prover integrate copy constraints with Plonk copy constraints?

*Onur:* Pairing repo public. Built KZG on top of it using Halo2 polynomial structures and some arithmetic functions. Integration effort is also public. Still missing proof system integration.

Is this KZG that uses Lagrange basis polynomials? Marked it has Lagrange form but not sure how this changes anything? Changes likely to occur when integrating proof system.

There is a different variant of KZG directly.

https://github.com/kilic/poly/blob/master/src/poly/kzg.rs

*CC and Carlos:* Used ethereum gas to produce execution gas test vectors. Have a pull request. https://github.com/appliedzkp/zkevm-testing-vectors/pull/1

This is almost done but could do with more input about what we want.

Will do another contract for the interaction with the storage.

*Han:* Explored state circuit with bus mapping. Is a little stuck. Will chat with Barry.

*Miha:* Experiment with Halo2. Rotation previous and next didn't go through without added hex. Probably doing something wrong. Added todos in memory circuit. Not a PR yet.

### How big should our custom constraints be?
More custom constraints means more G1 operations for the verifier but the number of pairings will be constant.

It's tricky to do copy constraints when you have variable slots. Is it the case for each op code, if I tell you the op code, you can tell me hoow many constraints? Yes. We could use a custom constraint per op code rather than a permutation argument.

For rotation can put in any i32. Within a custom gate if you know ahead of time that at some fixed opcode you are going to want to rotate, then can implement that in a custom constraint.

Does that cost one more KZG? Will incur extra cost. Yes. Extra field element and the prover has to create an opening for that polynomial at that specific point.

Don't do any copy constraints so can afford the additional cost. Adds an equality constraint. Read wires from previous gate. Either equality check or incremental check. We have to know the copy constraint that we are doing at setup time. Also don't need zero-knowledge.

#### Q: What should we include and not include in the Plonk implementation?
Removing zero-knowledge is fine. Not sure about copy constraints. Don't include for now and we can decide later.

On the verifier side would really like verifier contracts that verify some of the operations that we are using.

Will integrate it as is first and later look at zkEVM.

#### Q: Do we preprocess on every block?
No. We have a single circuit at setup time. The circuit per block is constant. Depending on the witness that changes the prover.

Problem with specialised circuit is need to do verification that setup was carried out correctly on the blockchain and this is very expensive.

Each block represents a new execution contract which is represented by our commitment to the bus mapping. The commitment to the bus mapping is a public input that changes with each instant.

#### Q: What is the cost requirements?
Use case for zk-rollups which is a smart contract. Adding call data is expensive for the EVM. Proof needs to be small.

Proof of validity for ethereum blocks. Those are off chain so having the proof be bigger is okay. Can use STARKs. With STARKs no limitation on the size per block will just have bigger proofs.

The proofs are completely the same but we would use a different polynomial commitment to compile the proof. Want to be able to just take one out and put one in depending on what attributes we want from the scheme.

### Next steps
Share test vectors with external teams that are interested in joining the community effort. Ask them to make custom constraints for specific op codes.

Generate testing framework for simplest task as example for external teams to follow. Aim for the easiest thing that we can run tests from. Create a repo that people can fork from.

Best place to contribute is in EVM proof. E.g. we implement add and then we ask them to do subtraction.

One proof for the state and one for the EVM. Provide them with a bus mapping. Bus mapping takes something off the stack, does an operation, and puts something back on the stack.

Final aim is a collection of gadgets which we are able to use.

Lets do a simple gate and reassess when we get there. Can probably be there in one or two weeks.

Separating op codes means we can do tests for each op code. This will make generating tests better.

TODO: Get call stuff thought out.

TODO: Look closer at testing vectors and Halo2. Fix issues in memory circuit.

TODO: Start creating a bunch of issues on the zkevm repo so that we can assign people different things.

TODO: Continue integration. Discuss memory stuff with Han and Barry and Onur.

TODO: Find good way to define lookup function in our spec.

## 25 June 2021

Attendants: Ying Tong, CPerezz, Han, CC, Thore, Miha Stopar, Onur, Kev, Barry, Rahul, Mary.

### Updates

We must charge gas. Overwise we are vulnerable to reentry attacks. https://quantstamp.com/blog/what-is-a-re-entrancy-attack

By Next week should have ported Bn256 to Halo 2 library. Currently going as expected and have not encountered any problems.

Looking into Dusk Plonk range proofs.

Running push and pop with test vectors. Feedback would be appreciated. https://github.com/appliedzkp/zkevm-testing-vectors/blob/layout_structure/contracts/StackPushPop/enriched-abi.json

Started prototyping circuit. Currently a toy example. Will push soon to applied zkp repository.

### Halo2 or Dusk Plonk?

CPerezz: Halo2 is much better option. Has good functionality, support from Zcash, Plonk is supported, library is being audited. Plookup will be enabled as if it is another custom constraint.

CC: Likes Halo2 better as well. It seems suitable for more complicated applications.

Is Halo2 one constraint per lookup? Hard to compare lookup to a custom gate. Argument demands that input values are included in table. Degree of a lookup argument is degree of input expressions plus degree of table expressions plus one. Doesn't make circuit bigger as no extra rows. But if you exceed the degree bound then it just won't run.

What defines the degree bound? Small in simple cases. Bigger in more complicated columns e.g. can do e.g. column1 * column2 - column3. Can turn lookups on and off depending on when constraint should hold or not.

Can we do similar tricks to quotient poly and split it into a few polynomials of different degrees? Would a bigger table have many more constraints? Lookup argument different from permutation argument and is not using copy constraints. Don't care about order as long as a subset of the table.

https://zcash.github.io/halo2/design/proving-system/lookup.html

We do already break down the quotient polynomial into chunks of degree (n-1).

### Goals for next week

**Implement bus mapping in Halo2.**

Bus mapping = reading from mapping with bunch of different subtables. Han and Miha will work on this. Start with memory circuit or stack? Ying Tong to pass on current work on this.

Bus mapping includes values read from or written to memory. Look them up both in EVM proof and state proof.

Wouldn't memory differ from contract to contract? How can we setup the correct memory from contract to contract? Memory tables are created on the fly so for each block new memory table is created.

Different from other understanding of lookup tables. Usually baked into the constraint system.

Lookup table = polynomial commitment = public input into circuit. Calculate it as witness values and pass those witness values to the circuit. Table columns and expressions can be built from public inputs.

Are there any fixed parts of the lookup table that don't vary from one instance to another? Yes. It contains both. Also, because our lookup table for the bus mapping is defined by the prover we must check that degree of bus mapping is below some limit, and also ensure that up to that degree the prover is not hiding anything in the bus mapping.

Will use KZG commitments to check degree bounds. Do we have to do that? Inside the circuit there's no way someone could construct a higher degree expression. But we cannot construct the expression inside the circuit because that would require G1 ops which do not have a nice representation. So this is all happening outside the circuit.

Degree checks of KZG commitments are pretty simple. Batching works but there is some additional cost per additional degree bound.

**Build more complicated test vectors and incorporate them with bus mappings.** Once we can do that we can separate EVM proof from state proof.

Onur is tackling first two bulletpoints from https://hackmd.io/Sw_kmrkqR2KOr-BFuwGSnA

**Start writing Halo2 circuits for different things.** To early to start smart contracts but worth gaining familiarity.

**Create resources to help new people join.** https://hackmd.io/JMTXr-ONR0eNGt4Xgvb-Ag

Create repo for the spec and create issues on the repo. Explore writing Plookup in Plonk in a how-to. Anyone interested is welcome to help.

### Additional questions
In Halo2 does the commitment scheme assume the polynomials are in coefficient form? Have API called commit-lagrange. Also have extended domain and convert between those for efficiency. The extended domain might be padding lagrange basis to a power of 2.

**Explore whether we can represent Halo2 IPA polynomials in Lagrange form**

Only helpful for Halo2 because we're not using it in the EVM. But we can input the Lagrange form into the KZG with this project. Kev has a version of KZG in Arkworks that takes in Lagrange form.

It's more of an optimisation.

Testing vector perspective. Would it be helpful to have the test vectors for some contracts yet? Might be useful in a weeks time, so yes.