code: https://github.com/scroll-tech/zkevm-circuits/blob/develop/zkevm-circuits/src/keccak_circuit.rs develop branch The Keccak hash function We shall first explain the Keccak hash function to be proved by our Keccak Circuit. This follows NIST Keccak Spec, Keccak Team Keccak Spec and the Keccak256 Implementation in our codebase. Keccak-f permutation function Any instance of the Keccak sponge function family makes use of one of the seven Keccak-$f$ permutations, denoted Keccak-$f[b]$, where $b \in {25, 50, 100, 200, 400, 800, 1600}$ is the width of the permutation. These Keccak-$f$ permutations are iterated constructions consisting of a sequence of almost identical rounds. The number of rounds $n_r$ depends on the permutation width, and is given by $n_r = 12 + 2 \ell$, where $2^\ell = \dfrac{b}{25}$. We focus on Keccak-$f[1600]$ which has $n_r=24$ rounds. At each round $1\leq k\leq n_r$, input are $5\times 5$ lanes of 64 bit words $A[x,y]$, where $[x,y]\in {0,...,4}\times {0,...,4}$ indicate the lane and the length of each lane is $64$-bit word. We then perform the following operations on $A[x,y]$:

Implementation: https://github.com/scroll-tech/halo2/pull/49 https://github.com/scroll-tech/halo2/pull/71 References: multivariate lookup argument: https://eprint.iacr.org/2022/1530 cq: https://eprint.iacr.org/2022/1763

code: https://github.com/scroll-tech/zkevm-circuits.git develop branch This draft may serve as a preliminary version of a part of future documentation/spec. Notice that the document is <i>not final</i> and may change due to potential errors in my understanding of the codebase or due to frequent changes of the codebase itself. Corrections, suggestions and comments are very welcome at any time. super_circuit Purpose

code: https://github.com/scroll-tech/misc-precompiled-circuit Let $p$ be the prime used in Modexp. When $x$ is U256, $\langle x \rangle$ stands for its limb representation; and $\langle x \rangle_p$ stands for $x\mod p$. Iterative algorithm for computing $\langle a^b \rangle_p$ Write $b=b_{n-1}+b_{n-2}\cdot 2+...+b_1\cdot 2^{n-2}+b_0\cdot 2^{n-1}$, i.e., in big-endian form $b=\overline{b_0b_1...b_{n-2}b_{n-1}}$. Then $$a^b=a^{b_{n-1}}\cdot (a^{b_{n-2}})^2\cdot ... \cdot (a^{b_{0}})^{2^{n-1}} \ .$$ So $a^b$ can be computed recursively as $$P_0=1, P_{k}=P_{k-1}^2\cdot a^{b_{k-1}}, k=1,...,n-1 \ ,$$ and $a^b=P_{n-1}$. This also applies when $\mod p$ is present, i.e., $a^b \mod p$ can be computed recursively as

code: https://github.com/scroll-tech/zkevm-circuits/blob/develop/zkevm-circuits/src/evm_circuit.rs develop branch. Purpose and Design The Ethereum Virtual Machine (EVM) is a state machine that defines the rules of valid state transition in the Ethereum protocol. This means that it specifies a deterministic function under which the next valid EVM state is computed from the current EVM state. The execution part of EVM uses opcodes to realize these state transitions, which results in an <i>Exection trace</i>.  The execution trace consists of each step of execution defined by the opcode. EVM Circuit aims at constructing a constraint system corresponding to this execution trace, that can be proved by some backend zk-proof system such as Halo2. The high-level design idea of EVM Circuit is somewhat reminiscent of the design of EVM itself (such as go-ethereum). In go-ethereum, an Intepreter loops over all instruction opcodes along the execution trace. At each instruction, the Intepreter helps to check relevant context information such as gas, stack, memory etc., and then sends the opcode to a JumpTable from which it fetches detailed operation that this opcode should do.

code: https://github.com/scroll-tech/mpt-circuit feat/refactor branch and feat/refactor_nonce branch. This draft may serve as a preliminary version of a part of future documentation/spec. Notice that the document is <i>not final</i> and may change due to potential errors in my understanding of the codebase or due to frequent changes of the codebase itself. Corrections, suggestions and comments are very welcome at any time. Thanks to @z2trillion for collaborating on drafting this documentation.

code: https://github.com/scroll-tech/mpt-circuit v0.4 branch. MPT table Merkle Patricia Tree is one of the key data structures used in Ethereum's storage layer. In our zkevm-circuits, we modify the original MPT into zkTrie, which is essentially a sparse binary Merkle Patricia Trie. A detailed description of zkTrie can be found in this zkTrie spec. In the below, to align with the naming in the codebase, we will use the terms "MPT" or "trie" to refer to the zkTrie (instead of the originally defined MPT as in Ethereum). In zkevm-circuits, we use MPT table to track step by step the state transitions from MPT operations. The MPT table has the following table layout q_enable address storage_key

code: https://github.com/scroll-tech/zkevm-circuits/blob/develop/zkevm-circuits/src/bytecode_circuit.rs develop branch The Bytecode table The EVM Circuit needs to lookup to the bytecode table that stores the correct bytecode information. This ensures that the bytes stored in the contract are the same as the bytes loaded in the table. The bytecode table has the following table layout: codehash tag (u64) index is_code value

code: https://github.com/scroll-tech/zkevm-circuits/blob/develop/zkevm-circuits/src/pi_circuit.rs develop branch Public Data PublicData contains the block header information (block contexts) as well as transactions information. It is structured as follows: # PublicData ## ChainID (u64Word) ## transactions - Transaction - block_number

code: https://github.com/scroll-tech/zkevm-circuits/blob/develop/zkevm-circuits/src/tx_circuit.rs develop branch Transactions Data in an Ethereum transaction According to this document of ETHTransactions, a submitted (legacy, EIP2718 type 0x00) transaction got recorded by the ethereum network will include the following data fields as information: raw: RLP encoded form of the tx RLP([nonce, gasPrice, gasLimit, to, value, data, v, r, s]); nonce: sequence number of tx; gasPrice: tx gas price per gas unit; gasLimit: the maximum amount of gas units that can be consumed by the tx;

code: https://github.com/scroll-tech/zkevm-circuits/blob/develop/zkevm-circuits/src/state_circuit.rs develop branch. EVM's read-write operations and the rw_table During execution, all of the EVM's read-write operations are recorded in rw_table, with an order sorted by a counter variable rw_counter. Each row of rw_table, a.k.a. RwRow, contains the following items as table columns: RwRowrw_counter is_write tag id address

code: https://github.com/scroll-tech/zkevm-circuits/blob/develop/zkevm-circuits/src/sig_circuit.rs develop branch Ethereum's tx signature process According to the Elliptic Curve Digital Signature Algorithm (ECDSA), the signatures (r,s) are calculated via ECDSA from msg_hash and a public_key using the formula (r,s)=ecdsa(msg_hash, public_key) The public_key is obtained from private_key by mapping the latter to an elliptic curve (EC) point. The r is the x-component of an EC point, and the same EC point's y-component will be used to determine the recovery id v = y%2 (the parity of y). Given the signature (v,r,s), the public_key can be recovered from (v,r,s) and msg_hash using ecrecover. The above scheme is applied to the Ethereum protocol. Each EOA address has its own private key and the corresponding public key is obtained via EC mapping (Note: only EOA address can initiate a tx and contract address cannot, because contract address is not calculated from public key but from nonce and EOA address). For a tx, we have msg_hash=keccak(RLP(tx's data that needs to be signed)). Since EOA account's address is created from from its public key via the formula caller_address=keccak(public_key)[-20:], we can recover the caller address once we recovered the public key.