Reading Time: 6 minutes

What is Proof of Work and how does this solve the Byzantine General’s Problem?

As we saw in our original attempt to solve the Byzantine General’s Problem, simply encrypting the messages would not be sufficient to prevent a bad actor from being able to tamper with it. Simply having the generals using a hash that matches the message as a way to guarantee the authenticity of the message is not good enough.

One way to solve the problem is to change the way the all generals reach consensus about the authenticity of the original message by agreeing to a modification to the original message such that it produces a very specific type of hash. Only a message, where the modification to the message results in an agreed type of hash, will ever be regarded as authentic. This is a very different problem to solve.

The traitors will no longer be running a trivial hash function to create a hash that matches their fraudulent message. Instead, they need to determine how their message needs to be changed to yield a hash that is acceptable to the other generals!

As will be shown below, this can be exceedingly difficult to determine.

Adding a nonce (number used once)

The way Bitcoin tackles this is by allowing for an additional variable, called a nonce, which is added to the contents of the block header:

Field Description
Version The version of the block, which indicates which set of block validation rules to follow.
Previous Block Hash The SHA256(SHA256()) hash value of the previous block’s header that this block is being built on top of. No previous block can be changed without also changing this block’s header.
Merkle Root The SHA256(SHA256()) Merkle root that is derived from the hashes of all transactions included in this block. None of those transactions can be modified without modifying the header.
Time When a miner is trying to mine this block, the Unix Epoch time at which this block header is being hashed is noted within the block header itself.
Bits The calculated difficulty target being used for this block
Nonce The field that miners change in order to try and get a hash of the block header that is below the Target.

Mining

Every time this nonce is changed, the hash process will yield a different hash value. Bitcoin nodes (analogous to the generals and the city) would now need to determine what value this nonce needs to be in order for the hash of the message (which includes the nonce) to meet the consensus requirements as agreed to by the generals. The process of finding this nonce is what is referred to as ‘mining’.

Nodes are iteratively calculating hashes, looping through many possible numbers until they find the right nonce because it cannot be calculated (recall that the hash function is a one-way function – it does not have an inverse). All nodes agree to what the requirements of this hash needs to be. This is constant and fundamental to the communications protocol that they abide by. This will always be the means by which everyone reaches a consensus on the authenticity of the messages.

The process of finding this nonce can be thought of as ‘mining’ for the right number…

Nodes are iteratively calculating hashes, looping through many possible numbers until they find the right nonce because it cannot be calculated…

Illustration

As an illustration, suppose the agreement between the generals is that the hash of the modified messages always begins with 04B0EB to be recognized as authentic. The generals and the city would therefore have to determine what the message/nonce combination needs to be in order to yield a hash beginning with 04B0EB. In the case of the previous message, it would have to be “Attack Monday. 9am 12345”.

The nonce value of 12345 is not trivial to compute. You literally have to calculate the hash for all possible combinations by looping through many possible numbers until you generate a hash beginning with 04B0EB. This requires considerably more computing power! Finding and revealing this nonce is proof that work (computational energy was expended) was done to modify the message appropriately. Hence the term Proof of Work.

Therefore, if the city had to tamper with the attack message, it would not only have to change the message but also recalculate a nonce that will give the fraudulent message the hash that the generals have agreed to. To take this further, the generals can build into their communications protocol a means by which to increase (or decrease) the difficulty of this hashing process to cater for the city beefing up its computing power.

Message authenticity now relies on the balance of computing power

Let’s imagine now instead of two armies on each side of the city we have many armies, and that attack instructions are grouped into blocks. All generals have to use computing power to find the nonce for a block of instructions that will yield an acceptable hash value for the block. We now have a way to make it practically impossible for the city to tamper with the blocks and find a valid nonce before the other generals unless it has a colossal amount of computing power that is similar to or greater than the combined computing power of honest generals.

This is the Bitcoin solution to the Byzantine General’s Problem. This mechanism for reaching consensus on the validity of transactions is called Proof of Work. Furthermore, the more generals that use this system of consensus, the more secure or tamper-proof the entire system becomes. The power is in the numbers. The similarities to the Bitcoin network is illustrated below:

The challenges presented in the Byzantine Generals’ Problem are the same challenges that exist in the case of distributed computing systems. There is a risk that a distributed system will contain bad actors that can undermine the integrity of the system. These bad actors may fail to pass on data or even send inaccurate data to other participants in the network.

The Byzantine Generals’ Problem is particularly challenging to a public blockchain (more on public and private blockchains can be found here) because there is no central authority to remedy any wrongs in the event of a Byzantine failure. Bitcoin extends the above solution by combining a consensus mechanism (Proof of Work) with incentives in order to provide a robust and sustainable solution to the Byzantine Generals’ Problem. Next: The Bitcoin blockchain and Proof of Work