GRANDPA: Prevent unlimited equivocations DoS

[rphmeier]

Unfortunately, we do have to account for unlimited equivocations in the protocol, and we will want to (eventually) see messages when consensus fails to make progress.

I would recommend implementing a round-robin network scheduler as described in aardvark: https://www.usenix.org/legacy/event/nsdi09/tech/full_papers/clement/clement.pdf

[rphmeier]

This can be done in parallel with other work on GRANDPA and consensus.

[rphmeier]

The approach to use here is (coupled with https://github.com/paritytech/finality-grandpa/issues/34) to allow up to 6 messages in the queue per authority (propose, prevote, precommit) per round, with equivocations on all possible. But any equivocation is redundant with all others, so those can be ignored.

[gterzian]

I'd like to look into this one. Any update or changes in the requirements since last discussed?

[rphmeier]

Same strategy as the last comment. We would need changes in the substrate-finality-grandpa/communications/gossip module to track which kinds of votes peers have sent us and that we have sent them. Needs to prune stuff from older rounds as well.

[gterzian]

We would need changes in the substrate-finality-grandpa/communications/gossip module to track which kinds of votes peers have sent us

I'm looking at VotingRound.process_incoming. Perhaps that could also be a good place to deal with some sort of round-robin scheduler?

allow up to 6 messages in the queue per authority (propose, prevote, precommit) per round

do you mean that a given voter could only send 6 messages per round of voting in total? Or is 6 the maximum per poll of a voting round?

Needs to prune stuff from older rounds as well.

If we implement the logic inside a given VotingRound, then I'm guessing it would be self-contained per round?

But any equivocation is redundant with all others, so those can be ignored.

Does that mean that if a voter is marked as an equivocator, we could ignore further message from it, or at least treat those messages as low-priority? If that's the case, the buffering and scheduling of messages could take it into account, and only handle messages from equivocators if we "dont't have a lot of other messages to handle". So in a busy poll, we just keep them buffered and only potentially handle at a later less-busy poll, if at all.

[Demi-Marie]

We would need changes in the substrate-finality-grandpa/communications/gossip module to track which kinds of votes peers have sent us

I'm looking at VotingRound.process_incoming. Perhaps that could also be a good place to deal with some sort of round-robin scheduler?

allow up to 6 messages in the queue per authority (propose, prevote, precommit) per round

do you mean that a given voter could only send 6 messages per round of voting in total? Or is 6 the maximum per poll of a voting round?

Needs to prune stuff from older rounds as well.

If we implement the logic inside a given VotingRound, then I'm guessing it would be self-contained per round?

But any equivocation is redundant with all others, so those can be ignored.

Does that mean that if a voter is marked as an equivocator, we could ignore further message from it, or at least treat those messages as low-priority? If that's the case, the buffering and scheduling of messages could take it into account, and only handle messages from equivocators if we "dont't have a lot of other messages to handle". So in a busy poll, we just keep them buffered and only potentially handle at a later less-busy poll, if at all.

If someone sends us a flood of messages (too many for us to handle), can we drop some?

[gterzian]

I've opened https://github.com/paritytech/finality-grandpa/pull/64 to discuss this more concretely...

[rphmeier]

@DemiMarie-parity

If someone sends us a flood of messages (too many for us to handle), can we drop some?

That's the goal. Alistair and I designed double-vote counting in GRANDPA so that a double-vote counts as all possible double-votes. This means that if I see a double-vote from a voter in a round, any further double-votes in that round are redundant and should not be sent to me. The rationale of this counting method is to give us a bounded amount of space to use per voting round, which isO(n_voters).

@gterzian

allow up to 6 messages in the queue per authority (propose, prevote, precommit) per round

OK -- I've not done a great writeup in this issue. here's the one from the gossip document.

---

Round message types:

• Prevote (max 2 per voter per round)
• Precommit (max 2 per voter per round)
• Primary-Broadcast (max 2 per round from a single, known, per-round rotating voter).

Although it says max 2 above, honest behavior of voters is to sign and send only one. However, we must import and propagate both votes if we receive more than one. Once we have received 2 of a kind, we can ignore further ones -- GRANDPA vote-counting makes further double-votes irrelevant, but accounting for the first double-vote might be necessary to advance consensus.

We can "time-out" messages from voters after receiving double-votes from them (again, only after processing those votes). Messages from timed-out voters can be safely ignored, but the time-out should be limited (10 minutes?) and we must be careful not to time-out more than $f=max(n-1, 0)/3$ at once. A FIFO would be good for that.

---

Note that this is for voters, not for peers. But we can expand this logic to our peers as well. A peer is not allowed to send us more than 2 (propose, prevote, precommit) messages for a single voter. Likewise, we are not allowed to send that to our peers. Just as an example: it's OK to send 2 of each, but not e.g. 3 proposes, 1 prevote, and 1 precommit.

Since this is tightly integrated into the gossip system, I think it will be difficult to do it at the level of the finality-grandpa crate.

[gterzian]

@rphmeier Thanks for additional info, I'll pause what I was doing over at https://github.com/paritytech/finality-grandpa/pull/64 and start looking at things at the level of gossip in Substrate itself... (at least I now know what a VotingRound is ...)

[gavofyork]

@rphmeier @andresilva please advise on what to do about this issue - there was a PR but it's pretty stale now.

[rphmeier]

AFAIK this was done ages ago