Let’s get consensus! (Part I)
One of the terms that comes up a lot when reading about the blockchain is the ‘consensus algorithm’ and how they can be different: proof of work, stake, consensus.
So, let’s dive into what these are, how they work, and some of the benefits of each.
What is a consensus algorithm?
A consensus algorithm is a set of agreements that allows people, or computers to agree on the current state of data entries, and changes (it can be more complicated, but let’s go with this for now) — without having a trusted third party tell us about it.
We are familiar with many common such algorithms in our common world. One common example is when we vote by a show of hands to elect a leader. In theory, the majority winner is accepted by all, and if one person tries to disrupt the election, or disputes the validity, the other people do not accept this.
With computers, to enable blockchain technologies, the problem is similar. We want a group of computers/servers to come to agreement on current state and a change in state. For example, the state may start out as:
Then, there can be a change in some way, so that:
John sends 2 to Shelly.
Now, as much as this example seems small, there’s a lot in it. Typically, a trusted third party, like a bank, would record this and manage the changes and updates. However, in blockchain technologies, there is no trusted third party and:
Any node (computer) can record information
- Any node can enter/exit at any time
- Any malicious node cannot stop the network (so long as 50% or more by some measures are honest)
We could imagine the challenges that come up with the John/Shelly transaction, among these are:
- Which node or nodes can I send this transaction record to?
- How can the node know that it is a legitimate request and not made by an imposter?
- How can the nodes share all of the legitimate transaction records and current state?
- How can there be economic incentives for nodes to bother being on the network in the first place?
- What stops a node from sending false/illegitimate transactions?
The consensus algorithm is designed to solve this.
So, let’s explain how one of these consensus algorithms. works, since this can be a little hard to envision.
And, to get started, we begin with a building block called a cryptographic hash function.
Now the cryptographic hash function is set of math and logic instructions that can take a block of data and output a fixed (such as 256) unique number. Hash functions are sometimes called checksums, because when sending a block of data, it’s common to send the data and the hash/checksum to make sure that not one bit is out of place.
Hash functions are also designed to be random, meaning that over a set of data, all numbers are equally common and despite what output has already occurred, the next output of any potential number is equally likely.
The cryptographic part of a hash function means that it is one-way, or while it is very fast to take a chunk of data and hash it for a 256 bit number, it is very hard to go the other way – which is taking a 256 bit number and finding a chunk of data which hashes to it.
In fact, ideally, the only way to do this is to randomly try numbers until you find one. And, since there are 2^256 possibilities, the entire computing capacity of world could not do this in the lifetime of many, many universes. (Yes, 2^256 is a massive number)
Ok…let’s do a proof of work algorithm now. Let’s do an example.
Email spam is a problem. One solution that has been proposed is to have senders pay something small (like a penny), which would bankrupt mass spenders. This is problematic requiring payment systems, money, etc. — so another proposal is to use a proof of work protocol, requiring senders to prove they have done work, before a message would be accepted.
Here’s how it could work:
Sender send request to receive mail to the recipient.
Recipient sends the sender a random 128 bit number and request sender to find another 128 bit number (called a nonce), that when concatenated to the end, will result in hash with 10 leading zeros.
Sender start trying random numbers to concatenate to the end of the nonce and hashes the united value until finding a number with 10 leading zeroes. On average, the sender would have to try 2^10 numbers to find such number.
Sender send the response to the recipient, who verifies it is correct, and then receives the email from the sender.
And, thus we have a proof of work algorithm. You would calibrate the number of leading zeroes requested so the work burden is minimal for sending one-off emails, but would quickly overload mass spammers. In addition, you would calibrate the number of leading zeroes as computer capacity increase, and every leading zero makes the work required twice as much. (In fast, there are ways to be even more precise, but let’s ignore for now)
Let’s use a proof of work algorithm for consensus:
Bitcoin uses a proof of work algorithm very similar to the anti-spam example above.
In bitcoin, nodes (or miners) receive transactions from wallets, which are computer software that can use digital signatures to properly sign that a transaction is taking place.
In our example, this would be:
John -> 2 -> Shelly (signed by John). (We can go into digital signatures at another time).
John’s wallet would generate this and broadcast it to many miners.
Each miner collects many transactions and puts them into a block. Then, the miner hashes the block, concatenates with a hash of the previous block, and then looks for an additional number to concatenate that when the whole thing is hashed, results is an agreed upon number of leading zeroes (slightly more precise, but this is close).
When a miner finds a winning number, the miner quickly broadcasts the result to the other miners. They all quickly check, verify the correctness and start building a new block and repeating the process. As compute power increases, such that blocks are being solved in less than 10 minutes, they agree to increase the difficulty (such as adding another 0).
In this way, they all agree that winning the block creates an authoritative record that they all act on.
And, how do they make money doing this – two ways: 1) they can charge fees to the wallet holder, and 2) one of the transactions they are allowed to put in is 6.5 BTC -> miner – thus mining bitcoin!
What are some downsides of this type of protocol? Well, for one, all the hashing consumes huge amounts of electricity and capital resources, without actually doing anything useful, accept coming to consensus – very expensive way to do this.
In addition, if over 51% of the compute power is compromised, the entire network would fail, and it can be slow as transactions can take up to 10 minutes or more to clear.
So, there are some solutions to these challenges, which we’ll get into next time…