Since Bitcoin's beginnings in 2009, it has given rise to a quorum of blockchain infrastructures aiming to improve the job or offer some particular function that is beyond the special scope of Bitcoin proper. For example, Ethereum provides a platform for processing smart contracts in a manner that is much more powerful than what Bitcoin offers. But, even if the blockchain offering does only the functions of Bitcoin, it can still differentiate itself so as to increase security, improve politics, reduce energy consumption, or greatly improve efficiency.
One way different blockchain offerings can differentiate from others to achieve some of these improvements is to change the manner in which consensus is managed.
So, what's that all about? This series of posts will take a closer look at consensus and see if we can understand it better. We'll break this topic into 3 posts:
- Foundations of Cryptocurrency and Blockchain
- Problems in Consensus and Consensus Types
- Consensus and Smart Contracts & EVMs
Before diving in, some questions that may come to mind include (that we'll address):
- What do we really mean by consensus?
- Is this a totally new idea created by the living person, Satoshi Nakamoto?
- How does consensus relate to the blockchain ledger?
- What does the consensus control? Incentives? Security? Reality?
- Does consensus come at a price or is it totally free since all this Bitcoin stuff is public?
- Consensus usually means more than one entity agrees on something, but who or what are those entities? Is it everyone?
- What if I want to explore my own idea about consensus? Do existing blockchain systems make that easy?
- What are smart contracts? How are they made? How are the used?
- Can I write a smart contract that does consensus? Is that a good idea?
If you already know about this topic, then you already know that I have asked some silly questions. But, the whole idea of blockchain is new to a lot of people. And for those of us who know anything about this, probably were asking some of those questions not long ago. After all, some of the recent additions to the world of peer-to-peer blockchain offerings (like Ethereum) are only a few years old.
What is Consensus?
The term consensus is a common word. So, what does it mean in the realm of peer-to-peer computers? Let's have a look.
First, keep in mind that consensus is something that happens among members of a group, a.k.a. more than one. The term carries with it the notions of many separate communicating entities or people. It also carries the notion of talking to those entities. That is, we must be able to ask questions and get answers out. When it comes to computers, the expectation is that they are separate and networked.
The term consensus means that a particular answer to a question posed to a number of individuals, qualified to answer, will be similar if not exactly the same. Here, the qualification aspect may simply mean ability to answer intelligibly in a language spoken by a group and perhaps in which the question was posed. For example, if you asked many English speakers, "Do most people have mothers?", then you would expect most people to answer "Yes". You can also see if there is a consensus about a consensus.
When the individuals are computers, we have to get more precise about communication and the process of agreement. Separate computers (or processes), called nodes, who participate in agreement over data points may do so if they can send, receive, and process messages that notate the question about certain data points in a common language. And, if one group of nodes is to come to an agreement, they should each act according to a pre-established set of rules for determining the acceptance of the data points. The computer programs that adhere to a set of rules for a particular version of consensus are said to execute (run) a consensus algorithm.
Consensus Algorithm Principles
If you go looking for ways of doing consensus with computers, you might find that there are many ideas about how to establish a consensus among many computers about a value. While there are many versions of consensus algorithms, there are some high-level guiding principles for developing the algorithms that people are beginning to come to a consensus on. These principles are as follows:
- Agreement: this is the general nature of consensus.
- Integrity: a node accepts a data point that other honest nodes accept.
- Safety: given some input (query), all nodes eventually produce the same output (response). This is similar to deadlock avoidance.
- Validity: accepted data points have been proposed by some node prior to the agreement among nodes.
- Termination: (also referred to as liveness) eventually well-behaved nodes propose some data point and also accept some data point.
- Fault Tolerance: if some small number of nodes (less than some threshold) fail to act in accordance with the consensus algorithm, the remaining majority nodes will recover and continue to operate normally.
Now, when the stream of data points handled by nodes is a ledger, as in a blockchain ledger, a consensus means many copies of the ledger being kept is the same or in synch. And, any question about the ledger asked of any node should be in accordance with the general consensus. While the details are complex, if you go looking, you will find that the guiding principles above are being addressed in the management of these ledgers.
While we have spoken of independent communicating nodes, we have not discussed the manner in which nodes talk to each other nor the order in which nodes are addressed. But, the manner in which the computers converse, what they do with information provided to each other, and the asynchronicity of the communication has a lot to do with how consensus algorithms differ. For instance, consensus might be controlled by a central authority, or it might be completely peer-to-peer with no apparent single authority.
Bitcoin is peer-to-peer, but how does it achieve security and move forward? It's all in the consensus algorithm. We examine that idea numerically a little later in this tutorial.
For now. let's appreciate the idea that the fictitious person, Satoshi Nakamoto, put together some ideas that had been around in distributed computing and cryptocurrency for a while. The innovation made by Satoshi was in the way distributed computing consensus was applied to a cryptographically tied ledger, enabling an irrefutable ledger of transactions established by a trustless consensus process. And here, by trustless we mean that the nodes don't have to be trusted 100%.
So, Satoshi's consensus is based on pre-existing ideas. How did those ideas arise and evolve into Bitcoin? We can take a quick look at that. And then, we can take a peek at how the evolution has been going for Bitcoin up to now so we can get to know consensus a little better. We can explore what it means to create our own consensus and how to do that. Maybe we could write consensus into a smart contract — is that a good idea? Let's find out!
Evolving to Blockchain Consensus: A Brief History
Using the term evolving makes some sense. The kind of consensus used by Bitcoin to vary its blockchain has been around considerably longer than Bitcoin. The blockchain, a highly specialized database, has been around, too. It does not even have to be distributed to be a blockchain. In some sense, some of the implementations were the "parents" and "grandparents" of Bitcoin. And Bitcoin might be the "parent" of Ethereum and other "rebellious youths" of the cryptocurrency world.
We can begin with currencies and ledgers.
Cryptocurrencies Existed Before Bitcoin
Before Bitcoin, there were already experiments in the use of cryptocurrency. Cryptography was used to sign and secure information about transactions, but, many utilized just the cryptography and attempted to create protocols in which services took care of the currency users.
Here are two articles that take use from the first notable uses of electronic payments, Blinded Money and SmartCards in the Netherlands, up through the introduction of HashCash on Bitcoin Magazine and Coindesk.
It was a novel attempt in the early to mid 1980's to use cryptography to conceal transactions that could go over the wire. BlindCash and SmartCard use in the Netherlands was the first time that a whole system got off paper. The plastic cards were around but they still had to be pressed onto carbon paper, with bank copies being delivered. These innovations took place shortly after the patent of RSA in September 20, 1983, following just a few years later. By taking cash away from places, problems of theft were solved.
The idea that money could be exchanged over the web also came later. PayPal got its start in the late 1990's, in 1998. This is a few years after the first web browser, Mozaic, whose first version appeared in March 1993.
In the same year that PayPal launched, Wei Dai launched B-Money. Many features found in Bitcoin were part of it. It was served by an anonymous peer to peer network and used the idea of an arbitrator. But, there is a subset of validators among those who keep track of transactions and have to come to a consensus in some way. The notion of a database is used, but not of a blockchain. How consensus is reached is not clear. But, there is something akin to Proof of Stake for bad behavior. Wei Dai's description of b-money is here.
B-money did not get enough interest to keep a company going. Later, Satoshi makes references to it.
HashCash introduced Proof of Work. HashCash is supposed to protect a receiver from spam. The idea is that the sender solves a cryptographic puzzle to prove to the receiver that the message (e-mail or something else) is worth receiving. Receivers are supposed to be able to discern that the proof has been done. Proof of Work was introduced in 1992 by Dwork and Naor, which HashCash used to send new money. But, HashCash was thought to be too greedy with resources.
For the attempts at cryptocurrency mentioned so far, there were no shared ledgers. Wei Dai had something like distributed consensus, but it was not tied to a blockchain. In fact, there does not seem to be a blockchain in use in those systems. But, blockchain might have been used by them. It was not new at all.
Blockchain Existed Before Bitcoin
A blockchain is a set of records (or pages) that are linked by their headers. Often, the linking is done by storing the hash of a block in the header of the next block. The newer block identifies a unique block in this way out of a whole universe of possible blocks. To prevent tampering in the new block, the header can be encrypted and the header can be made public.
There is nothing about a blockchain that is distributed. It could be. Since the linking is purely cryptographic, blocks don't have to be stored together on the same machined or disk. The linking is in fact a physical state of the universe independent of machines.
Similarly, there is nothing saying that the blockchain has to be distributed in pieces. There is nothing that says that it has to copied many times over. It is just a data structure, a highly specialized database.
The blockchain is not a typical database that has CRUD capabilities though. First, there is no destroy. There is no update. All you can do is create and read. And, the linking has to be achieved. The idea is that a ledger has to be created, and, the ledger has to be an accurate history of transactions.
In a blockchain used to implement a ledger, there is a need to ensure that the blocks move forward in time. The use of linking for timestamping digital documents is introduced here in a 1992 paper: Linking and Timestamps. The forward progression has to be established to prevent a rewrite of history. When history can be rewritten, double spending attacks can be created. The blockchain secures both cryptographic traceability and a forward progress in time making such attacks unlikely after a few more conditions on processing are met. This is the point where the ledger become immutable and irrefutable.
In order to make the long list of transactions manageable, searchable, and verifiable (especially the linking), the developers of the new uses of the blockchain turned to the Merkle Tree, a data structure that was invented in 1979.
We think of binary trees made up of nodes and edges, which are the branches. The root is the highest parent. And, each parent has one or two children. The Merkle Tree is a binary tree that realizes a link between parent nodes and children nodes by making the data of the parent node the hash of the combined data of each of its children. We've gone in-depth about merkle trees before, and they come with benefits common to binary trees, such as logarithmic searching and partial storage of information.
Bitcoin Utilizes Consensus for Security
In the blockchain offerings that have risen around Bitcoin, entire chains are stored at every node. The reason for that has to do with consensus.
Each time a block is linked on to the end of the blockchain, the growing ledger, the block has to be accepted as the true set of transactions being stored on the ledger. So, the nodes of the consensus network work at coming to consensus on the data point, which is the new addition to the historical record of transactions.
This consensus is not different than what is needed by distributed systems to agree on anything, or in other words, any kind of data point. Consensus is a distributed systems concept.
So, we can see a sort of duality here. Many copies of the ledger are made because each node will keep a private copy to examine by way of using it to make a decision about the validity of a new block that is proposed by some node. Many separate nodes are used to manufacture of society of individuals who reach a consensus in such a way that they can report that a block is valid. If at any time, a block comes into question, we should be able to query any node or collection of nodes in the system for the validity of a block. The nodes will make a quick search of the merkle tree and report back about the block according to the network's consensus.
At this point, it may be good to read the Satoshi Nakamoto paper, Bitcoin: A Peer-to-Peer Electronic Cash System, Satoshi Nakamoto, 2009.
Decentralization
Let's make note of the fact that Bitcoin consensus does not require any kind of centralized authority. There is no single arbitrator and the system is totally public. No single entity is required to own all the nodes. In fact, the Bitcoin community has plenty of incentives to make sure that many players own nodes.
The multiplicity of validators allows "trustless" transaction validation.
Given that no one organization owns more than some number of nodes, one can be sure that the consensus cannot be compromised. The system is not just peer-to-peer. Miners only enjoy a fair process if there are many competing miners. Since the system is open to anyone coming in and mining, there is always a force acting against aggregating nodes into a single controlling entity. This is a good thing.
In the next post, we'll take a look to see how the numbers of nodes stack up to keep consensus honest, and some different types of consensus.
