ZKEVM - Consideration on Transaction

In ZKEVM, we need to load transactions into circuit as witness, but for different use case, rollup (RU) and validity proof (VP), we might have different security requirement.

Rollup

If we assume the data availability comes from the calldata (the prover sends proof with encoded txs that it argues applied to new tx and state trie root), the proof should guarantee all txs are included and also verified.

It's costly to build the tx trie root to be public input in L1 verifier, so another naive approach is to create checksum of all txs (including the L1 deposit txs) on L1 verifier and use checksum as public input for constraint.

If we assume the data availability comes from the calldata, which means one can always rebuilds the latest state with all history L1 state trie root update txs, do we still need to build the tx trie in circuit?
han
I think that we can not worry about tha tfor now. But for compatibility reasons we should also include that eventually.
barryWhiteHat
When thinking about this, it also brings me a question: What's the main purpose of tx/receipt trie for? To prove some tx/receipt included in a specific block without re-executing the state transition?
han
Yeah so that a user can easily check their TX got included.
barryWhiteHat

Requirement

1. Which applies to tx trie also needs to apply to state trie.
2. Each tx is valid (we need to do RLP encoding + hash + ecrevoer for each)

   We might handle L1 deposit tx and L2 tx in different way.
   han

3. Checksum of txs applied to trie should match the public input

   To generate a checksum of all txs, using hash function seems intuitive, especially we might have multiple choices (keccak256, sha256, ripemd160, blake2b) in the end.
   We seem to have 2 choice: to hash all RLP encoded txs OR to hash all tx hashes. The former seems friendly to L1 verifier but in circuit we seem to hash twice on the tx (per tx and concatenated txs). We might know which to adopt after some cost estimation.
   han

Approach

1. Handle in EVM Circuit directly

We can add extra targets Tx, TxCalldata, and Call into State Circuit and constraint it as a read-only data, then in EVM Circuit we can do random access to any field of txs by their id and field key. In the beginning of each tx, we need to verify:

1. Hash of RLP encoded of tx is correct
2. Signature with hash recovers to same address to tx.origin
3. Other easier check like nonce, intrinsic gas, etc…

Then in the end of EVM Circuit, it iterates the same txs (no more or less) again to generate their checksum and constrain it to be equal to the public input one.

To make sure in the end it iterates the same txs, we might need some counter to make sure how many txs we have verified.

Q Not sure if there is other way to make the checksum gradually instead of iterating txs again in the end, then we can get rid of the counter
IMO it will be hard cause we are kind of passing bytes to Keccak256 Circuit where different txs could have different length after RLP encoding.
han
Seems at least nonce checks circuit because is has to be applied in order. For example if address_1 has two tx's in a block you need to check nonce =0 and nonce = 1 and ensure that tx 1 is applied first in evm. Its the same case with msg.value and msg.gas which can be grater than origin.balance in the second tx and case that to fail.
TL;DR we have to do some checks at least in evm proof as this is where ordered things are checked.
barryWhiteHat
Yes, nonce check is not a problem I think, in state circuit we constraint it to be sequentially increasing and the global counter to be monotonically increasing.
The main problem is still how do we ensure all txs posted to L1 as calldata are indeed executed in circuit.
han

2. Separate a Tx Circuit to handle

We can seperate all Tx, TxCalldata, and Call to another Tx Circuit just like how we did in Bytecode Circuit, which could reduce the complexity in EVM Circuit.

In Tx Circuit, it verifies all txs' signature and their checksum, then EVM Circuit can assume all txs are verified and use them directly.

But we still have to make sure EVM Circuit doesn't skip any tx, so a counter shared between them seems to be necessary.

Not sure if it save something, but at least it could reduce the development complexity (not messing up all the things in EVM Circuit).
han
generally agree. I assume you are checking stuff like nonce and balance tsuff in EVM circuit ?
Are you thinking to do a shuffle here to avoid the need for a counter ?
barryWhiteHat

Validity Proof

Not sure if VP needs to provide data of txs, but at least the proof should guarantee that all txs applied to new tx trie root also apply to new state trie root.

Requirement

1. Which applies to tx trie also needs to apply to state trie.
2. Each tx is valid (we need to do RLP encoding + hash + ecrevoer for each)

Approach

TODO