Bitcoin Mining - The Byzantine Generals Problem

“Mining” is how you produce new bitcoins. Mining works on the “proof-of-work” principle.  Proof-of-work, basically means this: Solving a problem must be extremely difficult, but once you solve it, proving that the solution is correct should be simple. WHY was proof-of-work was required in the first place?

One of the many problems that Nakamoto was facing was addressing the Byzantine Generals Problem.  Every digital peer-to-peer decentralized currency system failed because they failed to answer the Byzantine Generals Problem. Nakamoto was finally able to answer this using proof-of-work.

Ok so imagine that there is a group of byzantine generals and they want to attack a city. They are facing two very distinct problems:

  • The generals and their armies are very far apart so centralized authority is impossible, which makes coordinated attack very tough.

  • The city has a huge army and the only way that they can win is if they all attack at once.

In order to make successful coordination the armies on the left of the castle send a messenger to the armies on the right of the castle with a message that says “ATTACK WEDNESDAY.” However, suppose the armies on the right are not prepared for the attack and say, “NO. ATTACK FRIDAY” and send back the messenger through the city back to the armies on the left.

This is where we face a problem.

A number of things can happen to the poor messenger. He could get captured, compromised, killed and replaced with another messenger by the city. This would lead to the armies getting tampered information which may result in an uncoordinated attack and defeat.

This has clear references to blockchain as well. The chain is a huge network; how can you possibly trust them? If you were sending someone 4 Ether from your wallet, how would you know for sure that someone in the network isn’t going to tamper with it and change 4 to 40 Ether?

Satoshi Nakamoto was able to bypass the Byzantine General’s problem by inventing the proof of work protocol. This is how it works. Suppose the army on the left want to send a message called “ATTACK MONDAY” to the army on the right, they are going to follow certain steps.

  • Firstly, they will append a “nonce” to the original text. The nonce can be any random hexadecimal value.

  • After that, they hash the text appended with a nonce and see the result. Suppose, hypothetically speaking, the armies have decided to only share messages which, on hashing, gives a result which starts with 5 zeroes.

  • If the hash conditions are satisfied, they will send the messenger with the hash of the message. If not, then they will keep on changing the value of the nonce randomly until they get the desired result. This action is extremely tedious and time consuming and takes a lot of computation power.

  • If the messenger does get caught by the city and the message is tampered with, according to hash function properties, the hash itself will get drastically changed. If the generals on the right side, see that the hashed message is not starting with the required amount of 0s then they can simply call off the attack.

However, there is a possible loophole.

No hash function is 100% collision free.  Collision resistance means this: Given two different inputs A and B where H(A) and H(B) are their respective hashes, it is infeasible for H(A) to be equal to H(B). What that means is that for the most part, each input will have its own unique hash. However, in practice, no hash function is 100% collision free.

So what if the city gets the message, tampers with it and then accordingly change the nonce until they get the desired result which has the required number of 0s? This will be extremely time consuming but it is still possible. To counter this, the generals are going to use strength in numbers.

Suppose, instead of just one general on the left sending messages to one general on the right, there are 3 generals on the left who have to send a message to the ones on the right. In order to do that, they can make their own message and then hash the cumulative message and then append a nonce to the resulting hash and hash it again. This time, they want a message which starts with six 0s.

Obviously, this is going to be extremely time consuming, but this time, if the messenger does get caught by the city, the amount of time that they will take to tamper the cumulative message and then find the corresponding nonce for the hash will be infinitely more. It may even take years. So, eg. if instead of one messenger, the generals send multiple messengers, by the time the city is even halfway through the computation process they will get attacked and destroyed.

The generals on the right have it pretty easy. All they have to do is to append the message with the correct nonce that will be given to them, hash them, and see whether the hash matches or not. Hashing a string is very easy to do. That in essence is the process behind proof-of-work.

  • The process behind finding the nonce for the appropriate hash target should be extremely difficult and time consuming.

  • However, the process of checking the result to see if no malpractice has been committed should be very simple.

So, that is how miners in bitcoin implement proof-of-work to do their mining.

They use their computational power to mine for blocks by solving cryptographic puzzles. One block in bitcoin is mined every 10 mins.

18 views0 comments