appliedzkp zkevm（10）中的Transactions Proof

1. 引言

transactions proof会：

• 验证每笔交易的签名；
• 验证transactionsRoot对应的merkle patricia trie中刚好包含了所有的交易（不多不少）；
• 使得EVM proof可通过transaction table访问transactions data。

2. Transcation encoding

存在不同的交易编码方式。在第一版本的zkEVM将仅支持兼容EIP-155的Legacy transaction。未来将支持Non-Legacy （EIP-2718）transactions。

2.1 Legacy Transaction encoding

Legacy type为：

rlp([nonce, gasPrice, gas, to, value, data, sig_v, r, s])

• 在BIP-155之前，待签名的hashed data为：(nonce, gasprice, gas, to, value, data) with sig_v = {0,1} + 27
• 在EIP-155之后，待签名的hashed data为：(nonce, gasprice, gas, to, value, data, chain_id, 0, 0) with sig_v = {0,1} + CHAIN_ID * 2 + 35

其中的{0,1}表示的curve point y y y坐标的极性，该curve point对应为secp256k1签名过程中的公钥。

2.2 Non-Legacy (EIP-2719) Transaction encoding

根据：

• https://eips.ethereum.org/EIPS/eip-1559
• https://eips.ethereum.org/EIPS/eip-2718

Non-Legacy类型为：

0x02 || rlp([chain_id, nonce, max_priority_fee_per_gas, max_fee_per_gas, gas, destination, amount, data, access_list, signature_y_parity, signature_r, signature_s])

待签名的hashed data为：待定。

3. Circuit behaviour

Transactions proof证明电路中对应的public inputs有：

• chain_id
• transactionsRoot

每笔交易由以下参数定义：

• (nonce, gas_price, gas, to, value, data, sig_v, sig_r, sig_s)

其中可用作public inputs的参数有：

• (nonce, gas_price, gas, to, value, data, from)

Transactions proof证明电路的验证逻辑为：

• 1）txSignData: bytes = rlp([nonce, gas_price, gas, to, value, data, chain_id, 0, 0])
• 2）txSignHash: word = keccak(txSignData)
• 3）sig_parity: {0, 1} = sig_v - 35 - chain_id / 2
• 4）ecdsa_recover(txSignHash, sig_parity, sig_r, sig_s) = pubKey 或等价为 verify(txSignHash, sig_r, sig_s, pubKey) = true
• 5）fromAddress = keccak(pubKey)[-20:]

其中：

• 第1）步中对交易参数的rlp编码将采用定制的rlp encoding gadget来实现，以区分（不同于）MPT circuit中使用的rlp encoding。
• 第2）步中的待签名消息keccak hash验证将采用keccak circuit。该tx circuit将实现一个单独的对应keccak 的lookup table（使用RLC将rlp encoded transaction类加紧一个single value内）。
• 第3）步中根据待签名消息和签名恢复公钥将采用ECDSA circuit。该tx circuit将实现一个对应ECDSA的lookup table。
• 第5）步中的公钥keccak hash验证将采用keccak circuit。该tx circuit将实现一个对应keccak的lookup table。

根据以上信息，构建了TxTable：

0 TxID1 Tag2 Index3 valueTxContextFieldTag$TxIDNonce0$value: raw$TxIDGas0$value: raw$TxIDGasPrice0$value: rlc$TxIDGasTipCap0$value: 0$TxIDGasFeeCap0$value: 0$TxIDCallerAddress0$value: raw$TxIDCalleeAddress0$value: raw$TxIDIsCreate0$value: raw$TxIDValue0$value: rlc$TxIDCallDataLength0$value: raw$TxIDCallData$ByteIndex$value: raw

其中：

• Gas = gas
• GasTipCap = 0
• GasFeeCap = 0
• CallerAddress = fromAddress
• CalleeAddress = to
• IsCreate = 1 if to is None else 0
• CallDataLength = len(data)
• CallData[$ByteIndex] = data[$ByteIndex]

对于以上类型的table，有一些类似如下的约束：

• 1）对于每笔Tx，每个tag可且仅可出现一次。除外情况是：对于序号ByteIndex为0的情况，CallData可重复。
• 2）TxID必须从1开始，且随每笔交易顺序递增。
• 3）当Tag为CallData时，value必须在0~255之间。

由于交易table是基于public inputs构建的，Verifier（在zkRollup场景为L1合约）需要验证该table的所有行 是 基于交易data正确构建的。由于table构建的验证是在circuit之外进行的，因此，没必要在circuit内验证相同的约束。

3.1 Transaction Trie

对于每笔交易，tx circuit必须准备相应的key/value来构建transaction trie。这些key/value用于映射到MPT table的lookups中，以验证某棵树是以交易对应的key-value构建的，且该树的root value为transactionsRoot。

构建MPT table lookups，可证明：由空MPT开始，所插入的a chain of （对应每一笔交易的） key-value ，该Trie的root value为transactionsRoot。

更新每棵MPT所需的参数有：

• Key=rlp(tx_index)
• Value = rlp([nonce, gas_price, gas, to, value, data, sig_v, r, s])
• ValuePrev = 0

不过：

• 当前针对transaction trie update entries的MPT lookup table形状 暂未确定。
• 用于Transaction Trie的MPT proof不需支持deletion操作。

3.2 Circuit Behaviour捷径1

为简化起见，实现的第一版transaction circuit将使用一些捷径。 对于每笔交易，以下值将作为有效public inputs，在电路中将不对其验证：

• txSignHash（简化了电路，使其不需要计算txSignData）

特别地，对于zkRollup，将在L1合约的verification过程中，计算txSignData和txSignHash。

同时，将跳过对构建的Transaction Trie正确性的验证。当前的MPT电路将是特定的，并为实现Account Storage Tries和State Trie updates而准备的，这将不同于Tx Circuit中的使用场景：

• 1）需要在MPT中定义特殊的lookup table（不同于State Trie Lookup和Account Storage Lookup）来定义Tx Circuit。将从scratch开始构建trie，并获取其root。
• 2）State Trie和Account Storage Tire中插入的叶子节点具有固定的size，而Transactions Trie中的叶子节点为交易的RLP，其包含了可变size的calldata。这就意味着，所实现的MPT circuit需能适应可变长度的叶子节点。

一旦MPT的第一版迭代（满足State Circuit lookup所需）完成，将致力于实现本功能。

在功能实现的扩展Tx Table类似为：

0 TxID1 Tag2 Index3 valueTxContextFieldTag$TxIDNonce0$value: raw$TxIDGas0$value: raw$TxIDGasPrice0$value: rlc$TxIDGasTipCap0$value: 0$TxIDGasFeeCap0$value: 0$TxIDCallerAddress0$value: raw$TxIDCalleeAddress0$value: raw$TxIDIsCreate0$value: raw$TxIDValue0$value: rlc$TxIDCallDataLength0$value: raw$TxIDTxSignHash$value: rlc$TxIDCallData$ByteIndex$value: raw$TxIDPad00

在验证ECDSA签名时，不同于实现ECDSA lookup table，将对每笔交易使用一个ECDSA verification gadget。因CallData为可变长度，每笔交易将使用可变的number of rows，所以将对该table rearrange，使得每笔交易从固定的offset开始（通过将所有的CallData移到末尾），对于每笔交易，具体类似为：

0 TxID1 Tag2 Index3 valueTxContextFieldTag$TxIDNonce0$value: raw$TxIDGas0$value: raw$TxIDGasPrice0$value: rlc$TxIDGasTipCap0$value: 0$TxIDGasFeeCap0$value: 0$TxIDCallerAddress0$value: raw$TxIDCalleeAddress0$value: raw$TxIDIsCreate0$value: raw$TxIDValue0$value: rlc$TxIDCallDataLength0$value: raw$TxIDTxSignHash$value: rlc

该结构重复了MAX_TX次。当交易数小于MAX_TXS时，未使用交易所对应的行将用Pad tag标记。

对于每笔交易，该table的后续为：

0 TxID1 Tag2 Index3 valueTxContextFieldTag$TxIDCallData$ByteIndex$value: raw

这些行将重复MAX_CALLDATA_BYTES次，当所有交易calldata的总byte数小于MAX_CALLDATA_BYTES时，未使用交易所对应的行将用Pad tag标记。

以如上方式来组建table，使得每笔交易的CallerAddress和TxSignHash具有固定的offset。使得为这些cells值添加copy constraints到另一区域来执行验签和hash lookup成为可能。

4. 变更小结

• 1）跳过了对transaction trie构建正确性的验证（没有MPT table lookups）
• 2）跳过了对交易RLC获得待签名消息的验证。
• 3）跳过了对交易RLC哈希 以 获得待签名消息哈希的验证。
• 4）为tx table增加了TxSignHash标签（根据L1合约中的public input计算而来）。
• 5）不同于通过ECDSA table lookup来验证ECDSA签名，而是直接使用ECDSA chip：
  • 需要对tx table重排，使得每笔交易的CallerAddress 和 TxSignHash 具有固定的offset，为验签gadget实现copy constraint。将所有交易的CallData标签移到了tx table的末尾，在中间和末尾（在fixed offset区域 与 dynamic offset区域 之间）定义了padding。

参考资料

[1] zkEVM-specs Transactions proof