Copy

简介

copy类操作指的是在EVM中进行不定长的一段数据拷贝，例如CALLDATACOPY将calldata中的一段数据拷贝到memory中。拷贝以byte作为数据长度单位，不同于栈的U256。

由于拷贝的长度不定，即无法在编写电路时预先确定数据拷贝的长度，因此难以在不引入新子电路和子表格的情况下处理此类操作。

为了解决这个问题，我们定义了一个copy子电路。对于Copy类操作，假设其长度为len，在此子电路中，使用len行来处理。每一行都加上相应的约束来证明是从来源拷贝到去向的。对于每次操作，生成的Witness会包含len行的copy子电路的Row。

具体来说，以下操作属于Copy类操作：

• CODECOPY
• CALLDATACOPY
• RETURN
• RETURNDATACOPY
• LOG
• 调用开始时，CALLDATA要被写入STATE子电路所维持的状态中。这分为两种情况：
  • CALLDATA_FROMPUBLIC：外界（交易、公开数据）的CALLDATA输入
  • CALLDATA_FROMCALL：合约调用另一个合约的CALLDATA输入

下列表格展示了数据的来源可能是：state子电路中的memory、calldata、returndata，bytecode子电路中的bytecode，public子电路中的calldata和logdata。

state子电路

state
Memory	call_id	pointer_lo	stamp	value_lo	is_write
Calldata	call_id	pointer_lo	stamp	value_lo	is_write
Returndata	call_id	pointer_lo	stamp	value_lo	is_write

bytecode子电路

bytecode
pc	addr	bytecode

public子电路

public
TxCalldata	block_tx_idx	--	data_idx	data
TxLogData	block_tx_idx	log_index	data_idx	data

• CODECOPY, EXTCODECOPY：从bytecode到memory
• CALLDATACOPY：从calldata（state中的）到memory
• RETURN：从memory到returndata
• RETURNDATACOPY：从returndata到memory
• LOG：从memory到log
• 调用开始时，CALLDATA要被写入STATE子电路所维持的状态中。分为两种情况：
  • CALLDATA_FROMPUBLIC：从public的CALLDATA到state中的calldata
  • CALLDATA_FROMCALL：从memory到state中的calldata

设计

Witness、Column设计

共使用12列，参见代码。

pub struct Row {
    /// The byte value that is copied
    pub byte: U256,
    /// The source type, one of PublicCalldata, Memory, Bytecode, Calldata, Returndata
    pub src_type: Type,
    /// The source id, tx_idx for PublicCalldata, contract_addr for Bytecode, call_id for Memory, Calldata, Returndata
    pub src_id: U256,
    /// The source pointer, for PublicCalldata, Bytecode, Calldata, Returndata means the index, for Memory means the address
    pub src_pointer: U256,
    /// The source stamp, state stamp for Memory, Calldata, Returndata. None for PublicCalldata and Bytecode
    pub src_stamp: Option<U256>,
    /// The destination type, one of Memory, Calldata, Returndata, PublicLog
    pub dst_type: Type,
    /// The destination id, tx_idx for PublicLog, call_id for Memory, Calldata, Returndata
    pub dst_id: U256,
    /// The destination pointer, for Calldata, Returndata, PublicLog means the index, for Memory means the address
    pub dst_pointer: U256,
    /// The destination stamp, state stamp for Memory, Calldata, Returndata. As for PublicLog it means the log_stamp
    pub dst_stamp: U256,
    /// The counter for one copy operation
    pub cnt: U256,
    /// The length for one copy operation
    pub len: U256,
    /// The accumulation of bytes in one copy
    pub acc: U256,
}

其中，Type是

pub enum Type {
    #[default]
    /// Zero value for padding, under which id, pointer, and stamp are default value
    Zero,
    /// Memory in state sub-circuit
    Memory,
    /// Calldata in state sub-circuit
    Calldata,
    /// Returndata in state sub-circuit
    Returndata,
    /// Log in public sub-circuit
    PublicLog,
    /// Calldata in public sub-circuit
    PublicCalldata,
    /// Bytecode in bytecode sub-circuit
    Bytecode,
    /// Null for any value in read only/write only copy, under which id, pointer, and stamp are default value.
    /// If read only copy, dst type is Null. If write only copy, src type is Null. This is usually used
    /// in load-32-byte opcodes such as MLOAD, MWRITE, or CALLDATALOAD.
    Null,
}

例子：CODECOPY，从bytecode拷贝到memory。例子里长度为8，被拷贝的数据为0xabcd......见下表。

byte	src type	src id	src pointer	src stamp	dst type	dst id	dst pointer	dst stamp	cnt	len	acc
0xab	Bytecode	contract addr	some offset	nil	Memory	callid	some mem addr	some stamp	0	8	0xab
0xcd	Bytecode	contract addr	some offset	nil	Memory	callid	some mem addr	some stamp	1	8	0xabcd
...	Bytecode	contract addr	some offset	nil	Memory	callid	some mem addr	some stamp	2	8	...
	Bytecode	contract addr	some offset	nil	Memory	callid	some mem addr	some stamp	3	8
	Bytecode	contract addr	some offset	nil	Memory	callid	some mem addr	some stamp	4	8
	Bytecode	contract addr	some offset	nil	Memory	callid	some mem addr	some stamp	5	8
	Bytecode	contract addr	some offset	nil	Memory	callid	some mem addr	some stamp	6	8
	Bytecode	contract addr	some offset	nil	Memory	callid	some mem addr	some stamp	7	8

注意：同一次Copy的许多行里的pointer，是一样的，都和第一行相同。

门约束

门约束是指对每一行的数据进行检查和约束，以确保数据的正确性和一致性。

1. 长度约束：
   • 若 len - cnt - 1 == 0 或 len == 0：表示这一行是最后一行或没有数据（len == 0表示是填充行），因此下一行的 cnt 应为 0。
   • 否则：next_cnt = cnt + 1，并且下一行的 src_type，dst_type，src_xx，dst_xx，len 等都和当前行相同。
2. 填充行约束：
   • 若 len == 0：表示此行是填充行，此时 src_type，dst_type，src_xx，dst_xx，len 等全部是 nil 或者默认值。
3. 类型约束：
   • 若 src_type = Zero：表示此行的 src_id，pointer，stamp，byte 全为0。同理，若 dst_type 是 Zero，dst_xx 也应全为0。
   • 若 src_type = Null：表示此行的 src_id，pointer，stamp 全为0，但 byte 不做约束。同理，若 dst_type 是 Null，dst_xx 也应全为0。
4. 累积值约束（acc）：
   • 若 cnt = 0，acc = byte。
   • 若 cnt != 0，acc = byte + acc_prev * 256，其中 acc_prev 是上一行的 acc 值。注意此加法是有限域的加法，因此可能会得到超出有限域的结果而取模。

Lookup

Lookup的目的是确保每一行的数据拷贝操作是正确的。具体来说，每一行的数据都要进行两个查找：Lookup1和Lookup2。

首先，byte这一列要使用lookup进行范围证明（小于256的范围）。

Lookup1：来源验证

Lookup1是为了验证数据的来源是否正确，去向为bytecode的查找表，含义是确定拷贝的数据没错。具体情况视 src_type 而定：

1. Zero、Null：不进行lookup。
2. Memory、Calldata、Returndata：
   • 来源是此子表格的（tag=常数Memory/Calldata/Returndata, src_id, src_pointer + cnt, src_stamp + cnt, byte, is_write=常数0）。
   • 去向是state table的（tag, call_id, pointer_lo, stamp, value_lo, is_write），即 LookupEntry::State。
3. Bytecode：
   • 来源是此子表格的（src_pointer + cnt, src_id, byte）。
   • 去向是bytecode table的（pc, addr, bytecode），即 LookupEntry::Bytecode（并非 BytecodeFull）。
4. PublicCalldata：
   • 来源是此子表格的（tag=常数Calldata, src_id, src_pointer + cnt, byte）。
   • 去向是public table的（tag, tx_idx, idx, value），即 LookupEntry::Public。注意此tag是Public的Tag。

Lookup2：去向验证

Lookup2是为了验证数据的去向是否正确，去向为state（具体tag为memory）的查找表，含义是确定拷贝的数据确实写进去了。具体情况视 dst_type 而定：

1. Zero、Null：不进行lookup。
2. Memory、Calldata、Returndata：
   • 类似Lookup1，但 is_write=常数1。
3. PublicLog：
   • 来源是此子表格的（tag=常数tx_log, log_tag=常数bytes, dst_id, src_pointer + cnt, dst_stamp (不加cnt), byte, len）。
   • 去向是public table的（tag, log_tag, tx_idx, idx, log_id, value, len），即 LookupEntry::Public。

Core中的用法

在Core子电路的执行状态中，遇到与copy相关的状态时，处理方式如下：

CODECOPY, EXTCODECOPY

对于这两条指令，当数据不足时会填充0。因此，在从栈中获取 offset, length, dst_offset 这三个值后，通过Arithmetic子电路的Normallength来判断是否需要填充。向Normallength传入 length, offset, data_size，会得到两个长度：normal_length 和 zero_length（即填充的长度）。然后，通过lookup来约束normal_length和zero_length。

从core进行两个copy的lookup。一个的src type是bytecode，另一个的src type是zero。这两个copy的lookup可以安排在cnt=2行的前9个格子和次9个格子。对于每个copy的lookup，用门约束其各个位置的值，然后用lookup约束从core向copy去查找表即可。

CALLDATACOPY

对于这条指令，当数据不足时会填充0。不过，在读取CALLDATA时，我们可以让CALLDATA的默认值为0（类似MEMORY的设计）。因此，不需要像CODECOPY一样处理。此指令只需一个copy的lookup，可以安排在cnt=2行的前9个格子。

RETURN

对于这条指令，当数据不足时会填充0。不过，在读取MEMORY时，默认值为0。因此，不需要像CODECOPY一样处理。此指令只需一个copy的lookup。

RETURNDATACOPY

对于这条指令，当数据不足时会报错。因此，此指令只需一个copy的lookup。

MLOAD

此操作相当于进行了长度为32的copy，src type是memory，dst type没有，因此采用Null。注意，MLOAD往栈里写入数据，但不是通过copy的形式，而是将32个byte组合成U256然后写入，因此copy子电路不处理栈的写入。acc列起到了将32个byte组合的作用。实现中，我们进行两个长度为16的copy，用acc来获得每个16byte的U128，在cnt处使用值为16-1=15的查找表操作，用以获得最后的acc值。两个copy lookup的值记为value_hi和value_lo。因此，copy的lookup中也需要加入此acc列。在core里，通过copy的lookup获得value_hi和value_lo后，使用state的lookup写入栈。

MSTORE

此操作类似MLOAD，相当于进行了长度为32的copy，src type采用Null，dst type是memory。我们进行两个长度为16的copy，用acc来获得每个16byte的U128，记为value_hi和value_lo。在core里，使用state的lookup读取栈，栈的value的高位和低位要约束等于copy的acc（即value_hi和value_lo）。

CALLDATALOAD

此操作与CALLDATACOPY不同，反而与MLOAD类似。相当于进行了长度为32的copy，src type是calldata，dst type没有，因此采用Null。我们进行两个长度为16的copy，获得value_hi和value_lo，然后使用state的lookup写入栈。