The Byzantine Generals problem was first introduced in a computer science paper published in 1982. The problem discussed in the paper is that reliable computer systems must be able to function effectively in the presence of faulty components that may send conflicting information to different parts of the system. This issue is even more acute when we talk about decentralized computer networks. Imagine the following thought experiment: The Byzantine army has surrounded an enemy city. The army is organized into several units. Each unit is commanded by a general and they all need to come up with a coordinated plan of action. However, they are located away from each other and the only means to communicate among themselves is via messages. To make things more complicated, one or more of the generals are possibly traitors. The presence of disloyal generals means that misleading messages could be sent aiming to disrupt any coordinated plan of action, be it attack or retreat. To find a successful solution to this conundrum, the Byzantine army needs to find its path to coordinated action, one way or another. To achieve this, the Byzantine army needs an algorithm that works effectively towards a coordinated outcome where the loyal generals follow it and the traitors don’t. Now that you are familiar with the problem, let’s see its solution. It is called the Byzantine Fault Tolerance algorithm.
Over the years, there have been several proposed theoretical solutions involving game theory and math. The first practical implementation of the Byzantine Fault Tolerance algorithm came with Bitcoin’s Proof-of-Work. In this case, the “generals” are nodes on the Bitcoin network, also known as “miners”. A network node is a connection point that can receive, create, store and send data across a network. In other words, nodes are the connected dots that make up a network. To simplify, think of it in the following way. In the image we traditionally use to depict a blockchain, every single computer is a separate node. They are all connected and can receive, create, store, and send data to each other. In the context of the Byzantine Fault Tolerance algorithm, the important concept to grasp is that these mining nodes start from the assumption that nobody else on the network can be trusted. Proof-of-Work secures network consensus even in the presence of non-compliant nodes.
That is, even if there are some Byzantine generals who are not acting in the army’s best interest, coordinated action can still be achieved. Let’s see how this mechanism works in Bitcoin. As we all know by now, Bitcoin is a peer-to-peer network where all activities are done by its users through appropriate software and hardware. These activities include making transactions, receiving transactions, and verifying and transmitting transactions. Now, this is where we need to introduce the concept of “mining”, which many of you have probably heard. Mining is an activity, carried out by network participants, which involves Proof-of-Work and results in generating new coins as a reward for the miner who successfully did this Proof-of-Work first for each new block. Proof-of-Work requires a hefty number of calculations done by a computer aimed at solving cryptographic hash puzzles. These are the same puzzles described earlier, enabling the network to function and to continue exchanging transaction messages with other network participants. Let’s dig into the nuts and bolts of this mechanism to figure out how it works. First, let’s see how miners create new blocks. Mining nodes collect and aggregate new transaction data. Upon receiving such data, each node independent layer flies each transaction against a long list of criteria including:
– tracking the source of the digital money being spent;
– checking for double-spending of the same money
– checking if the total transaction volume is within the allowed range of 0 to 21 million Bitcoins
And the list goes on – the Bitcoin software installed on the node performs several other checks and balances. Verified transactions are aggregated into transaction pools, also called memory pools or mem pools where they wait until they are included in a block. As miners compete to be the first to come up with a new valid block, they need to make sure the transactions in their mem pools have not already been included in previous blocks. After collecting and arranging verified transactions in a candidate block, the miner needs to construct the block header, which includes a few important components: – a summary of all the transaction data in the candidate block;- a link to the previous block in the chain also known as a parent block;- a timestamp showing the time of the creation of the block; and- a valid Proof-of-Work The summaries of what’s included in a given block are done through hash functions, which process data in such a way that results in a standardized unique identification code.
This identification code is also referred to as a digital fingerprint. In this way, the system has a unique identifier for each block of transactions. Here are some examples of block headers as viewed in the block explorer. com and blockchain. info: As you can see on top, just below the block number, there is a long alphanumeric string called Block Hash or just Hash. Alphanumeric means that it consists of both letters and numbers. This is a type of encoding data and is the output result of processing the block header data below through Bitcoin’s cryptographic hash function. You may have heard the name of this function– SHA 256, which stands for Secure Hash Algorithm. You probably remember that we mentioned and explained briefly hash functions in the section about Cryptography. We are discussing them again here because they play such an important role in Proof-of-Work. As we’ve learned, a hash function can digest any kind of data, of any size, into a fixed-length string of characters, which can serve as a unique digital fingerprint or identifier. Moreover, these cryptographic hash functions work only in one direction. Once we have the output, we cannot simply invert the function, plug in the output, and get the input data on the other end. To illustrate what it means to invert a function, consider the four basic mathematical operations: – addition and subtraction are inverse functions of each other- multiplication and division are inverse functions of each other We can always construct equations with these functions to find any unknown variable.
For example: 3 * X = 15; X = 15 / 3 = 5 Many mathematical functions can be inverted in a similar way; however, this is not the case with cryptographic hash functions. The only feasible way an unknown random variable can be found in a cryptographic function’s input data set is by trying different values for the unknown, one by one, given all the other known parameters, in order to find out what works. This is basically a brute force approach of trying potentially all possible combinations. And this is precisely the element of “work” as used in Proof-of-Work. The work comprises all the iterative computations a computer needs to do to find a solution to the cryptographic puzzle.