A specification for a ZK-EVM
Olivier Bégassat 1 , Alexandre Belling1 , Théodore Chapuis-Chkaiban1 , andNicolas Liochon1
1ConsenSys, Applied R&D Team ∗October 2021

Abstract
We describe a zk-EVM arithmetization supporting the three following design goals: (1) support
for all EVM opcodes including internal smart contract calls, error management and gas management (2) ability to execute bytecode as is (3) minimal prover time. We strive to provide anarithmetization that respects the EVM specification as defined in the Ethereum yellow paper [1].
We provide an original and comprehensive approach of the zk-EVM problem which is technicallyrealizable using existing zero-knowledge proving schemes.

1

Introduction

1.1

Context and previous results

Increasing blockchains capacity, and hence lowering the transaction cost is a major technical challenge.
Rollups are promising technologies that would allow to considerably increase the capacity of the
Ethereum Blockchain. An introduction to Rollups, zk-EVMs and their role in improving Ethereum
capacity can be respectively found in [2, 3]. Recently, multiple attempts at building scalable andpractical rollup solutions have been positively received. zkSync [4], for instance, transpiles Yul intoa zk-VM friendly bytecode. Cairo [5], on the other hand, uses a custom architecture adapted to an
efficient STARK prover for smart contracts written in Cairo .
Other projects, such as Hermez [6] or Scroll Tech [7] aim to interpret directly the EVM bytecode,
without any intermediary transpiler or extra compilation step. This is also the approach we took.

1.2

Relation with existing projects

Our work draws inspiration from the existing design of Cairo [5] from which we borrow the conceptsof virtual columns, execution traces, range-proof and memory integrity trace permutation trick, andprovable read-only-memory. We extend and adapt these concepts to the different parts of our EVM
architecture. Most notably, we are able to adapt the EVM stack to a read-only architecture that leads
to a significant reduction of the size of our execution traces: we only need six pointers to represent thestack, while a naive implementation of the EVM stack would require at least 1024 pointers.
Our zk-EVM architecture comprises different modules, each tasked with proving the execution ofa specific part of the contract execution. We borrow this approach from Hermez [8].
∗ Email: firstName.lastName@consensys.net

1

1.3

Outline of this paper

The remainder of this paper is organized as follows:
1. Global organisation of the zk-EVM: provides a high level overview of the main componentsof our zk-EVM architecture.
2. Tools and notations: introduces the basic mathematical tools and methods used in our arithmetization,
3. Constraint sets: The low-level circuits for some of the components of our zk-EVM
To improve the readability of this paper, we have chosen to provide full constraint systems for afew (representative) modules only, which we strive to describe as comprehensively as possible. Other
modules, like the main execution trace and the storage module, have been fully designed - however,given the complexity of these components, we chose to postpone slightly their publication. If interested,
you may contact us directly for more information on these modules.
Given the complexity of our arithmetization, mistakes are to be expected.

Contents
1 Introduction
1.1 Context and previous results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Relation with existing projects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Outline of this paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
1
2

2 Global organisation of the zk-ethereum virtual machine
2.1 A high level overview of the zk-EVM modules . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Main execution trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 The RAM module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3 The arithmetic operations module . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.4 Binary, word comparison modules . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.5 Storage Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Arithmetization main ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Execution trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Module architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Dealing with inter-contract calls and batches . . . . . . . . . . . . . . . . . . . .
2.3 Putting it all together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
4
4
5
7
7
8
13
13
13
14
18

3 Tools and notations
19
3.1 Intertwining operator ⊙ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Permutation argument for column vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 (Row) permutation argument for matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 Plookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.5 Small-range range proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.6 If-elseif-else logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.7 GKR hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.8 Modules timestamps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.9 Constraint propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.10 Flags and instruction decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.11 Dealing with reverted transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.12 Error flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.13 Fees/Gas Costs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2

4 Word comparison module
24
4.1 Trace Columns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 Trace constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Constraint set for the Parent Memory module
27
5.1 Instructions treated . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 Trace columns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2.1 Stack trace inclusion columns: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2.2 Instruction unpacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.2.3 Parent module instruction decomposition: . . . . . . . . . . . . . . . . . . . . . . 28
5.2.4 Child module inclusion columns (word multiple memory): . . . . . . . . . . . . . 28
5.2.5 Call stack/SC batching: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2.6 Memory size, gas costs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2.7 Auxiliaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3 Opcodes constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3.1 MSTORE/MLOAD specific initialization. . . . . . . . . . . . . . . . . . . . . . 29
5.3.2 INIT instruction initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.3.3 RETURN specific initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.3.4 CALL specific initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.3.5 General value constraints. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.3.6 Memory size update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.3.7 RAM gas cost computation: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.3.8 Child RAM interior offsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.3.9 Value consistency/constraints: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3.10 Transition constraints: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.3.11 End instruction constraints: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6 Constraint set for the Child Memory module.
35
6.1 Role in the architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.2 Constraint columns for child RAM STORE/LOAD operations . . . . . . . . . . . . . . . 35
6.2.1 Parent module inclusion columns: . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.2.2 CRAM execution specific columns . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.3 Constraint set for the execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.4 Memory consistency columns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.4.1 Permutation columns: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.4.2 Force sorted columns: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.4.3 Range checks: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.5 Constraint set for the memory consistency . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2

Global organisation of the zk-ethereum virtual machine

Our model for a zk-EVM comprises various application specific subcomponents:• A (block specific) ROM (Read-Only-Memory) contains the bytecode of the smart contracts tobe executed.
• The main execution trace which processes the instructions and builds the stack memory.
• A small set of Application specific modules for RAM, storage, binary or arithmetic opcodes.
• An instruction decoder which decomposes the EVM opcodes in a series of instruction flags.

3

The ROM’s (which one may imagine as the concatenation of the bytecodes of the smart contracts
called in a block) main purpose is to translate the contracts bytecode into a succession of instructions
that can be processed by the zk-EVM.
Every module is designed to deal only with a certain subset of the EVM instruction set. Modules
select the instructions that concern them using specific flags from the flag decomposition provided by
the instruction decoder. The correctness of these flags and parameters is guaranteed by means of an
inclusion proof into the instruction decoder — an immutable piece of public data. Each module has
its own internal execution trace and associated constraint system. Modules are linked to the global
execution module by means of a bussing mechanism (in practice: plookup inclusion proofs).
This organization is represented in the figure 1.
Instruction Decoder

ROM

Child RAM Submodule

ALU256Main execution trace

Parent RAM Submodule

ALU128Storage

BinaryALU64Word Comparison

Figure 1: Modules of the zk-EVM. Arrows represent plookup inclusion proofs. N.B.: the Main execution trace, ALU, Storage, RAM, Binary and Word comparison modules also point to the instruction
decoder.

2.1

A high level overview of the zk-EVM modules

Here, we provide more details on the zk-EVM modules and their roles in the actual architecture.
The way these components interact and together constitute a zk-EVM is described on a high level insection 2.3.
About submodules: The modules in our zk-EVM split into submodules linked together by meansof Plookup proofs. The submodules defining a given module satisfy a hierarchical relationship: aparent submodule decomposes (a subset of module relevant) EVM instructions into atomic operations.
These operations are executed by its child submodule. This simplifies the mathematical formalizationof complex EVM operations, by balancing complex logic between different submodules.
The parent/child submodule structure is currently implemented in the RAM and ALU module.
2.1.1

Main execution trace

The main execution trace, or stack trace, is the core of the program execution. Every instruction goes
through the main execution trace and is either processed directly (e.g. P U SH, P OP , DU P or SW AP
instructions) or sent to other modules via a bus system - which we will describe extensively later.
Stack memory: The main execution trace also reproduces the stack architecture of the EVM. We
have chosen to rely on a read only memory model to reproduce the stack : the stack memory is amapping of Read-only-memory addresses (M em) to tuples (V al, P tr) composed of a stack value and4a pointer to the memory cell containing the previous stack element. The figure 2 provides an example
of such stack memory.
Mem
V al
P tr

0
v0
∅

1
v1
p1

···
···
···

2
v2
p2

N −1 NvN −1 vN
pN −1 pN

Figure 2: Table representation of the stack memory
Most of the EVM opcodes involve 0, 1 or 2 inputs, but some EVM instructions take more: CALL,
for instance, takes 7. Instructions like SW AP or DU P , implicitly take up to 16 (these instructions
may fetch the 16-th element of the stack and require access to all elements in between). Yet it proved
sufficient to keep track of only the two upper stack elements (rather than all 16 top stack elements),
thus our main execution trace only keeps track of the two upper stack elements. OPCODES that take3 arguments or more (explicitly or implicitly) need to be processed in several steps (i.e. several lines
in the execution trace), successively removing the top two elements of the stack.
It is comparatively easy to adapt our stack trace to deal with inter smart contract calls, andsmart contract batches : the stack memory can be reinitialized by adding stack elements pointing tothemselves which prevents contract calls from interacting with the stack cells that it shouldn’t haveaccess to. Dealing with inter smart contract calls is a recurrent issue among the existing models of
zk-EVMs.
2.1.2

The RAM module

Emulating efficiently the EVM RAM is a challenge in itself. Indeed, several instructions acting on
the RAM, such as RET U RN DAT ACOP Y , CALLDAT ACOP Y , RET U RN , BY T ECODECOP Y ,involve copying words of an arbitrary size (likely to be greater than the EVM word size - 32 bytes),that may come from two different smart contract memories. On the other hand, instructions like
M ST ORE, M LOAD, or M ST ORE8 act on at most 32 bytes of memory (1 byte for MSTORE8).
The EVM memory involves rather complex I/O relations due to it handling both bytes and words:
one can MSTORE elements in the memory at a byte granularity, but the MLOAD instruction always
retrieves EVM words (32 bytes) from memory. The EVM memory features a byte granularity, and32-bytes word addresses - i.e., this memory model can be seen as an array of maximum size 2256 whose
elements are bytes.
We have chosen to tweak slightly the representation and to store EVM words at word multiple
addresses, instead of bytes at any possible address. To store/load words to/from non word multiple
addresses, one would need to change at most two consecutive words in memory, the figure 3 provides
a graphical example of such memory model, with words of 4 bytes.
Reading addresses:

0x3

Reading output:

0xaa0240ff

Memory cells:
Memory addresses:

0x7

0x0240ff bb

0x15fe32aa
0x0

0x4

0x8

Figure 3: Overlapping reading process for words of 4 bytes.

5

To deal with the aforementioned technical challenges, we have decided to divide the RAM module
into two submodules: the child RAM and the parent RAM submodules. The consistency between thevalues of the parent and the child RAM submodules is guaranteed by a Plookup inclusion proof of theparent RAM submodule into the child RAM submodule.
Parent RAM submodule: The parent RAM submodule processes the memory instructions coming from the main execution trace - it decomposes these complex EVM instructions into simple
READ/WRITE memory instructions, that involve writing/reading at most two consecutive memory
words. The parent RAM submodule sends these simple instructions to the child RAM submodule.
Child RAM submodule: The child RAM submodule executes the simple instructions transmitted
by the parent RAM submodule, returns the result and verifies the consistency of the RAM memory
which amounts to checking that the RAM addresses are continuous and that the reading operations
are consistent with the previous values stored.
Worked out example. The figure 3 is an explanatory drawing of the interactions between theparent and the child RAM with 4-byte long words. This figure explains the interactions between theparent and the Child RAM for a RETURN operation, that stores the values of the current RAM
located from the address 0x13a2 to 0x12ab, to the caller RAM, at the address range [0xaace, 0xaac3].
Parent RAM:
0x0

: READ: WRITE

1Child RAM:
Current SC memory:
Current RAM addresses:
Caller SC memory:
Caller RAM addresses:

0x4
0x8
0xc
0x40ff 0x15fe32aa 0x40ffeb
0x2
0xb
2

3

4

5

0x17bb40ff
0x13a00x15fe32aa
0x13a40x40ffebaa
0x13a80xcdef40ff
0xaabc

0x15fe32aa
0xaac00x40ffeb76
0xaac4

6

Figure 4: Illustration of the relations between the parent and the child RAM, for a RETURN instruction.
This operation may be divided into 6 steps, indicated in the figure 3:
1. Read the last two bytes from the current RAM address 0x13a0
2. Replace the last two bytes of the caller RAM address 0xaabe with the previously read bytes
3. Read the whole memory word of the current RAM starting at the address 0x13a4
4. Store this memory word to the caller RAM at the address 0xaac0
5. Read the first 3 bytes of the memory word at the address 0x13a8 of the current RAM.
6. Replace the first 3 bytes of the memory word at the address 0xaac4 of the caller RAM.
6

2.1.3

The arithmetic operations moduleThis module emulates the EVM 256-bit arithmetic. It is comprised of 3 submodules: the ALU256,
the ALU128 and the ALU64 which respectively perform arithmetic operations on 256 bit long words,
128 bit long words and 64 bit long words. These three modules are tied together by Plookup inclusion
proofs of the 256ALU into the 128ALU into the 64ALU. The figure 5 provides an example of such
submodule communication to perform a 256-bit addition of two field elements.
256ALU: The 256-bit ALU decomposes 256-bit long input field elements into two 128-bit long field
elements - the high 128 bits and the low 128 bits - and sends arithmetic operation requests to the 128
bit ALU. It further computes the final result by computing the high/low bit decomposition of it.
128ALU: The 128ALU follows the same pattern, except that, this time the 128-bit words are decomposed into 64-bit words and arithmetic operation requests are sent to the 64ALU.
64ALU: The 64ALU does the actual computations: it checks that the inputs are indeed 64 bit words
by performing range proofs on the 16-bit decomposition of these 64-bit long words. The results aresent back to the 128ALU, which then sends back the results to the 256ALU.
ALU256
A256 + B256 = C256 + carry256

ALU128
Al,128 + Bl,128 = (Cl,128 , carryl,128 )Ah,128 + Bh,128 + carryl,128 = (Ch,128 , carryh,128 )ALU64All,64 + Bll,64 = (Cll,64 , carryll,64 )Ahl,64 + Bhl,64 = (Chl,64 , carryhl,64 )Alh,64 + Blh,64 + carryll,64 = (Clh,64 , carrylh,64 )Ahh,64 + Bhh,64 + carryhl,64 = (Chh,64 , carryhh,64 )Figure 5: Field element decomposition and submodules communication inside the arithmetic module,
addition example.

2.1.4

Binary, word comparison modules

The binary and word comparison modules are two separate modules that decompose field elements
into 16-bit words and perform binary operations on these 16-bit word.
Binary module: The binary module relies on Plookup to perform binary operations - one has
to prove the inclusion of quadruples (Inst, Byte1 , Byte2 , Byteres ) into a public logic table. Table 1
provides an illustration (with a byte decomposition, to simplify the representation) of this process the timestamp column allows keeping track of the instruction being currently executed (instructions
are executed in several steps, to decompose the inputs and perform bitwise operations).

7

Inst
AND
AND
AND
AND
XOR
XOR
..
.

Timestamp
1
1
1
1
2
2
..
.

Input10x1ea1ff
0x1ea1ff
0x1ea1ff
0x1ea1ff
0x10010x1001
..
.

Byte1
0xff
0xa1
0x1e
0x0
0x01
0x10
..
.

Carry10x1ea1
0x1e
0x00
0x00
0x10
0x00
..
.

Input20xff00ff00
0xff00ff00
0xff00ff00
0xff00ff00
0x10100x1010
..
.

Byte2
0x00
0xff
0x00
0xff
0x10
0x10
..
.

Carry20xff00ff
0xff00
0xff
0x00
0x10
0x10
..
.

Result0x00a1000x00a1000x00a1000x00a1000x00110x0011..
.

Byteres
0x00
0xa1
0x00
0x00
0x11
0x00
..
.

Carryres0x00a1
0x00
0x00
0x00
0x00
0x00
..
.

Table 1: Binary module execution trace
Word Comparison module: The word comparison module computes the difference between thebytes of two memory words, starting from the most significant byte and returns a comparison boolean:
for instance, when testing an inequality a < b, the word module returns 1 when this inequality isverified, 0 otherwise.
Table 2 represents the execution of this module in a similar way as the binary module execution.
For the sake of the representation, we will use 8-bit (byte) decomposition instead of 16-bits word
decomposition.
TS
0
0
0
1
1
1
2
2
2
..
.

Sw
1
1
1
0
0
0
1
1
1
..
.

Eq
0
0
0
1
1
1
1
1
1
..
.

Inst
SGT
SGT
SGT
LT
LT
LT
GT
GT
GT
..
.

Input_1
0xa3ff02
0xa3ff02
0xa3ff02
0x00a12c0x00a12c0x00a12c
0x0fabd9
0x0fabd9
0x0fabd9..
.

Input_2
0xa3ffb7
0xa3ffb7
0xa3ffb7
0x00a12c0x00a12c0x00a12c
0x0fc73d
0x0fc73d
0x0fc73d
..
.

Res
0
0
0
1
1
1
0
0
0
..
.

Prefix_1
0xa3
0xa3ff
0xa3ff02
0x00
0x00a10x00a12c
0x0f
0x0fab0x0fabd9..
.

Prefix_2
0xa3
0xa3ff
0xa3ffb7
0x00
0x00a10x00a12c
0x0f
0x0fc70x0fc73d
..
.

Comp
1
1
1
0
0
0
1
1
1
..
.

B_1
a3
ff
02
00
a1
2c
0f
ab
d9
..
.

B_2
a3
ff
b7
00
a1
2c
0f
c7
3d
..
.

BComp
0
0
1
0
0
0
0
1
0
..
.

Table 2: We abbreviate WCTimeStamp, SwitchFlag and EqFlag to TS, Sw and Eq respectively.

2.1.5

Storage Module

The storage module represents the EVM word addressable, word granular storage. This module isinitialized with the previous storage of the smart contract (the storage initialization consistency is
performed within the zk-EVM). The storage module outputs the new storage of the executed smart
contracts.
This module performs the elementary operations SST ORE and SLOAD. The main complexityof it relies on its storage check part that allows to:• Initialize the storage of the smart contracts loaded in the ROM• Check the consistency of the storage values used within the execution• Revert the storage state if the transaction has failed• Compute the final storage hash.
• Compute the gas cost associated with the storage operations.
8

Length
3
2
1
0
1
0
..
.

Figure 6: The above represents a portion of the tree of nested smart contract calls of a transaction.
The solid blue dots represent calls to a given smart contract A, the hollow ones represent calls to othersmart contracts. Red crosses represent reverts. The underlined integers k = [[ tk , tk+1 [[ represent the
STORAGE_TIMESTAMP intervals wherein a given smart contract performs storage operations
The smart contract calls within a given transaction form a rooted tree with directed edges (contract
calls) whose vertices (smart contracts) naturally carry labels: a smart contract address and a set ofsmart contract numbers (1 + dv where dv is the outgoing degree of vertex v). For a given smart
contract address and storage address we define extra labels: a time interval representing the (storage
time stamp) validity interval of stored values, the revert stamp, the previous revert stamp (i.e. therevert stamp containing the currently valid storage values) and the parent revert stamp (i.e. the revert
stamp to which to roll back in case of a revert). We stress that these labels depend not only on thesmart contract address but also on the storage address. This allows us to only propagate auxiliary
information only for the storage addresses that are effectively touched at a later point by the smart
contract. For a more detailed explanation of the tools we use to process reverted transactions (like therevert stamps), please refer to the section 3.11.
The main properties of these labels are that, for a given smart contract address and storage address,• the begin and end storage stamps labels with a given revert stamp form a partition by intervalsof either the empty interval (if the values at that address aren’t touched in the subtree) or of theinterval with the "entry" and "exit" storage time stamps of the (nested) call• the Previous_Revert_Stamp indicates the Revert Stamp of the last relevant modification to thedata at the storage address• the Parent_Revert_Stamp indicates the Revert Stamp to which to revert to when exiting the9Figure 7: We work with the smart contract A and a given storage address addr. We color the calls to
A in green if that call accesses (read or write) the address addr.

10Figure 8: This simplified view of the nested calls to A discards all calls to other smart contracts aswell as all calls to A that don’t access the storage address S
addr and whose descendants also don’t...
access it. N.B. We use the short hand a ⌣ b to represent k=a,...,b k = [[ ta , tb+1 [[ to represent the
STORAGE_STAMP intervals of validity. Since the call (a) reverts, one must initialize the storage
address addr of the contract A for the REVERT_STAMP = 10, this initialized value remains valid
until the next time addr is modified by a call of A within REVERT_STAMP = 10. Only the call...
(d) to A accesses addr at a REVERT_STAMP = 10. Its interval is thus 10 ⌣ 33. The call (b) to
A does’t access addr but one of its descendants does. We must thus load the currently valid value at...
the storage address addr along with the validity period, 3 ⌣ 9. Its descendant (call (c)) access addr
and reverts and is the only call to A for that REVERT_STAMP = 12, thus its STORAGE_STAMP...
validity interval is the whole time interval wherein (c) runs, i.e. 4 ⌣ 6. There are two calls to A at
REVERT_STAMP = 14, one which reverts, one which doesn’t revert on its own (but will be reverted
nonetheless, having positive REVERT_STAMP ). There are thus 3 STORAGE_STAMP intervals...
partitioning the STORAGE_STAMP interval wherein REVERT_STAMP = 14: 25, 26 and 27 ⌣ 31

11

SC
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A

ADDR
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr
addr

REV
10
10
10
10
10
10
11
12
12
12
12
14
14
14
14
14
14
14
14
14
14
14
14

SS
τ0
τ1
τ2
τ3
τ4
τ5
τ6
τ7
τ8
τ9
τ10
τ11
τ12
τ13
τ14
τ15
τ16
τ17
τ18
τ19
τ20
τ21
τ22

Inst
INIT
SLOAD
SLOAD
SSTORE
SSTORE
SLOAD
INIT
INIT
SSTORE
SSTORE
SLOAD
INIT
SLOAD
SSTORE
SSTORESLOAD
SLOAD
SSTORESLOAD
SSTORESLOAD
SSTORE
SSTORE

Val
v0
v0
v0
v1
v2
v2
v1
v1
v3
v4
v4
v2
v2
v6
v6
v6
v6
v7
v7
v8
v8
v9
v10

Beg
t1
t10
t10
t10
t10
t10
t3
t4
t4
t4
t4
t25
t25
t25
t25
t26
t26
t26
t27
t27
t27
t27
t27

End
t10
t34
t34
t34
t34
t34
t10
t7
t7
t7
t7
t26
t26
t26
t26
t27
t27
t27
t32
t32
t32
t32
t32

PREV
6
10
10
10
10
10
10
11
12
12
12
10
14
14
14
14
14
14
14
14
14
14
14

PARENT
6
6
6
6
6
6
10
11
11
11
11
10
10
10
10
10
10
10
10
10
10
10
10

Figure 9: The part of the storage execution trace that concerns itself with the storage operations performed by a smart contract in a block. It is ordered first by smart contract address(here: A), then by storage address (here addr ), then by REVERT_STAMP, then by STORAGE_STAMP. We use the shorthand Inst for INSTRUCTION, SS for STORAGE_STAMP, Beg
for Begin_STORAGE_STAMP, End for End_STORAGE_STAMP, REV for REVERT_STAMP,PREV for PREVIOUS_REVERT_STAMP, PARENT for PARENT_REVERT_STAMP, Val for
VALUE.

12

current revert stamp.
We provide a worked out example below. In the pictures below the blue dots represent calls to thesame smart contract. We have given each node a label (a)-(g) to be distinguish between them.

2.2

Arithmetization main ideas

We explain the main concepts of the arithmetization of the zk-EVM. We provide more details on themodules, their structure structures and their interactions with each other.
2.2.1

Execution trace

Each module comes with an associated execution trace. Execution traces can be pictured as 2 dimensional arrays (high level representation). In applications they will be encoded using polynomialcommitment (low level representation). The number of rows of each execution trace is proportional
to the number of instructions executed in the module; the number of columns is module-dependentand independent of the number of instructions executed by the module in a particular execution of
the zk-EVM. Execution traces have anywhere from 10 to 100 columns. We may assume, padding withappropriate default values as needed, that the number of rows of each execution trace is a power oftwo.
In practice, describing every column of the execution trace can quickly become tedious, so we havechosen to borrow the virtual column/subcolumn paradigm from Cairo - which is a rather convenientand powerful way to describe the arithmetization of the zk-EVM.
Virtual columns/subcolumns: Using our high-level representation of the execution trace, a virtualcolumn is a power of two-periodic subset of rows of a given column of an execution trace. For instance,
given an execution trace of size 2i , and a column C of this execution trace, V C defined by:
V Ck = C3+24 ×k , ∀k ∈ [[ 0, 2i−4 [[is the virtual column containing all rows of C whose row index is conguent to 3 mod 16.
A virtual subcolumn is a set of virtual columns obtained from another column or virtual column. Hence, the notion of virtual subcolumn supposes a relation dependance between the different
subcolumns belonging to the same column.
The main advantage of the notion of virtual column and virtual subcolumn is the fact that one is
not bound by the exact size of a given column: one column of an execution trace can be composed ofseveral virtual columns stacked together.
2.2.2

Module architecture

The columns of a module’s execution trace may be grouped into different subsets - each such subset
having a specific role in the execution proof generation. Figure 10 represents such a module architecture:• The instruction unpacking columns (green box): a group of columns that associates a given
EVM opcode to a sequence of flags, subsets of these flags being meaningful to a given module’s
execution trace. The consistency of the instruction unpacking columns is ensured by a Plookup
inclusion proof of the corresponding columns of the Instruction decoder module.
• The main execution consistency columns: a group of columns that matches the instruction
currently executed by a given module to the corresponding instruction that appears in the main
execution trace. The consistency of this set of columns is guaranteed by a Plookup inclusion
proof of these module columns in the corresponding main execution trace columns.

13• The module specific time execution columns (blue box): are the core columns of each module.
The constraints that must be verified during the module execution are applied to these columns.
• The module specific space execution columns (black box): are the columns associated withan underlying memory model specific to the module. These columns are used to check theconsistency of the memory model with the time execution part of the module. For instance,
the main execution trace space execution columns ensure the consistency of the Read only stackmemory; the ones of the child RAM submodule ensure the consistency of the RAM memory withthe read/write operation performed on the RAM.
• The range proof columns (orange box): are used for range proof purposes using the Cairo-stylerange proofs that will be described in the next section(Sub)Columns may belong to more than one group, and some modules may contain more than one
group for each category: for instance, in the main execution trace, there are two groups of space
execution columns - a first group ensures stack memory consistency; a second group ensures call stackmemory consistency. Besides, some modules may not use some groups of columns - the binary module,
for instance, doesn’t use range proof columns.
To simplify the formalisation, we have added a layer of abstraction, dividing the above groups ofcolumns into two bigger sets of columns: the time ordered columns and the space ordered columns.
The time ordered columns display an internal time coherence: two successive instructions appearing
in the time ordered part of a module are executed one after the other. This is needed to maintain a
global execution order coherence.
The space ordered columns often describe an underlying memory model - these columns are used to
enforce spatial coherence (e.g. memory address coherence). Two successive rows of a virtual column
belonging to the space ordered columns represent the same or two successive memory addresses. Thesecolumns are needed to ensure the memory consistencies of the zk-EVM, i.e. that the values read froma specific memory address match the ones previously stored at that same address.
2.2.3

Dealing with inter-contract calls and batches

The inter-contract call process of the EVM involves complex interactions between the two execution
environments of the caller and called contracts. We have chosen to handle all the interactions directlyin our zk-EVM model by creating a new execution environment every time a inter-contract call is
performed. To be able to correctly emulate inter-contract calls, one should be careful that:• The two execution environments are usually completely independant of one another (i.e. thecalled smart contract can’t access to the memory of the caller contract) as in the case of a CALL
instruction.
• Some interactions between the caller and the called contract are permitted in specific cases (e.g.
storing the returned data to the memory of the caller).
• Other less common opcodes (e.g. DELEGATECALL) allow the called smart contract to accessthe caller smart contract’s execution environment.
• Two call operations of the same contract involve creating two different execution environments.
We have decided to handle inter-contract calls using a CALL STACK structure, that keeps track of
the execution environment of the caller contract - that structure is particularly useful in dealing withchained contract calls as it is needed to retrieve successively the previous execution environments.
The consistency of the CALL STACK memory is ensured in the main execution trace, the same way
as the main STACK memory. The CALL STACK memory is a continuous READ ONLY MEMORY
that associates to a unique smart contract number, SC_N um, a n-tuple of associated information (suchas SC_ADDRESS, P rev_T op, P rev_RSP , P rev_P C, Ret_Of f set, Ret_Len, Caller_N um,
14

Time ordered columns

Space ordered columns

Inst Flags
Main traceconsistency

Execution Step: iModuleexecution

Range proofs

Internal Memory
consistency
Module stamps

Time coherence

Space coherenceInst Flags
Main traceconsistency

Execution Step: i + 1
Moduleexecution

Range proofs

Internal Memory
consistency
Module stamps

Figure 10: A module architecture illustration15

Depth), specific to the set of contracts executed. In a sequence of smart contracts executions (eachof which may call other smart contracts) the smart contract number is defined as starting with 0 for
the first smart contract being executed and incremented by one every time another smart contract is
executed (triggered either by an internal call or when exiting a sequence of internal calls and moving
onto a new transaction). As such the smart contract number is distinct from the smart contract’s
address/identifier and a given contract may have several smart contract numbers if it is called several
times in a batch of transactions. A pointer N ext_SC_N um keeps track of the next CALL STACK
address that is not yet attributed (in that respect its role is similar to the WSP pointer for the main
STACK memory).
The figure 11 provides a worked out example of the evolution of the call stack associated with theexecution of a batch of smart contracts.

16

DEP T H = 0

DEP T H = 1

DEP T H = 2

SC n°1SC n°2SC n°3SC n°0 (ROOT)

SC n°4SC n°5(a) A call stack graphical example

Step
0
1
2
..
.
103
104
105
..
.
208
209
..
.
287
288
..
.
354
355
..
.
360
361
..
.
365
365
..
.
387
388
..
.
453
0

Instruction
GLOB_IN IT
PUSH
PUSH
..
.
CALL
PUSH
JUMPI
..
.
CALL
PUSH
..
.
RETURN
PUSH
..
.
CALL
PUSH
..
.
RETURNSWAP2..
.
RETURNMLOAD..
.
RETURNPUSH..
.
RETURNGLOB_EN D

SC_N um
0
1
1
..
.
1
2
2
..
.
2
3
..
.
3
2
..
.
2
4
..
.
4
2
..
.
2
1
..
.
1
5
..
.
5
0

PC
0
0
1
..
.
92
0
1
..
.
750
0
..
.
75
751
..
.
354
0
..
.
43
354
..
.
250
93
..
.
165
0
..
.
230
1

Top
0
2
3
..
.
87
89
90
..
.
169
174
..
.
254
169
..
.
273
276
..
.
285
273
..
.
299
87
..
.
353
355
..
.
432
0

RSP
0
1
2
..
.
76
88
89
..
.
157
173
..
.
232
157
..
.
269
275
..
.
283
269
..
.
296
76
..
.
344
354
..
.
415
0

WSP
0
3
4
..
.
88
90
91
..
.
173
175
..
.
263
263
..
.
275
277
..
.
288
288
..
.
305
305
..
.
354
356
..
.
453
0

Caller_N um
0
0
0
..
.
0
1
1
..
.
1
2
..
.
2
1
..
.
1
2
..
.
2
1
..
.
1
0
..
.
0
0
..
.
0
0

P rev_P C
0
0
0
..
.
0
93
93
..
.
93
751
..
.
751
93
..
.
93
354
..
.
354
93
..
.
93
0
..
.
0
0
..
.
0
0

P rev_T op
0
0
0
..
.
0
87
87
..
.
87
169
..
.
169
87
..
.
87
273
..
.
273
87
..
.
87
1
..
.
1
0
..
.
0
0

P rev_RSP
0
0
0
..
.
0
76
76
..
.
76
157
..
.
157
76
..
.
76
269
..
.
269
76
..
.
76
0
..
.
0
0
..
.
0
0

(b) An example of a (partial) main execution trace call stack, associated with 11a

Figure 11: An example of the call stack evolution with inter-smart contract calls and batches.
17

DEPTH
0
0
0
..
.
0
1
1
..
.
1
2
..
.
2
1
..
.
1
2
..
.
2
1
..
.
1
0
..
.
0
0
..
.
0
0

2.3

Putting it all together

The architecture of our zk-EVM is rather complex - modules, instruction decoding, flags, bussing
system . . . This short section sums up the "gist" of how the modules and their constraint systems
relate to the main execution trace and assemble into a zk-EVM. Suppose that we want to prove theexecution of a smart contract whose bytecode and storage are stored in our zk-rollup. Here are themain steps of how that works:• We first load the full contract (EVM) bytecode into the ROM. We do this by building a
BytecodeROM column and a P CROM column. To prove that the bytecode of the ROM is correctly built, we compute the root hash associated with the ROM bytecode and compare it withthe codehash stored in the rollup.
• We then load the sequence instructions effectively carried out during the smart contract execution into the main execution trace. To verify that the opcodes executed are part of the ROM
bytecode, we perform a Plookup inclusion proof (table version) of the pair of commitments(P Cexec trace , Bytecodeexec trace ) into the table (P CROM , BytecodeROM ).
Our zk-EVM (i.e. the main execution trace and the various modules) cannot directly interpreted
these EVM instructions: we have to translate the Bytecodeexec trace column into a sequence of module
specific flags. This is the role of the instruction decoder, a public, immutable, data table, whose
commitment to the values is publicly available for consistency checks - the instruction decoder allows
for the flag decomposition of the EVM opcodes into a sequence of flags (IDF lag1 , . . . , IDF lagn ) thatcan be interpreted by the (main) execution trace and other relevant modules. The problem is then to
check the consistency between the instruction flags written into the execution traces (let’s note thesecommitments ET F lag1 , . . . , ET F lagn ) and the corresponding instruction flags hard-coded into the
instruction decoder. This is solved with a plookup proof of consistency.
• We perform a plookup inclusion proof between the n+1-tuple of commitments (Bytecodeexec trace ,ET F lag1 , . . . , ET F lagn ) and the associated tuple of commitments from the Instruction decoder(EV Mopcode , IDF lag1 , . . . , IDF lagn )Note that this process (instruction decomposition) is done both in the main execution trace and in
the module execution traces (using different sets of flags). The general idea is that the flags that areloaded into the Main Execution Trace are used for the inclusion proofs linking certain columns of themodule execution traces to the main execution trace, while the flags loaded into a module are used forthe internal constraints that must be satisfied by the columns of the module execution trace.
• Now that the EVM instructions can be interpreted by our zk-EVM, we have to execute theoperations and verify that the computations have been well performed. Depending on the valueof the instruction flags, a different part of the zk-circuit is going to be activated.
– For instance, to ensure that the Memory instructions of the current contract (such as
M ST ORE, M LOAD, RET U RN, CALL, ...) are transmitted to the RAM module, a flagcolumn RAM _Instruction is set in the main execution trace. When this flag is set, someconstraints of the main execution trace become active - for example, the value of the RAM
timestamp has to increase during this clockcycle.
In the RAM module, other flags will be set to select the internal module behaviour - todistinguish between the M ST ORE and M ST ORE8 instructions, a flag SIZE, containedin the instruction decoder and loaded into the RAM, imposes the length of the word stored
in the RAM, etc. . .
The ram execution trace is augmented with a constant column (equal to 1) which will be
included (along with other columns, such as the instruction column, the time stamp column,. . . ) into the main execution trace into the RAM _Instruction flag column.
18

– Another example may be the JUMP instruction that implies an exceptional modification of
the value of the PC - when the JU M P _F LAG is set, the circuit that performs the normal
update the PC is deactivated and the special PC update circuit is activated.
– Importantly, the constraint equations for the modules is independent of the precise sequence of module instruction being executed: there is a fixed, module-dependent set of
constraints ensuring the internal coherence of each module execution trace. The instructionspecific behaviour is selected within that set of constraints through the instruction specificflags.
• Every module is linked to the main execution trace by a Plookup proof: the M ODU LE_IN ST
flag (in the main execution trace) is set when an instruction that has to be transmitted toa given module, the M ODU LE_ST AM P keeps track of the current instruction number being executed by the module, and the top stack elements acts as input values for the modules, hence every Plookup inclusion proof has to show that the (M ODU LE_IN ST , IN ST ,M ODU LE_ST AM P , IN P U T1 , IN P U T2 ) module trace columns are included within the corresponding main execution trace columns.

3

Tools and notations

This section contains a high-level description of the main tools and techniques used in the arithmetization. The tools we describe below allow us (1) to prove claims about relationships between subcolumns
within a given execution trace (2) to prove claims about relationships between subcolumns from different execution traces and thus to connect different sumodules of the zk-evm to each other (3) toexpress program logic in the arithmetization.

3.1

Intertwining operator ⊙Given two column vectors A = (a0 , a1 , . . . , aN −1 )T and B = (b0 , b1 , . . . , bN −1 )T of equal length N
define A ⊙ B to be the column vector of length 2N obtained by intertwining the coefficients of A and
B like so: A ⊙ B = (a0 , b0 , a1 , b1 , . . . , aN −1 , bN −1 )T . Both A and B can be recovered from A ⊙ B as
periodic subsets (i.e. A and B are subcolumns of A ⊙ B). When A and B are viewed as polynomials
given by their evaluations (i.e. ak = P (k) and bk = Q(k) for polynomials P, Q) we can view A ⊙ B asa polynomial R, too, via R(k) = P (k/2) = ak/2 when k is even, R(k) = Q((k − 1)/2) = b(k−1)/2 when
k is odd.

3.2

Permutation argument for column vectors

We recall a Plonk [9]/Cairo-type [5] permutation argument allowing one to prove that two column
vectors A and B are, with overwhelming probability, row permutations of one another. Recall that A
and B are row permutations of one another if there exists a permutation σ of the index set {0, 1, . . . , N −1} such that for every row index i, Bi = Aσ(i) . The argument requires the introduction of a single
new column ΠB
A of length N , the construction of which requires a public random field element z ∈ F.
The values in this column are defined by
Y z − Aℓ B.
ΠA i =
z − Bℓ0≤ℓ<i3.3(Row) permutation argument for matrices

We can extend the previous argument to a row permutation argument for matrices. Two matrices
A = (Aij ) and B = (Bij ) (with r columns, N rows and coefficients in the field F) are row-permutations

19

of one another if there exists a permutation σ of the index set of rows {0, 1, . . . , N − 1} such that thei-th row of B equals the σ(i)-th row of A i.e. if∀i ∈ {0, 1, . . . , N − 1} ∀j ∈ {1, 2, . . . , r},Bi,j = Aσ(i),j

Our arithmetization requires arguments proving that two matrices are row permutations of one another.
We can use the row permutation argument for column vectors described above to prove the row
permutation property.
Indeed,Pit is enough to prove the row permutation property for a random linearPrrcombination j=1 θj Aj and j=1 θj Bj (where the A1 , . . . , Ar and B1 , . . . , Br are the columns of A 
and B respectively.) This argument requires the introduction of a single new column vector ΠB
A oflength N constructed by accumulating quotients of the coefficients of the random linear combinationsof values in A and B:
Y z − Pr θk Aℓ,k
 B
Prk=1
.
ΠA i =z − k=1 θk Bℓ,k0≤ℓ<iIn our applications the matrices A and B are constructed by specifying r column vectors A1 , A2 , . . . , Ar
for A and r column vectors B1 , B2 , . . . , Br for B (all of equal length N ). These column vectors are
obtained as columns/subcolumns of some module’s execution trace. We require such permutationarguments for two reasons:Space-time reordering the stack, memory and storage modules must satisfy two largely independent
sets of constraints: time consistency and space consistency. The stack, say, has to be consistent
with the temporal execution of the EVM — thus popping the top of the stack for instance must
modify the pointer to the top of the stack accordingly at the next clockcycle. On the other hand,
performing several pops in a row (or one of the stack pointers being sent a ways back down
below the top of the stack) will unearth values in the stack that may have been written there awhile back – thus we need to make sure that values once written to the stack are indeed the ones
recovered at a later stage through a pointer pointing to the corresponding stack address.
The execution trace of these modules will thus be tasked with proving both types of constraints
Cairo-style range proofs explained below
e to signify that B is a row permutation of the columne (resp. B = A)
We use the notation B = A
vector A (resp. B is a row permutation of the matrix A). Whenever we use this notation it is tacitly
assumed that the execution trace is augmented with a column Π witnessing the permutation.

3.4

Plookup

The overall architecture of our zk-evm is modular — separate subunits are specialized in certain
subtasks: they obey independent constraint sets and have separate (but not unrelated) execution
traces. Thus one module may be tasked with 256 bit arithmetic while another deals with binary
operations and yet another deals with memory. Connections between these modules allow modules todelegate computations that fall outside of their specialization to the relevant submodules.
Plookup arguments [10] are the means by which these connections are realized:
Plookup inclusion proofs between subcolumns we can relate the contents of subcolumns of one
execution trace to another by means of an inclusion proof. This serves two purposes: (1) it allows
the contents of the first column to flow as inputs into the second module where a specialized
computation might be verifiable or (2) to use the values of the first column to justify values ofthe second column when the second module can’t verify the associated constraints (e.g. how
hashes enter a non hash module).
Plookup inclusion proofs for tables arithmetic operations that are inefficient in field arithmetic(e.g. binary operations) are hardcoded in a plookup table and find their way into execution
traces by means of plookup inclusion proofs. Note that column contents can be filtered using
flag columns.
20

3.5

Small-range range proofs

Cairo-style range proofs (or short-range range proofs) apply to show that values in a column are withina relatively short interval [[ a, b ]] of consecutive integers. Doing this requires reordering the column inascending order while filling in all missing gaps. We thus require a permutation argument (witnessedby an extra column Π) along with row-wise checks to the effect that the reordered values start at a,end with b, and from one row to the next the values can only remain the same or change by +1.

3.6

If-elseif-else logic

Arithmetization of the EVM needs to handle branching execution paths conditional to some condition
being satisfied or not. In particular, we need to handle branching of the following sort: (1) given aboolean b ∈ {0, 1}, execute either path P0 or P1 according to whether b = 0 or b = 1 (1’) more generally,
given a constrained variable c ∈ {c1 , . . . , ck } for pairwise distinct field elements c1 , . . . , ck ∈ F, executethe corresponding path P1 , P2 , . . . , Pk depending on the value of c (2) given an arbitrary field elementa ∈ F, execute either path P0 or P̸=0 according to whether a = 0 or a ̸= 0.
Typically the variables conditioning the branching behaviour (b, c or a above) are taken direcly
from a (sub)column of the execution trace. Booleanity is simply checked in a quadratic constraint(b ∈ {0, 1} ⇐⇒ b2 = b) and the branching behaviour (i.e. the associated constraint) can be simply
expressed by means of a second quadratic constraint
similarly for constrained variables
Q ((1−b)P0 +bP1 ),P
albeit at the cost of higher degree constraints ( i (c − ci ) = 0 and i Li (c)Pi for adequate Lagrange
interpolation polynomials Li ). Branching behaviour of the third kind (i.e. where we need to distinguishd This column is
a = 0 from a ̸= 0) requires the introduction of a new column which we label 1/a.
dconstructed in such a way that a ◦ 1/a is a boolean column (where ◦ represents componentwise productof columns) along the appropriate subdomain of G.

3.7

GKR hashing

Our zk-evm uses an algebraic hash function compatible with efficient GKR arithmetization, for instance
MiMC hashes. There is thus a separate GKR-verifier module for hashing linked to execution tracesof the relevant submodules by means of plookup inclusion proofs. This decision was motivated by the
recent results on GKR, published on EthResearch [11]3.8

Modules timestamps

Timestamps are used internally in our arithmetization to link the different modules together. There
are two kinds of timestamps per module: instruction timestamps increase when a new instruction
starts sending requests to the module bus; atomic timestamps for each individual request that issent to the module bus — a single instruction may send several requests to the bus (e.g. CALL removes
the 7 elements on top of the stack in a sequence of 4 elementary steps popping the top two elements ofthe stack, which requires 4 requests to the Memory module). These timestamps are used to prove theinclusion of every instruction executed by each external module in the main execution trace; but also
to prove that each request sent to a child submodule by an associated parent module has been processed.
The GLOBAL_IN IT special opcode, executed before any other instruction, keeps track of thetotal number of instructions and atomic module calls and initializes the module timestamp values tozero for the next instruction. This number is compared to the sequentially built timestamp values of
the GLOBAL_EN D special opcode, executed at the last step of the execution trace.

3.9

Constraint propagation

An important point in the sequel is that the conjunction of our read-only-memory model with the useof plookup permutation arguments implicitly imposes a number of constraints on execution traces. In
21other words, there are many times where it is enough for us to describe a small number of constraints
to implicitly force other constraints to hold for a priori unconstrained variables.
For instance, if the memory’s Read Stack Pointer (RSP ) and Pointer to the top of the stack (T op)
are reassigned after the execution of an instruction to historical values of themselves, they will bereassigned coherently along with the corresponding values (V al(RSP ) and V al(T op)).

3.10

Flags and instruction decoder

Another major component of our zk-evm is the instruction decoder, which is basically a multiplexer
that associates an opcode to a sequence of flags that fully determine the behaviour of our zk-evm.
The instruction decoder data is a public data that explicitly states constraints between different setsof flags - for instance, when the CALL flag is set (ie its value is equal to one), then the RETURN flag
have to remain turned off to kill the constraints associated with the RETURN instruction that aren’t
used by the CALL instruction. This technique is extremely useful as it allows to drastically remove a
considerable number of execution paths that can’t be explored because of native constraints imposedin the instruction decoder.

3.11

Dealing with reverted transactions

The REVERT opcode and exceptional halting in the EVM reverts the changes that have been performed in the current transaction - the storage of the currently executed contract has to be reinitialized
to its former value, but also the ones that have been executed in nested calls that originated from thecurrent contract.
In this section and the following ones, we’ll introduce the two following definitions that are extremely
useful for the formalization of REVERT opcodes:
1. A reverted set is the set of the children of a reverted transaction. Any reverted transaction
belongs to a reverted set.
We introduce several tools and concepts to deal with the REVERT opcode and error flags:• A Curr_REV virtual column that activates whenever the current transaction is reverted or achild of a REVERTED transaction.
• A REV _F LAG virtual column that activates when a REVERT opcode is executed. When the
REV ERT _F LAG is set, the interrupt flag has to be set too.
• An IN T ERRU P T _F LAG that is a virtual column that activates whenever an error flag is set
or the REVERT opcode executed.
• A REV _ST AM P that is unique to every reverted set. Note that if a given reverted set, RC , isincluded in another reverted set RP , then the reverted stamp associated with the transactions
belonging to RC is different from the ones belonging to RP − RC
• A P arent_REV _ST AM P : tracks the revert stamp of the reverted set in which the current
reverted set is included. By convention, if the current transaction isn’t included in any reverted
set, P arent_REV _ST AM P = 0• A N ext_REV ERT _ST AM P : which tracks the number of the next revert stamp
To build coherently these flags, one has to detects when one enters or leave a reverted set andhow the reverted transactions automatically transmit the Curr_REV ERT ED flag value in caseof an inner-contract call. Basically, these three cases fully determine the Curr_REV ERT ED and
REV ERT _ST AM P updates :22

1. If the current instruction is RET U RN or ST OP , the Curr_REV ERT ED is not set andthe Curr_REV ERT ED flag is set, then the parent contract must be reverted too (ie, its
Curr_REV ERT ED flag is set): because otherwise there is a contradiction between the correct
execution of the contract (it has returned a value) and the fact it has been reverted.
2. If the current instruction is CALL and the Curr_REV ERT ED flag is set then set the called
contract Curr_REV ERT ED flag.
3. If the current instruction is neither CALL, RETURN nor STOP, then verify that the Curr_REV ERT ED
flag of the next instruction is the same as the current instruction.
4. If the IN T ERRU P T _F LAG is set, check that the Curr_REV ERT ED flag is set. Set the current REV ERT _ST AM P to the N ext_REV ERT _ST AM P and increment the N ext_REV ERT _ST AM P
Having defined the tools for REVERTED updates, one can now start to use them to update the
STORAGE in compliance with REVERT statements.

3.12

Error flags

According to the Ethereum yellowpaper, here are the cases that trigger an exceptional halt in the
EVM:• Insufficient gas.
• Invalid instruction.
• JUMP/JUMPI to an invalid destination.
• Insufficient stack items.
• Stack overflow (stack size exceeds 1024).
• Copying RETURNDATA from non existing positions• State modification during a static call.
Most of these cases can be simply dealt with using the tools and techniques described above. For
instance:• To deal with the insufficient gas error flag, one can perform a word comparison between the gas
value and its decrement for each step, raising an error flag when the gas value is insufficient for
the execution to pursue.
• The stack related errors are easily dealt with using stack size trackers and verifying that its value
is always comprised in [0,1023], setting an error flag if that’s not the case anymore.
• RETURNDATA related flags are dealt with by tracking RETURNDATASIZE and setting theassociated error flag in case of overflow.
• State modification during a static call is dealt by raising a flag when calling a forbidden instruction
during a static call.
• To check the validity of the destination of JUMP/JUMPI, one may impose a range check for the
maximum value of the PC in the current program, and add a P U SH_ARG flag to the ROM in
the case that one jumps to a PUSH argument in the bytecode. This case is considered to be anillicit jump destination by the Ethereum yellowpaper.

23• The instruction validity check is a bit more complex. Indeed, this amounts to verify that the
instruction opcode does not belong to the set of 80 EVM opcodes (which is not a continuous setof values). Normally, this check is performed using Plookup, which can be hardly adapted for atry/catch logic. A solution to perform instruction validity checks is to pad the opcode gaps withINVALID instructions, and then impose an opcode maximum value. Then, for every instruction
one has to perform a range proof to verify that the opcode falls in the authorized set of values.
Inside that range of values, Plookup will distinguish between licit and INVALID opcodes inside
the instruction decoder.

3.13

Fees/Gas Costs

After the error flags, dealing with the fees (or gas costs) is another tricky part of the zk-EVM, althoughnecessary to allow for backward-compatibility in smart contract execution.
According to the Ethereum yellowpaper, there are three types of gas costs that may occur in asmart contract execution:
1. A constant fee intrinsic to the operation currently executed. This is the case for most of thecommon instructions of the EVM (ADD, SWAP, DUP, ...)
2. A memory extension fee that depends on the current size of the memory RAM. This extension
fee depends on the number of EVM words one have stored in the RAM so far and is updated
dynamically during the execution of the program. There is an equivalent of the RAM extension
fee for the storage - the first access of a given address in storage will be way more expensive than
the subsequent ones, and setting a storage value to zero induces a gas reimbursement.
3. A last category of gas fee is related to smart contract interactions. This fee is payed for the
execution of instructions like ∗CALL or CREAT E∗. These fees are called dynamical fees andare the most complex category of fees to adapt to the zk-EVM framework.
The current fee value will be tracked using a gas virtual column. The current size of memory is
tracked in a M EM _SIZE variable that is updated in the child memory module as memory segments
are accessed. This M EM _SIZE variable allows us to perform this dynamic fee update during the
program execution.

4

Word comparison module

The word comparison module deals with the four word comparison instructions
• LT
• GT
• SLT
• SGT
which respectively return, for a := Input_1, b := Input_1, the boolean a ≤ b, a ≥ b, a < b and a > b.

4.1

Trace Columns

This module is comprised of the following columns:• WCTimeStamp increases by one with every instruction and remains constant during the execution of a given word comparison instruction.

24• Inst column of instructions• SwitchFlag• EqFlag• Input_1 The first word, remains constant during the instruction execution.
• Input_2 The second word, remains constant during the instruction execution.
• Comp This column is constant along a given time stamp and returns the result of the comparison
Input_1 < Input_2, i.e. Comp computes the value of SLT.
• Prefix_1 constructs the sequence of prefixes of Input_1, Byte by Byte
• Prefix_2 same for Input_2• B_1 the sequence of Bytes making up Input_1 starting from its highest Byte to its lowest• B_2 the sequence of Bytes making up Input_2 starting from its highest Byte to its lowest• ByteComp this column contains the result of the comparison B_1 < B_2.
• Decided this column may switch from 0 to 1 as soon as one can know the result of CompThe SwitchFlag and EqFlag encode the four comparison operations:
EqF lag = 0
EqF lag = 1

4.2

SwitchF lag = 0 SwitchF lag = 1
SLT
SGT
LT
GT

Trace constraints

The result column computes the result of the instruction using the equivalencesa ≤ b ⇐⇒ (a < b) OR (a = b)LT:
SGT: a > b ⇐⇒ NOT (a < b) OR (a = b)GT:a ≥ b ⇐⇒ NOT (a < b)Thus it is enough for us to compute the comparison a < b and this is the purpose of the Comp column
which always computes the boolean Input_1 < Input_2
1. The column Inst along with its flag columns SwitchFlag, EqFlag are Plookup verified against the
instruction decoder.
2. The columns B_1, B_2 and BComp are Plookup verified against a lookup-table that stores all
256 × 256 Byte comparisons.
3. WC_TimeStamp0 is initialized to the total number of calls to the Word Count module. Thiscondition is required to ensure that the inclusion proofs don’t "miss out" on requests to the word
count module.
4. for i = 1 WC_TimeStamp1 = 0
5. for i ≥ 1, WC_TimeStampi+1 = WC_TimeStampi or WC_TimeStampi+1 = WC_TimeStampi +1, i.e. (WC_TimeStampi+1 −WC_TimeStampi )(WC_TimeStampi+1 −WC_TimeStampi −1) =0.
25

6. for 1 ≤ i, WC_TimeStampi+32 = WC_TimeStampi or WC_TimeStampi+32 = WC_TimeStampi +1 since words have a fixed length of 32 bytes and 32 lines are enough for word comparison.
7. Res, Comp and Decided are binary, thus for all i: Resi (Resi − 1) = 0, Compi (Compi − 1) = 0
and Decidedi (Decidedi − 1) = 0
The other variables are updated differently according to whether WC_TimeStampi = WC_TimeStampi−1
or not:1. If - WC_TimeStampi = WC_TimeStampi−1 + 1:(a) (B_1)i = (Prefix_1)i and (B_2)i = (Prefix_2)i ,(b) (Prefix_1)i−1 = (Input_1)i−1 and (Prefix_2)i−1 = (Input_2)i−1 , i.e. we expect the prefixes
to equal the inputs at the end of a word comparison(c) If - (B_1)i = (B_2)i then Decidedi−1 = 0(d) Else If - (B_1)i ̸= (B_2)i then Decidedi = 1 and Compi = BCompi .
(e) If - (Input_1)i = (Input_2)i then Compi = 0
2. Else If - WC_TimeStampi = WC_TimeStampi−1 then(a) (Prefix_1)i = 256 · (Prefix_1)i−1 + (B_1)i and (Prefix_2)i = 256 · (Prefix_2)i−1 + (B_2)i ,(b) the inputs, the instruction and its flags, and the result of the comparison (Input_1 <Input_2) remain constant throughout the execution of a single word comparison:(Input_1)i−1 = (Input_1)i





(Input_2)i−1 = (Input_2)i





Insti−1 = Insti
SwitchFlagi−1 = SwitchFlagi
EqFlagi−1 = EqFlagi





Compi−1 = CompiResi−1 = Resi(c)i. If - Decidedi−1 = 0:
A. If - (B_1)i = (B_2)i then Decidedi = 0
B. Else If - (B_1)i ̸= (B_2)i then Decidedi = 1 and Compi = BCompi
ii. Else If - Decidedi−1 = 1: then Decidedi = Decidedi−1 .

We now specify the computation of Res. We have already specified that Res remains constant during
the execution of an instruction.
1. If - SwitchFlagi = 0 AND EqFlagi = 0: then Resi = Compi
2. If - SwitchFlagi = 0 AND EqFlagi = 1: then Resi = 1 iff Compi = 1 or (Input_1)i = (Input_2)i ,3. If - SwitchFlagi = 1 AND EqFlagi = 0: then Resi = 0 iff Compi = 1 or (Input_1)i = (Input_2)i .
4. If - SwitchFlagi = 1 AND EqFlagi = 1: then Resi = 1 − Compi

26

5Constraint set for the Parent Memory module

5.1

Instructions treated• CALL• RETURN• MSTORE• MSTORE8• MLOAD• CALLDATALOAD
Instructions not yet implemented:• CALLDATACOPY• RETURNDATACOPY• RETURNDATASize• CODECOPY• EXTCODECOPY• DELEGUATECALL• STATICALL• CALLCODE

5.2

Trace columns

5.2.1

Stack trace inclusion columns:• Stack_Inst: the instruction to be executed.
• RAM _T IM EST AM P
• Input1 : first input of the instruction.
• Input2 : second input (if any)
• Result: result of the instruction (element to be added on the stack - if any)
• EN D_F LAG0
• IN V ALID_IN ST RU CT ION

27

5.2.2

Instruction unpacking• IOP C_F LAG: if set, selects interactive memory opcodes like CALL, RET U RN . Otherwise, selects non interactive memory opcodes such as M LOAD, M ST ORE, M ST ORE8, CALLDAT ALOAD.
• M OP C_F LAG: Bit selection flag for non interactive memory opcodes. If set, selects M ST ORE, M ST ORE8.
Otherwise, selects M LOAD and CALLDAT ALOAD opcodes.
• Size_F LAG: set to the Size of the word to READ/STORE in memory.
• RET _F LAG: special case of the RETURN instruction• CALL_F LAG: special case of the CALL instruction• CALLDAT A_F LAG: special case that makes the instruction linked memory offsets to be
written as a calldata (for the CALL instruction)• IN IT _F LAG: initialize the RAM after a CALL instruction
5.2.3

Parent module instruction decomposition:• Inst_BInt_Of f set: instruction’s internal begin offset• Inst_BW d_Of f set: instruction’s word begin offset• Inst_EInt_Of f set: instruction’s internal end offset• Inst_EW d_Of f set: instruction’s word end offset• Curr_BInt_Of f set: current begin internal offset• Curr_EInt_Of f set: current end internal offset• Curr_BW d_Of f set: current beginning word offset• Curr_EW d_Of f set: current ending word offset (constrained to be either Curr_BW d_Of f set
or Curr_BW d_Of f set + 1).
• Curr_W d_V al: value of the current word read/written• Aux_BW d_Of f set, Aux_BInt_Of f set, Aux_EW d_Of f set, Aux_EInt_Of f set, Curr_Aux_W d_Of f set,
Curr_Aux_BInt_Of f set, Curr_Aux_EInt_Of f set : auxiliary parameters for the smart
contract call.
5.2.4

Child module inclusion columns (word multiple memory):• CRAM _Inst: the instruction to be executed by the child module (can be LOAD (CRAM _Inst =0) or STORE (CRAM _Inst = 1) ).
• CRAM _ST AM P : timestamp of the child module.
• CRAM _BW d_Of f set: the word multiple address to start writing to / reading from.
• CRAM _EW d_Of f set: the word multiple address to end writing to / reading from.
• CRAM _BInt_Of f set: contains the internal beginning address of the word currently read/written.
• CRAM _EInt_Of f set: contains the internal ending address of the word currently read/written.
• V al(CRAM _Inst) : value of the RAM instruction.
28

• CRAM _SC_N um: the SC memory to be loaded/written.
• CRAM _CALLDAT A_F LAG: a flag that determines whether the instruction acts on the RAM
or the CALLDATA
5.2.5

Call stack/SC batching:• SC_N um: current smart contract number in the batch.
• Caller_N um: caller smart contract number.
• Ret_Of f set(SC_N um), Ret_Len(SC_N um): execution stack inclusion
5.2.6

Memory size, gas costs• Curr_M em_Size: the current memory size in EVM words• M ax_M em_Size: maximum memory size
• Curr_CALLDAT A_Size: the current CALLDATA Size in EVM words• M em_IN CREASE_F LAG: a flag that indicates whether the memory size is increased• ∆Curr_M em_Size: the difference between the maximum and the current memory sizes.
• Gas_RAM : dynamic RAM gas cost paid by the instruction.
• Cost_RAM : current value of the memory cost function• Carry_Gas_RAM : used as a carry for the Gas_RAM calculation• Curr_M em2 /512: the floor value of Curr_M em2 divided by 512• ∗COP Y _Cost: cost associated with external data copy operations.
5.2.7

Auxiliaries• AU X_T RAN S

5.3
5.3.1

Opcodes constraints
MSTORE/MLOAD specific initialization.

If - (IOP C_F LAG)i = 0 (MSTORE, MSTORE8, MLOAD, CALLDATALOAD instructions) then
1. Unpack the first input (memory word offset) and set the instruction specific beginning word andinternal offsets:(Input1 )i = 32 ∗ Inst_BW ord_Of f seti + Inst_BInt_Of f seti
2. Compute the memory word ending word/internal offset using the Size variable (which is equal
to 31 for MSTORE/MLOAD and is equal to 1 for MSTORE8)(Input1 )i + Sizei = 32 ∗ Inst_EW ord_Of f seti + Inst_EInt_Of f seti
3. If - (M OP C_F LAG)i = 1 (MSTORE, MSTORE8 instruction) then:29

(a) Unpack the second input (word to write to memory) and set the instruction specific ending
word and internal offsets:(Input2 )i = V al(CRAM _Inst)i(b) Set the Child RAM instruction to store the value of the second input
CRAM _Insti = 1
4. Else If - (M OP C_F LAG)i = 0 (MLOAD, CALLDATALOAD instruction) then:(a) Unpack the result input (word to read from the memory) and set the instruction specificending word and internal offsets:(Result)i = V al(CRAM _Inst)i(b) Set the Child RAM instruction to read the value of the result input
CRAM _Insti = 0
5.3.2

INIT instruction initialization• If - IN IT _F LAGi = 1, then:
1. Initialize the begin word and interior offsets:
32 ∗ Inst_BW ord_Of f seti + Inst_BInt_Of f seti = 0
2. Initialize the end word and interior offsets:
32 ∗ Inst_EW ord_Of f seti + Inst_EInt_Of f seti = 32 ∗ M ax_M em_Sizei
3. Write to the memory:
4. Set the initial value to zero:

5.3.3

CRAM _Insti = 1
V al(CRAM _Inst)i = 0

RETURN specific initialization

If - RET _F LAG = 1:
1. Unpack the first input (instruction beginning offset)(Input1 )i = 32 ∗ Inst_BW ord_Of f seti + Inst_BInt_Of f seti
2. Unpack the second input (length of the word RETURNED)(Input1 )i + (Input2 )i = 32 ∗ Inst_EW ord_Of f seti + Inst_EInt_Of f seti
3. Initialize the auxiliary begin internal and word offsets with the return offset:
Ret_Of f set(SC_N um)i+1 = 32 ∗ Aux_BW d_Of f seti+1 + Aux_BInt_Of f seti+1
4. Initialize the auxiliary end internal and word offsets with the return offset:
Ret_Of f set(SC_N um)i+1 + Ret_Len(SC_N um)i+1 =32 ∗ Aux_EW d_Of f seti+1 + Aux_EInt_Of f seti+1
5. If - RAM _ST AM Pi = RAM _ST AM Pi−1 + 1, Start by a reading operation
CRAM _Inst = 030

5.3.4

CALL specific initialization

If - CALL_F LAGi = 1
1. If - it is the first CALL step: RAM _ST AM Pi = RAM _ST AM Pi−1 + 1: initialize the
CALLDATA parameters:(a) Unpack the memory data offset and length as instruction decomposition:
(Input2 )i+2 = 32 ∗ Inst_BW ord_Of f seti + Inst_BInt_Of f seti
(Input2 )i+2 + (Input1 )i+3 = 32 ∗ Inst_EW ord_Of f seti + Inst_EInt_Of f seti(b) Initialize the return data offset as the auxiliary memory offsets: Aux_BW d_Of f seti = 0
Aux_BInt_Of f seti = 0
(Input1 )i+3 = 32 ∗ Aux_EW ord_Of f seti + Aux_EInt_Of f seti
2. If - it is the last CALL step: RAM _ST AM Pi+1 = RAM _ST AM Pi + 1: initialize the
new CALLDATASize (done in the main execution trace constraints).
5.3.5

General value constraints.

1. If - RAM _ST AM Pi = RAM _ST AM Pi−1 + 1:(a) Initialize the current word and begin interior offset
Curr_BW d_Of f seti = Inst_BW d_Of f seti
Curr_BInt_Of f seti = Inst_BInt_Of f seti
5.3.6

Memory size update

The memory size is updated when an instruction starts to be executed. Then, the memory size is kept
constant throughout the execution of the instruction.
1. If - RAM _ST AM Pi = RAM _ST AM Pi−1 + 1 AND EN D_F LAG0 = 0:(a) If - M em_Increasei = 0:
i. Verify that the memory size is greater than the current max offset:∆Curr_M em_Sizei = Curr_M em_Sizei − Inst_EW d_Of f setiii. Do not increase the memory size:
Curr_M em_Sizei = Curr_M em_Sizei−1(b) Else If - M em_Increasei = 1:
i. Verify that the memory size is lower than the current max offset:∆Curr_M em_Sizei = Inst_EW d_Of f seti − Curr_M em_Sizei
ii. Increase the memory size:
Curr_M em_Sizei = Inst_EW d_Of f seti
2. Else If - RAM _ST AM Pi = RAM _ST AM Pi−1 AND EN D_F LAG0 = 0 then keep thevalues constant:∆Curr_M em_Sizei = ∆Curr_M em_Sizei−1
Curr_M em_Sizei = Curr_M em_Sizei−1
3. Else If - EN D_F LAG0 = 1: dealt with in the main execution trace.
31

5.3.7

RAM gas cost computation:• General cost computation: Cost_RAMi = ∗COP Y _Costi + Curr_M em2 /512i + 3 ∗ Curr_M em_Sizei
Gas_RAMi = Cost_RAMi − Cost_RAMi−1

Curr_M em_Size2i = Curr_M em_Size2 /512i ∗ 512 + Carry_Gas_RAM• If - CALLDAT A_COP Y _F LAG = 1:
∗COP Y _Costi = 3 ∗ CALLDAT A_Sizei• Else If - CALLDAT A_COP Y _F LAG = 0:
∗COP Y _Costi = 0
5.3.8Child RAM interior offsets

These conditions allows to adjust the child RAM interior offsets depending on the current word offset.
1. Always increase the Child RAM stamp
CRAM _ST AM Pi+1 = CRAM _ST AM Pi + 1
2. Impose the values of Curr_[∅, B, E]_[W d, Int]_Of f set(a) Always impose that Curr_BW d_Of f seti = Curr_EW d_Of f seti(b) If - Curr_EW d_Of f seti = Inst_EW d_Of f seti , thenCurr_EInt_Of f seti = Inst_EInt_Of f seti(c) Else If - Curr_EW d_Of f seti ̸= Inst_EW d_Of f seti , thenCurr_EInt_Of f seti = 31(d) If - Curr_BW d_Of f seti = Inst_BW d_Of f seti , thenCurr_BInt_Of f seti = Inst_BInt_Of f seti(e) Else If - Curr_BW d_Of f seti ̸= Inst_BW d_Of f seti thenCurr_BInt_Of f seti = 0
3. Impose the values of Curr_Aux_[∅, B, E]_[W d, Int]_Of f set. The values of Aux_Of f set
are constrained depending on the values of Curr_Of f set: we can’t impose the exact values ofCurr_Aux, the same way as Curr_Inst, because the respective internal offsets may be different.
(a) If - RAM _ST AM Pi = RAM _ST AM Pi−1 +1 (initialization performed in the generalvalue constraints) theni. Initialize the current auxiliary offsets
Curr_Aux_BW d_Of f seti = Aux_BW d_Of f seti
Curr_Aux_BInt_Of f seti = Aux_BInt_Of f seti32

ii. Initialize the current auxiliary ending offsets
32 ∗ Curr_Aux_EW d_Of f seti + Curr_Aux_EInt_Of f seti =32 ∗ Curr_Aux_BW d_Of f seti + Curr_Aux_BInt_Of f seti +(Curr_EInt_Of f seti − Curr_BInt_Of f seti )(b) If - Curr_BW d_Of f seti ̸= Curr_BW d_Of f seti−1 AND RAM _ST AM Pi−1 =RAM _ST AM Pi (the current instruction offsets changed)
i. Setting the beginning offset
32 ∗ Curr_Aux_BW d_Of f seti + Curr_Aux_BInt_Of f seti =32 ∗ Curr_Aux_EW d_Of f seti−1 + Curr_Aux_BInt_Of f seti−1 + 1
ii. Setting the ending offset
32 ∗ Curr_Aux_EW d_Of f seti + Curr_Aux_EInt_Of f seti =32 ∗ Curr_Aux_BW d_Of f seti + Curr_Aux_BInt_Of f seti +(Curr_EInt_Of f seti − Curr_BInt_Of f seti )(c) Else If - Curr_BW d_Of f seti = Curr_BW d_Of f seti−1 AND RAM _ST AM Pi−1 =RAM _ST AM Pi (the current instruction offsets did not change):i. Keep every offset constant:
Curr_Aux_BW d_Of f seti = Curr_Aux_BW d_Of f seti−1
Curr_Aux_EW d_Of f seti = Curr_Aux_EW d_Of f seti−1
Curr_Aux_BInt_Of f seti = Curr_Aux_BInt_Of f seti−1
Curr_Aux_EInt_Of f seti = Curr_Aux_EInt_Of f seti−1
5.3.9

Value consistency/constraints:

1. If - CALLDAT A_F LAG = 0 : do not set the CALLDATA flag:
CRAM _CALLDAT Ai = 0
2. Else If - CALLDAT A_F LAG = 1(a) If - IOP C_F LAG = 1
i. If - CRAM _Inst = 0: CRAM _CALLDAT A_F LAGi = 0
ii. If - CRAM _Inst = 1: CRAM _CALLDAT A_F LAGi = 1(b) Else If - IOP C_F LAG = 0:
CRAM _CALLDAT A_F LAGi = 1
3. If - M OP C_F LAG0 = 1 (MSTORE/MLOAD),(a) Set the current Child RAM smart contract number to the executed SC number
CRAM _SC_N umi = SC_N umi(b) Set the current child RAM begin/end interior offset to the current begin/end interior offset
CRAM _BInt_Of f seti = Curr_BInt_Of f seti
CRAM _EInt_Of f seti = Curr_EInt_Of f seti33

(c) Same thing for the word offsets
4. Else If - IOP C_F LAGi = 1(a) If - CRAM _Inst = 0 (READ from the current smart contract) theni. If - RET U RN _F LAG = 1 OR CALL_F LAG = 1
A. Set the child RAM smart contract number to be the current smart contract number
CRAM _SC_N umi = SC_N umi
ii. Set the child RAM interior offsets to be the current interior offsets.
CRAM _BInt_Of f seti = Curr_BInt_Of f seti
CRAM _EInt_Of f seti = Curr_EInt_Of f setiiii. Same thing for the word offsets(b) If - CRAM _Inst = 1 (WRITE to the caller contract) theni. If - RET U RN _F LAG = 1
A. Set the child RAM smart contract number to be the caller smart contract number(return the data to the memory of the called contract)
CRAM _SC_N umi = Caller_N umi
ii. If - CALL_F LAG = 1
A. Set the child RAM smart contract number to be the next smart contract number(write to the calldata of the next SC)
CRAM _SC_N umi = N ext_SC_N umi
iii. Set the child RAM interior offsets to be the return interior offsets.
CRAM _BInt_Of f seti = Curr_Aux_BInt_Of f seti
CRAM _EInt_Of f seti = Curr_Aux_EInt_Of f seti
iv. Same thing for the word offsets
v. Impose the previous value READ to be the new value stored:
V al(CRAM _Inst)i = V al(CRAM _Inst)i−1
5.3.10Transition constraints:

1. If - RET _F LAGi = 1 AND RAM _ST AM Pi+2 = RAM _ST AM Pi AND CRAM _Insti =0 (READ and RETURN), then:(a) The next instruction is WRITE back to the caller memory and the second next is READ
again.
CRAM _Insti+1 = 1
CRAM _Insti+2 = 0(b) One has to increase the word offset once the writing and reading operations are done:
Curr_W d_Of f seti+2 = Curr_W d_Of f seti + 1
2. If - M OP C_F LAGi = 1, AND RAM _ST AM Pi+1 = RAM _ST AM Pi increase theword offset.
Curr_W ord_Of f seti+1 = Curr_W ord_Of f seti + 1
34

5.3.11End instruction constraints:

If - End_W d_Of f seti = Curr_W d_Of f seti , increase the RAM STAMP
RAM _ST AM Pi+1 = RAM _ST AM Pi + 1
Else If - End_W d_Of f seti ̸= Curr_W d_Of f seti , keep the same RAM STAMP
RAM _ST AM Pi+1 = RAM _ST AM Pi

6Constraint set for the Child Memory module.

6.1

Role in the architecture

The child memory module has been introduced to take a part of the complexity of the parent memory
module to simplify the constraint system of this complex part of the architecture. The child memory
module is designed to perform the following operations:• Initialize all the memory cells that are going to be read/written from.
• Store to/load from the memory at most 32 bytes at two consecutive word addresses, in/from any
RAM/calldata that are loaded in the ROM• Verify the integrity of the RAM/calldata of the smart contracts loaded in the ROM
We will then decompose this section into two parts: on the one hand we will describe the constraint
set associated with he STORE/LOAD operations of the child RAM, on the other hand we will describe
how to check the memory integrity inside the RAM module.

6.2

Constraint columns for child RAM STORE/LOAD operations

6.2.1

Parent module inclusion columns:

These trace columns are used for the communication between the child and the parent RAM module.
• CRAM _Inst: the instruction to be executed by the child module (can be LOAD (CRAM _Inst =0) or STORE (CRAM _Inst = 1) ).
• IN IT _OP ERAT ION : special operation that initializes the RAM of a given SC.
• CRAM _ST AM P : timestamp of the child module.
• CRAM _BW d_Of f set: the word multiple address to start writing to / reading from.
• CRAM _EW d_Of f set: the word multiple address to end writing to / reading from.
• CRAM _BInt_Of f set: contains the internal beginning address of the word currently read/written.
• CRAM _EInt_Of f set: contains the internal ending address of the word currently read/written.
• V al(CRAM _Inst) : value of the RAM instruction.
• CRAM _SC_N um: the SC memory to be loaded/written.
• CRAM _CALLDAT A_F LAG: a flag that determines whether the instruction acts on the RAM
or the CALLDATA• IN V ALID_IN ST RU CT ION : the invalid instruction flag, turned on when a RAM INIT operation is performed at an invalid position. .
To simplify slightly the notations in the following subsections describing the constraint set of thechild RAM memory module, we will drop the CRAM prefix in the virtual columns names.
356.2.2

CRAM execution specific columns

These columns are used within the child RAM module to perform the CRAM specific STORE/LOAD
operations :• Curr_W d_Of f set: the current word offset to STORE to / READ from• Curr_Int_Of f set: the current interior offset being READ/STORED• Curr_V al: the current value to store/read in the RAM• Curr_Byte: the current byte being stored/read in the RAM• Curr_Carry: the remaining bytes to store/read in the RAM• Curr_Byte_N um: auxiliary variable that keeps track of the current byte number.
• Inst_Range_F lag: a flag that is set if
28 Curr_W d_Of f set + Curr_Int_Of f set∈ [28 ∗ BW d_Of f set + BInt_Of f set, 28 ∗ EW d_Of f set + EInt_Of f set]
• Inst_Byte: the instruction byte that is currently being read
• Inst_Carry: the remaining instruction bytes to read/store.
• P rev_V al: the previous value that was stored in the RAM at (Curr_W d_Of f set, Curr_Int_Of f set)
• P rev_Carry: carry for the previous value that was stored in the RAM at (Curr_W d_Of f set, Curr_Int_Of f set)
• P rev_Byte: the previous byte being stored in the RAM at (Curr_W d_Of f set, Curr_Int_Of f set)

6.3

Constraint set for the execution

One has first to distinguish between two cases: the current instruction is an INIT operation, the current
instruction is not an INIT operation.
The INIT operation is quite tricky as it must initialize all the memory cells that are going to beaccessed by the current transaction. A way to do that is to store a zero value for every word multiple
cell between zero and M AX_M em_Size.
• If - CRAM _ST AM Pi = CRAM _ST AM Pi−1 + 1:
1. Initialise the Curr_W d_Of f set:
Curr_W d_Of f seti = BW d_Of f seti
2. Initialise the Curr_Int_Of f set:
Curr_Int_Of f seti = BInt_Of f seti
3. Initialise the Curr_Byte_N um:
Curr_Byte_N umi = 31
4. Initialise the Curr_Carry:
Curr_Carryi = 036

5. Initialise the P rev_Carry:
P rev_Carryi = 0
6. Initialise the Inst_Carry:
Inst_Carryi = 0• If - IN IT _OP ERAT IONi = 1:
1. Store a value:

CRAM _Insti = 1

2. Impose to store zero:V al(CRAM _Inst)i = 0

3. If - Curr_W d_Of f seti = CRAM _EW d_Of f set:(a) Increase the CRAM stamp
CRAM _ST AM Pi+1 = CRAM _ST AM Pi + 1
4. Else If - Curr_W d_Of f seti ̸= CRAM _EW d_Of f set:(a) Keep the CRAM stamp constant
CRAM _ST AM Pi+1 = CRAM _ST AM Pi(b) Increase the Curr_W d_Of f set
Curr_W d_Of f seti+1 = Curr_W d_Of f seti + 1• Else If - IN IT _OP ERAT IONi = 0:
1. If - BInt_Of f seti = 0 AND EInt_Of f seti = 31 AND CRAM _BW d_Of f seti =CRAM _EW d_Of f seti : fast READING/WRITING operation:(a) Set the current RAM value to the READ/STORED value :Curr_V ali = V al(CRAM _Inst)(b) Increase the RAM stamp :CRAM _ST AM Pi+1 = CRAM _ST AM Pi + 1
2. Else If - BInt_Of f seti ̸= 0 OR EInt_Of f seti ̸= 31 OR CRAM _BW d_Of f seti ̸=
CRAM _EW d_Of f seti : slow READING/WRITING operation(a) If - Curr_Byte_N um ̸= 0:
i. Propagate the carry decomposition :
Curr_Carryi+1 = Curr_Carryi + 28 ∗ Curr_Bytei
P rev_Carryi+1 = P rev_Carryi + 28 ∗ P rev_Bytei
ii. Propagate the current and previous values:
Curr_V ali+1 = Curr_V ali
P rev_V ali+1 = P rev_V aliiii. Decrease the Curr_Byte_N um:
Curr_Byte_N umi+1 = Curr_Byte_N umi − 137(b) If - Curr_Byte_N um = 0:
i. Check that the Curr_Carry and the P rev_Carry matches the Curr_V al and
the P rev_V al:
Curr_Carryi = Curr_V ali
P rev_Carryi = P rev_V ali
ii. If - Curr_W d_Of f seti = EW d_Of f seti :A. Move to the next instruction: CRAM _ST AM Pi+1 = CRAM _ST AM Pi + 1
iii. Else If - Curr_W d_Of f seti = EW d_Of f seti − 1:
A. Move to the next word offset:
Curr_W d_Of f seti+1 = Curr_W d_Of f seti + 1
B. Reset the Curr_Byte_N um:
Curr_Byte_N umi+1 = 31
C. Reset the Curr_Carry and the P rev_Carry:
Curr_Carryi = 0
P rev_Carryi = 0(c) If - 32 ∗ Curr_W d_Of f seti + Curr_Int_Of f seti = 32 ∗ BW d_Of f seti +BInt_Of f seti : set the Inst_Range_F lag:
Inst_Range_F lagi = 1(d) Else If - 32∗Curr_W d_Of f seti +Curr_Int_Of f seti = 32∗EW d_Of f seti +EInt_Of f seti :i. Turn off the Inst_Range_F lag:
Inst_Range_F lagi+1 = 0
ii. Check that the Inst_Carry is the V al(CRAM _Inst):
Inst_Carry = V al(CRAM _Inst)(e) Else If - 32∗Curr_W d_Of f seti +Curr_Int_Of f seti ̸= 32∗BW d_Of f seti +BInt_Of f seti AND 32 ∗ Curr_W d_Of f seti + Curr_Int_Of f seti ̸= 32 ∗EW d_Of f seti + EInt_Of f seti keep the Inst_Range_F lag constant:
Inst_Range_F lagi+1 = Inst_Range_F lagi(f) If - Inst_Range_F lagi = 1:
i. The current byte is the instruction byte:
Curr_Bytei = Inst_Bytei
ii. Shift the instruction carry:
Inst_Carryi+1 = Inst_Carryi + 28 ∗ Inst_Bytei(g) Else If - Inst_Range_F lagi = 0:
i. The current byte is the previous byte:
Curr_Bytei = P rev_Bytei
ii. Don’t shift the instruction carry:
Inst_Carryi+1 = Inst_Carryi
38

6.4

Memory consistency columns

These columns are used to check the consistency of the RAM/Calldata of every smart contract
loaded in the ROM. These columns are the space reordered version of the constraint columns fromthe child RAM (section 6.2). More precisely, the columns from 6.2 are lexicographically ordered by(SC_N um, CALLDAT A_F LAG, Curr_W d_Of f set, CRAM _ST AM P ).
6.4.1

Permutation columns:^um• SC_N^• CALLDAT
A_F LAG^• Curr_W
d_Of f set• CRAM^_ST AM P
6.4.2

Force sorted columns:

These columns are sorted by force, following the lexicographic order defined above:^• CRAM_Inst: the child RAM instruction^• IN IT _OP
ERAT ION : the initialization flag.
^• IN V ALID_IN
ST RU CT ION : is turned on when an IN IT _OP ERAT ION is performed ata wrong position.
^ al• Curr_V^ al• P rev_V
6.4.3

Range checks:

To verify that the virtual column CRAM^_ST AM P increases well, one has to perform range checks^
on the difference between CRAM _ST AM P i and CRAM^_ST AM P i+1 . This leads us to introduce
the following virtual columns• ∆CRAM^_ST AM Pi• ∆CRAM^_ST AM P : the 16-bit decomposition of ∆CRAM^_ST AM P to check that ∆CRAM^_ST AM P ∈128[0, 2 ] (the difference has not overflown)

6.5

Constraint set for the memory consistency

g um = SC_N
g um
1. If - SC_N
ii+1gA_F LAG = CALLDAT
gA_F LAG(a) If - CALLDATi
i+1i. If - Curr_Wg
d_Of f seti = Curr_Wg
d_Of f seti+1
A. If - IN ITg_F LAGi+1 = 1: turn on the IN V ALID_IN ST RU CT ION flag the user has tried to initialize the RAM cell at an invalid timestamp.
^
IN V ALID_IN
ST RU CT ION i+1 = 1
39^
B. Compute the ∆CRAM_ST AM P :^∆CRAM_ST AM P i = CRAM^_ST AM P i+1 − CRAM^_ST AM P i
C. Impose that the current value is the same as next previous value:^ al^
P rev_V
i+1 = Curr_V ali
D. If - ∆CRAMg_ST AM P i = ∆CRAMg_ST AM P i+1 : impose the values ofCurr_V al and P rev_V al to be constant:(^ al = Curr_V^ al
Curr_Vii+1^ al = P rev_V^ al
P rev_Vii+1
g_Inst =E. Else If - ∆CRAMg_ST AM P i ̸= ∆CRAMg_ST AM P i+1 AND CRAM
0 (reading operation at two successive timestamps); impose the value consistency:^ al = Curr_V^ al
Curr_Vii+1
ii. Else If - Cur_Wg
d_Of f seti ̸= Curr_Wg
d_Of f seti+1
A. Impose the next operation to be the initialization of the memory cell:^
IN IT _OP
ERAT ION i+1 = 1
gA_F LAG ̸= CALLDAT
gA_F LAG(b) Else If - CALLDATi
i+1i. Impose the next operation to be the initialization of the memory cell:^
IN IT _OP
ERAT ION i+1 = 1
g um ̸= SC_N
g um
2. Else If - SC_Nii+1 : impose the next operation to be the initialization of
the memory cell:^
IN IT _OP
ERAT ION i+1 = 1

References[1]

DR. Gavin Wood. “Ethereum : A secure decentralised generalised transaction ledger”. In: (2021).
https://ethereum.github.io/yellowpaper/paper.pdf.

[2]

Vitalik Buterin. An Incomplete Guide to Rollups. Jan. 2021. url: https://vitalik.ca/general/
2021/01/05/rollup.html.

[3]

DeGate Team. An article to understand zkEVM, the key to Ethereum scaling. Sept. 2021. url:
https://medium.com/degate/an- article- to- understand- zkevm- the- key- to- ethereum- scalingff0d83c417cc.

[4]

ZK-sync official website. url: https://zksync.io/.

[5]

Lior Goldberg, Shahar Papini, and Michael Riabzev. Cairo – a Turing-complete STARK-friendly
CPU architecture. Cryptology ePrint Archive, Report 2021/1063. https://ia.cr/2021/1063. 2021.

[6] Hermez official website. url: https://hermez.io/.
[7] Scroll tech github repository. url: https://github.com/scroll-tech/.
[8] Hermez presentation at the EthCC4. url: https://youtu.be/17d5DG6L2nw.
40

[9]

Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrangebases for Oecumenical Noninteractive arguments of Knowledge. Cryptology ePrint Archive, Report 2019/953. https://ia.cr/2019/953. 2019.

[10]

Ariel Gabizon and Zachary J. Williamson. plookup: A simplified polynomial protocol for lookup
tables. Cryptology ePrint Archive, Report 2020/315. https://ia.cr/2020/315. 2020.

[11]

Olivier Begassat Alexandre Belling. Using GKR inside a SNARK to reduce the cost of hashverification down to 3 constraints. June 2020. url: https://ethresear.ch/t/using-gkr-inside-asnark-to-reduce-the-cost-of-hash-verification-down-to-3-constraints/7550.

41