# Bytecode

Bytecode电路用于约束智能合约的字节码，并为其他电路提供字节码的来源依据。通过Lookup约束，其他子电路可以验证操作的字节码是否合法。

在Bytecode表中存放的可能不仅仅是一个合约的字节码，不同合约的字节码以地址（address）进行标识，每个地址唯一对应一个字节码。对于一个合约的字节码来说，`pc`是opcode或者no_code(push的byte)唯一的标识。

在对Bytecode进行处理时，将Bytecode分为两类：

**Opcode（非PUSH）**：

- 操作指令，如ADD、SUB、CODECOPY等。

**Opcode（PUSH）**：

- 包括PUSH1至PUSH32，以及PUSH操作码后跟随的字节。

## Witness、Column设计

### Witness设计

Witness结构体`Row`包含多个字段，用于记录字节码处理过程中的相关信息：

```rust
#[derive(Clone, Debug, Default, Serialize)]
pub struct Row {
    /// the contract address of the bytecodes
    pub addr: Option<U256>,
    /// the index that program counter points to
    pub pc: Option<U256>,
    /// bytecode, operation code or pushed value
    pub bytecode: Option<U256>,
    /// pushed value, high 128 bits (0 or non-push opcodes)
    pub value_hi: Option<U256>,
    /// pushed value, low 128 bits (0 or non-push opcodes)
    pub value_lo: Option<U256>,
    /// accumulated value, high 128 bits. accumulation will go X times for PUSHX
    pub acc_hi: Option<U256>,
    /// accumulated value, low 128 bits. accumulation will go X times for PUSHX
    pub acc_lo: Option<U256>,
    /// count for accumulation, accumulation will go X times for PUSHX
    pub cnt: Option<U256>,
    /// whether count is equal or larger than 16
    pub is_high: Option<U256>,
}
```

- **cnt**: 如果是非 PUSH 的 Opcode 则 cnt=0，对于 PUSH 指令，cnt 为 PUSH 的 byte 的数量，如 PUSH1 --> cnt=1, PUSH2 --> cnt=2, PUSH31 --> cnt=31, PUSH32 --> cnt=32，对于 no_code 则 cnt 的值为 (0~cnt-1)。

- **is_high**: cnt >= 16 时为 1，cnt < 16 时为 0，主要用于辅助计算 acc 的值（规定 acc 的值最多为 16 个字节）。

- **acc_hi**: cnt >= 16 的 Bytecode 执行此计算，`acc_hi_pre * 256 + bytecode`，即计算 byte 的累加值。

- **acc_lo**: cnt < 16 的 Bytecode 执行此计算，`acc_lo_pre * 256 + bytecode`，即计算 byte 的累加值。

- **value_hi**: cnt >= 16 的 Bytecode 的最终累加值，即最终的 acc_hi。

- **value_lo**: cnt < 15 的 Bytecode 的最终累加值，即最终的 acc_lo。

注：Opcode(非PUSH)的 cnt、is_high、acc_hi、acc_lo、value_hi、value_lo值都为0

假如有如下指令：

```shell
PUSH1 0xa
PUSH18 0x02030405060708090a0b0c0d0e0f10111213
ADD
```

假设 addr 为 0xaa，则表格如下：

| addr | pc  | bytecode | acc_hi | acc_lo                          | value_hi | value_lo                          | cnt | is_high |
| ---- | --- | -------- | ------ | ------------------------------- | -------- | --------------------------------- | --- | ------- |
| 0xaa | 0   | PUSH1    | 0x0    | 0x0                             | 0x0      | 0xa                               | 1   | 0       |
| 0xaa | 1   | 0xa      | 0x0    | 0xa                             | 0x0      | 0xa                               | 0   | 0       |
| 0xaa | 2   | PUSH17   | 0x0    | 0x0                             | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 17  | 1       |
| 0xaa | 3   | 0x2      | 0x2    | 0x0                             | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 16  | 1       |
| 0xaa | 4   | 0x3      | 0x203  | 0x0                             | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 15  | 0       |
| 0xaa | 5   | 0x4      | 0x203  | 0x4                             | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 14  | 0       |
| 0xaa | 6   | 0x5      | 0x203  | 0x405                           | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 13  | 0       |
| 0xaa | 7   | 0x6      | 0x203  | 0x40506                         | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 12  | 0       |
| 0xaa | 8   | 0x7      | 0x203  | 0x4050607                       | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 11  | 0       |
| 0xaa | 9   | 0x8      | 0x203  | 0x405060708                     | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 10  | 0       |
| 0xaa | 10  | 0x9      | 0x203  | 0x40506070809                   | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 9   | 0       |
| 0xaa | 11  | 0xa      | 0x203  | 0x405060708090a                 | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 8   | 0       |
| 0xaa | 12  | 0xb      | 0x203  | 0x405060708090a0b               | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 7   | 0       |
| 0xaa | 13  | 0xc      | 0x203  | 0x405060708090a0b0c             | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 6   | 0       |
| 0xaa | 14  | 0xd      | 0x203  | 0x405060708090a0b0c0d           | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 5   | 0       |
| 0xaa | 15  | 0xe      | 0x203  | 0x405060708090a0b0c0d0e         | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 4   | 0       |
| 0xaa | 16  | 0xf      | 0x203  | 0x405060708090a0b0c0d0e0f       | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 3   | 0       |
| 0xaa | 17  | 0x10     | 0x203  | 0x405060708090a0b0c0d0e0f10     | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 2   | 0       |
| 0xaa | 18  | 0x11     | 0x203  | 0x405060708090a0b0c0d0e0f1011   | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 1   | 0       |
| 0xaa | 19  | 0x12     | 0x203  | 0x405060708090a0b0c0d0e0f101112 | 0x203    | 0x405060708090a0b0c0d0e0f10111213 | 0   | 0       |
| 0xaa | 21  | ADD      | 0x0    | 0x0                             | 0x0      | 0x0                               | 0   | 0       |
| 0xaa | 22  | STOP     | 0x0    | 0x0                             | 0x0      | 0x0                               | 0   | 0       |

### Column设计

Bytecode电路的配置结构体`BytecodeCircuitConfig`包含多个列和选择器，用于约束和验证字节码：

```rust
#[derive(Clone)]
pub struct BytecodeCircuitConfig<F> {
    q_enable: Selector,
    /// the contract address of the bytecodes. public input
    instance_addr: Column<Instance>,
    /// bytecode, operation code or pushed value. public input
    instance_bytecode: Column<Instance>,
    /// the contract address of the bytecodes (need to copy from public input)
    addr: Column<Advice>,
    /// the index that program counter points to
    pc: Column<Advice>,
    /// bytecode, operation code or pushed value (need to copy from public input)
    bytecode: Column<Advice>,
    /// pushed value, high 128 bits
    value_hi: Column<Advice>,
    /// pushed value, low 128 bits
    value_lo: Column<Advice>,
    /// accumulated value, high 128 bits. accumulation will go X times for PUSHX
    acc_hi: Column<Advice>,
    /// accumulated value, low 128 bits. accumulation will go X times for PUSHX
    acc_lo: Column<Advice>,
    /// count for accumulation, accumulation will go X times for PUSHX
    cnt: Column<Advice>,
    /// whether count is equal or larger than 16
    is_high: Column<Advice>,
    /// for chip to determine whether cnt is 0
    cnt_is_zero: IsZeroWithRotationConfig<F>,
    /// for chip to determine whether cnt is 15
    cnt_is_15: IsZeroConfig<F>,
    /// for chip to check if addr is changed from previous row
    addr_unchange: IsZeroConfig<F>,
    /// for chip to check if addr is zero, which means the row is padding
    addr_is_zero: IsZeroWithRotationConfig<F>,
    /// for rlc of bytecodes, used for keccak hash lookup; second phase column
    rlc_acc: Column<Advice>,
}
```

对于IsZeroConfig小工具，如果传入的值为0则返回结果为1，如果传入的值不为0则返回结果为0

- cnt_is_zero：用于判断cnt是否为0
- cnt_is_15：用于判断cnt是否为15
- addr_unchange：用于判断address是否发生了变化（Bytecode circuit table中可能是多个合约Bytecode共存的，不同的Bytecode对应不同的address），addr_cur - addr_prev，如果为0则addr没有发生变化
- addr_is_zero：Bytecode circuit table中会存在一个除了有实际意义的row之外，还存在一些为了凑行数的padding row，这些padding row所有的格子都是0

## 门约束

cnt=0的情况有三种：Opcode(非PUSH)、PUSH指令PUSH的最后一个byte、padding的row

- **Padding行**：`addr = 0`

- **Opcode（PUSH）**：`cnt_prev=0 && cnt_cur !=0`

- **Opcode（非PUSH）**：`cnt_prev=0 && cnt_cur =0 && addr != 0`

- **PUSH的byte**：`cnt_prev != 0 && cnt_cur != 0`

- **PUSH的最后一个byte**：`cnt_prev != 0 && cnt_cur == 0`

#### **Pc 约束**

- 当地址发生变化时（表示新的合约开始），`pc` 应从 0 开始：

  ```
  addr change ----> pc = 0
  ```

- 当地址未发生变化且地址不为 0 时（同一个合约中），`pc` 是累加的：

  ```
  addr unchange && addr != 0 ----> pc_cur - pc_prev = 1
  ```

#### **Padding Row**

在填充行中，所有相关字段的值都为 0：

```
cnt、addr、pc、bytecode、value_hi、value_lo、acc_hi、acc_lo、is_high、rlc_acc、hash_hi、hash_lo 都为 0
```

#### **Opcode（非 PUSH）**

对于非 PUSH 的操作码，以下字段的值都为 0：

```
cnt、value_hi、value_lo、acc_hi、acc_lo、is_high 都为 0
```

#### **Opcode（PUSH）**

对于 PUSH 指令：

- `cnt` 不为 0，`acc_hi` 和 `acc_lo` 均为 0：

  ```
  cnt != 0, acc_hi = 0, acc_lo = 0
  ```

- `value_hi` 和 `value_lo` 由下一行进行约束。即当 `cnt_prev != 0` 时，`value_hi` 和 `value_lo` 均与上一行相等。因此 PUSH 指令的所有行的 `value_hi` 和 `value_lo` 均等于 PUSH 的最后一个 byte 的 `value_hi` 和 `value_lo`：

  ```
  value_hi 和 value_lo 的最终值等于 PUSH 的最后一个 byte 的 value_hi 和 value_lo
  ```

#### **cnt_prev != 0**

当 `cnt_prev != 0` 时，表示当前行是 PUSH 指令的字节：

- `cnt` 是递减的：

  ```
  cnt_prev != 0 ----> cnt_prev - cnt_cur = 1
  ```

- 用于约束 `cnt = 15` 和 `cnt = 16` 的分界线：

  ```
  cnt_prev != 0 -----> is_high_prev - is_high_cur - cnt_is_15 = 0
  ```

- 约束 `acc_hi` 的值：

  ```
  cnt_prev != 0 ----> acc_hi_prev + is_high * (acc_hi_prev * 256 + bytecode) - acc_hi_cur = 0
  ```

  当 `is_high = 0` 时，`acc_hi` 的值不变：

  ```
  cnt_prev != 0 && is_high = 0 ----> acc_hi_cur - acc_hi_prev = 0
  ```

  当 `is_high = 1` 时，`acc_hi_cur` 的值为 `acc_hi_prev * 256 + bytecode`：

  ```
  cnt_prev != 0 && is_high = 1 ----> acc_hi_prev * 256 + bytecode - acc_hi_cur = 0
  ```

- 约束 `acc_lo` 的值：

  ```
  cnt_prev != 0 ----> acc_lo_cur - acc_lo_prev - (1 - is_high) * (acc_lo_prev * 256 + bytecode) = 0
  ```

  当 `cnt < 16` 时，即 `is_high = 0`，`acc_lo_cur` 的值为 `acc_lo_prev * 256 + bytecode`。

- `value_hi` 和 `value_lo` 的值保持不变：

  ```
  cnt_prev != 0 ----> value_hi_prev - value_hi_cur = 0, value_lo_prev - value_lo_cur = 0
  ```

#### **PUSH 的最后一个 byte**

- `cnt_prev != 0` 且 `cnt = 0` 时，`value_hi` 和 `value_lo` 的值等于 `acc_hi` 和 `acc_lo`：

```
cnt_prev != 0, cnt = 0 ----> value_hi = acc_hi, value_lo = acc_lo
```

#### rlc_acc

- 当地址发生变化时，`rlc_acc` 为当前 `bytecode`：

  ```
  addr change ----> rlc_acc = bytecode
  ```

- 当地址未发生变化且地址不为 0 时，`rlc_acc` 累加：

  ```
  addr unchange && addr != 0 ----> rlc_acc = rlc_acc_prev * challenge + bytecode
  ```

#### **hash_hi 和 hash_lo**

- 当下一行的地址发生变化时，当前行存放有合约的哈希值：

  ```
  addr_unchange_next != 0 ----> hash_hi 和 hash_lo 不为 0
  ```

- 其他情况下，`hash_hi` 和 `hash_lo` 的值均为 0：

  ```
  addr_is_not_zero && addr_unchange_next != 0 ----> hash_hi 和 hash_lo 为 0
  ```

## Lookup约束

每一个byte都应该在fixed电路中Lookup到，即每一个字节大小都应该在0~255范围内。

**Lookup Fixed table**：约束Bytecode是否为正确的Opcode，格式为`<tag=Bytecode, bytecode, is_push, cnt>`。

**Lookup keccak table**：格式为`<pc+1（即length）, rlc_acc, hash_hi, hash_lo>`，仅在下一行的`addr change==0`时进行。

**Lookup Public table**：格式为`<tag=CodeHash, addr, hash_hi, hash_lo>`，仅在下一行的`addr change==0`时进行。

## 2024-07-01更新

### 需求

bytecode可能存在一种情况，在bytecode末尾的PUSH可能存在push字节码不足的情况，如：

```shell
./evm --code 6f2f --json run
{"pc":0,"op":111,"gas":"0x2540be400","gasCost":"0x3","memSize":0,"stack":[],"depth":1,"refund":0,"opName":"PUSH16"}
{"pc":17,"op":0,"gas":"0x2540be3fd","gasCost":"0x0","memSize":0,"stack":["0x2f000000000000000000000000000000"],"depth":1,"refund":0,"opName":"STOP"}
{"output":"","gasUsed":"0x3"}
```

如上`6f`是`PUSH16`但是PUSH指令后面不足16个byte，会将PUSH指令后面的值右边填充0，如上`0x2f000000000000000000000000000000`

### 实际trace中遇到的原因

原因是合约字节码后面都会有一段`metadata`，这段`metadata`描述了一些编译器相关的信息，并不再有效的(p c可以跳转到的)bytecode之内

按照正常流程，pc跳转执行bytecode，并不会执行到这部分代码，但是zkevm在解析bytecode是从前向后按照顺序解析，就会出现将metadata的数据解析为无效OPCODE的情况

### 方案

生成bytecode witness时，对bytecode进行处理，当PUSHX后面的字节数量不够X个，用`0` padding到X个，这些padding行使用` is_padding`进行标识，如果是padding行，则`is_padding`的值为1。并新增一个`length`，用来记录有效code的长度(除了padding行的有效行)，这种情况下的最后一个有效行就是`addr != 0 &&addr_nochange_next && is_padding == 0 && is_padding_next == 0 `

但是有时并不会遇到`当PUSHX后面的字节数量不够X个`的情况，这种情况下的，最后一个有效行就是`addr != 0 && addr_change_next && is_padding ==0`

因需要区分两种情况，为简化，所以不管会不会出现`PUSHX字节不够X`的情况都进行padding，总的padding数量32, 即`最终长度(带有padding的长度)-有效长度(无padding的长度) == 32`

 keccak计算hash时不算这部分padding的值

### 新加约束

length:  `length_cur == length_prev`

最后一个有效行：
  `addr != 0 &&addr_nochange_next && is_padding==0 && is_padding_next == 1`---> `pc == length -1`
  即 pc == length -1为最后一个有效行

Padding:

​    padding的位置如果是PUSH的byte，则按照PUSH的约束执行

   如果padding的位置不是PUSH的byte，则除addr, pc, length外的所有值都为0