Disputes

Fast forward to more detailed disputes requirements.

Motivation and Background

All parachain blocks that end up in the finalized relay chain should be valid. This does not apply to blocks that are only backed, but not included.

We have two primary components for ensuring that nothing invalid ends up in the finalized relay chain:

• Approval Checking, as described here and implemented according to the Approval Voting subsystem. This protocol can be shown to prevent invalid parachain blocks from making their way into the finalized relay chain as long as the amount of attempts are limited.
• Disputes, this protocol, which ensures that each attempt to include something bad is caught, and the offending validators are punished. Disputes differ from backing and approval process (and can not be part of those) in that a dispute is independent of a particular fork, while both backing and approval operate on particular forks. This distinction is important! Approval voting stops, if an alternative fork which might not contain the currently approved candidate gets finalized. This is totally fine from the perspective of approval voting as its sole purpose is to make sure invalid blocks won't get finalized. For disputes on the other hand we have different requirements: Even though the "danger" is past and the adversaries were not able to get their invalid block approved, we still want them to get slashed for the attempt. Otherwise they just have been able to get a free try, but this is something we need to avoid in our security model, as it is based on the assumption that the probability of getting an invalid block finalized is very low and an attacker would get bankrupt before it could have tried often enough.

Every dispute stems from a disagreement among two or more validators. If a bad actor creates a bad block, but the bad actor never distributes it to honest validators, then nobody will dispute it. Of course, such a situation is not even an attack on the network, so we don't need to worry about defending against it.

We are interested in identifying and deterring the following attack scenario:

• A parablock included on a branch of the relay chain is bad

We are also interested in identifying these additional scenarios:

• A parablock backed on a branch of the relay chain is bad
• A parablock seconded, but not backed on any branch of the relay chain, is bad.

Punishing misbehavior in the latter two scenarios doesn't effect our security guarantees and introduces substantial technical challenges as described in the No Disputes for Non Included Candidates section of Dispute Coordinator. We therefore choose to punt on disputes in these cases, instead favoring the protocol simplicity resulting from only punishing in the first scenario.

As covered in the protocol overview, checking a parachain block requires 3 pieces of data: the parachain validation code, the AvailableData, and the CandidateReceipt. The validation code is available on-chain, and published ahead of time, so that no two branches of the relay chain have diverging views of the validation code for a given parachain. Note that only for the first scenario, where the parablock has been included on a branch of the relay chain, is the data necessarily available. Thus, dispute processes should begin with an availability process to ensure availability of the AvailableData. This availability process will conclude quickly if the data is already available. If the data is not already available, then the initiator of the dispute must make it available.

Disputes have both an on-chain and an off-chain component. Slashing and punishment is handled on-chain, so votes by validators on either side of the dispute must be placed on-chain. Furthermore, a dispute on one branch of the relay chain should be transposed to all other active branches of the relay chain. The fact that slashing occurs in all histories is crucial for deterring attempts to attack the network. The attacker should not be able to escape with their funds because the network has moved on to another branch of the relay chain where no attack was attempted.

In fact, this is why we introduce a distinction between local and remote disputes. We categorize disputes as either local or remote relative to any particular branch of the relay chain. Local disputes are about dealing with our first scenario, where a parablock has been included on the specific branch we are looking at. In these cases, the chain is corrupted all the way back to the point where the parablock was backed and must be discarded. However, as mentioned before, the dispute must propagate to all other branches of the relay chain. All other disputes are considered remote. For the on-chain component, when handling a dispute for a block which was not included in the current fork of the relay chain, it is impossible to discern between our attack scenarios. It is possible that the parablock was included somewhere, or backed somewhere, or wasn't backed anywhere. The on-chain component for handling these cases will be the same.

Initiation

Disputes are initiated by any validator who finds their opinion on the validity of a parablock in opposition to another issued statement. As all statements currently gathered by the relay chain imply validity, disputes will be initiated only by nodes which perceive that the parablock is bad.

The initiation of a dispute begins off-chain. A validator signs a message indicating that it disputes the validity of the parablock and notifies all other validators, off-chain, of all of the statements it is aware of for the disputed parablock. These may be backing statements or approval-checking statements. It is worth noting that there is no special message type for initiating a dispute. It is the same message as is used to participate in a dispute and vote negatively. As such, there is no consensus required on who initiated a dispute, only on the fact that there is a dispute in-progress.

In practice, the initiator of a dispute will be either one of the backers or one of the approval checkers for the parablock. If the result of execution is found to be invalid, the validator will initiate the dispute as described above. Furthermore, if the dispute occurs during the backing phase, the initiator must make the data available to other validators. If the dispute occurs during approval checking, the data is already available.

Lastly, it is possible that for backing disputes, i.e. where the data is not already available among all validators, that an adversary may DoS the few parties who are checking the block to prevent them from distributing the data to other validators participating in the dispute process. Note that this can only occur pre-inclusion for any given parablock, so the downside of this attack is small and it is not security-critical to address these cases. However, we assume that the adversary can only prevent the validator from issuing messages for a limited amount of time. We also assume that there is a side-channel where the relay chain's governance mechanisms can trigger disputes by providing the full PoV and candidate receipt on-chain manually.

Dispute Participation

Once becoming aware of a dispute, it is the responsibility of all validators to participate in the dispute. Concretely, this means:

• Circulate all statements about the candidate that we are aware of - backing statements, approval checking statements, and dispute statements.
• If we have already issued any type of statement about the candidate, go no further.
• Download the AvailableData. If possible, this should first be attempted from other dispute participants or backing validators, and then (via erasure-coding) from all validators.
• Extract the Validation Code from any recent relay chain block. Code is guaranteed to be kept available on-chain, so we don't need to download any particular fork of the chain.
• Execute the block under the validation code, using the AvailableData, and check that all outputs are correct, including the erasure-root of the CandidateReceipt.
• Issue a dispute participation statement to the effect of the validity of the candidate block.

Disputes conclude after ⅔ supermajority is reached in either direction.

The on-chain component of disputes can be initiated by providing any two conflicting votes and it also waits for a ⅔ supermajority on either side. The on-chain component also tracks which parablocks have already been disputed so the same parablock may only be disputed once on any particular branch of the relay chain. Lastly, it also tracks which blocks have been included on the current branch of the relay chain. When a dispute is initiated for a para, inclusion is halted for the para until the dispute concludes.

The author of a relay chain block should initiate the on-chain component of disputes for all disputes which the chain is not aware of, and provide all statements to the on-chain component as well. This should all be done via inherents.

Validators can learn about dispute statements in two ways:

• Receiving them from other validators over gossip
• Scraping them from imported blocks of the relay chain. This is also used for validators to track other types of statements, such as backing statements.

Validators are rewarded for providing statements to the chain as well as for participating in the dispute, on either side. However, the losing side of the dispute is slashed.

Dispute Conclusion

Disputes, roughly, are over when one side reaches a ⅔ supermajority. They may also never conclude without either side witnessing supermajority, which will only happen if the majority of validators are unable to vote for some reason. Furthermore, disputes on-chain will stay open for some fixed amount of time even after concluding, to accept new votes.

Late votes, after the dispute already reached a ⅔ supermajority, must be rewarded (albeit a smaller amount) as well.