Asynchronous Byzantine Fault Tolerance (ABFT) has become one of the ways of delivering consensus in the DLT (distributed ledger technology) arena – for example by Hotstuff. Because these have deep roots in cryptography, protocols based on approaches like Byzantine Fault Tolerance (BTF) are in use by many projects.
In the words of Wikipedia: “A Byzantine fault is a condition of a computer system, particularly distributed computing systems, where components may fail and there is imperfect information on whether a component has failed. … In a Byzantine fault, a component such as a server can inconsistently appear both failed and functioning to failure-detection systems, presenting different symptoms to different observers. It is difficult for the other components to declare it failed and shut it out of the network, because they need to first reach a consensus regarding which component has failed in the first place.” ABFT is a specific form of Byzantine Fault Tolerance (BFT).
The two generals problem
For those unfamiliar, BFT takes its name from what is often referred to as the Byzantine Generals Problem. Developed to describe a situation in which, in order to avoid catastrophic failure, two generals must agree on a concerted strategy. But either the of the actors and/or the means of communication may be unreliable.
Jim Gray gave it the name ‘The Two Generals Paradox‘ in 1978 in his “Notes on Data Base Operating Systems”. This built on the work of E A Akkoyunlu, K Ekanadham, and R V Huber in 1975 in their “Some Constraints and Trade-offs in the Design of Network Communications”.
Put as simply as possible, the problem is this. Two armies, led by different Generals A and B, are preparing to attack a fortified city. Their armies are encamped near the city, each in its own valley. A third valley separates the two hills. The only way for the Generals A and B to communicate is to send messengers through this middle valley. Unfortunately, the city’s defenders occupy this third valley and so may capture any given messenger sent through the valley.
Generals A and B have agreed beforehand they will attack. But they have not agreed a time to attack. To win Generals A and B must combine and coordinate because the city’s defenders are strong enough to vanquish either A or B individually, or in in series. Thus, to capture the city, Generals A and B must attack at the same time. To arrange this, they must communicate and agree the time to attack – and agree they will attack.
Neither General A nor B will attack, because they know they will lose, until they are certain their counterpart will attack at the same time. Because any one message can go missing as easily as any other message, both Generals require a potentially infinite series of messages to ensure they have come to a consensus and so initiate a successful attack.
Dr Gray’s characterisation of the Two Generals’ Paradox lies in the impossibility of designing any approach which overcomes:
- the communication synchronicity (or lack of) issues between Generals A and B
- the trust needed that the other General will perform as promised.
The relevance and HotStuff
The blockchain industry often seems, from outside, like a series of compromises without a great deal of light. Accompanying this is much promise about what blockchain technologies will achieve, with exciting visions of the future. There is often little awareness of the slow pace of real progress.
Into this space has arrived ABFT which has become popular with some but not others (this is normal in any evolving technology space). HotStuff is a leader-based Byzantine fault-tolerant replication protocol for a partially synchronous model. Once network communication becomes synchronous, HotStuff enables a ‘correct’ leader to:
- drive the protocol to consensus at the pace of actual (vs. maximum) network delay (responsiveness)
- deliver communication complexity that is linear (to) the number of replicas.
This results in HotStuff being a partially synchronous BFT replication protocol which satisfies the above. To achieve this, the builders of HotStuff:
- uses a framework which forms a bridge between classical BFT foundations and blockchains
- allows the expression of other known protocols (DLS, PBFT, Tendermint, Casper) in a common framework.
According to a Cypherium post on Medium, Hotstuff “improves upon the reservations that critics wage against BFT blockchains, and it does so without sacrificing some other aspect of the protocol. In a brief half-page of code, HotStuff dramatically edits out the former inefficiencies of asynchronous BFT protocols.
“In fact, HotStuff makes BFT more scalable by an order of magnitude, as the algorithm’s view-change complexity is made quadratically faster — a function of simply the number of nodes in the network, as opposed to a function of the number of nodes squared, as is the case in PBFT.”
Enterprise Times: What does this mean
At the heart of all blockchain initiatives lies a dilemma – how to handle consensus. The Bitcoin model, consuming vast amounts of energy and with depressingly slow performance, is not relevant for modern enterprise commerce (though it is interesting as a demonstration of what not to do). Yet proceeding down, say, the permissioned blockchain route, while opening up performance, removes the anonymity and lack of a ‘principal’ that Bitcoin-like blockchains offer.
HotStuff is a further step forwards. It is part of the largely hidden research activities that enterprise IT (and businesses) do not see. Interestingly it comes from research carried out by Cornell University and UNC-Chapel Hill – and VMware Research. The latter, to Enterprise Times, is an unexpected progenitor.
Net, net: keep an eye on HotStuff. After all Facebook’s Libra uses something similar (even if Libra is likely going nowhere).