Call link: https://ethereumfoundation.zoom.us/j/96738752557?pwd=eUVMZEdwSS9IcEtJVmVRU3JrWVJHUT09
Han, Shin , Chih-Cheng
Edu has been on state circuit busmapping too
Han, Barry W, Miha S, Edu, Shin, Thore H, Marios, Chih-Cheng, Onur, YingTong
CALL
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
24th optional
31th cancel
YT: extrmemly optimistic. expect Jan under MIT
Han, Barry W, Miha S, Edu, Shin, Thore H, Marios, Chih-Cheng
Carlos and Onur didn't make it today
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
Han, Barry W, Miha S, Edu, Kev W, Shin, Thore H, Carlos P, Marios, Onur, Chih-Cheng
500k gas in 10 hrs
Han, Barry W, Miha S, Edu, Kev W, Shin, Thore H, Carlos P, Marios, Onur
bus-mappingbus-mapping for querying intermidiate state when parsing traceChih-Cheng L, Han, Barry W, Miha S, Edu, Shin, Carlos P, Marios, Onur.
MPT now have the most columns
Chih-Cheng L, Han, Barry W, Miha S, Edu, Kev W, Shin, Thore H, Carlos P, Mary M, YingTong L.
yt: prefer using beta version halo2
yt: haven't estimated for proof size
barry: how to convert rows and columns into proving time
targeting a simple transfer
Chih-Cheng L, Han, Barry W, Miha S, Edu, Kev W., Shin, Thore H.
assert_zero, is_zero and assert_equal, is_equal assert_not_equal, division and inversion constaints for the base field.barry, kev: don't think so. (consult Mary on this)
We know the
depends on the custom gate we are using.
degree of the equation n -> 16n
2 pairings + scaler* n_customgates
Chih-Cheng L, Han, Barry W, Miha S, Onur K, Edu, Ying Tong
onur: after Onur and Xin prepare the trait
barry: need to find someone on it
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.
miha: keccak will be the dominating factor of cost
yt: no update
Chih-Cheng L, Han, Barry W, Miha S, Onur K, Edu, Ying Tong, Thore, Carlos P, Kev W.
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
now: taking tx -> trace steps
future: taking block(s) -> txs -> trace steps
barry: recursion is for proof but not for call and txs
barry: don't think we are likely do to multiple blocks
han: multiple blocks more complexity, need to think more …
YT: no
cc: improve spec writing
barry: do they need to spec something on busmapping?
cp: don't think so
Attendants: Chih-Cheng L, Han, Barry W, Miha S, Onur K, Edu, Ying Tong, Thore, Mary M. Carlos P.
https://github.com/zcash/halo2/issues/377
gadgets and abstractions we do
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.
yt: cautions optimistic on MIT but don't know when
yt: Does aggregator circuit need to do wrong field aggregation?
onur: yes
circuit aggregated bn point in bn scalar field.
write down some thing about aggregator circuit
Attendants: Chih-Cheng L, Han, Barry W, Miha S, Onur K, Edu, Kev, Ying Tong, Thore
onur: more columns means we have more commitments to open
yt: need to fact check this and get back
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
aggegrating proofs
recursion: efficient but preventing paralleling
Aztec style recursion, that can be checked with 1 pairing and works in evm
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
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
separate generic and zkevm specific one.
constraint builder need to be aware of max degree
impl Expression
wrong field
EVM circuit
MPT circuit
keccak proof
EC verification
We can optimize how many proof/circuits we want
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:
yt: no. expect to have updates 1 week from now
Attendants: Carlos P, Chih-Cheng L, Han, Barry W, Miha S, Mary M, Onur K, Edu
To make sure witness generation
5 mul 1m row?
how many for recursion?
each column brings an addition and multiplication
multiplication is the bottleneck.
barry: the current project is scalabitly focus than privacy. But mostly because compatebilty issue
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: Circuit become over 100 columns, not sure if that's ok.
need to write down more details to have better estimation
Attendants: Carlos P, Ying T, Chih-Cheng L, Han, Barry W, Miha S, Kevaudray W,
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.
Might need to implement the tree in rust.
so that memory is more friendly in the circuit. We can have 3 bytes in mem key
sounds reasonable to all
Attendants: Carlos P, Ying T, Chih-Cheng L, Han, Barry W, Miha S, Kevaudray W,
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
Attendants: Chih-Cheng L, Han, Barry W, Miha S, Kevaudray W, Thore H, Rahul B S, Mary M,
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.
Attendants: Chih-Cheng L, Han, Barry W, Onur K, Carlos P, Thore H, Miha S, Mary M, Kevaudray W,
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:
license that zkevm should use:
Attendants: Chih-Cheng L, Han, Ying T, Barry W, Onur K, Rahul B S, Carlos P, Thore H, Miha S,
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?
Attendants: Chih-Cheng L, Han, Ying T, Barry W, Onur K, Rahul B S, Carlos P, Thore H, Kevaudray W, Miha S,
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
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.
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
Attendants: Chih-Cheng L, Han, Ying T, Barry W, Onur K, Rahul B S, Mary M, Carlos P, Thore H, Vitalik, Kevaudray W
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.
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
Attendants: Chih-Cheng L, Kevaudray W, Han, Ying T, Barry W, Onur K, Rahul B S, Mary M, Thore H
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.
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
Attendants: Miha S, Chih-Cheng L, Kevaudray W, Han, Ying T, Barry W, Onur K, Rahul B S, Mary M, Vitalik B, Thore H
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.
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.
Attendants: Miha S, Chih-Cheng L, Kevaudray W, Han, Ying T, Barry W, Onur K, Carlos P, Rahul B S,
cc:pyspecs
Onur:
YingTong:
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:
Attendants: Miha S, Chih-Cheng L, Kevaudray W, Han, Ying T, Barry W, Mary M, Onur K, Thore H.
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.
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.
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.
Attendants: Miha S, Chih-Cheng L, Kevaudray W, Han, Ying T, Carlos P, Barry W, Mary M, Rahul B S, Onur K, Thore H.
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.
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.
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
Attendants: Miha Stopar, Chih-Cheng L, Han, Kevaudray W, Han, Thore H, Onur K, Ying T, Carlos P, Barry, Mary M.
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.
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.
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.
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.
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.
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.
Attendants: Ying Tong, CPerezz, Han, CC, Thore, Miha Stopar, Onur, Kev, Barry, Rahul, Mary.
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.
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).
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.
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.
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe