Some thoughts on fraud proofs and phase 2 of sharding

[bowenwang1996]

As we all know, one important feature of phase 2 of sharding is that no validator node needs to track all shards. In order to achieve that, the current nightshade design relies on hidden validators and fishermen to submit fraud proofs when they see an invalid state transition. The fraud proofs can be verified by all validators without having access to any shard's state and therefore even if an entire shard is corrupted, the network's security is not compromised.

However, as we get closer to phase 2, the team noticed a problem: a single malicious validator can cause the chain to rollback. This is because each shard is essentially an optimistic rollup and the state transition (new state root) committed to the main chain for a specific shard entirely depends on the validator that produces the chunk. This means that a malicious validator can single handled commit an invalid state transition. Since validators on other shard do not validate this state transition, the block that contains this invalid state transition won't be immediately discarded and will rather be built upon until there is a fraud proof that shows the invalid state transition. The main problems here are 1) the stake that can cause the chain to rollback is quite low and 2) a misconfigured validator can easily cause the chain to be rolled back.

Before we discuss solutions, I think it is important to understand the problems here more deeply: why is it bad for the chain to be rolled back? We can think about this from two different perspectives:

• Damage to the protocol itself. In our design, the chain won't be actually rolled back if there is a fraud proof. Rather, the state will be reverted. More specifically, if there is an invalid state transition that happens at block h and the fraud proof is in block h+1, block h+2 will be built on top of h+1 and all the state roots in block h+2 will be the same as before block h. From this perspective, there is nothing wrong with the chain itself if we consider the "state transition" in block h+2 as part of the protocol.
• Damage to users. The main problem here is that now there can be a final block with invalid state. As a result, applications need to redefine what it means for a transaction to be completed or final. Another problem that comes with this is that the rainbow bridge currently assumes that final blocks cannot contain invalid state and this needs to be changed as well. It is worth noting, however, that we have to consider the possibility of final blocks not being valid in the current design anyways, regardless of whether one malicious validator can cause the chain to roll back. The difference here is that a roll back may cause some transactions to become invalid and they need to be resubmitted and in general degrades the user experience, so we would not like to happen very often.

Regarding solutions, I think there are generally two directions of thinking: addressing it on the protocol level and addressing it on the application level.

• Addressing the concern on the protocol level: the general idea is to increase the number of confirmation on the state transition so that one malicious validator is not sufficient to cause trouble.
  • A simple idea is to require a fixed number of additional confirmation for a chunk to be included in a block. Let's assume there are at least 10 validators for each shard (the exact number doesn't matter, but if the number of validators assigned to each shard is too small, it would be too easily corruptable). Now we can say that in order for a chunk C to be included in a block H, there needs to be at least 2 validators from this shard who sign off on the chunk, i.e, they verify that the state transition of the previous chunk proposed by C is correct. In terms of implementation, we can augment approvals to include such verdict, i.e, since each validator is assigned to some shard, their approvals can include a post state root of the previous block to verify the validity of the previous state transition. This way we can reduce the overhead caused by this extra step. Likely it will still slow down the block production though.
  • There are more ideas depending how much we want to change the finality gadget. Having more time between when a block is produced and when a block is finalized would allow for more thorough checks that increase the confidence in the blocks that are finalized. Note that currently block approvals also attest to the validity of the block, i.e, if a validator approves a block, they also approve the state transition of the shard they track . Also note that approvals are transitive, i.e, if there is an approval on block h, it also approves the state transition in block h-1. We can therefore use approvals to understand the confidence in the state transitions. As an example, if block h and h+1 are produced and when block h+2 is about to be produced, there is still no sufficient amount of approvals (exact number TBD) accumulated for some shard, then block h+2 will build on block h-1 instead.
• Addressing the concern on the application level: the idea here is that since the main concern is about users, we can think about how to give different guarantees to users. What seems important here is the notion of finality. Currently some applications crucially rely on final blocks not getting rolled back. We can potentially introduce two other levels of finality: one that indicates sufficient number of approvals (2/3 for example) have been accumulated on each shard and another that indicates the duration of the challenge period (no rollback possible after this point). Applications can decide what level of finality they want to rely on. For most applications, the current finality makes sense. For financial applications they likely want to be more prudent and wait for a longer period of time.

One unresolved problem here is how light clients should operate if final blocks could contain invalid state. Light clients on their own cannot determine the validity of the state roots included in the light client blocks and have to depend on something external for this purpose.