[proof-chunk] merge to main branch

hero78119 commented 4 months ago

Description

This PR makes the first move toward single block chunking into multiple proof & aggregation

Issue Link

https://github.com/privacy-scaling-explorations/zkevm-circuits/issues/1498

Type of change

[x] Breaking change (fix or feature that would cause existing functionality to not work as expected)

Rationale

design rationale are list below as separated section

hero78119 commented 4 months ago

Docs & materials

slides
high level diagram https://github.com/privacy-scaling-explorations/zkevm-circuits/pull/1690
permutation fingerprint https://hackmd.io/NPDfrFfjQoa5ebzH6bS39w

hero78119 commented 4 months ago

Permutation Fingerprints

To constrain 2 rw_table

chronological rw_table: sorted by rw counter
by-address rw table: sorted by address

are equals across multiple chunks, we constrain Permutation(chronological_rw_table) == Permutation(by_address_rw_table) via circuit constrains. Permutation fingerprints, in shorts, are via RLC columns of each row into one and accumulated into a single field value, passing them via public input across different chunk, and reach to end last chunk last row.

In the end, equality are constraints by gate in super_circuit https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/0ab41c9d2f8ec7e4645ddece4ea30fe66b314091/zkevm-circuits/src/super_circuit.rs#L250-L270

hero78119 commented 4 months ago

Continuity constraint on evm_circuit execution state

We introduce new virtual steps

EndChunk: write execution state back to rw_table
BeginChunk: read execution state from rw_table

to carry on the execution state begin chunk. BeginChunk will be append ahead of chunks execution steps except for the 1st chunk, while EndChunk will be added append to end of chunks except for the last chunk (EndBlock instead)

For rw_table we already able to carry on it continuity via public input, we dont implement extra public input to carry execution state. Instead we just write execution state from/to rw_table to get a free-ride.

An exception: begin_chunk/end_chunkwe can NOT read/write exec state rwc field

https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/3bbc757a20d9d9f7759db47c096d5395361bee74/bus-mapping/src/circuit_input_builder/execution.rs#L37

to rw_table because we rely rwc to assure rw lookup correctness. Therefore initial_rwc/end_rwc are exposed as evm circuit public input via chunk_ctx_table

https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/2fb87b0d96b07ec652fd55c37846e5c325c54b47/zkevm-circuits/src/evm_circuit.rs#L390-L391

and in execution.rs circuit first/last row we lookup rwc from chunk context table

There is one interesting property of BeginChunk: it will constraint next execution state, so it can NOT be ahead of BeginTx, because BeginTx is the one define new transaction execution state. This was implemented in naive way: checking and chunk ahead before max_rws to assure there is space for end_tx -> begin_tx

https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/0ab41c9d2f8ec7e4645ddece4ea30fe66b314091/bus-mapping/src/circuit_input_builder.rs#L440-L446

hero78119 commented 4 months ago

Bus-mapping witness chunking

Overall it follows the original design of circuit_input_buider to leverage mutable context when processing steps. In proof chunking, we introduce new chunk_ctx which is basically recording context information related to chunk, such as current chunk index…

With check_and_chunk condition match https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/0ab41c9d2f8ec7e4645ddece4ea30fe66b314091/bus-mapping/src/circuit_input_builder.rs#L371-L378 we finalize current chunk and bump chunk_ctx to the next, until we reach the end of desired number of total_chunks. To support dynamic max_rws/max_evms calculation in unittest, there will be 2 pass going over whole block. First pass is for estimated max_rws/max_evms needed per chunk, and then second pass go over block again and finalized circuit_input_builder<FixedParams>.

New Chunk witness. While Block witness deal with block level data, Chunk as its name, is for chunk level data. chunk_convert which output all the chunks to be filled into individual super circuit as witness.

hero78119 commented 4 months ago

permutation fingerprint challenges

Permutation challenge is specially designed as an application-level challenge out of native halo2. The reason is because permutation challenge are cross different ConstrainSystem which halo2 yet support. The challenge are computed in bus-mapping via get_rwtable_cols_commitment Giving rw_table column vector from multiple chunk, this function will derive respective KZG commitments for each column and then poseidon hash all of them for challenge. challenge will be feed to super circuit as public input.

In aggregation circuit, user challenge value will be verified via poseidon circuit.

hero78119 commented 4 months ago

chunk consistency check on aggregation circuit

Each chunk will derive respective super circuit proof and in final aggregation circuit we layout all of them to prove

validity of each proof
consistency check between ith, {i+1}th chunk via public input

Above verifier logic are arithmetization into circuit constrain in root_circuit With those magic to hide all the detail from final decider, final snark public_input is just lo-hi hash without leak any chunking context and complexity.

hero78119 commented 4 months ago

rw_table padding logic

rw table will be padding to max_rws and previously we are padding via Rw::Start ahead. With reasoning here we introduce new padding Rw::Padding. To relief the complex padding rwc calculation across chunk, right now we adapt simply design by incremental rwc just within each chunk. It will make Padding in by-address sorted might got rwc different by 0, 1. This relaxation reflect in build_padding_constraints constrain.

We will lookup consecutive padding in end_chunk/end_block via RwTablePaddingGadget to avoid malicious insertion.

Actually the rw lookup targeting table is chronological_rw_table and the table constraint on incremental rwc is not implemented yet. Means right we can randomly sorted chronological_rw_table within single chunk while still keep lookup correctly. This mechanism can be implemented later

hero78119 commented 4 months ago

What can be done after next

With first move of proof chunk we achieve the milestone to be able to deal with proof parallism on block data level by concurrent provers, each deal with smaller k to get final chunk, and then aggregate all proof.

An known limitation on root circuit, with current complex linearization(gate) functions, under k=26 in root circuit we can only verify 2 super circuit prove. To fully relax the power, we can design root circuit as recursive proof (issue https://github.com/privacy-scaling-explorations/zkevm-circuits/issues/1631) so this part can be slightly eliminated.

with recursive proof, root circuit part still be limited as sequential execution.

hero78119 commented 4 months ago

relevant tests

hero78119 commented 4 months ago

circuit stats (before & after)

chunkctx_table

new added table

+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| circuit        | constraints | rots | min/max(rots) | fix_cols | selectors | adv_cols | perm_cols | lookups | degree | mem_gb |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| chunkctx_table | 1           | 2    | 0/1           | 1        | 1         | 1        | 1         | 0       | 3      | 54     |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+

state circuit

new padding step logic increase number of constraints

+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| circuit        | constraints | rots | min/max(rots) | fix_cols | selectors | adv_cols | perm_cols | lookups | degree | mem_gb |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| state          | 203         | 3    | -1/1          | 3        | 0         | 49       | 0         | 36      | 10     | 2224   |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| state          | 242         | 3    | -1/1          | 3        | 3         | 64       | 5         | 36      | 10     | 2984   |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+

evm circuit

constraints increase due to

new virtual step state transition
permutation fingerprint gadget
chunk context lookup

+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| circuit        | constraints | rots | min/max(rots) | fix_cols | selectors | adv_cols | perm_cols | lookups | degree | mem_gb |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| evm            | 42318       | 21   | 0/20          | 5        | 3         | 131      | 3         | 53      | 7      | 2976   |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| evm            | 43624       | 22   | -1/20         | 8        | 8         | 175      | 10        | 68      | 9      | 4116   |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+

super circuit

+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| circuit        | constraints | rots | min/max(rots) | fix_cols | selectors | adv_cols | perm_cols | lookups | degree | mem_gb |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| super          | 45168       | 106  | -89/207       | 57       | 16        | 498      | 25        | 235     | 10     | 21736  |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+
| super          | 46514       | 106  | -89/207       | 61       | 25        | 558      | 38        | 250     | 10     | 24620  |
+----------------+-------------+------+---------------+----------+-----------+----------+-----------+---------+--------+--------+

privacy-scaling-explorations / zkevm-circuits