feat: txList zk proof

[dantaik]

Describe the feature request

When a block is proposed, the protocol can request the proposer to submit a ZKP for the txList called txListProof. This txListProof shall cover all the logics inside LibInvalidTxList. verifyTxListInvalid. txLisher tProof will not be verified on L1 by default, but if other nodes realized that txListProof is invalid, the node can request to verify the txListProof then once the verification failed on L1, the block is immediately marked as proven-as-invalid.

When the main ZKP is ready to prove the entire block, it shall also cover whatever txListProof is trying to prove. In other words, the main ZKP is a super set of txListProof.

The benefits

1. We can remove LibInvalidTxList.sol and remove TaikoL2.invalidateBlock and TaikoL1.proveBlockInvalid, making proving invalid transaction easier.
2. We can optionally remove all signatures from txList to save L1 space.
3. We do not need special circuits for invalid blocks.

The downside

1. Time to generate the txListProofs may be long enough to affect the user finality since blocks cannot be proposed immediately after transactions are bundled together. This may be a huge negative UX issue for Taiko users.
2. For blocks that contains duplicate transactions, we currently count on the proposer to quickly replace his existing proposeBlock transactions with a new proposeBlock transaction (with higher gas price and a new txList), but if we need a txListProof, then the proposer can only replace his pending proposeBlock with some other transactions.

Describe alternatives you've considered

Description of the alternatives you've considered here.

Additional context

Additional context here.

[dantaik]

Given what I know now, I would vote against this feature. @Brechtpd

[Brechtpd]

I think the main question boils down to how much we are about where the potential MEV in a block goes to.

For blocks that contains duplicate transactions, we currently count on the proposer to quickly replace his existing proposeBlock transactions with a new proposeBlock transaction (with higher gas price and a new txList), but if we need a txListProof, then the proposer can only replace his pending proposeBlock with some other transactions.

This is also not possible with the current commit-reveal scheme I think as proposers will always be running behind. They would react to another block being proposed, but because there's an additional delay again for their newly proposed block it seems inevitable that the similar conflicts will happen whenever they can actually submit their updated block.

So I don't really think using a proof or not on the proposer side is worse than doing commit-reveal. Depending on how many blocks are being proposed and how long the delay it may be a bit worse or a bit better, but the main problem remains. And it does make the protocol simpler, so would say it's better than commit-reveal for that at least.

That's why I think it kind of just boils down to protocol level MEV protection question. There's currently substantial drawbacks by trying to mitigate MEV theft on the protocol level, which I'm not even sure how useful is as there are also offchain methods available that are more powerful and more flexible (currently flashbots which has some drawbacks, but generally fine I think to have as an option proposers can opt to use if they want):

• A proposer knows some particularly interesting MEV opportunity: the block proposer will opt to not share the transaction in the public mempool and uses flashbots to submit the block(s) to try and get the most of that MEV.
• In the general case where the MEV in a block is nothing special people can build on top of each other using the public mempool using the L1 implementation of feat: Conditional transactions #13209. But I think this also means that inevitably most, if not all, of the MEV + transaction fees goes the Ethereum validator as the Ethereum validator will just pick the propose transaction willing to pay the highest fee. And because this the block is public being the proposer is as simple as just stealing the block and making sure you're paying the highest fee, so the L1 fee paid will be very close to the total L2 fees earned in the block. I don't think this is necessarily a bad thing as the proposer didn't find anything too special in the block (otherwise would have opted to go the private route using the flashbots option), but it does make it so being a proposer is potentially less attractive.

Currently I think we just do away with commit-reveal and only do the proof method if it's very fast to generate (so not yet in any case).

[Brechtpd]

Some resources I found interesting about flashbots on how they mitigate DOS risks (they use trusted dedicated relayers):

• https://notes.ethereum.org/@casparschwa/Bya8S_81Y
• https://docs.flashbots.net/flashbots-auction/overview

Not only interesting to us because of the the L2 proposing possibilities, but also because the current proving fee system is vulnerable to DOS risks as well. #351 (comment)

[dantaik]

Thank you for your feedback, Brecht. I think I'm more or less convinced that txListProof may be a good idea instead.

1. It will simplify the protocol in terms of contract complexity and gas cost, we do need extra circuits for it.

2. If a txListProof can be generated 12-36 seconds, we can disable or remove commit-and-propose; if it can be genereated faster, maybe we can keep commit-and-propose and config it to wait for 1 block time (12 second), then the effective delay will be the txListProof time + 12 seconds; if the proof takes a few minutes, then it's a user experience issue (are we OK with it?)

3. It seems Taiko proposers shall work with MEV builder on L1 to protect their blocks (proposeBlock transactions). From the MEV perspective, a proposeBlock transaction is no different from a profitable Uniswap trade transaction on L1. So maybe we don't even need to offer any stealing-prevention in our rollup contract design.

[Brechtpd]

• I'm in favor of removing the commit-reveal scheme in all cases, I only see downsides. What are the reasons you would keep it?
• How do you see efficient block proposing happen with the delays caused by commit-reveal/txListProof generation? Even 1 block delay seems problematic.

[dantaik]

• I'm in favor of removing the commit-reveal scheme in all cases, I only see downsides. What are the reasons you would keep it?

If we do not want to solve any MEV related issues in the protocol, I agree that we should remove commit-and-propose.

• How do you see efficient block proposing happen with the delays caused by commit-reveal/txListProof generation? Even 1 block delay seems problematic.

If we cannot afford any delay in block proposal, then txListProof is indeed problematic. Don't you think?

[dantaik]

A draft implementation is here: https://github.com/taikoxyz/taiko-mono/pull/13225/files

[Brechtpd]

If we do not want to solve any MEV related issues in the protocol, I agree that we should remove commit-and-propose.

If we can come up with something that is better than what can be achieved offchain I'm all for it, but it seems problematic with the current approach for decentralization without a leader.

If we cannot afford any delay in block proposal, then txListProof is indeed problematic. Don't you think?

Yep. Similar to above, if we can find a way to have it without impacting the efficiency of proposing than it'd be a nice thing to have. Perhaps some out of the box thinking of easy ways to prove a block is invalid without the attached txListProof is something to explore (for example an optimistic rollup style fraud proof could be used instead, but that's of course a huge dependency to add so doesn't make sense, although if we add a fraud proof system in our multi-prover setup we would already have that dependency).

[dantaik]

Let's try to implement the txListProof and measure it's time cost asap. Hopefully it's small enough.

[Brechtpd]

The most problematic part for proving a block has invalid data is the RLP format. But now that I have worked with RLP in the MPT circuit maybe not necessarily super complex to support invalid data as well. Will spend some time looking into the RLP circuit used for decoding the transactions and see what's possible.