Blockchains simplified
Byzantine Generals Problem.
In a paper by Lamport et. al., the authors introduce the Byzantine generals problem by posing the following question.
A Byzantine army has now encircled a city and has multiple generals stationed at different points on the circumference. Each of these generals lead a battalion. The decision to be made is whether the army as a whole should attack or retreat. A lapse in coordination means a defeat of the army. That is, if some generals attack, while some retreat — it would lead to the Byzantine army losing the battle. The generals should decide among themselves whether to attack or retreat.
How should a general decide to attack or retreat with the battalion of his/hers?
Simple! Every general sends out a messenger to every other general saying whether or not he/she thinks they all should attack. Once he/she gets the message from every other general, act based on majority vote.
The catch in the story is that some of the generals are traitors. The messenger could forge the votes too.
If there are five generals 2 saying attack, 2 saying retreat — the 5th traitor general could send “attack” to the ones saying retreat and “retreat” to the ones saying attack. This leads to a half hearted attack, and the army falls.
Relevance to Computer Science
This problem in which the Generals are replaced with nodes (computers) and the messengers with links (wires) lays foundation for the Byzantine Fault Tolerance. A Byzantine fault tolerant network is one that is able to take a decision inspite of non-tamper proof links and nodes trying to manipulate the output of the network. Some simple solutions to make a network fault tolerant may be seen here.
This is a long standing problem in Computer Science, and a crucial missing part for truly distributed networks.
A paper was published under the authors’ pseudonym Satoshi Nakamoto, which incorporates game theory and cryptography to overcome the Byzantine Failure.
The system developed was called Blockchain and its first practical implementation — Bitcoin. The way to overcome the Byzantine Failure which Bitcoin uses is called Proof-of-Work, which we will discuss further down.
Satoshi Nakamoto owns 1Million Bitcoins and has never transacted or withdrawn any of those till date!
Blockchain
A blockchain is a public ledger, a publicly available record of all transactions. Think of transactions as some activity that happens on the Blockchain network. A transaction could be a payment (Bitcoin), someone storing a file (IPFS — Interplanetary file system), someone sending a message and so on. The blockchain is one huge list of all possible transactions on the blockchain network.
The Bitcoin blockchain which consists of information about who paid whom and how much, grows by 1MB every 3 seconds. That is 1TB per year! All the transactions on the blockchain are stored in small subparts called blocks. Each block has a few lines of transactions. The number of lines may be limited by a maximum value or quantized in time.
Every block has a reference to the block that preceded it, thereby forming a chain. Hence the name “Blockchain”.
At every stage, transactions are written to a new block only after all the blocks upto the last block are validated to be true by the network. A valid block is a block where all transactions mentioned in the block are true. Hence, to verify if the entire ledger is in a correct state, it is enough to verify if the last block is correct, because it is known that the entire ledger upto the previous block (referenced to by the previous pointer) is verified. No alterations can be made to any block in the history, for all practical purposes. And, the process of block validation is non-trivial — infact, NP Hard. NP Hard is a problem that takes a lot of time to solve, but once a solution is found, it is easy to verify that the solution is correct.
Alex Rampell has an interesting explanation using a die-roll. Imagine everyone who is trying to validate a block gets twodice to roll. A block is said to be validated if the dice roll produces two 6s. The only way to get two 6s is to keep trying to roll continuously. The faster you are able to roll, more the probability that you get two 6s. But once you get two 6s, it is easy to verify that you indeed got two 6s (by just looking at them).
The best way for the computers to win a block is to try to do the validation by doing an equivalent of die rolls as fast as they can, which practically means more computation power and electricity. Side note, this is true only for proof-of-work which is what Bitcoin uses.
The incentive for validating a block the fastest is that you get incentivized in crypto currency. For validating a block on Bitcoin, the node gets 12.5 BTC at the time of this writing.
I know this is confusing, the following interactive examples might serve some help :)
Block
As mentioned above, a block is a sub set of the entire ledger. It has a few transactions’ information stored on it. A block contains
- Some data, i.e. the list of transactions
- A magic number called Nonce. The Nonce doesn’t have any value of its own.
- A hash.
The block chain network sets a rule that all the hash-es of valid blocks should start with a fixed number of zeros. In the following example, the number of preceding zeros in the hash is 4. Bitcoin currently uses 18 zeros. To make the block valid, we need to find a Nonce that when concatenated with data, produces the hash with the required number of zeros. Try adding some data in the following widget. You will see that the background turns red, meaning the block is invalid. Try finding a new nonce by clicking on mine. The process of finding these nonce is called mining. After a successful mining, you’ll notice that the nonce has changed, and a new hash has been created with the required number of zeros in the start.
If you tried out the widget, you’ll notice it takes time to compute the nonce (computationally intensive). Finding the nonce is atleast NP-Hard. Meaning it is very difficult to find a nonce that is valid, but very easy to verify once a nonce is found. There is no algorithm that can find such a nonce, except trying nonces randomly. Once a node finds a nonce, it broadcasts the nonce to all other nodes, who can very easily see that the nonce has been found, and mark that block as verified. To verify, a node has to take the nonce broadcasted, and concatenate it with the data and see if the hash matches the required zeros criteria. Calculating the hash is an easy and computationally fast task. The fact that the nonce has been found can be used as a fair way to say that the computer that found it actually spent computational power (work) — i.e. to randomly try enough number of nonces. To compensate for the money spent in form of electricity bills, the miner is rewarded with a token/coin. Ofcourse, the fact that the coins were awarded is also stored on the blockchain. This form of verification of blocks is called Proof of Work (PoW). There are other forms too, which we’ll see soon.
Here is what an actual bitcoin block looks like.
Blockchain
We mentioned earlier that every block has a previous reference. This forms the block chain.
Check out a blockchain example here
If you change the data or any other value in any of the blocks, all the subsequent blocks become invalid.
This is because, when you change the data of one block, its hash value changes. The next block uses the hash new hash value to refer to the block whose data you changed. So the nonce which was calculated for the previous data+previous pair, now is invalid. The same logic propagates.
To make a hard fork, you will have to mine all the blocks after the block from where you made the fork (where you made the change). This is what ensures that a transaction once recorded on the blockchain cannot be changed. This is called immutability of the blockchain.
Verification
Every node on the network maintains a blockchain record of its own. There might be multiple versions of a block chain. Some fraudulent node may make a valid block with an incorrect transaction in it.
This means that the no other node except the fraudulent node will have this incorrect block.
When there is a mismatch in block content, the network votes. Every node will pick the chain that atleast 51% of the other nodes say is correct, and take up that chain and forcing a fork. Every node broadcasts which nonce it accepted.
Once a node recieves a nonce from some other node, it is best for it to stop trying the nonces and verify the nonce it has recieved. This is because, if the nonce is correct, it doesn’t make sense for the node to find another nonce. Every node will (usually) accept only the first nonce it recieves.
There can be more than one nonces that can satisfy the condition of correctness. If multiple nodes find a nonce which are all different at the same time without any fraud, the network will accept the one that the maximum number of nodes accept, when each node broadcasts which nonce it accepted. In this case, the node whose nonce is accepted is awarded some coins, and as consolation, all the nodes that found a correct nonce in a sufficiently close time interval will be awarded some coins too (lesser than the one which was accepted).
This means that the blockchain will be correct as long as atleast 51% of the nodes are honest.
Bitcoin
The first commercial use of a blockchain was the Bitcoin.
The data stored on a block in a bitcoin network are financial transactions saying who paid whom how much.
Whenever someone mines a block (finds a nonce), they are rewarded a few bitcoins agreed upon by the network. This is rewarded through something called coinbase (do not confuse with the company name) — a transaction is made from “coinbase” to the miner. This money invented out of thin air, and accepted to be a valid transaction by the network. To validate any transaction in the current block, the miner has to see whether for each of the transactions, the payee has enough balance to make the transaction. Since all the transactions in the history of bitcoin is accessible to all, it is possible to do this verification.
In every other way, bitcoin is just a form of blockchain.
Mining Bitcoin
Mining Bitcoin (or for that matter Ethers or Litecoin) has gathered a lot of attention. A lot of people around the world run super large clusters to perform this mining. Each computer is a node in the network, a cluster may be registered as multiple nodes on the bitcoin network.
If you want to mine on your computer you can do so too. It just not worth it anymore on commodity hardware. The process of mining is highly parallelizable. A CPU, with usually 2–4 cores can only parallelize computation only so much. People soon started using GPUs to do the mining — a GPU may have 1000s of cores. But the amount of Bitcoins you’d make using GPUs too is now will be less than the amount of money you spend on electricity for running the mining. A GPU powered by an Nvidia K80 GPU will be able to generate about 1 million hashes per second. People now use ASICs — specially designed for mining bitcoins — which can generate 1000000 Million hashes per second.
How can I own Bitcoin?
You might be mildly disappointed by the fact that mining bitcoin, for all practical purposes is a loss inducing activity. To make things worse, Ethers and Litecoin are lossful too.
You can however buy Bitcoin on exchanges by paying cash in your local currency. These exchanges sell bitcoin just like a stock exchange by speculating the value of the coins.
The oldest hosted wallet for bitcoin is Coinbase. Here is its seed round pitch deck.
You can also look up ZebPay if you are in India.
Each user is identified by an address (an alpha numeric string). All transactions are directed from and to addresses. Every address is unique. If you sign up for a wallet like Coinbase or Zebpay, the company manages the address for you. You can safely share this address with anyone to which you want money credited to, with your privacy safe.
Why is there so much hype about Bitcoin, overnight?
The hype about bitcoin in the tech circles is not recent. It has been in news ever since Satoshi Nakamoto released their(?) paper. Marc Andreesen, creator of the first web browser, says the blockchain is the biggest breakthrough in technology since the internet.
Blockchains finally give us a way to establish trust on the internet. (You know how a node has behaved in the history of the network)
The Winklevoss Twins (remember The Social Network?) invested $11Million early on and now are worth $400Million.
As of August 8, 2017 — Bitcoin successfully made it’s first major hard fork because of a software upgrade. Thereby, shooting the value of the bitcoin north. This has been seen as an indicator that of the consensus within the network and its stability.
Bitcoin now has a market cap of $68Billion.
Ethereum
The next biggest blockchain after the Bitcoin is Ethereum with $28Billion market cap.
Ethereum was founded by a group of people closely involved with the Bitcoin network, after a feud relating to expanding the capabilities of the Bitcoin network.
Ethereum allows issuance of smart contracts.
In a traditional transaction like say piano classes, you have the following ways to make the transaction.
- You pay once the tutor has taught you to play
- You pay and then the tutor teaches
In case 1, there is no guarantee that you’d pay the tutor after you’ve learnt to play. In case 2, there is no guarantee that you’d be taught after you pay.
Here is where Ethereum kicks in and introduces smart contracts.
A smart contract is where you make a payment along with a verifiable condition. When the verifiable condition is met, the payee gets the amount. If the verifiable condition is not met in a specified amount of time, the money is reverted to you. The network will verify whether the condition has been met. The condition is a script written in a turing complete language. Meaning, if you can write a script in any other turing complete language like say Java, or Python, you can write the same algorithm in this language too. TL;DR, you can specify very complex verifable conditions too.
This introduces something that was not possible with traditional money.
Ethereum is at an inflection point. It, like bitcoin, uses PoW (Proof of work). It however argues that this results in monopoly of people who can spend the maximum on infrastructure. And some day will get institutionalized by large companies. Ethereum will soon move to Proof of stake. This is one of the reasons Ethereum is not shooting up with all other crypto currencies ever since the bitcoin fork.
Psst, here’s a pro tip. Don’t invest in Ether mining hardware. It will soon become redundant.
Proof of stake, will not be so expensive to calculate. The exact details of this is still in RnD mode, led by the charismatic 20-something year old, Vitalik Buterin
Other blockchains
Litecoin — Just like bitcoin, but lower transaction fees
IPFS — A distributed file system
Why blockchain is a big deal
Blockchain has the immediate advantages
- It is decentralized. Unlike country currencies controlled by governments, crypto currencies are not held by a single country or institution. So things like demonetization cannot take place without majority consent.
- Clearance is fast. Clearances are made within 10minutes, which might take days in a traditional payment gateway
- Micropayments become possible. The transaction fees for standard currency is so high online that is isn’t feasible to make very small payments. Bitcoin allows transactions to one 100000000th of a bitcoin, called a Satoshi.
- Machine transactable. Machines can make automated payments (Smart contracts)
Where is bitcoin used
Bitcoin became notorious for its darkweb transactions. But the implications are much larger than that. It is easy to make payments online across borders, without institutional interference. True you cannot pay over the counter at a grocery store from your bitcoin wallet, but it isn’t impossible in the future.
Notable companies are 21.co (pay to ask questions to celebs), Brave (Browser by makers of firefox for ad free internet), Toshi (Browser for Ethereum apps)
Widgets used on this blog are adapted from https://github.com/anders94/blockchain-demo/
You can send me some coins :)
Ether address : 0x6Bbc4C3b9316Fc9210B1C0De3D8Aa2bA7932Ae98
Bitcoin address : 1BPjA26jXnnGKmFbeqWsuWSjoSrqXFWDh6
