This repository has been archived by the owner on Jul 5, 2024. It is now read-only.
[proof-chunk] super circuit implement new permutation gadget for evm rwtable lookup #1601
Assignees
Milestone
Comments
hero78119
changed the title
hero78119
changed the title
hero78119
changed the title
This was referenced Sep 14, 2023
4 tasks
4 tasks
4 tasks
hero78119
added a commit
that referenced
this issue
Oct 30, 2023
…nk (#1641) ### Description [_PR description_] ### Issue Link #1601 ### Type of change - [ ] Bug fix (non-breaking change which fixes an issue) - [ ] New feature (non-breaking change which adds functionality) - [x] Breaking change (fix or feature that would cause existing functionality to not work as expected) - [ ] This change requires a documentation update ### Highlights - separate rw_table in evm_circuit/state_circuit and each have its own permutationchip. fingerprints checking will be deferred to root circuit. - disable rwtable first row check (by disable selector offset=0 in state_circuit, other offset toggle on as usual), since it will be copy constraints via public input. - keep `Rw::Start` and introduce `Rw::Padding` to support post-padding in address-sorted rwtable in last_chunk. - instance (new public input) column are design into two, one for prev_chunk context, another for current_chunk context to be used for next chunk. So in root circuit commitment of instance column can be used in snark-verifier without need to unwrap it. > Update on 18 Oct 2023: beginchunk/endchunk virtual step, inner_rw_counter, chunkctx - add Begin/EndChunk virtual step. BeginChunk is not mandatory in first chunk first step. while EndChunk is not mandatory in last chunk last step. - add `inner_rw_counter` which is local rw_counter within each chunk. This is used to count valid rw_row and assure Rw::Padding are append consecutively in `end_block.rs` logic => EndChunk should apply similar check later on - introduce chunkctx->{chunk_index, total_chunks} to tell first chunk (chunk_index==0) and last chunk (chunk_index + 1 == total_chunks) during witness generation/constraints assignment - add chunkctx_table to able to lookup chunk context (chunk_index, next_chunk_index, total_chunk, initial_rwc, end_rwc..etc) in exec step to allow various conditional check based on current chunk context ### How Has This Been Tested? [_explanation_] ### More context on Rw::Padding (Not cover in current PR, will be handled in later multiple chunk PR to make scope smaller) In new logic, `Rw::Start` will be insert in first chunk offset 0, while other holes are filled by `Rw::Padding` in last chunk(s). The address-sorted rwtable layout will be ``` address-sorted rwtable ## first chunk [ Rw::start, // offset 0, Rw::Start is only in first chunk, and only in offset 0, constrainted by public input ....(normal Rw), ...(Rw::Padding), // padding if there are only one chunk ] ## end chunk (if there are > 1 chunk) [ ....(normal Rw), // offset 0 are carry over from previous chunk, other are address sorted ...(Rw::Padding) // padding in end chunk ] ``` For chronologically rwtable, since there is no in-row constraints to check each Rw operation, so theoretically Rw::Padding rows can be filled in any offset. However, we also need to assure there is no malicious insertion other than Rw::Padding. To do that, we will rewrite this logic in later PR https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/main/zkevm-circuits/src/evm_circuit/execution/end_block.rs#L86-L90 to lookup consecutive `Rw::Padding` at **chronologically** sorted table, at the END of EACH chunk. > A tricks: first Rw::Padding rw_counter need to be set as last (globally) valid row rw_counter + 1. This is to make sure in both chronologically rw_table or address-sorted rw_table it's always append in the end of rw_table. ``` chronologically rwtable, ascending sorted by `rw_counter`. ## first chunk [ Rw::start, // offset 0, Rw::Start is only in first chunk, constrainted by public input ...(normal Rw), ...(Rw::Padding), // first Rw::Padding rw_counter need to be set as last (globally) valid row rw_counter + 1, last means from last !!chunk!!. It assures Rw::Padding always append at the end of each chunk ] ## end chunk (if there are > 1 chunk) [ ....(normal Rw), // offset 0 are carry over from previous chunk, other are rw_counter sorted ...(Rw::Padding) // padding, also rw_counter sorted ] ```
|
Status: this issue has already been resolved via #1641 and is now in the branch https://github.com/privacy-scaling-explorations/zkevm-circuits/tree/proof-chunk but not yet in main |
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
This issue focus on super circuit change scope.
Based on the design https://hackmd.io/NPDfrFfjQoa5ebzH6bS39w
There will be 2 RwTable
EVM circuit will switch to lookup into new chronologically-sorted rwtable, and at the end we need to constraints multi-sorted rwtable vs chronologically sorted rwtable are permutation of each others.
To prove permutation of 2 tables, we can introduce a new permutation gadget to layout the custom gates to constraint permutation fingerprints updated of 2 rwtable, and at the last row we constraints the permutation fingerprints equality of 2 rwtable fingerprints.
Permutation fingerprint challenge
To update the permutation fingerprints there need a challenge. In super circuit scope we can trust challenge bypass from public-input first, and constraint its consistency from row 1 to the end row. The validation of challenge will be outside of super circuit, which is in the scope of root circuit + snark-verifier in another issues. #1603
Last chunk (reminded by @ed255 )
Introduce new public input
is_last_chunk: boolto toggle some extra custom gates check for last chunkEnbBlockBesides to keep scope smaller, this issue keep single supercircuit proof (chunk) as usual. Multiple supercircuit proof chunk can be defered into #1604
The text was updated successfully, but these errors were encountered: