Introduction to Distributed Ledgers
Ledgers are hard to distribute and keep updated without any central authority. Think of how hard it would be to share an excel spreadsheet between you and your friends that associates each of you with a number — let’s call it “friendcoin”. Each of you has to have a copy of the spreadsheet and it has to be kept up to date. You can only move friendcoin from your entry in the spreadsheet to someone else’s. When you do, you have to tell other people so they can change it too. Whenever you hear about a change, you also pass it on to a few people. Consider the following situations:
- Alice lies to everyone about Steve transferring all his friendcoin to her. (fraudulent transactions)
- Alice tells Bob she wants to transfer all of her friendcoin to Eve but tells everyone else that she wants to transfer it all to Steve. (double spending)
- Alice and Steve have a fight. Steve’s friends refuse to update their spreadsheet with any transactions to her while others think it’s unfair and continue to allow her to receive transfers. (censorship)
There are any number of ways the spreadsheets could become out of sync. There are possible social solutions, like voting to resolve disagreements or putting someone in charge for a week and rotating that person. These could work between you and your friends. They won’t work with a ledger containing millions or billions of people who don’t know or want to trust each other.
A solution to the fraudulent transaction problem, where Alice invents a transaction from someone else, has been known since 1978 with the publication of the RSA paper which introduced public key encryption and ˜cryptographic signatures. Instead of (or as well as) storing the name of a person in the ledger we can store their public key. That way, anyone wanting to make a transfer must sign their request with their private key.
Bitcoin
A solution for the other problems wasn’t known until Satoshi Nakamoto anonymously published his/her paper on bitcoin in 2008. It solved both the censorship and the double spend problem. The solution was roughly this:
- Update the the ledger with groups of transactions (called “blocks”). Only one party can add a block at a time. They have complete authority about what transactions gets included in their block.
- Each block has a header which has a hash of the previous block’s header as one of the fields. This makes the blocks into a linked list or a “blockchain”.
- Choose who will be the next block creator by running a game: Whoever is the first to find a hash with a number of leading 0s, where the input is the header of block they want to add, gets to add their block. This computationally difficult task is called proof of work (PoW) and the people playing are called miners.
- Whenever a miner is presented with two valid yet contradictory chains, they choose the longest one to work on top of.
- Parties are incentivised to play the game. The winner of the game is rewarded with the currency of the ledger (ie bitcoin). The reward usually comes from collecting transaction fees and/or the ability to add a predetermined amount of bitcoin out of thin air to their associated public key.
That’s a rather shallow summary but it gives us the key principles. We can make a distributed ledger work if we represent it as a series of transaction blocks. The blocks are the only thing that modify the state of the ledger. Block creators are chosen probabilistically according to their hashing power. As long as a large proportion of the hashing power isn’t owned by one group a variety will add blocks, making censorship and double spending impossible under reasonable assumptions. You can’t censor transactions, you can only delay them, because even if you try, soon someone else is going to add a block that will include it. You can’t double spend because only one of your transactions will end up in the canonical blockchain.
Nakamoto’s paper didn’t contain any new mathematical discoveries or constructions. It was a genius work of cryptographic engineering rather than mathematics. Seven years after its publication, in 2015 a group of cryptographers published a paper at Eurocrypt conference which formally demonstrated the security of the bitcoin protocol. Bitcoin was the first solution to the distributed ledger problem. As of writing, there have been over 300 million uncensorable trustless peer-to-peer transactions made through the bitcoin blockchain.
Ethereum — A notable innovation
Although it’s not related to consensus algorithms, it’s worth mentioning that ledger state transitions are not the only thing you can represent with blockchains. Ethereum uses a blockchain with a Turning complete language to represent a virtual machine. While it also has built-in ledger functionality, a programmer can embed code in the blockchain which can be called by them or by others. When these calls are made they are executed by every “miner” on the Ethereum network deterministically to produce the same state change. The biggest use of this seems to be for creating “tokens”, parallel ledgers within the Ethereum blockchain that have their own properties. For an proper explanation, see the whitepaper. For our purposes it is not important what exactly is being represented by the blockchain just how we can come to a decentralised trustless consensus about what is in the chain.
Bitcoin’s problems
Bitcoin has exploded in popularity and price. This has made the prize of the PoW game very valuable. In order to win, miners have engaged in an arms race of computational hashing power and cheap electricity. According to Digiconomist, bitcoin miners are consuming two billion dollars a year worth of electricity. All of this to process around seven transactions per second. It’s worth taking that in. The bitcoin network consumes about as much electricity as New Zealand to process seven transactions per second.
With that in mind remember that this is just a zero-sum game created to decide who gets produce the next block. Adding more hashing power to the network doesn’t improve its functioning at all. The system is just meant to provide a way to choose block creators that can’t be rigged to always choose the same group.
To make things worse PoW is not really doing its job. The high cost of mining created economies of scale pushing smaller players out of the game. Hashing power has been centralising. Now a worryingly small group of miners control a large share of the network’s hashing power. As far as we know none of them are using their hashing advantage maliciously, but the whole premise of bitcoin is we should only have to trust in cryptography, not people.
Ouroboros — Proof of Stake
What if we didn’t have to play this game? What if we could pick parties to create blocks in some other way? If so, we’d have a distributed ledger with each block producer using no more electricity than a typical web server. Make no mistake, if we could do this without sacrificing security it would be magical. In my opinion, it would be the greatest distributed ledger discovery since the original invention on bitcoin.
The claim is that Ouroboros can do it. It is one of a few protocols based on the idea that you can replace Proof of Work with Proof of Stake. That is, you can replace hashing power as the input to the block creator selection process with stake (the amount of currency you already own).
In the next article I’ll go into more detail about how Ouroboros and Ouroboros Praos use stake to determine the block producers.
