2024-12-10 PSE debug tool(WIP) remove hardcode position 0 lk mutiplicity check PR 649 prover (WIP) skip PCS commitment/opening for structual column issue 654 based on issue 654 works, we can add new task to skip commitment of range table optimize opcode circuit with 32-bit range check proposal in #702

lookup argument: Logup The LogUp formula in summary like this image Where LHS is the witness vector W to be lookup and $W(j) = W_j$, for $j \in [1, l]$ RHS is the target table $T(x)$ with $T(i) = T_i$, for $i \in [1, i]$ $i << j$ range check scenario $M(x)$ is the couting for the respective lookup record, for $M(i) = m_i$This is called Indexed Lookup

new_gate_design sumcheck formula syntax: initial claim = sumcheck formula phase 1 out (gate x wit_out ) $$ \sum_{i} \alpha^{i} \space \text{wit_out}{i}[rt_i || ry_i] = \sum{i} \alpha^{i} \sum_{g \in [0, G]} \sum_{s || x} \text{eq($rt_i$, s)} \space \text{copy_to}{\text{g ->i}}(ry_i, x) \ \text{V}{g}[s||x] $$

optimize LogUp challenge in IVC background In pull-request read-write lookup offline-memory-checking logUp-based implementation in (Super)Nova R1CS discussion, one of remains question is to optimise the cost of random oracle circuit in IVC. This post try to address the issue and propose a design. Design rationale One of the nice property to derive challenge via random oracle in folding IVC is we can decouple random oracle into function composition, and relax one or more of function to loose property, e.g. one of them not nessesary to satisify indifferentiable from a random oracle, while still keep overall composition result indifferentiable from random oracle. With relaxation, we implement relaxed function in IVC step circuit, while in the final SNARK pass accumuation result to another random oracle function to get the challenge which indifferentiable from random oracle. Random Oracle Terminology cited from Proving the correct execution of concurrent services in zero-knowledge

Changed History Date Memo Editor 2023-09-19 address few typo and comments @sungmingwu 2023-09-16

Change History Date Memo Editor 2023-09-22 second version @rrtoledo 2023-09-19

zkGeth Design Changed History Date Memo Editor 2023-09-27 update memory commitment methodology @sungmingwu

Proof Chunk & aggregation approach 1 chunk by block/multiple blocks then aggregate => adopt by Scroll question remained: still hard limit on the amount of gas we can prove. approach 2 docs by Edu chunk by sub-circuits logically and lookup across chunk via multiplexing design

Porting ethereum execution-clients implementation onto Risc-zkVMs with bounded soundness Movivation a crazy project https://github.com/ethereum-optimism/cannon run compiled geth on MIPS emulated by EVM, its derived from optimistic rollup design. Ethereum's multi-client iteract with zkEVM https://vitalik.eth.limo/general/2023/03/31/zkmulticlient.html Background As known, there are many types of zkVMs each targetting differrent goals. There are being categoried into type 1 - 4, quantitized by their deviation regarding to EVM specifications. There are few challenges in current PSE type-1 zkEVM implementations

Addressing Problems Existing design rely on verifier to compute 2 hirarchy of random linear combination to prepare instances. The 1st hirarchy happened on convert block/transaction information which bytes up to U256/Word level. For example, take block -> difficulty as example. To fit into BN254 field, we need below convertion let difficulty = rlc(block_values.difficulty.to_le_bytes(), randomness); // Word to Little ending byte first, then rlc. region.assign_advice( || "difficulty", self.block_table.value, offset, || Value::known(difficulty), )?;