feat(protocol): Unprovable blocks

Brechtpd commented 1 year ago

Problem

Good description of the problem and possible solutions: https://community.scroll.io/t/the-proof-overflow-problem/841/1

If we want to be able to prove any block up till some amount of gas, then we have to set the block gas limit very low because the worst case scenario in terms of prover work compared to gas usage is bad. This is very wasteful, because even if most blocks can be proven with a lot less work, we still have to set the L2 block gas limit to something we can prove no matter what a transaction does. While this will be very possible in the future, in the short term with our current tech we have hard limits on what we can prove with reasonable hardware requirements for the prover.

As this is a relatively short term problem, the solution should also be relatively simple. Unfortunately, directly proving that a block is not provable in a zk proof is not easy. Changing some gas costs is also a possibility, but then we're playing loose with the type-1 definition and it also solves the problem in a sub-optimal way.

Proposal

I would propose a simpler solution. Let's assume we already support SGX proofs https://github.com/taikoxyz/taiko-mono/issues/13693, but this proposal does not really depend on SGX.

For proposed blocks, there's two options:

The block is provable: a zk + SGX proof is submitted showing that all transactions in the txList were executed as expected.
The block is unprovable: a zk + SGX proof is submitted, but
- The SGX proof shows that the block is unprovable for the given txList and world state, and instead an empty block (with just the anchor tx) was inserted (similar to what is done if the txList data is invalid).
- The zk proof shows that the block hash was correctly calculated for this empty block.

For unprovable blocks we would depend on SGX to prove that we should skip the block. In many ways this is very reasonable, even if the SGX proof is wrong the worst that can happen is that some transactions that should have executed did not. The bigger problem with this however is that if a block is marked as unprovable incorrectly, this invalidates the immediate finality of blocks after they are proposed. Finality (is SGX is broken) is thus reduced to the time till verification. Not great.

So what if we don't want to rely on just SGX to prove that a block is unprovable. In the scheme above we have actually created a fraud proof scenario: anyone can show that the SGX proof is invalid by submitting a normal provable block proof! So the only thing we have to do when an unprovable block proof is seen on-chain, is to make sure the window to get that "fraud proof" in is long enough, the time until the block can be verified needs to be artificially extended when the unprovable block path is taken in the fork choice. The fraud proof window can also be set quite low because the amount of money that can be stolen by marking a block as unprovable is related to the the economic activity in that block (and potentially the following blocks) because the only thing an attacker can do is skip transactions. This is similar to re-orgs in L1s, and unlike the fraud proof for an optimistic rollup where an attacker has full control over the new state root and so the total TVL is at risk.

We can even have a system in place that reduces that fraud proof window when another signature is submitted by a trusted entity (like Taiko) that also attests that the block is unprovable.

The explanation above uses SGX, but in the end this scheme working only really depends on the "fraud proofs". So the only real benefit of SGX is that it already gives very good guarantees on the correctness of the data from the start (this seems like a good idea for optimistic rollups I feel, they should do this). It also kind of removes the need for provers having to stake something so they can get slashed for submitting a wrong unprovable block proof, because it's already very hard to get the wrong proof on-chain (the protocol could give some extra reward instead in the very low change this would happen), but of course still something we could do.

Alternatively we could also require an SGX proof that a block can be proven at the proposer side. However I don't think this really adds a lot, and now places the burden of generating this SGX proof on the proposer side which seems to have some significant downsides, and not really any upsides.

Required changes

Block proposers should now check if the block can be proven before they propose a block, otherwise they will have wasted money by proposing the block (they will not get any fees for an unprovable block). Most blocks should be provable so this shouldn't really be much of a problem in practice, but under some DoS attack this may be the case. To mitigate this the block proposer can simply remove transactions at the end of the block until the block is provable. The proposer may also choose to include only transactions with a low enough gas limit that are known to always be provable. To know if a block can be proven or not, the block can be given to the prover software where the block is checked to be provable or not (without generating the actual proof of course).
An extra block validity rule is added, similar to the invalid txList case. If the block is unprovable it is replaced by an empty block (only anchor tx). This also means that L2 nodes need to do the exact same checks on the block to know if the block should be executed or not.
An extra fork choice parameter is added in the smart contract for provable/unprovable. For block verification we always just check the provable block case first. If no proof is there, the unprovable case is checked. If an unprovable block proof is available there that fork choice is chosen, but only after an additional delay for the fraud proof window.
An extra input into the circuits: provable or not provable (not provable will replace the txList with an empty list)