In this article, we go over Proof of Work (PoW), the solution used by Bitcoin, as a consensus mechanism.
In their paper, ‘The Byzantine Generals Problem’, Leslie Lamport, Robert Shostak and Marshall Pease demonstrated how the problem could be solved assuming that at least two-thirds of the generals were loyal. However, having a majority of good actors in the network is not something that can be assumed, especially when dealing with billions of dollars’ worth of value.
Another solution proposed was that the messages sent out be unforgeable using cyclic redundancy check codes (CRC codes), which detect accidental changes to data. Using this method, data which is entered into the system gets a check value attached. This check data is based on polynomial division of the content. When the data is received, it is run through the same polynomial division, and checked if it matches. If not, it is registered as faulty. However, CRC codes were deemed inadequate, as a single Byzantine fault could present different data to different observers while appearing to be valid. (Taken from https://pdfs.semanticscholar.org/1d60/cd67863ba55589214578c0954672a279922e.pdf)
In 2009 the world was introduced to Bitcoin, which had managed to find a solution to the Byzantine Generals Problem, using a SHA-256 cryptography as a way of making the messages unforgeable.
What is SHA-256
SHA-256 was developed by the National Security Agency (NSA). It is a cryptographic hash function, which is an algorithm that takes data of any length, and produces a data output of a fixed length. It has been used to protect sensitive information, such as passwords on databases. SHA-256 is well known for collision resistance, meaning that it is unlikely that two different inputs produce the same output.
For a hash function to work, it has to be easy and quick to verify. This means that the if the output data is re-entered into the hash function, it will produce the initial data input every time instantly.
Any data changes in the original input data also has to result in a change in the output data. The smallest byte of data change in the original data has to change the output data significantly, to ensure that it is unforgeable.
These are the main features of cryptographic hashing that makes it so useful for the Proof of Work consensus mechanism.
Proof of Work
PoW is most famously used by Bitcoin as a consensus algorithm. Bitcoin’s protocol has rules about how each block of data should be like, and will reject all blocks that do not comply with the rules. There are two main parts that we will be focusing on in this article, which is the ‘mining’ of Bitcoin, and the validation of transactions. These 2 processes are linked together, and are executed by ‘miners’.
Within each block of data, there is the signature of the miner, the transactions they are validating, a reference hash to the previous block, a timestamp, a hash of the Merkle root, as well as a random number (a nonce).
Transactions: these are Bitcoin being transferred from account to account. A transaction is not on the blockchain until miners verify it
Reference Hash: This is the hash of the previous block. This ensures that the block of data is valid and not randomly created
Nonce: This is an arbitrary number added to the dat
Signature: This allows the Bitcoin protocol to determine who should be rewarded with newly minted Bitcoin
Timestamp: This indicates when the block was formed
Merkle Root: it is the hash of all the hashes of all transactions in the block. This allows a user to verify that the transaction is verified by the network
With the data arranged in the required order, the miners then run this data through the SHA-256 hash function, which becomes the next block.
Bitcoin has a hard cap of 21 million Bitcoin, which means that there will never exist more than 21 million Bitcoin in the entire world. This is something that was hard-coded into the protocol, and cannot be changed by anyone. A computer can run through hundreds of thousands, or even millions, of hashes in seconds. If it were so easy to mine Bitcoin, the supply would be exhausted in seconds, and the value would be worth almost nothing.
Anticipating this, the person(s) known as Satoshi Nakamoto built in a difficulty counter into the Bitcoin protocol, which adjusts the difficulty of mining based on computational power. As more and more computational power is added to the network, the difficulty for mining increases, and it does so by only accepting a hash that ‘looks’ a certain way. In the case of Bitcoin, there is a specific number of 0s that have to be in front of the hash for it to be a valid hash, and the difficulty increases every 2016 blocks. The difficulty is adjusted to ensure that 6 blocks are produced an hour, an average of 1 every 10 minutes.
For miners to mine a new block, their hash of transactions has to comply with the Bitcoin protocol. To get data that produces the right hash is highly unlikely. However, they are not allowed to tamper with any part of the data block, or else it would be invalid. Thus, they used a nonce to change how the block looks. The chances of success are incredibly small, as the Bitcoin protocol dictates that the block has to start with upwards of 17 0s at time of writing.
To get the hash of the next block, it requires a miner to expend considerable computational power and generate billions and billions of hashes to find one that fits the criteria. This is where the term ‘Proof of Work’ is coined: there is no shortcut to finding the next hash other than using brute force computing to trial and error the nonce till something fits, and all miners are racing to find this block. If the block is found, all previous trials and errors become useless; the miners now race to find the next block to build on top of it. This directly translates into electricity being used up, as their hardware is constantly burning up power to perform these calculations in attempt to be the first to find the new block.
On the rare occasion that two blocks are found at the same time, it now becomes a race to see who can propagate their block faster through the network.
Alice and Bob both find a hash suitable for block 1000 at approximately the same time. This block is uploaded to the network, and other miners begin to work on the subsequent block based on one of their blocks. Alice’s block has 100 miners working on finding the next block (team Alice), while Bob has 10 miners who are working on his block (team Bob). Block 1001 is found 10 minutes later using Alice’s block. This is now the longest chain in the blockchain, and Bob’s block is orphaned (discarded). Everyone who was working on Bob’s block now has to rush to find block 1002 based on Alice’s block.
Mining is a constant race to find the next valid block on the longest chain, and this is a process that takes up a tremendous amount of power.
Miners are therefore paid for their services with newly minted coin that have never existed before; hence the name mining. In the process, they perform a vital function of verifying transactions.
How does PoW solve the Byzantine Generals Problem?
The Bitcoin protocol has a specific requirement for the blocks, which makes each block difficult to produce. For a bad actor to do so, he/she would have to expend considerable resources to find a valid block. If the information inside does not comply with the Bitcoin protocol, it is discarded as invalid, and the energy would have been wasted. More importantly, there is a whole network of actors who are also racing to find the same block, which gives the bad actor a very small window.
The blockchain is also linked all the way back to the Genesis block, the very first block in the blockchain, and it can be checked easily to see if it is valid. This means that for someone to change the information of a block, he/she would have to change the information in all blocks after it before the next block is found. The only chance of that happening would be if the bad actors controlled 51% of all computational power in the network, something that is improbably.
Proof of Work was the benchmark for consensus mechanisms in blockchains. By making an actor sacrifice real-world resources, they are strongly disincentived from being a bad actor, and would benefit from being a good actor.
More importantly, PoW helps to give a tangible value to an otherwise intangible asset. The energy expended on finding the next block is something that can be calculated, and is therefore, at the very least, worth something in the real world.