BLOG

Byzantine Fault Tolerance in Blockchain Part 1

by Sysco LABS Articles 2 September 2019

Written By: Isham Mohamed – Sysco LABS EAG R&D Team 

Blockchain. Unless you’ve been living under a virtual rock, this is almost certainly a technology you’ve at least heard of as of late. Even so, it’s a good idea to start at the top.  

The most famous implementation of Blockchain was the BitcoinA virtual currency that shook the traditional foundation of money. All of this started after the creator of Blockchain, Satoshi Nakamoto, wrote a white paper about the Bitcoin, which you can find here: Bitcoin: A Peer-to-Peer Electronic Cash System. Before the bitcoin, there was no concept of the blockchain. So, if you’re a beginner, I strongly recommend your starting point be the white paper. 

As of writing, the value of a bitcoin is $3847.23! Why it is so valuable? Well, because it is computationally impossible to cheat the Blockchain.  

The main objective of this article is to give you an insight on what the threads in a blockchain network are, and how they overcome it especially bitcoin.  

Let’s start with the Byzantine Generals problem. With a modern twist 

 

A number of Byzantine Generals are going to attack a city from multiple directions. The city is strong enough to withstand an attack by individual armiesAttacking the city at the same time is the only way to capture it. Each of the generals will announce a time to attack. Since there isn’t a commanding general, all generals must agree on the earliest attack time proposed”  

In this situation, it doesn’t matter when they attack, the only requirement is to attack at once. This way they have enough power to defeat the city. At first glance, the protocol seems to work fine, but there is one catch though. Not all the generals are loyal!  

 

There can be a situation when a traitor general sets the attack time as 1 to one set of generals and 6 to the others. For the sake of clarity, the illustration above only shows the messages sent from the faulty node. Based on the protocol the generals are supposed to follow, E and D would attack at 2, while B and C would attack at 1.  

In general, fault tolerance deals with node failures such as VM, OSPower, or any hardware failures. But having a Byzantine fault tolerance in a distributed system is the hardest.  

A peer to peer system is already built upon uncertainty. There is no central control, and the threat of malicious nodes are high.  

The concept of “Consensus in a peer to peer system, is taking the final decision as a system. In our generals’ example, it’s the attack time T. It’s not sufficient that everyone knows T. We also need everyone to know that everyone knows T, and that everyone knows that everyone knows that everyone knows T!! 

This is the Byzantine Fault Tolerance (BFT) in a nutshell. 

 

So, in the above problem lets assume only one general is traitor. To archive BFT we can simply send the messages we received from every other node to every other node. At the end of the second cycle, each node will have all the messages that each of them received in the previous roundBy looking at those set of messages, a node can easily tell that the faulty node is A, since the messages from A are the only contradictory messages. It can be proven that if we have F faulty nodes, by having F+1 rounds we can identify all the faulty nodes. At last a solution!  

But this isn’t a perfect solution. There are problems in this approach as well,  

1) We don’t know F.  

2) We can’t afford to send so many messages in a peer to peer system. Modern blockchain systems use various techniques to archive complete and partial BFT 

One such critical system is Bitcoin. In Bitcoin, there can be many malicious nodes trying to fool the others, similar to the general’s problem. All nodes must agree to an identical chain, and all nodes should trust that all other nodes have the same chain. 

Before we look into how blockchains solve these issueswe should look at what can go wrong in a blockchain application. We know that blockchain applications use asynchronous key cryptography to authenticate transactions, but what does that actually mean 

It means only Bob can spend Bob’s money and every other node can verify it in the case of Bitcoin. This makes it impossible for someone to spend Bob’s money unless his private key is compromised. Because of the difficulty in doing this, what someone can hope to do is to spend their money twice. This is called the double spending problem.  

Simply put, give the bitcoin to someone, get the real world benefit out of it and delete the transaction. This is what’s meant by cheating a blockchain.  

With that said, now we understand the Byzantine General’s problem, and a naïve solution for systems with bounded faults. We have also related the Byzantine Generals problem with blockchain and the need for solving it with a different approach.  

In the next part, we will look into the basic structure of a blockchain and the rationalities behind the proof of concept algorithm used in Bitcoin to archive consensus. 

References  

Bitcoin: A Peer-to-Peer Electronic Cash System
Satoshi Nakamoto’s original paper is still recommended reading for anyone studying how Bitcoin works. Choose which…bitcoin.org 

Emails | Satoshi Nakamoto Institute
Edit descriptionsatoshi.nakamotoinstitute.org 

Leave a Comment

Tags