appliedzkp的zkevm（12）State Proof

1. 引言

State Proof可帮助EVM Proof检查所有random read-write access records的有效性，通过首先按唯一index将这些records分组，然后按access order进行排序。将access order称为ReadWriteCounter，会对access records技术，同时为每个record提供唯一标识。当生成state proof之后，也会生成BusMapping作为lookup table 分享给EVM proof。

2. Random Read-Write Data

State proof会维护 EVM proof的random accessible data的读写部分。

在state proof中记录的操作有：

• Memory：以byte array的方式调用memory。
• Stack：以RLC-encoded word array的方式调用stack。
• Storage：将账号的storage看成是key-value mapping。
• CallContext：为call的上下文。
• Account：为账号的state（nonce, balance, code hash）。
• TxRefund：refund给tx sender的金额（value）。
• TxAccessListAccount：为account access list 的state。
• TxAccessListAccountStorage：为account storage access list的state。
• AccountDestructed：为某account destruction的state。

以上每个操作都使用不同的参数来缩影。具体见RW Table。

所有table的key拼接在一起形成该data的唯一索引。每个record都与一个ReadWriteCounter关联，这些records首先通过其唯一索引分组，然后按ReadWriteCounter递增排序。已知对前一record的access，每个target都有其自身的格式和更新规则，如 Memory中的values可以8-bit来表示。

3. Circuit Constraints

约束主要分为两类 ：

• 1）可影响所有操作的全局约束：如key的字母排序。
• 2）对每个操作的特定约束：每种操作类型采用selector-like表示，以启用仅用于该操作的额外约束。

用于保证proper ordering/transition of values的约束，借助fixed lookup table，采用range checks of the difference between the consecutive cells。由于采用lookup table来证明correct ordering，每列都必须排序，因此需要定义其包含的最大值（将对应fixed lookup table的size）。同一table内2个连续的cell将有差值，反向排序将时该差值wrap around为一个非常大的值（由于field域计算），使得该结果不在table内。

参考资料

[1] State Proof