Skip to content

GitLab

新注册的用户请输入邮箱并保存，随后登录邮箱激活账号。后续可直接使用邮箱登录！

Last edited by gzxu
Page history
This is an old version of this page. You can view the most recent version or browse the history.

6 bytecode

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以字符串的形式表现比较形象）：

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 18 1
0xaa 3 0x2 0x2 0x0 0x203 0x405060708090a0b0c0d0e0f10111213 17 1
0xaa 4 0x3 0x203 0x0 0x203 0x405060708090a0b0c0d0e0f10111213 16 1
0xaa 5 0x4 0x203 0x4 0x203 0x405060708090a0b0c0d0e0f10111213 15 0
0xaa 6 0x5 0x203 0x405 0x203 0x405060708090a0b0c0d0e0f10111213 14 0
0xaa 7 0x6 0x203 0x40506 0x203 0x405060708090a0b0c0d0e0f10111213 13 0
0xaa 8 0x7 0x203 0x4050607 0x203 0x405060708090a0b0c0d0e0f10111213 12 0
0xaa 9 0x8 0x203 0x405060708 0x203 0x405060708090a0b0c0d0e0f10111213 11 0
0xaa 10 0x9 0x203 0x40506070809 0x203 0x405060708090a0b0c0d0e0f10111213 10 0
0xaa 11 0xa 0x203 0x405060708090a 0x203 0x405060708090a0b0c0d0e0f10111213 9 0
0xaa 12 0xb 0x203 0x405060708090a0b 0x203 0x405060708090a0b0c0d0e0f10111213 8 0
0xaa 13 0xc 0x203 0x405060708090a0b0c 0x203 0x405060708090a0b0c0d0e0f10111213 7 0
0xaa 14 0xd 0x203 0x405060708090a0b0c0d 0x203 0x405060708090a0b0c0d0e0f10111213 6 0
0xaa 15 0xe 0x203 0x405060708090a0b0c0d0e 0x203 0x405060708090a0b0c0d0e0f10111213 5 0
0xaa 16 0xf 0x203 0x405060708090a0b0c0d0e0f 0x203 0x405060708090a0b0c0d0e0f10111213 4 0
0xaa 17 0x10 0x203 0x405060708090a0b0c0d0e0f10 0x203 0x405060708090a0b0c0d0e0f10111213 3 0
0xaa 18 0x11 0x203 0x405060708090a0b0c0d0e0f1011 0x203 0x405060708090a0b0c0d0e0f10111213 2 0
0xaa 19 0x12 0x203 0x405060708090a0b0c0d0e0f101112 0x203 0x405060708090a0b0c0d0e0f10111213 1 0
0xaa 20 0x13 0x203 0x405060708090a0b0c0d0e0f10111213 0x203 0x405060708090a0b0c0d0e0f10111213 0 0
0xaa 21 ADD 0x0 0x0 0x0 0x0 0 0
0xaa 22 STOP 0x0 0x0 0x0 0x0 0 0

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, rlc_acc, hash_hi, hash_lo都为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累加)

hash_hi和hash_lo

addr_unchange_next != 0时，即下一行的addr change，下一行是新合约的开始，则当前行存放有合约的hash值(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，因为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时进行（即合约的最后一个bytecode所在行存放着合约bytecode的hash值）。

Lookup Public table，addr和hash新增的往public table的lookup。<tag=CodeHash, addr, hash_hi, hash_lo>。此lookup只在下一行的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的情况

查看议题：https://git.code.tencent.com/chainmaker-zk/zkevm/issues/72

方案

生成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

Copyright © 2024 ChainWeaver Org. All Rights Reserved. 版权所有。

京ICP备2023035722号-3

京公网安备 11010802044225号