Malice: make interesting events handling fork resilient

Description

This point was raised by Bart in slack.

The current processing "pipeline" is very vulnerable to forks. We add interesting events to interesting_events for a peer every time we process such events by that peer, which means that if there is a fork, the adversary can control which event gets into the "queue" first. Then, after reaching binary consensus, we just pop front() from there, which may give different results for different nodes...

This process should be changed:

Instead of keeping the queue of interesting events, have a field interesting in the event itself with possible states Unknown, NotInteresting, Interesting, Consensused(usize) (Unknown for the initial state before processing for the first time) and oldest_interesting_event_index: BTreeMap<PeerId, usize> remembering what is the oldest interesting event by that peer that we remember. Then, once a binary decision is reached, we could check which of the interesting events are still interesting and seen by the deciding event, which would protect against forks.

Note:
An advantage of this approach: every meta-election can have this map of interesting events' indices as a kind of a definition of a starting point. This would define a point beyond which we don't have to traverse the graph in order to analyse a given meta-election.
Consensused(usize), on the other hand, would contain the index of the stable block at which the given event got consensused, so if we wanted to analyse some historical meta-election, we could check if an event should have been considered Consensused at that point, or just Interesting (usize could also be a Hash, but indices would be a way to speed up the comparison).


Update 2018-10-03:

During a HO with Fraser and Adam we decided to not tag events with the status, as the benefits of that are unclear/too small for now. The task will be to focus on fork resilience by itself.

The fork resilience will be accomplished by making sure that the interesting events taken as candidates for the next stable block are strongly seen by either the observers, or the deciding event (those two approaches should yield equivalent results, but might differ in performance). This is more in line with the paper, which uses being strongly seen by observers as the property that ensures agreement.

Environment

None

Assignee

Adam Cigánek

Reporter

Pierre Chevalier

Start date

2018/10/15

End date

2018/10/16

Task progress

None

Baseline start date

None

Baseline end date

None

Story Points

4

Components

Priority

Major
Configure