10 public

Public

总体布局

本段介绍结构体PublicCircuitConfig的列及其含义。

单功能列 Single-purpose columns

下面是public子电路中的单功能的列:

    /// various public information tag, e.g. BlockNumber, TxFrom
    tag: Column<Instance>,
     /// tx_id (start from 1), except for tag=BlockHash, means recent block number diff (1...256)
    block_tx_idx: Column<Instance>,

tag 指该行数据的类别, 其具体类型为:


pub enum Tag {
    #[default]
    Nil,
    ChainId,
    BlockNumber,
    BlockHash,
    // block coinbase and timestamp
    BlockCoinbaseAndTimestamp,
    // block gas limit, and the BaseFee
    BlockGasLimitAndBaseFee,
    // the total number of txs and logs in a block, and the block difficulty
    BlockTxLogNumAndDifficulty,

    // TxIsCreateAndStatus :  include tx is create and call data gas cost, and tx status
    TxIsCreateAndStatus,
    // combine From and Value together to reduce number of lookups
    TxFromValue,
    // combine To and CallDataLength together to reduce number of lookups
    TxToCallDataSize,
    // tx gas limit and tx gas price
    TxGasLimitAndGasPrice,
    TxCalldata,
    TxLog,
    TxLogData,
    // bytecode size
    CodeSize,
    // bytecode hash
    CodeHash,
}

block_tx_idx 指该条目的idx，在block相关的条目，表示该block在chunk的idx。在交易相关的条目，等于block_idx * 2^32 + tx_idx，tx_idx表示表示该tx在block的idx。当tag=BlockHash, 表示允许获取该条目的max_block_idx.

多功能列 Versatile columns

为了减少列的使用,缩减电路规模,设计了多功能的列。在不同的行数据类别下,这些列存放不同的数据。目前设计有4个多功能列,代码里呈现为:

values: [Column<Instance>; NUM_VALUES],

表设计

区块公共数据存放

tag为ChainId时,该行数据值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
ChainId	0	chain_id[..16]	chain_id[16..]	0	0

tag为BlockNumber时,该行数据值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
BlockNumber	0	0	Block_Number_first	0	Block_Num_in_chunk

当前block的 BlockNumber_cur = Block_Number_first + block_idx_cur

tag为BlockHash的时候,遍历最近的history_hash,每行存放数据值如下:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
BlockHash	max_block_idx	hash[..16]	hash[16..]	0	0

block_tx_idx 存 max_block_idx （表示该hash最多能被 chunk 内第几个block读取到），value[2] 存 block_number（表示当前hahs对应的block_number）

从stack中弹出要读取的 blcok_number_pop，读取当前区块的 blcok_number_cur，block_idx_cur。这样 lookup 时相关的约束就改成了：

max_block_idx = blcok_number_pop + 256 - block_number_first
value2 = blcok_number_pop
另外，max_block_idx - block_idx_cur - 1 需要约束 U8 lookup。

tag为BlockCoinbaseAndTimestamp时,该行数据值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
BlockCoinbaseAndTimestamp	block index	coinbase[..4]	coinbase[4..]	BlockTimestamp[..16]	BlockTimestamp[16..]

tag为BlockGasLimitAndBaseFee时,该行数据值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
BlockGasLimitAndBaseFee	block index	BlockGasLimit[..16]	BlockGasLimit[16..]	BlockBaseFee[..16]	BlockBaseFee[16..]

tag为BlockTxLogNumAndDifficulty时,该行数据值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
BlockTxLogNumAndDifficulty	block index	tx_num	log_num	BlockDifficulty[..16]	BlockDifficulty[16..]

tag为TxFromValue时,该行数据值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
TxFromValue	block_tx_idx	from[..4]	from[4..]	value[..16]	value[16..]

tag为TxToCallDataSize时,该行数据值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
TxToCallDataSize	block_tx_idx	to_hi	to_lo	0	tx.input.len

tag为TxIsCreateAndStatus时,该行数值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
TxIsCreateAndStatus	block_tx_idx	1/0(if create contract is 1,else 0)	call data gas cost	call data size	tx status

tag为TxGasLimitAndGasPrice时,该行数值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
TxGasLimitAndGasPrice	block_tx_idx	None	tx.gas	gas_price[..16]	gas_price[16..]

将合约的输入数据按byte遍历, 每个byte存放进TxCalldata的数据行,其中idx为该byte在合约的输入数据中的次序,byte为该次序对应的byte数据,该行数值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
TxCalldata	block_tx_idx	0	0	idx	byte

区块log数据存放

区块中每笔交易可以产生多条log,遍历区块中每笔交易的每个log,其中topic_num为该log中topics的数目(不超过4)；tx_idx为该log所属的transaction_index；log_index为该log的log_index；address为该log所属的地址；如果topic_num为0的话,log_tag为AddrWith0Topic；如果topic_num为1/2/3/4的话,log_tag为AddrWith1/2/3/4Topic。

tag为TxLog,该行数值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
TxLog	block_tx_idx	log_index	log_tag	address[..4]	address[4..]

tag为TxLog的时候,根据topic的数目,依次存放topic1/2/3/4的数据,其中topic_hash为该topic对应的hash,topic_log_tag为Topic1/2/3/4,每行数值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
TxLog	block_tx_idx	log_index	topic_log_tag	topic_hash[..16]	topic_hash[16..]

tag为TxLog时候,记录了log的data长度(data_len),该行数值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
TxLog	tx_idx	log_index	log_tag=DataSize	0	data_len

将log中的数据按照byte便利,每个byte存放一行,其中data_idx为该byte在数据块中的次序,其中LogTag::Data为该数据类型,每行数值为:

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
TxLog	tx_idx	log_index	LogTag::Data	byte	data_idx

合约公共数据存放

tag为CodeSize时,该行数据值为:

code_size hi的值应该为0，因为EVM的硬性要求（code size均不超过约4万）

tag	block_tx_idx	value[0]	values[1]	values[2]	values[3]
CodeSize	0	code_addr hi	code_addr lo	code_size hi	code_size lo

2024年5月更新

上述所有列都变为 Column<Advice> 。

问题1

如何输入公开数据到zk电路里？

解决方法：将上述所有列所有行进行哈希。将哈希值作为 Column<Instance>，仅需1列。2行，存hash_hi,lo。

问题2

上述有6列，怎么做哈希？

解决方法：假设6列的值都是u8，那将6列按列连接起来成为一个u8的数组进行哈希。我们的KeccakTable是用输入的RLC进行lookup的。注意到，连接起来的数组的RLC（CONCAT_RLC）有如下等式

CONCAT_RLC = R^5 RLC[0] + R^4 RLC[1] + R^3 RLC[2] + R^2 RLC[3] + R^1 RLC[4] + RLC[5]

其中RLC[]是六列分别的RLC。R是用于RLC的随机数r的length次方。length是整个Public table的有效数据在u8表示下的长度。

因此步骤是：

将原来table的数值转化成u8（见下段）
建一列cnt，从0开始数。建一列length，所有值都是最终的length。
求得6列的RLC（需要新一列记录rlc累加值）
求得随机数r的length次方（需要新一列记录次方的累计值）
求CONCAT_RLC
使用length，CONCAT_RLC向KeccakTable进行lookup，得到hash的hi，lo（在新建的一个或两个Column<Advice>中，新建的两个列，可以每行都是hash的hi，lo）. lookup条件cnt==length-1
使用equal约束，Column<Advice>中的hash和Column<Instance>中的hash相等。

问题3

怎么将原来table的数值转化成u8？

解决方法：上述的value都是在U128范围内的，因此，原来table的一个数值可以变为16个u8数值。那么原来table的一列就要新建一列，原来的一列中的一行的value，在新列中要占用16行。

~~再新建一列ring_16，以15,14...1,0这样循环。在ring_16==0时，对新列中16行和原来列的1行的value进行约束，证明16个u8拼成了一个value。~~

当Tag 不是Nil时，不是TxCalldata，不是TxLogData时，我们要约束Rotation 0到-15的行，约束1：他们的Tag要是Nil（除了当前行）。约束2：16行的16个u8拼成了一个value。

这样，原来table的两行之间，要插入15行的填充行（tag为Nil），填充行在value的地方没有任何意义，只在u8的地方有意义。~~lookup也要加上ring_16，且lookup时ring_16=0。~~

当Tag是 TxCalldata 或 TxLogData 时，因为每一行之间有大量重复数据，例如Tag、block_tx_idx、value_3都是相同的，因此仅对于第一行（idx==0），进行类似约束：约束Rotation 0到-15的行，约束1：他们的Tag要是Nil（除了当前行）。约束2：16行的16个u8拼成了一个value。

对于第二行及以后（idx!=0），仅对于Rotation 0的行约束，约束byte（本来就是u8）等于相应的u8那列的值。同时还要约束tag等于tag_prev，idx=idx_prev+1等等。

这样，原来table的idx==0的行上边，要插入15行的填充行（tag为Nil）。idx!=0的行上边，不需要插入。

我们原来table有6列，因此对于每列，都要进行这样的约束。

约束梳理

首先新表的列有以下几列,Column<Advice>:

tag、block_tx_id、value0、value1、value2、value3、

tag_u8、block_tx_id_u8、value0_u8、value1_u8、value2_u8、value3_u8、

tag_u8_rlc_acc、block_tx_id_u8_rlc_acc、value0_u8_rlc_acc、value1_u8_rlc_acc、value2_u8_rlc_acc、value3_u8_rlc_acc、

cnt,length, concat_rlc_acc、hash

Column<Instance>: hash

值assign

原始值为：tag、block_tx_id、value0、value1、value2、`value3

原始值以u8展示tag_u8、block_tx_id_u8、value0_u8、value1_u8、value2_u8、value3_u8，因为原始值都是U256类型且都不超过U128，拆分为u8之后即16个u8（这里的拆分方式需要与计算keccak传入的u8列表顺序一致，暂定使用大端序列）

以u8计算rlc_acc: tag_u8_rlc_acc、block_tx_id_u8_rlc_acc、value0_u8_rlc_acc、value1_u8_rlc_acc、value2_u8_rlc_acc、value3_u8_rlc_acc，计算公式：rlc_acc = rlc_acc_prev*random + cur_value, 起始rlc_acc=cur_value，即表格的第一行的值都为起始rlc_acc，所有的rlc_acc的计算持续到整张表结束, rlc_acc只能在assign value到电路中时才能够计算，因为要获取challenge的值

length: 整个表格的长度，一列的值都相等

cnt: 从1开始，持续自增，直到length, cnt==1是第一行，cnt==length是最后一行, 为什么从1开始，需要一行的padding行(cnt=0,q_enable不开启)

final_rlc_acc：当表格结束时，最后一行的tag_u8_rlc_acc、block_tx_id_u8_rlc_acc、value0_u8_rlc_acc、value1_u8_rlc_acc、value2_u8_rlc_acc、value3_u8_rlc_acc的值即为整个public表的六列原始值的rlc_acc，暂称为final_rlc_acc

challenge: 用来存放challenge的值

random_vec: 用来存放 random^5, random^4, random^3, random^2, random

concat_rlc_acc: 整个public表中所有数据的rlc_acc，计算方式为:

tag_u8_final_rlc_acc*random^5 + block_tx_id_u8_final_rlc_acc*random^4 + value0_u8_final_rlc_acc*random^3 + value1_u8_final_rlc_acc*random^2 + value3_u8_rlc_final_acc*random + value3_u8_final_rlc_acc

注：这里不再以单独的列存放concat_rlc_acc，直接在lookup时进行concat_rlc_acc的计算

Hash: Column<Advice>类型，只有在length-1和length两行有值，分别为public_hash_hi和public_hash_lo

约束

Random

1列challenge和五列random<random, random_pow_2, random_pow_3, random_4, random_5>

challenge的约束：

如果cnt==1
challenge_cur == challenges_expr.keccak_input()
如果cnt != 0
challenge_cur == challenge_prev * challenges_expr.keccak_input()

random约束

每一行都有：
random = random_prev
random^2 = random^2_prev
random^3 = random^3_prev
random^4 = random^4_prev
random^5 = random^5_prev

random^2 = random * random
random^3 = random^2 * random
random^4 = random^3 * random
random^5 = random^4 * random

最后一行(cnt==length)
random = challenge(即random值为challenges_expr.keccak_input()^length)

length

length = length_prev（从cnt=0开始约束）

最后一行，length = cnt
cnt

cnt = cnt_prev+1（从cnt=1开始约束）

最后一个有效行：last_valid_row为length-1

rlc_acc约束:

cnt=1的行，rlc_acc=cur_value_u8

cnt=1..=length, rlc_acc = rlc_acc_prev*random + cur_value_u8

assign value时并没有避开cnt=0的这个填充行，因为填充的为0，所以对于cnt=1的行来说：

rlc_acc_cur = rlc_acc_prev(cnt=0, value is zero) * challenge + value_cur,

所以 rlc_acc_cur = value_cur

U8和value，以及idx

如果 tag_cur !=nil && tag_cur != TxCalldata && tag_cur != TxLogData 或者 tag != nil && (tag==TxCalldata || tag_cur == TxLogData) && idx(value2) == 0

贼有0-15行的u8的值，等于第15行的value的值

let v1 =  value0_u8.Rotation(0);
let v2 =  value0_u8.Rotation(-1) * pow_of_two::<F>(8));
let v3 =  value0_u8.Rotation(-2) * pow_of_two::<F>(16));
let v4 =  value0_u8.Rotation(-3) * pow_of_two::<F>(24));
let v5 =  value0_u8.Rotation(-4) * pow_of_two::<F>(32));
let v6 =  value0_u8.Rotation(-5) * pow_of_two::<F>(40));
let v7 =  value0_u8.Rotation(-6) * pow_of_two::<F>(48));
let v8 =  value0_u8.Rotation(-7) * pow_of_two::<F>(56));
let v9 =  value0_u8.Rotation(-8) * pow_of_two::<F>(64));
let v10 =  value0_u8.Rotation(-9) * pow_of_two::<F>(72));
let v11 =  value0_u8.Rotation(-10) * pow_of_two::<F>(80));
let v12 =  value0_u8.Rotation(-11) * pow_of_two::<F>(88));
let v13 =  value0_u8.Rotation(-12) * pow_of_two::<F>(96));
let v14 =  value0_u8.Rotation(-13) * pow_of_two::<F>(104));
let v15 =  value0_u8.Rotation(-14) * pow_of_two::<F>(112));

let v16 = value0_u8.Rotation(-15) * pow_of_two::(120));

pub fn expr_from_be_bytes<F: Field, E: Expr>(bytes: &[E]) -> Expression { let mut value = 0.expr(); for byte in bytes.iter() { value = value * F::from(256) + byte.expr(); } value }


```shell
let v_original = value0.Rotation::cur()

约束有: v_final == v_original

tag和value约束

如果tag_cur !=nil && tag_cur != TxCalldata && tag_cur != TxLogData，则有

# tag约束
tag.Rotation(-1) == nil
tag.Rotation(-2) == nil
tag.Rotation(-3) == nil
tag.Rotation(-4) == nil
tag.Rotation(-5) == nil
tag.Rotation(-6) == nil
tag.Rotation(-7) == nil
tag.Rotation(-8) == nil
tag.Rotation(-9) == nil
tag.Rotation(-11) == nil
tag.Rotation(-12) == nil
tag.Rotation(-13) == nil
tag.Rotation(-14) == nil
tag.Rotation(-15) == nil

如果tag != nil && (tag==TxCalldata || tag_cur == TxLogData) && idx(value2) != 0则

value2_cur(idx_cur) == value2_prev+1 (idx_cur+1)
tag_cur == tag_prev
block_tx_idx_cur == block_tx_idx_prev
value0 == value0_prev  (the value of value0 is log_index or zero)
value1 == 0 (the value of value1 is zero)
value3 == value3_u8

tag_u8 == 0
block_tx_idx == 0 
value0_u8 == 0 
value1_u8 == 0 
value2_u8

如果 tag==nil

block_tx_idx_cur == 0
value0_cur == 0
value1_cur == 0
value2_cur == 0
value3_cur == 0

hash约束

1）lookup keccak table: <length, concat_rlc_acc, public_hash_hi, public_hash_lo> (在整张表的最后一行进lookup)

当cnt == length-1时，即最后一行进行lookup

let length = length.Rotation::cur();
let public_hash_hi = hash.Rotation::prev();
let public_hash_lo = hashRotation::cur();
let random_pow_5 = challenge.Rotation(-4);
let random_pow_4 = challenge.Rotation(-3);
let random_pow_3 = challenge.Rotation(-2);
let random_pow_2 = challenge.Rotation(-1);
let random = challenge.Rotation::cur();
let tag_final_rlc_acc = tag_u8_rlc_acc.Rotation::cur();
let block_tx_id_u8_final_rlc_acc = block_tx_id_u8_rlc_acc.Rotation::cur();
let value0_u8_final_rlc_acc = value0_u8_rlc_acc.Rotation::cur();
let value1_u8_final_rlc_acc = value1_u8_rlc_acc.Rotation::cur();
let value2_u8_final_rlc_acc = value2_u8_rlc_acc.Rotation::cur();
let value3_u8_final_rlc_acc = value3_u8_rlc_acc.Rotation::cur();

let concat_rlc_acc = tag_final_rlc_acc * random_pow_5 + block_tx_id_u8_final_rlc_acc * random_pow_4 + value0_u8_final_rlc_acc * random_pow_3 + value1_u8_final_rlc_acc * random_pow_2 + value2_u8_final_rlc_acc * random + value3_u8_final_rlc_acc

注：电路运行前，public整张表在拆分u8的计算hash(instance)的时候也需要按照tag、block_tx_id、value0、value1、value2、value3这个顺序

2）copy约束

hash有两列，hash_hi, hash_lo

cnt=0位置的hash_hi=instance_hash[row=0]

cnt=0位置的hash_lo=instance_hash[row=1]

每一列的值都是相等的，赋值时使用的copy

hash_hi_prev = hash_hi_prev.copy_advice(hash_hi_cur);
hash_lo_prev = hash_lo_prev.copy_advice(hash_hi_cur);

问题：

如何判断当前行是最后一行

cnt != 0 && cnt_next == 0
如何判断表格当前行为第一行

cnt==1,即第一行
如何判断TxCalldata或者TxLogData开始行开始行

idx==0, 即为第一行
无效行(0~15行的1～15行)填充0还是和有效行(0～15行中的第0行)一样的值、

填充0
LogIndex之间是否需要约束，每一个当前一条的log与上一条log之间的index值是递增的，但是每一条log又被拆分称了多个(logTopic，logSize，logData)

不需要约束，只要保证最终的hash一致即可
如block_tx_idx等是否需要约束

不需要约束，只要保证最终的hash一致即可

其他：

为什么concat_rlc_acc = tag_u8_final_rlc_acc*random^5 + block_tx_id_u8_final_rlc_acc*random^4 + value0_u8_final_rlc_acc*random^3 + value1_u8_final_rlc_acc*random^2 + value3_u8_rlc_final_acc*random + value3_u8_final_rlc_acc

假如一个value被拆分成了16个字节：v1~v16，则value的rlc计算为:

v1, rlc1 = v1
v2, rlc2 = rlc1*random + v2, 即 v1*random + v2
v3, rlc3 = rlc2*random + v3, 即(v1*random + v2)*random + v3
v4, rlc4 = rlc3*random + v4, 即((v1*random + v2)*random + v3)*random + v4
v5, rlc5 = rlc4*random + v5, 即(((v1*random + v2)*random + v3)*random + v4)*random + v5
...
v16, rlc16=rlc15*random+v16

上面计算方式可化简为：

rlc = v1 * random^15 + v2 * random^14 + v3 * random^13 + ... + v15*random + v16

即，假如value被拆分为了len个字节v₁~ v_len ，则有

rlc= v₁ * random^(len-1) + v₂* random^(len-2) + ... + v_len-1* random + v_len