Distributed Consensus and the Byzantine Generals Problem

July 7, 2020 inThoughtby Findora

This article is the second part in our series on consensus. In the first part, we covered the need for decentralized consensus. Now we will discuss classical vs. probabilistic consensus and some of Findora’s innovations.

As we discussed in the previous installment, consensus is an evolving area of research. For a distributed network to be reliable it needs to be able to handle components that give conflicting information to different parts of the system. Achieving this reliability is done through consensus protocols.

So far, most research has focused on two primary consensus methods: classical consensus algorithms, including so-called byzantine-fault tolerant algorithms (BFT), and probabilistic consensus algorithms, such as Bitcoin’s consensus protocol.

The Byzantine Generals Problem

Instead of a computer system trying to reach consensus, consider the following analogy:

During one of the many wars fought by the Byzantine empire, several army divisions lay siege to a city. The generals need to stay at their posts and can only communicate by messenger. The generals now need to agree on whether to attack or retreat. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching an agreement.

To safely proceed, the generals need to figure out a method to guarantee that the loyal generals decide upon the same plan of action. At the same time, they need to ensure that a small number of traitors can’t cause the loyal generals to adopt an evil plan. This is known as the Byzantine Generals Problem. Simply put, a commanding general must send an order to his lieutenant generals such that:

  1. All loyal lieutenants obey the same order.
  2. If the commanding general is loyal, then every lieutenant obeys the order he sends.

Early in the war, the tacticians hadn’t given much consideration to traitors amongst the high ranking generals. Because of this, they only sent three generals to command their army during this siege. As it turns out, with only three generals present, if one turns traitorous and starts sending conflicting commands, it’s impossible to find who the traitor is and reach consensus.

As we can see in the diagrams, if one of the lieutenants is a traitor, then the other lieutenant has no way of knowing if he’s lying or if the commander sent conflicting commands to both lieutenants. Likewise, if the commander is a traitor and sends two conflicting messages, the lieutenants have no way of knowing whether the other lieutenant is lying about the command he received or not.

Let’s imagine that in this particular siege the commander-general happens to be the traitor. The honest lieutenants follow his commands. The army ends up losing one of their divisions that attacked on its own while the other two divisions retreated under orders of the traitorous commander. Sadly there is no way for the final lieutenant to prove whether the commander was a traitor or if the attacking lieutenant went rogue.

Finding solutions

Word of the failed siege reached back to the Byzantine homefront. The Byzantine tacticians now had to figure out a way to reach consensus among their army divisions despite potential traitors amongst the generals.

The solution they came up with was simply requiring four or more generals to be present. In this scenario, we can reach consensus if the majority of generals are honest under the following assumptions:

  1. Every message is delivered correctly
  2. The receiver of a message knows who sent it
  3. The absence of a message can be detected.

A traitorous commander may decide not to send any order. Since the lieutenants need to obey some order, by default, they will retreat if no order is given within a certain timeframe.

We can see two possible scenarios in the diagrams above. In the case of a single rogue lieutenant, we can easily single him out and reach consensus. Since every lieutenant receives the attack command from a majority of generals, we know that the lieutenant saying ‘retreat’ is a liar. If it turns out that the commander is a traitor, we can also easily figure this out. Each lieutenant can independently discover the orders received by their fellow lieutenants. This way, they can figure out if the commander is giving opposing commands and is, therefore, a traitor. In either of the scenarios, the corrupt party will be ousted, and consensus can be achieved.

Classical consensus algorithms are focused on this type of problem. This is why they are also called Byzantine-fault tolerant algorithms.

Consensus protocol participation

BFT protocols were initially designed for a fixed set of generals, and are therefore sometimes called permissioned consensus. In a blockchain setting, we don’t deal with generals at war requiring a safe plan of attack. However, it’s easy to draw comparisons to a blockchain system. We can imagine the Byzantine generals not agreeing on a plan of attack but instead voting on valid transactions to be added to the blockchain. Our Byzantine generals are now validators for our blockchain, together they collectively propose, ratify, and ultimately reach agreement on the valid set of transactions to be included in the next block. So long as fewer than 1/3 of the validators are traitors who lie about the validity of transactions, such a blockchain will continue to function and achieve finality, a state that can’t be altered in the future.

Because the validator set is fixed, permissioned BFT is appropriate for a blockchain operated by a consortium of predetermined validators. In this setting, the system is secure if the consortium is chosen well such that less than ⅓ of the validators would turn out to be traitors. For a decentralized blockchain, this introduces some problems however. First, it requires a validator selection process such that every user around the world trusts ⅔ of the validators. Beyond that, it greatly limits the inclusivity of the system.

Nowadays, consensus protocols allow for more flexible validator sets. One such protocol is federated Byzantine agreement (FBA). In FBA, each validator creates a quorum, which is the validator’s own trust circle. In a classical BFT protocol, this quorum would strictly be made up of ⅔ of the validator set. However, in FBA, a validator can set the quorum itself, e.g., ½ of a US bank consortium or ⅔ of an international bank consortium. This type of consensus works as long as validators make wise trust choices and there is sufficient intersection among trust circles.

Many cryptocurrencies employ a different type of consensus, sometimes referred to as probabilistic consensus. The name derives from the fact that these consensus methods never reach true finality; they can only make it harder to change a historical state. Rather than a set of validators coming to an agreement, many parties will compete in a round. Based on some resources they hold, one participant will be chosen to put forward the current state of the system. In Bitcoin, this is done through proof-of-work. In PoW, the resource is processing power. If a participant has more processing power, they will have higher odds to find the correct hash and thus be chosen to create the next block. Proof-of-stake methods achieve a similar method of consensus at a high level, but change the resource from processing power to stake held in the system. These types of consensus are akin to a lottery: we can think of these resources as lottery tickets: the more you own, the greater your chances of winning.

Incentive compatibility

The security of these lottery-like systems relies on the assumption that the majority of those in control of the necessary resources are honest. To ensure the security in a blockchain setting, the block creator is generally awarded some form of compensation. For example, in Bitcoin, you would get all the transaction fees included in your block and an additional block reward, newly minted Bitcoin included in every new block. It is reasoned that providing sufficient incentives will keep the majority of validators honest, as being dishonest would work against one’s financial interests.

This incentive compatibility comes into question when considering what happens if the potential gain of a malicious action were to far exceed the reward for being honest. This is particularly a concern if the consensus network is used for managing assets beyond just a native currency, which derive their value externally. For this reason, pure incentive-backed consensus is not compatible with managing $100+ trillion of assets held in securities and traded in the world’s capital markets.

It is also important to realize that a blockchain for recording ownership of external assets has a different significance than a blockchain used only for native assets, e.g., Bitcoin. A fork in the Bitcoin network would create different Bitcoin versions such as Bitcoin and Bitcoin Cash. In contrast, real-world assets such as real estate or company stock, for example, depend on external entities for enforcement. A blockchain provides compelling evidence of ownership, but a judge wouldn’t evict someone over a fraudulent transaction involving a representation of his house on the blockchain. From this perspective, a malicious operator will more likely suffer from the loss of integrity than successfully stealing a house over the blockchain.

For these reasons, many existing public blockchain consensus protocols are not ideal for dealing with real-world transactional systems and asset representations. Findora endeavors to build a public transactional infrastructure which is not only suitable for natively digital assets, but also efficient representation and transfer of real-world assets. As such, Findora’s consensus protocol Finsense will integrate elements from proof-of-stake and FBA networks, thus creating a network that is well suited for hosting any asset, even those far exceeding the monetary value of any on-chain compensation.