Neo's Consensus Protocol: How Delegated Byzantine Fault Tolerance Works

In Part 1 and Part 2 of our series on the Neo Smart Economy we gave a broad overview of how the Chinese blockchain platform works and discussed some of the economics behind the coin.  Today we shift our focus to Neo’s proposed Consensus Mechanism.

The Byzantine Generals’ Problem 

The best known consensus mechanisms are Proof of Work (e.g. Bitcoin) and Proof of Stake (e.g. NXT).  Neo proposes an improvement by using Delegated Byzantine Fault Tolerance (dBFT) as its consensus mechanism.  Since dBFT is a new protocol this has led many people to question how it works and why it is an improvement over other consensus mechanisms.  The updated Neo whitepaper, Neo documentation site, and DBFT Whitepaper provide the framework for Neo’s dBFT model if you want to read more.

The Byzantine Generals’ Problem (original paper) occurs anytime we try to determine the TRUE outcome of a vote.  Imagine 9 Generals for the Byzantine empire have encircled the city of Rome with their armies.  In order to successfully take Rome the generals must attack or strategically retreat in unison.  If any general acts opposite the consensus decision then the armies will be routed and defeated.  The decision to attack or retreat is put to a daily vote and whichever option receives >50% of the vote is what the generals agree to do.  Since each General is commanding their army in separate geographic locations around the city they utilize courier’s to carry their vote to the other generals.

This system has inherent flaws.  First, any number of the Byzantine Generals could be bribed by the Romans to betray the Byzantine army, these would be Traitorous Generals.  Second, any general cold make an inappropriate decision as to whether they should attack or retreat, these are Improperly Functioning Generals.  Third, the couriers carrying the votes of the generals could be bribed by the Romans to alter the votes in a traitorous way.  And fourth, the couriers could fail to deliver their message or deliver the wrong message.

The Byzantine Generals’ scenario is an analogy for the problem faced by distributed computing systems: How do we reach consensus when faced with untrustworthy  and malfunctioning actors that threaten to destabilize the ecosystem?

Delegated Byzantine Fault Tolerance

Numerous protocols have been developed to solve the Byzantine Generals’ Problem.  Hyperledger, for instance, uses Practical Byzantine Fault Tolerance in its Proof of Work algorithm.  Neo, on the other hand, implements Delegated Byzantine Fault Tolerance to solve the Byzantine Generals’ Problem.  The Neo creators chose this protocol because it should allow for better scaling and performance when compared to currently existing solutions.

Scalability is a major issue for any blockchain.  As the number of transactions and network size increase, the blockchain must be able to scale proportionally.  If it cannot scale with demand then transactions will be delayed or never processed at all.  We see this issue currently with the Bitcoin scaling debate and SegWit2x that threaten to fork the blockchain.

To explain how dBFT works we will use a simplified analogy as follows.  There is a country called Neo.  Every citizen in the country is given the right to vote on who will be their leader, also called a delegate.  The delegates make the laws of the country.  If the citizens disagree with how a delegate voted on a law then they can vote for a different delegate next time.Citizens then tell all of the delegates what will make them happiest.  Every delegate must keep track of the demands of all of the citizens and document it on a ledger.  These demands will be added up to pass laws aimed at making the citizens happy.

When it is time to pass a law a Speaker is randomly assigned from the group of delegates.  The Speaker then proposes the law based off of the demands of the citizens.  In the speaker’s proposed law he calculates how the law will affect the country’s Happiness Number (a measure of how happy they are).  Next, the speaker individually hands out to the delegates his proposed law.  The delegates then decide if the Speaker’s calculation matches their own and confer with the other delegates to verify the calculated Happiness Number is correct.  If 66% percent of the delegates agree that the Speaker’s calculated Happiness Number is correct then the Law passes and is finalized.

Figure 1: All nodes acting honestly with 100% Consensus.  Law A (the block) will be verified.

If less than 66% of the delegates are in agreement then a new Speaker is randomly selected and the process starts over.  This system is designed to protect against traitors/evil-doers and dysfunctional leaders (i.e. leaders who aren’t malicious but simply have trouble calculating the Happiness value).

 Applying this analogy to the Neo blockchain, anyone owning Neo is a citizen.  The majority of Neo holders are Ordinary Nodes that can only transfer or exchange assets.  Like citizens in the country of Neo, they do not participate in block validation.  Delegates represent Bookkeeping Nodes in the Neo Economy.  Bookkeeping Nodes verify each block written to the blockchain.  To become a Bookkeeping Node certain requirements must be met, such as special equipment, dedicated internet connections, and a certain of amount of GAS (1,000 at the time of writing).  We will discuss how to become a Bookkeeping Node in another post.

The demands of the citizens are the transactions made by Neo holders.  The law represents the current block in the blockchain and the Happiness Number is the hash of the current block. Now let’s look at how the system protects itself.

The Dishonest Speaker

There is always a chance the Speaker, who is randomly selected from the Delegates, could be dishonest or malfunctions.  In the following example the Speaker sends a malicious message (Law B) to 2 of the 3 Delegates and an accurate message (Law A) to 1 Delegate.

Figure 2: The dishonest Speaker sends an accurate message (A) to the Left Node but sends a malicious message (B) to the Middle and Right Nodes.

In this scenario the law proposal will be rejected.  The Middle Delegate and the Right Delegate will not calculate the same Happiness Number as the one was proposed by the Speaker’s communication and cannot verify the Speaker’s law, resulting in 2 rejections of the law.  The Left Delegate, who was sent the accurate law, would confirm the Happiness Number sent by the speaker resulting in 1 verification of the law.  This proposal would be rejected because it did not receive 66% consensus (2 votes needed) and a new Speaker would be randomly chosen, starting the process all over again.

The Dishonest Delegate

In this situation the Speaker is honest and one of the Delegates is misbehaving.

Image 3: The Right Delegate sends incorrect messages (B) to the other Delegates.

This would lead to validation of Law A proposed by the Speaker.  The Honest Delegates (Left  and Middle) would be able to verify the Honest Speaker’s proposed Law A and thus achieve 66% consensus.  The Delegates could also determine that either the Speaker lied to the Right Node or that the Right Node was dishonest.It is not clear at this time, but it is likely that data about the honesty/functioning of each Delegate will be available for Citizens to review.  This will guide voters’ decisions about which Delegate is the most trustworthy and, by extension, who to vote for.

More to Come

Neo is still developing their Delegated Byzantine Fault Tolerance protocol.  This article is meant to describe the protocol in simplified terms while leaving out many proposed complexities.  Also, because dBFT and the Neo blockchain are still being developed, many aspects of how this protocol will work on the Neo blockchain are not yet known.  Very soon we will discuss how to become a Bookkeeping Node in the Neo Economy as well as pose some important questions we hope get answered by the Neo Development Team.
 

 Tip Jar

Bitcoin - 1CFSxj1dy4a9B4ZYwvDmdds8zB3unNSW2t

Litecoin - LZxBp3QAZ2SDheN8FaRVHg4nuWPnWAQSdP

Ethereum - 0x009561fC7CF8656c53EB0874c601DC359E40f76f

NEO - ANwvg4giWPxrZeJtR3ro9TJf4dUHk5wjKe

Dash - XkAGSD83Mb9TD4whTeJ6SQawBh56WjwUEM

Ripple - rEfV4j3Jhzj1BW8948ePHTPEnqCf9cxt7w

IOTA - YMPFQWXQYHT9DDJVGDGY9SNCSB9F999UDAVWLGXGEIBPHUXJYHQDVWMFFWCTSUTMIUDFNQIBUTQUJGSWZCKMHUOKTB