Invalid state transitions are a real threat in sharded blockchains. As a result, state challenges are essential to the nightshade sharding design. However, they are very quite complex and difficult to design and implement. This thread attempts to document the known challenges with state challenges and spark discussions on how we could handle them.
Note: This thread only discusses challenges for invalid state transitions. Also, It is not the purpose of this thread to provide a comprehensive design of how challenges in general should be built, even though there will be some design discussions
Revert the chain
When a challenge is successful, the state needs to be rolled back to the state before the invalid block or chunk before we apply the challenge and slash the malicious attackers. However, if we actually roll back the chain we may break doomslug since there will be conflicting approvals. As a result, we decide to keep building on the same chain and only rollback the state. More concretely, let’s say block H contains an invalid state transition in shard X and a challenge is included in block G, then the post state root of G in X is the prev state root of H in X with the challenge applied (i.e, some accounts may be slashed).
Challenge period
Should there be a limit on how far back a block can be challenged? If there is no such limit, essentially nothing on-chain can be really considered “final”, which is suboptimal. If there is some limit, what should that limit be?
State witness and the size of a challenge
When there are delayed receipts (potentially a large number of them), the challenge may need to include all of the delayed receipts to demonstrate that the state transition is incorrect. This could lead to a challenge being very large in size. Moreover, we have a limit on the size of network messages and challenges cannot be too large (or we need to find ways to divide one challenge into multiple messages).
Number of challenges in one block
To prevent the size of a block from blowing up, it may make sense to set some limit on the number of challenges that can be included in one block. For example, we can set the limit to 1.
Slashing
When we apply a challenge, some accounts are going to be slashed for committing invalid state transitions. However, one concern is that validators can get slashed if there is a bug in the protocol that caused different validators to apply different state transitions on the same chunk. This could happen, for example, if there is a bug in wasmer that classifies some nondeterministic error as deterministic, then some nodes may apply a different state transitions than other nodes and they would start challenging each other. To prevent honest validators from losing their stake due to a bug, @alexatnear proposed that we introduce a boolean flag in Account to indicate whether the account is slashed and set it to true when we apply a challenge to slash some validator. If the boolean flag is set to true, the account is frozen and no tokens can be withdrawn. If this slashing is caused by a bug, then we can later on do a protocol upgrade to reset the boolean to false on affected accounts. One (small) downside, however, is that no tokens are actually burnt here.
Another question related to slashing is which accounts are slashed when an invalid state transition happens. Do we only slash the chunk producer?
Diverging chains
Let’s consider an extreme case where half of the nodes apply some state transition and the other half apply some different state transition for the same chunk (this could happen due to some bug, as mentioned above). When this happens, each half will submit challenges to slash the other half and it would create two chains each with a different set of validators. Each chain can keep building because the slashed validators do not contribute towards the total stake. This may create a lot of confusions and undefined behaviors.
Who can challenge
In order to submit a challenge, the challenger must stake some amount of tokens so that the network won’t suffer from spams. In addition to validators, we need to have fishermen who also stake tokens to have the right to submit a challenge.