Byzantine fault tolerance, based on the Byzantine Generals problem, is a must for decentralised networks where nodes need to come to agreement even if some are malicious. @dirvine goes through what BFT is, and crucially what it misses.
General progress
@davidrusu Has been working on decoupling AE from the join messages and has made some good progress there, the join code is quite a bit simpler now.
@joshuef is looking at joining nodes too, and has found some anomalies. When more than a third of responses from elders have been received, the joining node asks again. With five elders, having received two responses, the node retries and gets two more replies. But at that stage it receives a response for the first try, which causes a stall/ghost node situation.
He has also successfully removed more locks, meaning that adults can now write directly to the filesystem without any intermediate stages. An important simplification.
And in another bit of streamlining, @bzee has refactored part of qp2p into a more Quinn-like API where there is no separate data structure needed for incoming connections or streams.
Byzantine Fault Tolerance
Byzantine generals problem in real-world terms
In the Byzantine Generals Problem, an army has the city of Byzantium under siege. The generals commanding these forces need to decide the time to attack. If all the generals lead their forces to attack the city at the same time, victory is assured, but if they attack at different times, they lose. The generals have no direct communication with one another and the message carriers may be enemy spies, may be killed by the defending forces or the messages themselves might have been changed. Plus, of course, some of the generals themselves might be traitors. How do the generals ensure their forces all attack at the same time?
This is the problem that decentralised networks must overcome.
Applying the analogy to decentralised systems we get:
- Loyal generals ==> honest nodes
- Traitorous generals ==> faulty nodes
- Enemy Army we are sending messages through ==> unreliable asynchronous network which may drop and delay messages
This story is a digestible cover for some fairly heavy maths in which it turns out that so long as no more than a third of the generals are treacherous, the honest generals can coordinate their plans successfully – Byzantine Fault tolerance (BFT).
We have multiple nodes, some of which can be dishonest and some can suffer comms failures between them.
The classical Byzantine generals problem is one of local state synchronisation in spite of traitorous generals attempting to diverge states. To broaden it out a bit, both ATTACK and RETREAT would be correct (valid) answers… as long as all loyal forces do the same.
For our purposes, the classical Byzantine generals problem is a constrained view of BFT. It’s focused purely on consensus and so it needs to deal with more types of faults.
There are other notions of BFT we can look at instead to handle problems with membership.
Here the issue is that we have a fork. When adults and elders leave or join the nodes can have different views of the section. Though this fork will eventually be resolved, the decisions made during the split view, e.g. a DBC spend, are hard to handle. Thus we are trying to avoid this split-view through consensus.
One option Mostafa and @Davidrusu are working through is a broadcast protocol called Verifiable Consistent Broadcast (VCBC).
BFT Broadcast Protocols
A broadcast protocol tries to disseminate a message from a node to the network. The BFT version tries to ensure that all nodes agree on the message this node had sent:
On the left we have an honest node 1 broadcasting msg to 2,3,4,5. On the right we have a faulty node 1 broadcasting a to 2,3 and b to 4,5.
A BFT broadcast protocol protects against the fork in the second case by ensuring all honest nodes either agree to the same message from node 1 or they all refuse to accept any message from node 1.
The way this is done in VCBC is through a 3 phase protocol:
- Node 1 broadcasts the message it wants everyone to see
- All nodes check if this is the first time Node 1 has sent a message, if so responds with a signature share over the message:
sigma_j(m) - Node 1 waits until they receive >2/3rd of the signature shares to aggregate into a full signature, then broadcasts the full signature to the network convincing everyone that they all have the same message.
Let’s look at how this algorithm breaks down.
VCBC crucially relies on more than 2/3rd’s of the network following the protocol faithfully. We can ask ourselves: “What damage can be done if 1/3rd or more of the nodes are faulty?”
If more than 1/3rd but fewer than 2/3rds + 1 are faulty, then the worst they can do is stall the network by refusing to contribute signature shares.
If more than 2/3rds are faulty, then the faulty nodes can make signatures over any message they like.
However, this fact only holds true if the BFT nodes collude. i.e. if they are not the same attacker then they don’t matter as much. They will not create a fork.
So a critical part of BFT avoidance is the word COLLUDING.
A great mind experiment is solving the BFT problem by having MANY attackers. In this way, the single colluding attacker is diluted by other attackers and honest nodes.
What does this mean in real life?
If we consider the mind of an attacker. What would he prefer?
- The network is still running
- His enemy has taken control of the network
Clearly, the answer is the network is still running honestly. So unless an attacker has majority control (2f+1, where f = the number of bad, colluding nodes) then he cannot take over the network.
So if we have N==9 and attack nodes==9 but colluding nodes==0, then we have no issues?
So 100% of nodes being attackers is OK.
It is only when we have colluding bad nodes we have issues. There are two ways/thresholds in play here. If we consider a colluding attacker then the thresholds are:
- The attacker controls >=1/3 nodes
- The attacker controls >=2f+1 nodes.
1 Is a vandalism attack where he can stall decisions and the network.
2 Is a takeover of the section at least.
So perspective matters here. The more attackers we have, the more secure our network! We can reduce an attacker’s influence by having many attackers and/or many honest nodes.
So what is the BFT attack on a broadcast protocol
When we discuss a BFT attack, we mean a colluding attacker. Individual attackers are fine.
We can tolerate fewer than 1/3rd colluding bad nodes. Whereas there may be many bad nodes, we are protected as long as no colluding group exceeds 1/3 of decision makers (to stall) or 2f+1 to create a fork (takeover).
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!
Still in the weeds, but solid progress being made. All else comes from the basic mechanics being correct.
