Blockchain for CS People
Dissecting the Hype
Blockchain is one of the most misunderstood technology that exists right now. On one end, blockchain is one of those tech words that has been mythified to be a world-changer: a tool that can solve poverty, world hunger, and other grandeur things. It’s easy to get caught in the marketing hype and get a non-accurate, sugarcoated idea of it. On the other end, some people think blockchain is “just a linked-list” and has no use cases outside of cryptocurrency. While both extremes have some kernel of truth, I think that there should be an elaboration to be made to truly understand the potential and limitation of the technology.
In this article, I will try to explain what blockchain is as comprehensive, easy-to-understand, general, and bullshit-free as possible with mild concepts that are familiar with CS students so you could understand why it is designed the way it is.
By taking interest in this article, I assume that you’ve heard the popular discourse about blockchain and cryptocurrency already and familiar with terms like Bitcoin, immutability, and decentralization.
For educational purpose, I’ll base my explanation on the definition I found on tendermint.com:
“Byzantine fault tolerant state replication machine”
“Holy shit, is that even English?” If it sounds too complicated, just memorize it for a few minutes :). Once you understand the concept of “State Machine Replication” and “Byzantine Fault Tolerant” that I will explain in the next 2 sections, you should know what blockchain is all about. Please also note that this definition is not universally accepted (as I will explain in the second section), but I will still use it as it is the most succinct and general definition I found online. So take it with a grain of salt.
Got the definition memorized already? I’ll start by explaining the later part of the definition.
What Does It Actually Do: State Machine Replication
Blockchain is built on the idea of no single point of failure i.e. how do we build a system of computers that still works even if a part of it isn’t working. To do so, we must treat all computers in the system equally, because if there’s a computer that’s more important than the other, then it is the point of failure.
This means that if our application involves data storage (which is majority of programs, if not all of them) we must distribute the data across those computers so that if some computers went bust, the data still survives. This property (resistant against individual crashes) is called Crash Fault Tolerant (or simply just Fault Tolerant). Doing this and keeping the data consistent across computers is a challenge that blockchain is trying to solve.
In the most general form, physically, blockchain is built to store identical data modification history on multiple computers. Why do we store modification history, instead of the data itself? This is done to ease the consistency-enforcing mechanism. To explain it further, let’s imagine a scenario.
Let’s say we have 3 computers
C, together storing a replicated variable
x that must be consistent across computers, which is initialized as 0.
- At 3.00 pm,
x = 42(and then broadcasted it to the entire network)
- At 3.01 pm,
x = 69(and then broadcasted it to the entire network)
- At 3.05 pm,
In an ideal world, at 3.05 pm,
x should always be 69. But unfortunately it’s not always the case, because the network can be faulty:
A has a shitty internet and it takes 3 minutes for it to send data to
B only takes 1 minute, then at 3.05 pm,
C will be 42, not 69 as it should be, because
x = 42 arrive after
x = 69 (3.03 pm vs 3.02 pm respectively).
B (69) will now differ from
C (42), which is bad!
x is the amount of dollar someone has in a bank account and
C is an ATM. He/she will be confused if the amount of money displayed is different depending on which ATM is visited!
But if we assign a time information to the message, we can solve this problem. So, instead of
“Hey folks, I modified
x, and it’s now
“Hey folks, at
3.00pm, I modified
A computer in the network can record these messages, and no matter how shuffled it arrives, it can eventually deduce the correct value by reconstructing the modification history from the time information.
Footnote: the time information associated with a message doesn’t have to be a ‘wall’ time, and in blockchain systems that I’ve looked like Bitcoin and Ethereum, it’s not (in Ethereum it uses something called
account nonce), but the principle remains the same. If you want to study this further, look into the topic of “logical clocks” in Distributed System.
This method of achieving (eventual) consistency across different computers is generally known as State Machine Replication. The name comes from a program flowchart abstraction called Transition System, which is used to describe the general condition (called ‘state’) of a system and how those condition changes (called ‘transition’). In the scenario above,
state = data and
transition = data modification. If you want to study this further, there’s a good article based on a project here.
Notice that after
x is replicated, we can still know the value of
x even if 2 out of 3 of them crashes and become inaccessible. The system has developed tolerance against partial crashes.
To recap, blockchain is built specifically to store data modification history (transition data) so that many computers in the network can easily reconstruct the data easily and consistently, so that the system is robust against individual crashes.
So hopefully you now understand the second part of the definition. But this itself is nothing new, and in fact, the original paper of State Replication Machine was released in 1984. What makes blockchain special is its additional fault tolerance.
What Makes It Special: Byzantine Fault Tolerant
Technically speaking, this property means that, aside from tolerating crashes, the system can also withstand some faulty messages. To explain this, let’s slightly modify the previous example to demonstrate what is not BFT.
At 3.01 pm, after
x = 69, it correctly notifies
x = 69, but due to bugs or some intentional purposes, it falsely notifies
x = 80. Now the system becomes inconsistent:
A thinks that
x = 80 while
C think that
x = 69. This system is not Byzantine Fault Tolerant, as
B has successfully deceived
A, intentionally or not.
Blockchain isn’t like this, however. It can detect confusing messages that are trying to mess with the consensus. Because there is no single source of truth, a peer does this by ‘double-checking’ each message with its connected peers to see if the message it received made sense. e.g. if a message said
x = 80 but other peers told you that
x is actually
69, you’ll know that something is wrong.
Footnote: It is named ‘Byzantine’ because of a random allegory from Robert Shostak that got popular. Just read the abstract of this paper.
Practically speaking, this means that a blockchain system can withstand a certain amount of bad peers in the system that tries to mess with the history. It makes the history that has been stored very hard to mutate (but not impossible). This is done by following certain rules for determining whether the message is valid. This rule is called a consensus protocol. 2 most popular BFT consensus protocol that exists right now is PBFT and Nakamoto.
PBFT is the older algorithm from those two. It’s quick but requires a computer to be connected to every other computer, hence not scalable in terms of the number of participants. Grossly simplified, this protocol lets the individual computers to vote for what the correct data is. Current blockchain systems that implement this algorithm include (but not limited to) Ripple, Stellar, and Hyperledger.
Nakamoto consensus protocol is the one that has been hyped with blockchain. It doesn’t require full knowledge of the network (you don’t have to be connected to every computer) hence is scalable in terms of the number of computers, but is slow and not scalable in terms of performance. Grossly simplified, this protocol algorithmically delegates a computer to validate incoming transition data and add it to its preferred history in such a way so that a computer with the same preferred history as the majority of computers in the network gets delegated more frequently. The algorithm used is usually based on cryptography (hence the term ‘cryptocurrency’). Current blockchain systems that implement this algorithm include (but not limited to) Bitcoin, Litecoin, and Ethereum.
The name ‘blockchain’ stems from this consensus protocol, where the transition data is usually validated in batch (a ‘block’) and that block is going to be cryptographically appended (‘chain’-ing it) to their predecessor.
Footnote: there is a third consensus protocol that is in the work, called Snow.
The Nakamoto protocol has some different ‘flavors’ depending on its algorithm in deterring bad peers that try to inflate their influence in the network by spawning many Virtual Machines (technically called Sybil). There are Proof of Work and Proof of Stake to name a few.
Grossly simplified, Proof of Work introduces a computation cost for a client to be able to contribute to the consensus, so someone that tries to artificially become a majority must spend a lot of money to buy/rent beefy computers. You can’t just spawn low-spec VM / buy cheap computers to cheat. There is a good explanation of a Proof of Work based blockchain in this video. In PoW, the act of validation is usually called ‘mining’, because you need to spend a lot of power to get a reward, just like a real miner.
Proof of Stake, on the other hand, introduces a direct financial cost rather than computational cost. You must have a certain amount of wealth to be able to join the consensus and you will receive no reward if you cheat. By doing this, you’ll reduce the probability of Sybil actors by requiring someone to have 3x amount of threshold wealth to spawn 3 additional VMs, for example. Some Proof of Stake system also punishes you by taking your money for trying to cheat.
Some experts said that Nakamoto protocol is the defining characterisitic of a blockchain system (i.e. a byzantine fault tolerant state replication machine that doesn’t use Nakamoto consensus is not blockchain). I personally share this sentiment, but as mentioned in the third paragraph, for educational purposes, I will take a more generic approach towards the definition and say that a similar system that doesn’t use Nakamoto consensus is still blockchain.
Footnote: There is a term called Distributed Ledger Technology (DLT), but it’s less popular than Blockchain
To recap, as long as every computer act in their self-interest by following the protocol, blockchain cannot be affected by bad clients that try to deceive other clients by messing with the data modification history. But as soon as there is a coalition that takes up a certain amount of the computer population in the network (the specific amount is determined by the specific protocol), then the BFT property of blockchain is not true anymore. It’s not perfect, but more robust than a single point of failure in a centralized architecture.
Hopefully the term “byzantine fault tolerant state replication machine” makes sense to you now. Now let’s move from the realm of theory to the land of implementation.
Public and Private Blockchain
Because of the difference in network knowledge requirements in the consensus protocol, we can divide blockchain systems into 2 categories.
Public blockchain, as the name suggests, is a blockchain system where everyone can help maintaining the history. It uses consensus protocol that doesn’t require perfect knowledge of the network membership: everyone can contribute, everyone can go, and nobody needs to know everybody. As long as your computer can run the provided program, you can contribute to the consensus. Bitcoin and Ethereum are two of the most popular project of public blockchain.
One major limitation of public blockchain is, because of how their incentive system works, they’ll always be implemented as a cryptocurrency first. You can add additional functionality to it, but you can’t really make a blockchain public without introducing cryptocurrency into it. For deeper and philosophical reasons behind it, please read Naval Ravikant’s thread about it. Here’s a short aphorism of it, taken from Naval’s 31st tweet:
“It’s nonsensical to have a blockchain without a coin just like it’s nonsensical to have a market without money”
You can, however, make a currency-less blockchain by implementing it privately
“The banks and the corporations say, ‘Oh, bitcoin’s awesome. We want that. Only without the open, decentralized, peer-to-peer, borderless, permissionless part. Could we instead have a closed, controlled, tame, identity-laden permission version of that please?’” – @aantonop
Private blockchain is where the maintainer is chosen by some authority (a federation or some kind). It usually uses a consensus protocol that requires perfect knowledge of the network. Ripple and Hyperledger are two of the most popular project of private blockchain.
Note that a private blockchain can still be used by the public and all of the data inside it is not necessarily private. It just means that the blockchain is privately maintained.
Private blockchain offers a somewhat weaker form of immutability because there is usually smaller set of computers controlling it, hence fewer computers someone needs to control to mutate the history.
With those distinctions in mind, let’s look at some actual products.
Because of its BFT property, blockchain can be used to directly facilitate the cooperation of multiple selfish users (usually businesses) without fearing the other party cheating on them. e.g. voting without fearing your vote being tampered, exchanging valuable items without fearing that the other party weren’t fulfilling their end of the bargain, sharing a database of useful-but-sensitive information without fearing unfair sharing, etc.
Traditionally, this is done by trusting a mediator institution that make sure each participant play by the rule. By replacing the middleman with blockchain, you can cut bureaucracies and make the system more robust.
Two examples of this are J.P. Morgan’s Interbank Information Network (IIN), which is used as interbank payment settlement system instead of using an intermediary institution like Visa, and Tradelens, which is a supply chain tracking service for shipping companies.
This use case is usually popular only in a business-to-business context, hence it’s usually implemented as a private blockchain and not a lot of them are publicly discussed aside from benchmarking studies like this.
Of course, some businesses (like a bank) are also a form of mediator institution. So instead of mediating the mediators, why don’t we mediate the end users directly?
This is the idea behind cryptocurrency. Cryptocurrency means that the blockchain is used to directly store consumer’s transaction data. It allows you to send and receive money without a middleman like a bank or PayPal.
One small upside of sending money this way instead of using a centralized service like PayPal is, because of its peer-to-peer nature, the money goes straight into the receiver’s account, with no for-profit company in the middle asking for a hefty fee. There will still be a fee if this is implemented on a public blockchain (for the consensus maintainer) but is usually designed to be a lot smaller.
Cryptocurrency is the original use case of public blockchain tech and where all of the hype is coming from. This is because the idea is so novel back then: the idea that you can ‘be your own bank’ and have freedom from big government, an anarcho-capitalism dream. But due to its inability to scale in terms of performance, the progress of this application is a little bit stagnated.
With that said though, cryptocurrency doesn’t have to use a public blockchain (Ripple and Facebook’s Libra is two of them), but the idea of a non-government-issued currency held by some corporation/federation makes it vulnerable to legal problems and give its own reason for stagnation.
Smart Contract / dApp Platform
Another interesting use case of blockchain is to store arbitrary programs and their history of inputs. This program is usually called smart contract. You can also string a bunch of smart contracts together to form a more complex application, usually called a dApp, short for distributed app (think of it like microservices). Ethereum is the most popular project to do this, but being a public blockchain, Ethereum also serves as a cryptocurrency platform below it.
The logic of this is you can reconstruct any program’s state and storage just by reconstructing its operation on all of the inputs that have been fed into it. It is called ‘smart contract’ because one of the earliest imagined use cases of it is to further formalize business procedures. Hence just by storing an architecture-agnostic assembly code (like WASM or Java Bytecode) and its complete history of inputs, we can ‘distribute’ any arbitrary computation in a BFT way.
Because it supports arbitrary computation, in theory, you can make arbitrary programs on top of it. The catch is, the performance will be slow because the computation needs to be replicated by every computer in the network to enforce consistency. Also, if it’s run on top of public blockchain, to prevent DoS attack, you usually have to pay some money proportional to the amount of computation and storage you use (think of it as a vending machine for computation). For those reasons, it’s not practical for compute-heavy program (like training a deep learning model).
If the smart contract platform also supports cryptocurrency, aside from supporting arbitrary computation, you can also send and/or receive money programmatically (imagine having a simplified PayPal API).
You can even build a dApp that forms another protocol on top of its underlying platform. In fact, this is the popular use of dApp: to harness the goodness of blockchain without creating a whole new platform. Some of this dApp introduces its own currency (sometimes called ‘token’) as an economic incentive to contribute to the dApp or just to represent some value.
Here are some examples of interesting smart contract that I’ve found:
- uPort, a decentralized credential system
- democracy.earth, a voting system
- Basic Attention Token, an ethical advertising system
- gitcoin, a GitHub bounty system
- Augur, prediction market
One thing to note here is that the term “using blockchain technology” can refer to both building blockchain platform or building dApp on top of blockchain, depending on the project.
Now we have looked at the current typical application of blockchain. Next, let’s discuss the most important thing: when you should and shouldn’t use it.
But At What Cost?
Being a shiny object, everyone tries to incorporate it into their project to look revolutionary. But there are actually very few specific use cases for it. We can relate it with the definition I use in the previous paragraphs and form 2 rule-of-thumb about its use case:
Do you even need your app to be distributed in a p2p way?
Most of digital services can be implemented in a simple client-server architecture. But if you’re running a mission-critical service, like financial or healthcare services, it makes sense to add some necessary complication by making the server distributed so that the service will still be up even if some computer crashes.
One other use case of peer distribution is to build a censorship-resistant app. Maybe you want to build something that a certain legal body doesn’t like (e.g. wikileaks, genesis library, etc.), then it also makes sense to make the app distributed so that it’s not easy to take down.
But just because it needs to be equally distributed, doesn’t mean that it has to use blockchain: blockchain is just a subset of peer-to-peer distributed system. The real question is, do you really need its fault tolerant property?
Do you need you app to be byzantine fault tolerant?
Do you need your system to double-check each input (BFT)? Or do you just want your system to be tough against partial failure (CFT)?
Although theoretically, with a modern smart contract platform like Ethereum, you can build almost any arbitrary application on top of blockchain, it doesn’t always make sense to do so. BFT is a nice property to have in your system, but as mentioned earlier, it also introduces a lot of performance overhead, complexity, and in the case of public blockchain, a small fee per computation.
As a further rule of thumb, you probably need BFT if each computer in your system is politically different from each other. In other words, they don’t really trust each other (e.g. different organizations, different entities with their own self-interest, the threats come from within the system, folks trying to cheat). If you just want your system to be ‘hackproof’ (the threat comes from outside the system), you don’t really need BFT. You probably can solve it with traditional methods e.g. firewall, encryption, and backups.
“But by both having BFT and traditional security measures, isn’t my application will be, like, super duper robust?”. Yes, it is, and this is also the point where the line between necessity and desire gets a little blurry. Again, there are no hard rules, but if you feel that your application is hypercritical and very appealing to hack, and you’re sure that this is justified and not just some random paranoia, and you’re okay with the development, performance, and potentially financial cost that come with it, then this is another use case for blockchain technology. What are the odds, though? You’re probably overinflating the importance of your app.
If you have answered “no” in either of those questions, then it’s probably overkill to use blockchain in your project.
But if your answer is “yes” on both of those questions, then you’ve just found the perfect technology! Go think of something unique, as currently the space is pretty sparsely populated.
Build something and surprise the world!