On chain execution of fork accountability protocol

[milosevic]

As described in https://github.com/tendermint/spec/blob/master/spec/consensus/fork-accountability.md there are several kind of attacks that can lead to a fork in case Tendermint failure model (https://github.com/tendermint/spec/blob/master/spec/consensus/light-client.md#tendermint-failure-model) assumptions do not hold.

With respect to the way evidence misbehaviour is constructed and processed we make difference between:

• individual evidence (equivocation, phantom and lunatic validators attack(https://github.com/tendermint/spec/blob/master/spec/consensus/fork-accountability.md#off-chain-attacks)) and
• global evidence (flip flopping attacks (https://github.com/tendermint/spec/blob/master/spec/consensus/fork-accountability.md#flip-flopping)).

In the former case, we can construct evidence of misbehaviour for an individual process and evidence is self-verifiable, i.e., it does not require access to the state of all (correct) validators to check its validity. In the latter case, detecting faulty validators requires access to the state of all (correct) validators and running fork accountability procedure (tendermint/spec#55).

In case of fork attack there is at some point in time +1/3 of voting power controlled by the faulty validators, therefore there is a risk that faulty validators will censor propagation and execution on the chain of the corresponding evidence (detected by some correct party). Therefore, one line of thinking would suggest halting the chain in case of fork detection and execution of the fork accountability procedure off-chain by relying on social consensus. On the other side, as validator set in Tendermint is dynamic, faulty validators might not be able to guarantee they would stay in power long enough to censor fork accountability protocol. For example, faulty validators at the moment of detection of attack do not control anymore 1/3+ of voting power of the current validator set as in the meantime there have been some movement of voting power due to delegation/redelegation or additional voting power being staked. Therefore, execution of the fork accountability protocol on the chain still seems like interesting system feature even in case of network forks.

Execution of fork accountability protocol on chain would allow dealing with both kind of evidences (individual and global) uniformly, although the cost of evidence processing would not be the same. In case of individual evidences, as evidence is self-verifiable, processing is very similar to the way Tendermint currently deals with equivocation. In case of global evidence type, protocol is more complex and expensive as it requires some kind of challenge-response protocol, that requires suspected validators to publish its vote sets on chain. Protocol needs to be carefully designed as it affects gossip layer (evidence and vote set propagation) and on-chain parameters (size of the block and maximum size of the evidence part in the block). Furthermore, it might increase DDoS attack surface.

@ebuchman @cwgoes @josef-widder

[melekes]

from @james-ray:

A more responsible punishment mechanism can be done as follows:

When we find the chain forks, we should interrogate each voter in the intersection of the two precommit sets why it does so.
If we can find or it can provide a PoLC that is for the committed block of higher height, we turn to interrogate the voters in the intersection of this set and the lower precommit set.
If the voters in this set fail to provide a PoLC of which the height is greater than the lower committed height and less than its vote height for the higher committed block in some configured heights (e.g, 100 blocks), they are going to be punished.
Note that they should be punished in both chain forks.

No matter you committed which block, you should not change your decision, the chain has already forked, and we don't rollback, otherwize Byzantine nodes will send out previous precommts to arbitrarily rollback the chain. We just need to punish the voters which send the malicious prevotes that cause the fork.

As for the implementation, I think the interrogation and response can be done in the block, once you have received 2/3+ precommits for another block on a different chain, you include this set and your local set in the block, the intersection of the two precommit sets is as an "interrogated set", then we select subsequent block proposers from this set to give each of them a chance to provide PoLC of a lower round, the intersection of the PoLC set and the lower precommit set is a new "interrogated set". If the round of the included "interrogated set" is the lower commited round + 1, and it is a prevote set, the voters in the intersection of this set and the lower precommit set are definitely guilty, and we can punish them immediately.

[melekes]

@cwgoes want to add your thoughts on delegating fork accountability to external validator set here?

[cwgoes]

Aye - one implementation consideration to keep in mind is that we will want the ability to run the fork accountability protocol in the application (e.g. Cosmos SDK) for a validator set stored in state (not the validator set of the running chain), in order to allow for cross-chain validation (ref cosmos/ibc#27).

[james-ray]

There is still something to think about for the implementation: what if the attackers block the net and the block proposers in the first "interrogated set" cannot send out proposal block, after some configured heights, the intersection of they and the lower precommit set are punished, but the real culprits may not all be punished.

[james-ray]

We can let the evidences be able to broadcast in the net, so other honest block proposers can help attach the evidence into their proposal blocks. Currently we have "DuplicateVoteEvidence", maybe we can add new type of evidence.
But the "interrogated set" is not the evidence that can directly used and punish. Only in the case that the height of the "interrogated set" is equal to the lower precommit set height and the round of the "interrogated set" is equal to (the round of the lower precommit set + 1) and it is a prevote set, it is a strong evidence that the intersection of the "interrogated set" and the lower precommit set are Byzantine.

[melekes]

Done in #4821