6 bytecode

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包含多个字段，用于记录字节码处理过程中的相关信息：

#[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

假如有如下指令：

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包含多个列和选择器，用于约束和验证字节码：

#[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字节码不足的情况，如：

./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