Blockchain as A Byzantine Consensus Problem
Bitcoin (1 BTC ~1023 USD) is a cryptocurrency and a payment system that has gained momentum over the past few years in technology and banking sectors and has the potential to power organisations in the near future. Blockchain is the technology driving Bitcoins. Blockchain essentially is a ledger of digital records stored in a chain of units called blocks. This ledger is primarily a database that is agreed upon by various node in the network. This distributed database is synchronised, replicated and shared over multiple sites in different countries.
Blockchain provides a solution to the Byzantine General’s problem. The problem is as follows:
Several Army battalions surround a castle in the hope of attacking it. A general leads each battalion and there is a lead general. The attack is successful only if all the battalions attack at the same time. These battalions are surrounding the castle, hence there is no centralised command. The generals must send messages to other battalions to specify the attack time. Some of the generals might be traitors and will not obey the commands or the messages might get corrupted. So the questions arises how to send messages that cannot be tampered with and find out who the traitors are in order to lead a successful attack?
Comparing the Byzantine General’s Problem to that of Blockchain. Every update (messages) to the distributed ledger (time of attack) must the trusted. In a network, there are millions of nodes (generals) distributed over various locations. It is not possible for every node to verify the authenticity of every other node. So how do you make sure that the incoming updates to the ledger is authentic and at the same time make sure that the information in the ledger is not corrupted?
Blockchain solves this problem (in this case Byzantine General’s Problem). Consider the case where Person A has to pay 1 BTC to Person B. A’s bitcoin wallet tell the ledger record this transaction. For this transaction to take place, every node in the network examine the existing ledger to verify the legitimacy of the transaction (whether A has the sufficient funds or not). Once a node verifies the legitimacy it becomes part of a queue and the next potential block for the block chain. For this transaction to be added to the ledger Nodes (called miners) try to solve a problem known as “proof of work”. Once a node solves the problem, it sends the solution for verification. If the solution is verified, the transaction is added to the blockchain. Every block has to be approved by the nodes in the network, the ledger is a chain of these blocks, hence the ledger as a whole is also trusted. The blockchain reaches consensus through cryptographic hashing of transactions and the “proof of work validation”. The objective of the miners is to find a value (called nonce) that produces a similar hash under the bitcoin protocol. This is done through trial and error and takes up a lot of computation power. Nodes usually compete with each other to calculate nonce and the wining is incentivized. This makes blockchain nearly unhackable. Despite several tries the ledger has never been hacked.
As discussed “proof of work” requires a lot of computational resources. Bitcoin rewards the nodes that do these computations with its own bitcoins. Blockchain would not be as effective there was not incentives for nodes for doing the computation. Another issue would be that since a lot of computational power is required, the cost of running specialised hardware could be more than the reward that is being gained. There have been other algorithms that require less computation but are not as secure the current algorithms.
In conclusion Blockchain has provided a method to tackle the Byzantine General’s Problem. This is not application specific and be used for various application other than Bitcoins. It removes the need for a centralised node to authenticate and update the ledger. It works to distribute this over various nodes in the network where any node can authenticate updates to the ledger.
More about “proof of work”: http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/
Interesting article by Marc Andeerssen: https://mobile.nytimes.com/blogs/dealbook/2014/01/21/why-bitcoin-matters/