Project Spotlight: Maidsafe and PARSEC Part 3

This is Part 3 in a 3 part series on PARSEC, the Protocol for Asynchronous, Reliable, Secure and Efficient Consensus as designed by Maidsafe. Part 2 can be found here. This was first published on FlatOutCrypto.

Part 2 looked at how information is shared. We will now look at how we come to consensus.

Asynchronous Binary Agreement

Binary agreement is used to decide a ‘single meta-election’, which is the process that decides if a node’s input should be used in coming to consensus. This is achieved through a method known as ‘Binary Value Broadcast’ or, in the case of PARSEC, Binary Value Gossip (BVG). This transforms individual node’s estimates for a given binary variable into a set of binary values called “bin_values”. It needs four properties which are required for Binary Byzantine consensus, as defined by Pierre Chevalier in his presentation:

• Obligation: If at least a third of the correct nodes BV-gossip the same value, that value is eventually added to the set of binary values (bin_values) of each correct node.
• Justification: If bin_values contains a value, it has been BV-gossiped by a correct node
• Uniformity: If a binary value is added to the set bin_values of a correct node, it will eventually be added to all correct nodes’ bin_values
• Termination: Eventually the set bin_values of each correct node is not empty

So basically:

Any value (which for example could be a true or false meta-vote for a given gossip graph) estimated by over a third of nodes will be added to the binary values of each node (Obligation).

The whitepaper’s outline of how the gossip graph looks when we start to take into account true/false estimates

A concrete coin is needed in this process because it will return a binary value that is common but will also ‘fail’ unpredictably (c. 1 in every 3 times in the case of PARSEC), returning a non-binary value, which won’t have any negative consequences. It is essentially used as a tiebreaker, to solve a split where all honest nodes are tied between true and false in the event that a malicious actor is intentionally keeping a tie such that no decision can ever be reached.

Mostefaoui, Moumen, and Raynal’s paper on Asynchronous Binary Agreement introduce the concept of the ‘common coin’ into attaining consensus. Essentially the common coin:

1. Would be a device that all nodes could choose to flip which would either return a ‘heads’ or ‘tails’ result
2. Would have a result not predictable in advance by any node
3. Ensures that any time a node flips, all other nodes will observe the same value for their flip

First the network finds the oldest gossip event in the gossip graph that can see a supermajority of observers and applies BVG until the bin_values outlined above contain something (note: when the bin_values aren’t empty they are said to contain an auxiliary value). This BVG goes on until there are valid auxiliary values that have been created by a supermajority of different nodes.

At this point there are three steps with three potential outcomes for each which we go through in order until a supermajority is seen for either true or false:

Step 0 (forced true)

• A true value is reached if there is a supermajority seen of true aux values
• However, if there is a supermajority of false values then the node’s estimates are updated to false and we move on to Step 1 with an empty set of bin_values again and no auxiliary values (the process outlined above restarts)
• If there is no supermajority at all then in Step 1 true is estimated, but again with an empty set of bin_values and no auxiliary values

Step 1 (forced false)

• Same as above, but using false as a basis instead. So if a supermajority of false aux values are seen then a false value is reached, if no supermajority is seen then Step 2 begins with false as the estimate but if a supermajority of true aux values are seen then estimates are changed to true

Step 2 (genuine flip)

• If there is a supermajority of either true or false aux values then that becomes the updated estimate, otherwise a concrete coin is flipped and the estimate becomes that value

The coin makes the process slightly more confusing, as it seems to indicate that true/false decisions are taken on the whim of a random coin flip. That is not the case. It is just the estimate which is updated — that does not become the decision itself of true or false. An honest node will never ‘lie’ or change its observation because of the coin flip, it will only change if it sees that its observation is incorrect (because a majority of other nodes are returning a different value). Consensus is reached when the estimates described above become decisions.

The reason the coin is used is to prevent an attacker from working against honest nodes by manipulating the true/false flips. The final stage, the genuine flip, introduces an unpredictability that a bad actor cannot predict and so avoids the scenario where they keep the protocol tied and unable to make a decision.

How is the concrete coin result generated?

“In order to get the result of the coin flip, we will look for the first gossip event by the node with the leader index 0 that has an aux value in the current step, and take the least significant bit of its hash.”

The final point to cover is how the concrete coin actually generates the result. PARSEC ties the concrete coin to gossip events, or more specifically by converting a gossip event to a binary value (e.g. a value made up solely of 1 and 0) and then using the smallest digit of said value (the rightmost value) as the basis for the random binary value (either true = 1 or false = 0). The gossip event is chosen by sorting all nodes into a ‘leadership index’. This is known as the gradient of leadership which the whitepaper defines as:

“The leadership index of node Y at gossip event e will be its index on the list of all nodes in the network, sorted by XOR-distance from round hash(e) (the XOR-distance being simply Y ⊕ round hash(e)). The round hash is defined as “round hash(e) = hash(hash(X), hash(B), hash(round(e)))”

What this essentially means is that nodes are sorted by the distance between the hash of their public identifier and the hash of the subject node of the meta vote, the hash of latest event that reaches consensus and the hash of the round number. By sorting the hash numbers in such a way a ranking table is formed and crucially it is formed in a manner which means that the table will be different and random every time.

To get past that hurdle [that the first leader might be dead and never gossip such an event] we use the responsiveness threshold, which is just an integer function of N. This threshold will denote the number of gossip events caused by responses we will allow ourselves to create before we use another leader — one whose event we see, and who has the lowest leadership index.

This random result has to be supplemented by a means to account for a failed or delayed node (to ensure asynchrony). The responsiveness threshold gets around this by putting in place a limit of the number of gossip responses to gossip events that are received before it is assumed the leader node (the highest ranking in the gradient of leadership table) has failed because otherwise they would have responded already.

Conclusion

These different aspects referred to above are what allow Maidsafe to claim that PARSEC is a completely decentralised, open source, highly asynchronous, Byzantine Fault Tolerant consensus mechanism. The concepts outlined combine to achieve consensus without the need for a centralised authority; it does so without relying on synchrony; and it it is Byzantine Fault Tolerant as it can continue to operate despite the presence of delayed or non-functioning nodes.

Despite trying to break this down I am under no illusions it is a particularly easy read. However, hopefully I have explained the concepts in the whitepaper taken for granted as presumed knowledge and brought some clarity as to what PARSEC is trying to do and how the team have achieved it.

Disclaimer: I do not hold MAID and have no plans to buy. If you enjoyed this article then please follow me @FlatOutCrypto