Blockchain 101: Beyond Crypto, Introduction To The World of Decentralization (Part I)
UPDATE (June 19th, 2021): I decided to completely remove the cryptocurrency section from this blog series. After all, the goal of this series is to share educational knowledge about the technical aspect of blockchain. If you are looking for financial advice or speculations on cryptocurrencies, you will not find those answers in this series.
Hello, readers! I bet you are here because you most likely have heard people saying things like, “Bitcoin is a good store of value and a hedge against inflation”. This is a plausible (albeit debatable) argument from a financial standpoint because the Bitcoin protocol has been programmed to cap its maximum supply at 21 million BTC. No single government, central bank, or entity has the authority to control the circulation of Bitcoin. In other words, Bitcoin is less likely to go brrrrr….
Ok, but how does it work? The short answer: Bitcoin’s ability to operate autonomously is done by using a technology called the blockchain.
In this series, we will cover the following topics to learn more in-depth about this technology:
PART I:
- Closing The Trust Gap
- Achieving Consensus With Byzantine Fault Tolerant (BFT) Algorithms
- Cryptography and Hashing
- Blockchain BFT Algorithms
PART II:
- Smart contracts and decentralized applications (dApps)
- The Blockchain Trilemma
- Where Are We Today?
Everything covered here is solely based on my knowledge of the technology and my observation of its current trend. I hope this series would make a great resource to guide you to the fundamentals of blockchain.
Without any further ado, let’s dive in!
Closing The Trust Gap
To begin a trade, the involving parties must trust each other. I would describe the act of trusting to be a spectrum rather than a binary decision factor. In other words, it’s important to realize how much you can trust anyone. To establish trust, we rely heavily on centralized intermediaries, a.k.a. middlemen to enforce any agreement between the involving parties. The use of intermediaries however would arise the following problems:
- Single point of failure
- The rise of monopolies or a central authority becomes too powerful
- The exchange of information is at risk of being tampered with
Robinhood (definitely my favorite example here) is a brokerage app that claims, “Investing is for everyone”, is popular among novice investors because of its user-friendliness, gamified interface, and easy access to the stock market. The principle behind Robinhood is to give the public their fair share of investment opportunities. That principle shattered during the event of the Reddit-fueled GameStop share price hike in January 2021, Robinhood broke this trust by shutting down GameStop trading for retail investors, which brought lawsuits filed against them. The reliance on intermediaries may help to generate trust to some extent, but it is not bringing us near the right end of the trust spectrum. (In the case of Robinhood, it’s taking us in the opposite direction) This forms a gap between the trust that we are willing to afford and complete trust.
Allow me to introduce you to the new thing that could bring us closer to complete trust. This new thing is a distributed ledger. A ledger is used as a bookkeeping tool to record and timestamp all transactional data. To prevent any centralized authority from tampering with the content of the ledger, it must be distributed across all participating entities. Since the event of the GameStop craze, there is an increasing demand for decentralized and censorship-resistant trading. This is something that can be implemented by using distributed ledgers. Consider this ridiculously simplified example, an investor buys a share, then the ledger records the transaction and distributes it across the network. That way, other participants would acknowledge that a transaction occurred and adds it to their copy of the ledger. When the network can reach a consensus on a canonical truth, it becomes a trustless network. Giving complete trust is the same meaning as complete removal of the necessity to trust, therefore closing the trust gap. Consensus eliminates the need to trust because all transaction activities became transparent and verifiable. In the event when any participants decide to shut down the network, it would require a more significant effort to do so, compare to its centralized counterpart. Basically, it would require a majority of the network (51% or higher) to agree to shut down.
If you are having trouble visualizing the above example, check out this short clip about Bitcoin explained by a three-year-old.
Now that you understand the reasoning behind using a distributed ledger. You are probably wondering, how does it reach a consensus? Or on a bigger issue, how does it detect a group of malicious actors that are collectively propagating false information? This is a major problem for distributed computing systems, which is known as a Byzantine fault, named after the Byzantine General Problem. In the next section, we discuss the mitigation of such issues.
Achieving Consensus with BFT Algorithms
A fault is a computing system failure. In a system that relies on a central server, a fault would usually lead to a stop fail. For example, the system instantly crashes when the server shuts down. The source of the fail is easy to locate. Byzantine faults are unlike any other faults. Components in a distributed computing system could be failing, but still functioning at a capacity (or worse, may behave maliciously) that might not be detectable by a failure detection system. It is also challenging for other components to declare it a failure because it would require the network to reach a consensus. The best analogy to describe such a problem is the Byzantine General Problem.
Suppose there are four groups of soldiers, with each group led by a general, are planning on an invasion on a massive fortress. The fortress has the necessary armory to defend itself against attacks from each group unless they are all attacking at the same time. The four generals must reach an agreement to either vote on attacking together or retreating from the war.
The million-dollar question, “Can the generals trust their peers?”. The worst part of this problem is that one of the generals could be a traitor, who might intentionally send misinformation as a result the groups can never reach a consensus.
The answer to the question is that it is impossible to catch the traitor. We have to assume that there are always going to be bad actors in our distributed network and come up with a solution that tolerates it, so reaching a consensus is still possible. These solutions are said to be Byzantine Fault Tolerant (BFT).
Another million-dollar question, “How many traitors can be tolerated?” According to the Byzantine General Problem paper, it presents the following lemma,
“ The Byzantine General Problem seems deceptively simple. Its difficulty is indicated by the surprising fact that if the generals can send only oral messages, then no solution will work unless more than two-thirds of the generals are loyal. ”
The problem is unsolvable if more than 1/3 of the generals are traitors. We can express the problem in a Math equation, (N) is the total number of generals and (m) is the maximum number of traitors that can be tolerated:
N ≥ 3m + 1, # of traitors ≤ m
We are going to prove the above lemma using induction by simulating the Oral Message Algorithm, OM(m). We restructure the generals into a hierarchy. The commanding general is put on top, giving out messages to the rest of the generals, who we call lieutenants. Lieutenants can also verify the message received from the commander with their peers.
In the diagrams below, each lieutenant has a vector that corresponds to the message that they heard from their peers and the commander. The lieutenant’s final decision will base on the majority votes as shown on the vector.
Base Case: N = 4, m = 0, this is straight-forward.
Case 1a: N = 4, m = 1, one of the lieutenants is a traitor.
The traitor’s goal is to disrupt the network from reaching a consensus. For that reason, we don’t care what the traitor says, hence N/A.
Notice how the network still achieves consensus, regardless of the traitor’s vote. Would it matter if the commander is the traitor?
Case 1b: N = 4, m = 1. Commander is the traitor.
Even though the commander sent out conflicting messages, the network can still resolve to a consensus, as long as the number of traitors is tolerable. Let’s see what happens if there are more traitors above the threshold.
Case 2: N = 4, m = 2
The lieutenants failed to reach a consensus, while the commander gave the attack order. Leaving the commander to carry out a solo attack and dies. (Remember, the winning condition is that all generals must attack together or retreat).
The Oral Message algorithm shows a certain degree of Byzantine fault tolerance, but it can also get very expensive. The more traitors there are in a network, the more loyal generals are needed to mitigate Byzantine faults, which also requires more messages to be transmitted. Therefore, we should proactively reduce the number of traitors to optimize BFT algorithms, and that is exactly what Blockchain BFT algorithms do!
Cryptography and Hashing
Before moving on to Blockchain BFT algorithms, we are going to learn the basics of blockchain security. If the word “cryptography” sounds familiar to you, that’s because it is one of the ingredients to bake the cryptocurrency cake.
Cryptography + Currency - Trust = Cryptocurrency
In modern computers especially when there is an exchange of information, that information is encrypted with asymmetrical cryptography. The reason for it being asymmetrical is that it uses a private-public key pair. The public key encrypts the message, whereas the private key decrypts it. The following simple diagram illustrates end-to-end asymmetrical encryption.
We call User 1 (Alice), and User 2 (Bob). Alice is sending a message to Bob, she encrypts the message using Bob’s public key so Bob can decrypt it later with his private key. If the message is intercepted by an eavesdropper (Cerine), Cerine has no better way of decrypting the message than brute-forcing the secret code from Bob’s private key.
Encryption in blockchains is similar. When a user creates a new cryptocurrency wallet, they are given a private key (often in the form of a mnemonic seed phrase). The private key generates the public address using a hash function. The private key is also used to sign transactions (to spend funds), only the public address is to be shared with others on the network for receiving funds and verifying transactions. Since the public address is derived from the private key, it is safe to assume that a transaction made from the address is valid. In other words, the user should not share or lose their private keys, otherwise, they permanently lose their funds. A hash function is a mathematical function that takes an input and generates a consistent, yet unpredictable output. The goal is that getting an output from the input should be easy and consistent, but going in the reverse direction is infeasible.
One of the most robust cryptographic hash functions is the SHA-256, which is used by Bitcoin and many websites. When browsing on a secure website, you are most likely to find SHA-256 in the HTTPS certificate. Click on the lock icon on the address bar -> Certificate -> Details, then take a look at the signature hash algorithm field.
The Ethereum Blockchain uses a more enhanced version of the SHA-256 hash, which is keccak256. If you are interested in getting a hands-on experience to see keccak256 in action, click here. You would notice that even a slight change of just one bit of data, would yield a completely different output.
keccak256("Preston") = fe28c574892bfa1611dd3ef693dda97a2bb0be58604af528d09c5a2b7171e981keccak256("preston") = c871e1102cdbbf6f2169c68188e5c4e5689635343eafd7a7bb62460e1977c936
Let’s look into how we can use hash functions and cryptography to sign and verify a transaction. Be aware, I am using the term “public key” and “public address” interchangeably. As I said earlier, the public address is derived directly from the private key using a hash function. You could think of it like this:
hash(sk) = pk //sk = secret key, pk = public keyHow can we use it to verify transactions?
A key point to note is that the transactions are sorted in a certain structure, called a Merkle tree, which brings the ability to quickly verify one’s “possession” of Bitcoin. In other words, to say that one has X amount of Bitcoins, the blockchain can efficiently look for all past signed transactions by the user and return the net sum. Therefore, the user must sign every new transaction to make it deterministically verifiable. Now let’s look at how a private key signs transactions.
In this scenario, Alice is sending Bob 10 “Ledger Dollars” ($LD). The blockchain would first perform a check to see if Alice has the sufficient balance to pay Bob, by looking at previous and unconfirmed transactions, to prevent double-spending. Once the blockchain confirms Alice can pay Bob, Alice signs the transaction and broadcasts it to the network. The process of signing is taking Alice’s private key (SK), the transaction message, and Bob’s public key as parameters of the hash function which then generates the signature of the transaction.
hash(<Alice's SK>, "Alice sends Bob 10LD", <Bob's PK>) = signatureYou might notice a major security flaw in the above implementation. Generating an exact signature may require the attacker to steal Alice’s private key. But using the above hash function, Bob, the attacker, can copy and re-broadcast the same signature to the network, giving himself multiple batches of 10 LD. This is known as the replay attack. The general approach to solve this problem is to have the blockchain automatically assign a unique identifier for each transaction, and take that ID as an additional input of the hash function. That way, all transactions must have a unique signature.
hash(ID ,<Alice's SK>, "Alice sends Bob 10LD", <Bob's PK>) = signatureOk great, Alice signed the transaction. How can others verify that the signature is valid? Remember, the public only has information of Alice’s public key and the transaction signature. This is the cool part, we know that both info is derived from Alice’s private key. There must be a special method that we can use to recover Alice’s public key from the signature. If the recovered address value matches Alice’s public address, then the signature is valid.
ecrecover(<signature>) = <pk>For most popular blockchains, this is implemented using very complicated math, which is way beyond the scope of ̶m̶y̶ ̶e̶x̶p̶e̶r̶t̶i̶s̶e̶ this blog series. For the math nerds out there, check out elliptic curve cryptography and ECDSA.
> Takeaway: it is infeasible (theoretically possible) to reverse engineer hash functions from the output, except to naïvely go through 2²⁵⁶ possible guesses. Here’s a really interesting video by 3Blue1Brown, who did the math to show how much of a computation resource is required to break a 256-bit hash.
At this point, we have a basic understanding of the use of hash functions and cryptography in blockchains. In the next section, we are going to apply them to learning Blockchain BFT Algorithms!
Blockchain BFT Algorithms
Let’s recap on how we could come up with the best approach to deal with Byzantine faults. Our ideal approach has the following assumptions:
- Catching malicious actors is a challenging task, we are better off using a BFT solution.
- Our BFT solution should discourage malicious behavior to become more efficient.
In 2008, the creator of Bitcoin, Satoshi Nakamoto devised a revolutionary BFT algorithm called Proof of Work (PoW). PoW is heavily dependent on the use of hash functions. PoW involves a participant in the Bitcoin network to use their computer that is installed with a specialized GPU, called the Application Specific Integrated Circuit (ASIC) to run trillions of hashes per second. This process is also known by most of us, as Bitcoin mining, and the participants are known as miners. In the previous section, we mentioned that if we are given the output of a hash function, your best bet in finding the input is none other than guessing it. In a PoW blockchain, miners around the world compete against each other, until the first miner finds the correct guess, wins the lottery and gets rewarded, then repeats the process. Instead of saying finding the correct guess, we are going to use a different term. We are calling it a nonce. Depending on how good my drawing is, I hope it would make the best of my ability to illustrate how the nonce secures the Bitcoin blockchain.
The simple ledger is now divided into n-size blocks and chained together. For every block, the hash function takes the parameter of the previous block hash, all transactions in the block, and the nonce, which then computes the block hash, ties to the next block, and so on. The function looks like this:
hash(<prev block hash>, [...T], nonce) = <block hash>A rule is set by a difficulty adjustment algorithm at every new round of the mining competition. The general rule is to compute the nonce to find a hash with N-bits of leading zeroes. The mining difficulty is exponential to N. The faster it gets to produce blocks, the more difficult it is to mine them. Once a miner finds the solution, it can be easily verified by computing a single hash. If the solution is correct, the new block gets broadcasted to the network, so other miners can add it into their copy of the blockchain.
When an attacker decides to tamper with even a single transaction in a block, the block hash will be altered drastically, which breaks the chain with the domino effect, renders all subsequent blocks invalid.
For an attacker to make their bogus transactions valid, it would require them to redo the work to chain the modified block to the next block, and the block after that. It all boils down to a race between re-chaining the blocks vs. the network mining a new block, which is computationally infeasible. This is how PoW de-incentivizes attackers because such an attack is both computationally and financially expensive. The cost far outweighs the gain. The longer a blockchain is, the more resistant it becomes. Given that Bitcoin is the oldest blockchain, it is arguably the most secure.
Hold up! You might say. What if, there is more than one block mined at the same time? The longer blockchain rule still applies here. An assumption for transactions in a newly added block is that they are not final yet, and we should wait for a period of time to reach finality. Finality is a measurement of block time to wait for more new blocks to be mined until it is long enough that we can confirm the transactions can not be changed or reversed. When a user on the blockchain receives multiple conflicting blocks, all the user has to do is wait for more incoming blocks, then trust the longer blockchain.
However, if there is a significant amount of miners who can not agree on which new blocks to include, this could lead to a hard fork. A hard fork creates an entirely new blockchain that has a common root with the blockchain that it diverges from. Not all forks are created because of disagreement among miners, it can also be an upgrade or a protocol change on the blockchain. In this case, all miners would adapt to the new fork. The new blockchain can implement its own set of rules, and it would not affect all the new blocks that are added to the old blockchain. These are some of the Bitcoin forks: Bitcoin Cash, Bitcoin SV, Litecoin (forked Luckycoin, which forked Dogecoin), and Bitcoin Gold. As for the Ethereum fork, there is Ethereum Classic. The cause behind this fork is still controversial until this very day, I definitely recommend that you check out the notorious DAO attack to learn more about the Ethereum fork. We won’t go into details on the impact of blockchain forks here. (I guess I could write about it in my next post).
Proof of Work is an effective consensus algorithm, but not one without a few caveats. For an obvious reason, it requires very high computational power. The annual power consumption by Bitcoin mining is around 120 terawatt-hour (TWh), almost the same as the annual electricity use in Argentina. Even by not accounting for electricity cost, Bitcoin mining is only profitable with hardware that is specifically designed for mining, the ASIC. A decent ASIC mining rig costs about $5,500 a piece. It is estimated that it would make about $3,000 annual gain. Again, assuming you are getting free electricity and Bitcoin price does not crash, it would still take you almost two years to break even. PoW is putting a very high entry barrier for new miners to get into this digital gold rush. Another risk associated with PoW algorithms is the possible formation of mining cartels. A group of miners can pool their computing resources together, which would give them a better chance of winning this lottery. If this group of miners controls over 51% hash power of the entire network, they would have a final say on which transactions to add to the blockchain. To combat some of the PoW flaws, The Ethereum Foundation team is currently working on a multi-phase upgrade to building Ethereum 2.0, which migrates from the current PoW chain to a chain that uses a different BFT algorithm, called Proof of Stake (PoS). Ethereum developers have been researching PoS algorithms since 2014, they eventually came up with their implementation of the algorithm for Ethereum 2.0, called Casper The Friendly Finality Gadget (Casper FFG). Before going into details, we should know the basic requirements to participate in PoS.
Participants on PoS blockchains do not need special and costly hardware to provide security. Instead, they would pay a “security deposit” that is locked into a smart contract. (We will cover more about smart contracts in Part II. For now, you can think of it as an agreement between the participants and the protocol). The locked funds are used as a stake that grants voting power to the participants to get the network to reach a consensus. Any attempts to attack the network will result in their staked funds getting slashed. Since the participants are not computing hashes to mine blocks, these participants are now called validators. A validator would usually assume one of the two roles. One validator is chosen by the protocol algorithmically as the block proposer, while the remaining validators would attest to the proposed block. If the block proposer does not propose a block by a deadline, then a new validator will be chosen as the proposer. Validators who fulfilled the responsibilities for their roles would get rewarded. (Note: This is all you need to know about PoS algorithm. Casper FFG is the realization of the algorithm for Ethereum 2.0. It can get rather complex, so don’t sweat about it if you are confused. You can check out other PoS blockchains, such as Cardano, Tezos or Polkadot.)
Unlike PoW chains, Casper FFG only focuses on reaching a consensus, which separates the block proposing mechanism. A group of attestors listen for new incoming blocks and cast their votes. If the network were operating normally, blocks should be linearly added and form a linked list. Occasionally, multiple blocks can be proposed at the same time and make their own branch (can be due to a network latency issue or malicious intent), thus forming the block tree. For a more efficient runtime, Casper FFG places a checkpoint for every 100 block heights, forming a checkpoint tree, which is a subtree of the block tree.
The content of the vote is a link consisting of two checkpoints from different heights. We call the lower checkpoint (the source), the higher checkpoint (the target), and the root of the tree is the genesis block, which is finalized by default. The link that receives more than 2/3 of the total votes would become a supermajority link, which would finalize the source checkpoint and the target checkpoint is said to be justified. On the next round of voting, the justified checkpoint would then become the source, and this process goes on. The validators can not (1) vote on targets that are already finalized (double-voting) and (2) vote on multiple links whose targets are on the same height (conflicting votes), otherwise, they would get penalized. This is a very simplified walkthrough of Casper FFG. If you are curious to learn more about it in-depth, read this paper.
The entry cost to stake on Ethereum 2.0 is 32 ETH, which is about $102 K at the time of writing. Casper FFG follows the same rule as our solution to BGP, that is an attack would require over 1/3 of the total staked ETH. At the time of writing, there is currently a total stake of 4.24 million ETH (~$13 billion), so the financial cost for such an attack would be about $4.33 billion. This shows that PoS can be just as effective as PoW to de-incentivize attacks, but more environmentally friendly. If you are interested in learning more about staking on ETH2.0 (and potentially making a passive income), you can find out more info on Eth2 Launchpad.
By chaining blocks together, we are essentially making all transactions stored in the ledger immutable (cannot be tampered with). If someone were to ask you to describe blockchains in the most succinct sentence possible, it would be:
“Blockchain is a network of immutable and distributed ledgers.”
Simple as that.
> Checkpoint: If you are still here, first of all, congratulations! You made it to the end of Part I. I know it’s very long, but I can assure you that the fun part is just about to begin. If you feel confident that you fully understand everything up until this point, you already know the core fundamental of blockchains. From here on, we are going to focus on blockchain applications. (No more of the boring, theoretical and abstract stuff)
Continue to Part II.