Skip to content
This repository has been archived by the owner on Jul 5, 2024. It is now read-only.

[proof-chunk] chunk supercircuit to multiples proof #1604

Closed
Tracked by #1498
hero78119 opened this issue Sep 14, 2023 · 0 comments
Closed
Tracked by #1498

[proof-chunk] chunk supercircuit to multiples proof #1604

hero78119 opened this issue Sep 14, 2023 · 0 comments

Comments

@hero78119
Copy link
Member

hero78119 commented Sep 14, 2023

Depends on #1601, #1602, #1603, #1614

witness

Chunk rwtables

  • chronologically sorted rwtable
  • multi-sorted rwtable.

in bus-mapping to generate different super-circuit proof. Need to compute global challenge by commiting rwtable columns of different chunk, chaining them as input to get poseidon hash as global permutation fingerprint challenges.

There some some noted for supercircuit change

  • evm_circuit introduce inner_rw_counter in execution step to differentiate with global rw_counter. This is used in every chunk end_block to lookup and assure there are consecutive padding steps append at the end of chronological rw_table.
  • ...

custom protocol in root circuit

Enable custom protocol in root circuit for

  • poseidon hash
  • consistency in public input
  • equality of permutation fingerprint on last supercircuit proof.
  • assure some meta flags on last supercircuit proof.

More context on Rw::Padding handling

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, 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
]
@hero78119 hero78119 changed the title [proof-chunk] root circuit chunk supercircuit to multiples proof [proof-chunk] chunk supercircuit to multiples proof Oct 9, 2023
@hero78119 hero78119 assigned hero78119 and unassigned hero78119 Nov 28, 2023
@ed255 ed255 moved this to ✅ Done in zkEVM Community Edition Mar 21, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
Status: Done
Development

No branches or pull requests

2 participants