Bitcoin, Blockchain, And A Byzantine General
Introduction to blockchain, the unsung hero of Bitcoin and a brief history of the technologies leading to blockchain.
It was a dark and gloomy night. The impenetrable city was surrounded, the invading army had camped outside of the city. Three battalions commanded by great generals anxiously waiting for their next move. It was now or never, they had to attack the city and finally claim their victory. It was no easy task, the city had great defenses, the only way to succeed was to attack at the same time, three battalions attacking the city at the same time from different fronts.
The generals can only communicate using a messenger and they all need to be synced for the attack to be a success. However, there was a problem, one of the generals have gone rogue and is working with the enemy. The rogue general might decide to fallback and not go ahead with the attack, or worse, can send out a false message which might lead to the death of a lot of soldiers. How do the generals come to a consensus despite the rogue general and go ahead with the coordinated attack?
At the face of it, it sounds rather simple, give it some thought, and then, I assure you, you’ll be fascinated by this simple yet brilliant conundrum. This little story is called the Byzantine Generals Problem¹ and is the motivation for Byzantine Fault Tolerance (BFT)¹. BFT talks about a reliable computer system (often distributed) that has the ability to perform its tasks despite faulty components providing contradicting and false information. When it comes to distributed computing systems, the key is for the independent components to have consensus when performing the designated task. This elusive muse of a problem was theorized by Leslie Lamport, et al¹, in 1982. Fast forward to 2008, we see a high BFT solution in a paper a by Satoshi Nakamoto² and implementation in 2009, yep, BitCoin. Fun fact, Satoshi Nakamoto is a pseudonym and the identity of the person (or the group of persons) is still a mystery.
Bitcoin relies on its ledger technology that allows the transactions to be immutable, secure and distributed. Because it’s distributed, multiple copies of the ledger are maintained and the distributed network reaches consensus over the validity of every new block (a block contains one or more transactions) added to a linked list (a chain), welcome to Blockchain. Now, who first came up with blockchain is a bit of a confusing topic, in most cases, Nakamoto is credited as the creator of blockchain, however, the original paper on bitcoin does not exactly mention blockchain. There is also an earlier (1991) academic paper by Stuart Haber and Scott Stornetta³ which discusses the same idea and Nakamoto in (his/her/their) paper references to this. I think that bitcoin was the first practical implementation of blockchain and that is sort of the reason that people sometimes wrongly consider it’s the same thing and the true potential of blockchain was overshadowed by bitcoin, for a while.
Blockchain is an ever-growing acyclic list of nodes linked together by a hash. A single node, a block, contains the hash of the previous node, its own hash, timestamp, and some data. The data part contains information about the transactions. Each block will be linked to the previous block by the hash of the previous block.
Pretty simple right? But how does this make it secure? Can’t anyone add a block to the blockchain? To answer that, we need to look at both public (permissionless) and private (permissioned) blockchains.
Private Blockchain:
Closed to a trusted set of nodes. Only these permissioned nodes can participate. Can be seen in some corporate and/or banking systems. Private blockchains do not necessarily require a proof-of-work, which might be an overkill given the nodes are trusted.
Public Blockchain:
Anyone can participate, and is decentralized, i.e. Bitcoin, the most famous blockchain. Participants need to solve a mathematical problem to find the answer to be able to add the next block (mining) to the chain. This is referred to as Proof-of-Work ⁵’ ⁶.
Further to these major divisions, blockchains can be further divided based on what nodes are allowed to do, as in the actions the nodes are allowed to perform within the blockchain.
Proof-of-Work:
Assume someone wants to change a block in the middle of the chain, because of the nature of the blockchain, when the data changes, the hash will change, and the next block now won’t link to the previous block because the hash is different. So whoever wants to change the data will have to change all the nodes after the intended node to make the chain-linked and valid again. This is not impossible if that party have enough computational power. This is where proof-of-work comes in, proof-of-work is a process of finding a hash value that satisfies some criteria set by the blockchain system. The idea is for a hash to be valid, it needs to qualify a certain pattern. In the example below, it needs to have four leading zeros. This is called the mining difficulty. Since the same data which run through the same hashing function returns the same hash, a nonce (number once used) is introduced. What mining essentially is, to run the data and an incrementing nonce through a hashing function till you get the desired hash. The first person to get the answer becomes the miner of the block and is compensated with a reward (mining bitcoin).
This process is expensive, if you’ve read about Bitcoin consuming energy and contributing towards global warming, that’s because of this Proof-of-Work and the associated mining difficulty. As the blockchain grows, the difficulty will be increased to maintain the legitimacy of the network and to keep hostile nodes taking over the network. An alternative was proposed called Proof-of-Stake, rather than the nodes competing to mine the next block, a random node is selected to mint/forge the next block. the selection criteria are based on a stake (wealth, age, etc…), PoS is widely debated and some have highlighted issues with it. So back to answer the question, Can’t anyone add a block to the blockchain?, They can, given they satisfy the above-explained conditions, oh and one more thing, the network needs to reach consensus to do so.
Consensus:
When a miner has mined a new block, that miner needs to add the new block to his/her own ledger (remember the ledger is distributed, everyone maintains a copy of the ledger), and upload it to the network. Every other node receives the copy of that ledger and validates the validity of the new block, including the validity of the transaction history. If you look at this more detailed diagram of a blockchain, you will notice a tx_root, which contains the hashes of previous transactions in a Merkle Tree⁴. By having a copy of the ledger’s headers, one could compute the validity of the previous transactions by traversing the tree.
![Bitcoin Block Data, Matthäus Wander [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons](https://miro.medium.com/v2/resize:fit:1100/format:webp/1*9mnrgbfFCdaUgDKBt_5Wig.png)
Only when this validation is complete and the network agrees, reaches consensus, on the validity of it, the miner will get the reward. This ensures that the blockchain system has a way of fending off attackers and rejecting malicious information and functioning in a high BFT mode. Yep, this is where the Byzantine general makes an appearance again (you should also read about Practical BFT⁷). However if an attacker succeeds to overpower the network, by having more nodes, the attacker will gain control of the network.
As such, the verification is reliable as long as honest nodes control the network, but is more vulnerable if the network is overpowered by an attacker. While network nodes can verify transactions for themselves, the simplified method can be fooled by an attacker’s fabricated transactions for as long as the attacker can continue to overpower the network.² — Satoshi Nakamoto, A Peer-to-Peer Electronic Cash System, P5
What Nakamoto achieved with Bitcoin is monumental, what really interests me is its underlying ledger or Blockchain. Blockchain is not without fault or 100% BFT, however, it opens up some interesting avenues around decentralization and eliminating the middleman. Currency is just one area where decentralization can be used and eliminating a central authority to certify the validity of a transaction. If you look at things like Ethereum⁸, which is a complete decentralized system, where you write decentralized applications (dapps) which will run as intended across the system. I can have my dapp run without the need for a central hosting space or service or execution environment. What Ethereum is, is a programmable blockchain.
Blockchain is a medium of trust, a medium without a central moderator and its applications are limitless. Any scenario you need to track transaction history, i.e. shipping history of goods, or authenticity of things and their messages in an IoT network, activity on shared forums or document sharing platforms, even identity itself can be decentralized and supported by a distributed medium of trust.
Power to the people finally?
[1]: Lamport et al, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 4 Issue 3, July 1982
https://people.eecs.berkeley.edu/luca/cs174/Byzantine.pdf
[2]: Satoshi Nakamoto, A Peer-to-Peer Electronic Cash System. 2008. https://bitcoin.org/bitcoin.pdf
[3]: Stuart Haber, W. Scott Stornetta, How to Timestamp a Digital Document. 1991. https://www.anf.es/pdf/Haber_Stornetta.pdf
[4]: Merkle, R. C. (1988). "A Digital Signature Based on a Conventional Encryption Function". Advances in Cryptology — CRYPTO '87. Lecture Notes in Computer Science. 293. pp. 369–378. doi:10.1007/3-540-48184-2_32. ISBN 978-3-540-18796-7
[5]: Jakobsson, Markus; Juels, Ari (1999). “Proofs of Work and Bread Pudding Protocols”. Secure Information Networks: Communications and Multimedia Security. Kluwer Academic Publishers: 258–272. doi:10.1007/978–0–387–35568–9_18
[6]: Adam Back, Hashcash, May 1997. http://www.cypherspace.org/hashcash/
[7]: Castro, Miguel, Liskov, Barbara (1999). “Practical Byzantine Fault Tolerance”. Proceedings of the Third Symposium on Operating Systems Design and Implementation. http://pmg.csail.mit.edu/papers/osdi99.pdf
[8]: Buterin, Vitalik, A NEXT GENERATION SMART CONTRACT & DECENTRALIZED APPLICATION PLATFORM. http://blockchainlab.com/pdf/Ethereum_white_paper-a_next_generation_smart_contract_and_decentralized_application_platform-vitalik-buterin.pdf
