TODO add change log. In summary, we are exploring the "linear zkVM prover" $O(c_1N + c_2)$ for $c1$ -> 1 , $c_2$->0, along with the least commitment data as possible. The linear prover should be optimal complexity, since no matter how we still need to go through all the data. We think a "linear prover" should satisfy No FFT (NTT) => sumcheck protocol basedsumcheck is all we needed in the endgame, probably :) ? Less commitment => based on GKR Non-uniform: prover time complexity per proof just pay-as-you-go.

This note shows a pseudocode of create_proof of halo2_proofs and counts the memory usage for each moment. fn create_proof(params: &KZGParams, pk: &ProvingKey, circuit: &Circuit, instances: &[&[F]]) { // Let: // // - k: log 2 of number of rows // - n: `1 << k` // - d: Degree of circuit // - e: Extension magnitude, equal to `(d - 1).next_power_of_two()` // - c_f: number of fixed columns

Feature Completenes Do we accept outsourcing RIPEMD 160 and blake2f to grantees?YEs http://testool-public.s3-website.eu-central-1.amazonaws.com/nightly.1704843658.e26176d.html Proof Chunking

Keep Novi work separate from halo2 workNovi based on arkworks ecosystem.Keep working on it, independently of halo2 GKR work separate for now halo2 team is renamed to tooling team -> halo2l? TODO: Find a good name primitives team is sepparate and collabs with halo2 team

Raphael A third-party OAuth application (notes.ethereum.org) with access to public information (read-only) was recently authorized to access your account. In the zkEVM project we are aiming at verifying a block. To do so, we basically get a block's trace and commit to it in different tables. We then check that each operation is valid and check the consistency of the input/output with the tables that we lookup to. Q: Can you expand on this? How do you check that opearations are valid and, more importantly, what is exactly in the table? One of the major hurdle we have is that we cannot easily change the size of our circuit because of the size of the SRS. Some of the blocks that we have may be represented by circuits too large for the current SRS we have. (Some may also be much smaller, and we will not be inefficient (but that is a different conversation).) We started recently a project called "proof chunking" whose goal is to "split the circuit/instance/proof" such that we can prove (efficiently if possible) the whole block. Q: how do you $conect$ the different circuits? I am trying to think about it in terms for instance of R1CS, how would you manage to work with a srs that is smaller than the size of the witness?

This note tracks potential EVM upgrade in the near future, and tries to give each naive workload and feasibility estimation. Shanghai List taken from Shanghai Network Upgrade Specification. Included EIP Workload Uncertainty [^uncertainty]

Layout Memory as byte per row Single table for all precompiles sequence_id operation io length index byte

To implement BN254 precomiles in EVM circuit seesm to be impratical (probably fine to do add but definitely not fine for scalar mul or pairing), so we could delegate the computation to another sub-circuit and communicate the input by bn254_table. First we need to estimate how many different input could happen inside a single block (30M gas): Operation Gas Cost Maximum Different Input Row Cost [^row-cost-of-v2] BN254Add ≥ 100 + 150 <code>≤ 120000 ≈ 2^16.87</code>

Questions Q1 - Storage non-existing check Currently in State circuit it's speced here as: if value_prev == 0 and value == 0: mpt_lookup(NonExistingStorageProof, key) else: mpt_lookup(StorageMod, key, value_prev, value) Where the StorageMod supports insertion and deletion as said in this mpt-proof.md.

State write reversion might be the most trick part to explain in EVM circuit. This note aims to illustrate how current approach works with some diagrams, and collect all the other approaches for comparison. Revert or not With full execution trace of a block, if we iterate over it once, we can know if each call including create is successful or not, then to determine if which state writes is persistent, others are not. So each call could be annotated with 2 tag: is_success - If this call ends with STOP or RETURN is_persistent - If this call and all its caller have is_success == true

Requirement Verify a list of transactions In the beginning of each transaction or internal call, verify one of:Simple ether transfer and goto next transaction Contract creation and begin bytecode execution Contract interaction and begin bytecode execution In each step of bytecode execution, we need to verify all kinds of possible result, which includes all opcode and their different success or failure case. In the end of each internal call, it resume to caller. (A call ends with any failure execution results or success of STOP, RETURN, or REVERT)

Introduction This note aims to explore how EVM circuit handles EOA call (transaction) and internal call. EVM circuit basically iterate over a list of transactions and verify each transaction's update is applied to state trie. Also each transaction could have serveral recursive internal calls with max depth 1024. Every time when we encounter a internal call, we switch to a new execution environment. And we switch back to caller when encountering a explicit STOP and REVERT, or any kinds of error. But it's hard for circuit to memorize all caller's execution state like program_counter, stack_pointer, etc... So we use state circuit to help maintain the consistency of execution state just like the way we maintain stack and memory. So this note proposes 3 extra targets in state circuit:

Reversion In EVM, there are multiple kinds of StateDB update could be reverted when any internal call fails. tx_access_list_account - (tx_id, address) -> accessed tx_access_list_storage_slot - (tx_id, address, storage_slot) -> accessed account_nonce - address -> nonce account_balance - address -> balance account_code_hash - address -> code_hash account_storage - (address, storage_slot) -> storage

Sparse Base Each operand of keccak_f is 64-bit value in base 2 initially, so when we are doing base conversion from $b_1$ to $b_2$, we are doing: $x = \sum_{i=0}^{63} x_i b_1^i \rightarrow y = \sum_{i=0}^{63} f(x_i) b_2^i.$ The base can be up to 15 without wrapping around the field size ($15^{64} - 1 \approx 2^{250} < 2^{253}$). When doing conversion in practice, we don't lookup the 64-bit value, which could be too large. So we split it into chunks to fit system table size limit then using running sum trick to convert by lookup chunk by chunk. In fraklin, they seem to have table size limit around $2^{16}$, so conversion from base 13 they have chunk size 4, and from base 9 they have chunk size 5, where both have table size around $2^{16}$. ($4\log_213 \approx 14.8$ and $5\log_29 \approx 15.85$). The numbers could be found here.

Visualization Slide Definition step - We used to call it slot, but I found most time it's called a execution step. cell - a unit to store witness, located by tuple (column, row) Introduction EVM circuit basically iterate over a list of transactions to verify their update is applied to state, so we need to: Initialize a call and start to exection if it's a contract creation or if receiver is a contract

Introduction This note tries to figure out how storage circuit should work with evm circuit especially encountering REVERT in sub calls. (extending the reverting process describe here) We focus on storage of account state and error caused by REVERT in this note. Definition contextgc - global counter addr - account address holding opcodes pc - program counter op - opcode respect to addr and pc

Definition slot - multiple rows to verify a single op q - selector to enable a slot, should be 1 only in the last row in a slot. x_diff_inv - witnessed by prover to be inv(fixed_x - x), where the fixed_x is baked into circuit. It's used to switch on op and case custom constraint by 1 - (fixed_x - x) * x_diff_inv (is_zero expression). contextgc - global counter addr - address holding opcodes pc - program counter op - operator respect to addr and pc sp - stack pointer ... - more will be needed, see more details here

:::info Update: We should just follow traditional Fiat-Shamir, to always commit and generate challenge. Assuming EVM state transition is deterministic is not working for malicious prover. ::: Introduction In circuit, in order to reduce constraints, we try to use random linear combination as a cheap hash function on range-checked bytes for: Fit 32-bytes word (256-bits) in 254-bits field Accumulate arbitrary-length bytes (or say fit arbitrary-length bytes in 254-bits field)

Different editions Community https://drive.google.com/file/d/1mhO5otzOsVLDGwyNI1CQKWzE1Ly3FQws/view?usp=sharing Consensys Polygon Topics for discussions Insufficient capacity to verify 15m gas In community edition, the main VM circuit needs lots of witnesses per step, and to support the same gas limit target of current Ethereum (15m gas) in a single proof, and not blow up the amount of polynomials, we use lots of rotations. However, the usage of lots of rotations also limits the amount of gas we can verify, the bound of each dimension looks like:

Introduction In EVM circuit, ExecutionState are not well balanced, some are very complicated and require many lookups, some are not. But the cost of EVM circuit is determined by the worst case, this note shows how we strike the balance by folding the layout and improve the lookup usage efficiency. Approach For example, we want to perform 2 lookup (bitwise and and bitwise or) to the same table without too much overhead. Naive Layout $$ \begin{array}{|c|c|} \hline