# 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列，参见代码。

```rust
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是

```rust
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`来获得每个16`byte`的`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`来获得每个16`byte`的`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`写入栈。