[proof-chunk] root circuit constraints permutation fingerprint and challenges

[hero78119]

Depends on https://github.com/privacy-scaling-explorations/zkevm-circuits/issues/1601

Permutation Fingerprint

Validation of permutation fingerprint (field equality) is on last row of last chunk, imply the equality check gate of rwtable fingerprints should be able to toggle on and off as an option. In root circuit, there need an extra protocol to constraint the last chunk permutation fingerprint need to be on, while the other should be off.

Validation of Challenge

Need to encode poseidon hash statement as protocol after https://github.com/privacy-scaling-explorations/zkevm-circuits/issues/1602. and challenge is computed via Poseidon hash with input commit(m1) || commit(m2) || ... where commit mN defined as Nth column commitment of rwtable. Commitment of columns belongs to 2 rwtables should all being include to derive global challenge.

Furthermore, there need an extra protocol to constraint challenge output from poseidon matching with global challenge pass in supercircuit public input.

Changed Item

New public input in supercircuit

• LHS & RHS permutation fingerprint

• challenge of permutation fingerprint. We need 2 challenges: alpha & gamma.

  $\prod_{i=0}^{m-1} (\alpha - (cell_i[0] + \gamma \times cell_i[1] + \gamma^2 \times cell_i[2] + ...))$

• is_last_chunk to enable public input

it seems is_last_chunk is possible to be hints from non-deterministic advice instead of public input. However it involve more ad-hoc change to commit a non-deterministic advice on the fly outside of supercircuit circuit, which involved more hyper-parameter to support this workaround. @han0110 any opinion on that ~?

Extra protocols

• poseidon hash circuit to derive challenge from rwtable commitment
• constraint is_last_chunk=true in last chunk
• constraint computed_challenge == challenge in last chunk

[hero78119]

Hi @han0110 and @ed255 would you kindly help to review the issue and provide more feedback :) ?

[ed255]

Overall sounds good to me! Here are some notes of things I found missing:

• Each memory operation requires several field elements. One solution for the fingerprinting is to first do RLC of each element, and then accumulate the result in the fingerprint. For this we need 2 challenges (alpha and gamma). See:

$\prod_{i=0}^{m-1} (\alpha - (cell_i[0] + \gamma \times cell_i[1] + \gamma^2 \times cell_i[2] + ...))$

When chunking we need to accumulate the memory operations from all chunks. This can be done in two ways:

• a. Each chunk accumulates their 2 traces and expose them via public inputs, and then the root circuit multiplies them to get the global LHS and RHS to compare
• b. Each chunk continues accumulating from the previous chunk (except for the first one which starts with 1). Then the last chunk verifies the global LHS and RHS. This requires 4 extra public inputs per chunk: LHS_prev, RHS_prev, LHS_next, RHS_next.

About the is_last_chunk parameter, if we setup the circuit with a static number of chunks, this value could come from a fixed column. But I think the important idea is that there should be a provable way to distinguish the last chunk, because it will need to perform special verifications. One example can be checking that both accumulated LHS and RHS are the same, but we also need to check that the last EVM step is an EndBlock.

[hero78119]

Overall sounds good to me! Here are some notes of things I found missing:

• Each memory operation requires several field elements. One solution for the fingerprinting is to first do RLC of each element, and then accumulate the result in the fingerprint. For this we need 2 challenges (alpha and gamma). See:

∏i=0m−1(α−(celli[0]+γ×celli[1]+γ2×celli[2]+...))

When chunking we need to accumulate the memory operations from all chunks. This can be done in two ways:

• a. Each chunk accumulates their 2 traces and expose them via public inputs, and then the root circuit multiplies them to get the global LHS and RHS to compare
• b. Each chunk continues accumulating from the previous chunk (except for the first one which starts with 1). Then the last chunk verifies the global LHS and RHS. This requires 4 extra public inputs per chunk: LHS_prev, RHS_prev, LHS_next, RHS_next.

About the is_last_chunk parameter, if we setup the circuit with a static number of chunks, this value could come from a fixed column. But I think the important idea is that there should be a provable way to distinguish the last chunk, because it will need to perform special verifications. One example can be checking that both accumulated LHS and RHS are the same, but we also need to check that the last EVM step is an EndBlock.

Thanks for the reminding. I just updated description related to permutation fingerprints, and think option *a is better for it got less fields exposed to public input, with same complexity constraints.

For provable checks when is_last_chunk toggle on is updated in https://github.com/privacy-scaling-explorations/zkevm-circuits/issues/1601