feat: Equivocation in prevotes

[josef-widder]

#103 deals with equivocation in precommit messages. There are also scenarios where equivocation in prevotes may lead to liveness issues. We need to add a similar flow as we did for applyCommit for applyVote (record evidence, generate event).

It seams that that liveness of Tendermint is actually based on the following "gossip" property:

every message sent from a correct process to a correct process is reliably received (and timely after GST)
if a correct process sees a 2/3 quorum (of prevotes or precommits), then every correct process will eventually see the same quorum (and "timely" after GST)
The latter quorums may contain messages by Byzantine nodes. As we want to shield the votekeeper agains spamming from Byzantine nodes (and thus only store one message per round and height and step and sender), we propose a specific logic to 2/3 quorums. This is what applyCommit and applyVote should take care of.

The question remains what is the strategy to "gossip" the quorums. This is mostly a performance optimization (speed on the common case where this gossiping should be need at all, vs. delay if things go bad, where we need to explicitly gossip)

[josef-widder]

• write a run that deadlocks because of equivocation in prevotes (both for line 28 and line 36). This is the problem of the "hidden lock" (liveness problem).
• add applyQuorum to votekeeper
• perhaps do a simple wiring in the driver and store the quorums in the global state (similar to message buffers),
• and show a scenario where this solves the liveness issue (we have to see how close we need this to be to the implementation and how we do the implementation of quorum gossiping)

[josef-widder]

started to work in branch i309-equivoc-prevotes but I am blocked now. Will resume after two weeks doing audits.

[josef-widder]

Note: hidden lock means that a proposer hasn't seen a lock from a previous round. As a result the correct process with the lock won't prevote for the proposal, and we are stuck:

• after GST, to prevent hidden locks we want the property that:
  • if a correct process locks a value then every correct process will set valid value in the same round to the same value
  • this can be done
    • (1) by timeout magic, as I only lock when I am im prevote, which means there is enough time for the others to receive the messages
    • (2) by the gossip property

The run should show a scenario where this is broken right now:

• a process locks based on 2f+1, at least one message by Byzantine node b
• b equivocates to a different process before it has the 2f+1
• now it never sets valid value, even if there are no timeouts ever

[josef-widder]

hiddenlockrun is now in the branch. I will next do some wiring to pass around the Polka so that the remaining node becomes unlocked

[cason]

Notice that a Polka plus a full value v results on a ValidValue(r, v) event as in #312.