Continuing with our progress in adapting decentralised networking consensus protocols for our purposes, in this case handling section membership, this week Mostafa takes us through ABBA and MVBA. ABBA is a coin-flipping protocol for binary agreement. If a section needs another adult the elders can choose a single node to prevent mass joining, while MVBA is used to decide between competing proposals, such as which nodes should be elders in the next iteration of the section.
General progress
@roland has been hard at work on a new TestNetwork utility will to facilitate setting up the environment for node tests. We can tell the builder to generate a network with a specific SAP in a prefix and it will create a functional and configurable network with all the gaps filled in. @oetyng is now re-factoring to enable some end-to-end tests that had been disabled after the bidirectional stream work, which had been stuck for a while.
@chriso has refreshed our AWS setup and we’re now just checking how best to leverage this during PRs (to get more speed and reliability for certain tests).
@joshuef and @roland continue to reduce the number of write locks we take on the node state. These are messages to sent between elders and clients contacting them to make sure the client has up-to-date information about the section before it tries to make a request. These write locks are another place where we can block code execution and slow a node down. They’re also an unnecessary complication and a potential source of bugs. We now only take a lock on AE messages that actually update us (previously it was all AE messages). We also no longer lock during data replication or dysfunction tracking. So we’re much closer to a lean/sane Node state, which only needs write access for a small subset of tasks network-knowledge related tasks
In addition to this work, @bochaco is also working on AE messaging and removing redundant logic in client AE handling.
ABBA and MVBA
ABBA protocol
ABBA or Asynchronous Binary Byzantine Agreement is a way to solve the consensus problem in asynchronous networks. In particular, ABBA can be used for deciding a yes/no question as a group.
In this protocol, each party starts by broadcasting their preference (yes/no). If there is no majority for the initialized values, the parties start a threshold coin-tossing scheme which will produce a random result that all can agree to. ABBA is a non-deterministic protocol, its output is a random number. If we replay the input events we might get different output.
The consistency is ensured by VCBC. As covered last week, VCBC is a broadcast protocol that tries to disseminate a message from a node to the network, with all nodes agreeing on the message the node sent. VCBC protocol can be modified in order to only accept the valid and correct proposals.
We use VCBC to make sure the messages broadcast by nodes are valid. VCBC is simply a validation check. So if an elder broadcasts a proposal that anther node should be admitted into the section, the other nodes can assure themselves that the elder is not corrupt or faulty and the proposal should be taken seriously.
After that we can use rounds of ABBA to come to agreement through a threshold signature scheme which continues until the majority of the elders reach a consensus. ABBA will always terminate. It will always produce a random binary value which is used to make the decision. If we have enough votes we can commit to the proposal.
The order of elders matters. Imagine elders are ordered like this: [3,5,7,2,1]
and 3 is offline. After VCBC, we have proposals [-,P5,P7,P2,P1] The first proposal is P5. We run ABBA for P5. We know P5 is valid and all the elders have it (consistently broadcast), therefore it should be decided after a while.
The weaker validity notion
We are taking these vanilla algorithms and altering them for our purposes. Since VCBC has already validated the messages for us, we can simply require that an honest party may only decide on a value for which it has the accompanying validating data. Otherwise it gets rejected.
This allows us to make the ABBA protocol become simpler.
MVBA protocol
The Multi Values Byzantine Agreement protocol (MVBA) is used when there is more than one proposal for reaching consensus.
We can use it when multiple elders leave or multiple adults become eligible for promotion at the same time, so there a number of possible versions of the next iteration of the section.
In this scenario, each party consistently broadcast its proposals via VCBC and after receiving enough proposals from honest parties (valid) the protocol starts running a binary agreement (using ABBA) per proposal. When the first proposal gets decided the process terminates.
Membership problem
So what is all this trying to solve? It’s about promotion and demotion of elders. This process needs to happen with the agreement of a supermajority of the honest elders, and we want to avoid total order as this is very compute-intensive and not the way nature does things. We also need to handle high levels of concurrency (multiple concurrent joiners/leavers) without having to wait on order, and being able to handle or disallow forks.
Our approach is to tackle this problem using the MVBA protocol. In this scenario, each elder proposes a list of view of the elders that will be in charge of the section after the change and broadcasts it to the other elders. This continues until the majority of the elders receive sufficient proposals from the other parties. After that the proposals are voted on using the ABBA protocol so that one final list of elders is chosen at random from those proposed.
We are deeply looking at this area, as you know, and there are trade-offs and choices to be made. One improvement we can make is to use validatable proposals. Membership allows us to do that thereby decreasing the time to an agreement. Another area is concurrency. Whereas strict order does not allow concurrency there are options, these are complex options to consider, but likely much less code again. In any case, it is good to have options, but tailoring these options to the specific case of membership gives us many choices and we can then consider the trade-offs with more certainty in this use case.
Useful Links
Feel free to reply below with links to translations of this dev update and moderators will add them here:
Russian ; 
German ; 
Spanish ; 
French; 
Bulgarian
As an open source project, we’re always looking for feedback, comments and community contributions - so don’t be shy, join in and let’s create the Safe Network together!
