Thanks to Kev and Ignacio for discussion on this note.

In the case that Ethereum decides that the builder of a block is responsible for the proof of the previous block, it is necessary to be able to proof a block is invalid. Proofs of Invalidity are not necessary in the Prover Killers Killer design. In this note we discuss when proofs of invalidity are necessary.

Suppose the builder of block N is responsible for the proof of block N-1. However, block N-1 may be invalid. The first problem is that the beacon proposer may not know which head to build on since it may not have seen a proof of block N-1. What should it do? A reasonable rule seems to be that the beacon proposer should only consider blocks for which it has seen validity proofs. Assume that there is a validity proof for block N-2 and the beacon proposer takes that block as its head.

How does the beacon proposer convince the attesters that it left out the validity proof of block N-1 honestly instead of leaving it out maliciously to e.g. extract more MEV? Attesters could differentiate between an honest and a malicious beacon proposer in the following ways:

1. Re-execute block N-1 which clearly is a nonsensical solution in the zkEVM paradigm.

2. Assume there is always at least one party proving the block if it is valid. Then if there is no proof, allow the beacon proposer to build on block N-2. There could now be a split-view attack where a prover publishes the proof at the same time as when the beacon proposer publishes its beacon block which could grieve the slot N beacon proposer. To prevent this, a mechanism like the Prover Killers Killer design is necessary. This option therefore is almost identical to the Prover Killers Killer design.

3. Provide proofs of invalidity. The beacon proposer could propagate a proof that block N-1 is invalid in order to convince attesters that block N should build on block N-2 instead of N-1. The beacon proposer, however, cannot prove invalidity by themselves as we assume beacon proposers do not have prover hardware. That means a different execution proposer would have to do so. Today builders bid for the right to become an execution proposer via MEV-Boost. Possibly, builders could include proofs of invalidity if they want the beacon proposer to choose a different head than the last available beacon and execution blocks.

That leads to the conclusion that proofs of invalidity are necessary if Ethereum does not use the Prover Killers Killer design.