GitLab

Bytecode circuit用于约束合约的Bytecode，为其他电路提供bytecode的来源依据，其他子电路可通过Lookup约束来验证所操作bytecode码是否是合法的。

Bytecode table中存放的可能并不只是一个合约的Bytecode，不同的合约的Bytecode以address进行标识，Bytecode与address是唯一一一对应。

对于一个合约的Bytecode而言，pc是opcode或者no_code(push的byte)唯一的标识

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

1. Opcode(非PUSH)：操作指令，如ADD、SUB、CODECOPY
2. Opcode(PUSH)：PUSH1~PUSH32，以及PUSH的Byte

Witness、Column设计

Witness

#[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，则表格如下（这里的Opcode以字符串的形式表现比较形象）：

Circuit Column

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

门约束

addr = 0 ----> Padding row(所有值都为0)

cnt_prev=0 && cnt_cur !=0 ----> OPCODE(PUSH)

cnt_prev=0 && cnt_cur =0 && addr != 0 ---> OPCODE(非PUSH)

cnt_prev != 0 && cnt_cur != 0 ------> PUSH的byte(非push的最后一个字节)

cnt_prev != 0 && cnt_cur == 0 -------> PUSH的最后一个字节

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

Pc

addr change ----> pc=0 (addr发生变化，说明是一个新的合约，pc应该从0开始)

addr unchange && addr != 0 ----> pc_cur - pc_prev = 1 (同一个合约中pc是累加的)

Padding row

cnt、addr、pc、bytecode、value_hi、value_lo、acc_hi、acc_lo、is_high都为0

Opcode(非PUSH)

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

Opcode(PUSH)

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

value_hi和value_lo由下一行进行约束，即当cnt_prev!=0时，value_hi、value_lo都和上一行相等，以此类推则PUSH指令的所有的row的value_hi和value_lo都会等于PUSH的最后一个byte的value_hi和value_lo（PUSH的最后一个byte的value_hi和value_lo是我们想要的最终的value_hi和value_lo）

cnt_prev != 0

cnt_prev != 0说明当前行为PUSH指令PUSH的byte

cnt_prev !=0 ----> cnt_prev - cnt_cur = 1 (PUSH指令的cnt是递减的)

cnt_prev !=0 -----> is_high_prev - is_heigh_cur - cnt_is_15 = 0 (用于约束cnt=15和cat=16的分界线的cnt, 当cnt=15时, cnt_is_15=1，因为cnt>=16时is_high=1, cnt<16时is_high=0, 所以cnt_is_16_is_high - cnt_is_15_is_high =1)

cnt_prev !=0 ----> acc_hi_prev + is_high*(acc_hi_prev*255 + bytecode) - acc_hi_cur =0(约束acc_hi)

  cnt_prev !=0 && is_high=0 ----> acc_hi_cur-acc_hi_prev=0 (cnt < 16的行，acc_hi的值是不变的)

  cnt_prev !=0 && is_high=1 ----> acc_hi_prev*256 + bytecode - acc_hi_cur =0 (即acc_hi_cur的值为acc_pre*256+bytecoce)

cnt_prev !=0 ----> acc_lo_cur - acc_lo_prev - (1-is_high) *(acc_lo_prev*255 + bytecode)=0 (约束acc_lo，当cnt < 16, 即high=0时，acc_lo_cur=acc_lo_prev*256 + bytecode)

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=acc_hi, value_lo=acc_lo

rlc_acc

addr change ----> rlc_acc=bytecode (addr发生变化，说明是一个新的合约，rlc_acc开始)

addr unchange && addr != 0 ----> rlc_acc = rlc_acc_prev * challenge + bytecode (rlc_acc累加)

Lookup约束

每一个byte都应该在fixed电路中Lookup到，即每一个字节大小都应该在0~255范围内~~（是否真的有必要进行Lookup，因为bytecode列是从instance_bytecode来的，是公共数据）~~

Lookup Fixed table， 约束Bytecode是否为正确的Opcode, <tag=Bytecode, bytecode, is_push, cnt>

Lookup keccak table，<pc+1（即length）, rlc_acc, hash_hi, hash_lo> 去往Keccak table查。此lookup只在下一行的addr change==0时进行。

Lookup Public table，addr和hash新增的往public table的lookup。<tag=CodeHash, addr, hash_hi, hash_lo>。此lookup只在下一行的addr change==0时进行。（也许addr要拆成hi和lo）