Category: blockchains

Consensus Mechanisms and Blockchain Immutability

As discussed previously on this blog, the proof of work (PoW) mechanism is used by Bitcoin and some other cryptocurrencies to enable network nodes to arrive at a consensus as to the valid public blockchain, and to ensure its immutability. There are, however, many other blockchains making use of alternative protocols. Examples include proof of stake (PoS), delegated proof of stake (DPoS), proof of burn (PoB), proof of authority (PoA), proof of exchange, proof of space, and others. There is considerable debate and strong feelings surrounding these issues, with many people arguing that one or other of these protocols is better than the alternatives. Often though, the specific implementation is as important as which category a particular chain’s mechanism fits into. So, here, I take a high-level approach and consider what we should be looking for in a consensus mechanism.

The following are required of a consensus mechanism:

  1. enable users to have their transactions included in blocks that are added to the blockchain.
  2. enable the network to come to a consensus as to the valid state of the blockchain.
  3. ensure immutability, so that once transactions have been confirmed on the blockchain, they are never altered or removed.

In addition, we can consider how efficiently the protocol achieves these goals. For example, how quick and how cheaply can transactions be made? Also, what is the cost of maintaining the network, both financially and environmentally? These are separate points though, which will also likely factor into the choice of a preferred protocol, but which I will not pursue here. Continue reading “Consensus Mechanisms and Blockchain Immutability” →

The Double Spend Problem

One major issue of decentralized digital currencies that was solved by the invention of Bitcoin and the blockchain, is the double spend problem. It is worth taking a step back to understand why we need blockchains in the first place, and why they are constructed in the way they are.

driving

To illustrate this, consider the following short tale. Alice is the owner of one bitcoin. We use public key cryptography to determine ownership, so that Alice is in possession of the private key for the bitcoin address. This means that she is able to prove ownership by digitally signing messages. Using the associated public key, anyone is able to verify the signatures and confirm that they have indeed been authorised by Alice.

First, Alice visits Bob, who has an item for sale. For the sake of the story, he is selling a car. He also agrees that one bitcoin is a fair price, so agrees to sell it to Alice. For her part, Alice creates a transaction transferring her bitcoin to Bob’s address and signs it. Bob now has a transaction giving him the bitcoin, and can prove to anyone that it has been authorised by Alice. So, he gives her the car and she drives away.

Next, Alice visits Carol, who is selling some jewellery. She agrees that one bitcoin is a fair price. So Alice again creates a transaction, paying the very same bitcoin to Carol’s address, and signs it. As happened with Bob, Carol knows that she can prove to anyone that the transaction has been authorised by Alice, so hands over the items. Alice drives off in her new car wearing her new designer jewellery.

double spend

Something has gone badly wrong here. Somehow, Alice has managed to spend the same bitcoin twice. Either, she has created new coins out of thin air, or at least one of Bob and Carol are going to lose possession their coins once the double spend is noticed. Either way, this approach would be very bad for the use of bitcoin as a medium of exchange.

How can the situation above be avoided? There is no way that Bob can know for sure that Alice will never sign any other transactions spending the coin that she has supposedly given him. As long as she remembers the private key, she can sign as many transactions with it as she likes. Similarly, Carol can never be sure what transactions Alice may have signed previously in private transactions with other parties.

To solve this problem, the initial transaction between Alice and Bob cannot be entirely private. The information has to be passed on to some other party or parties so that, later, Carol will be able to check with them to see if Alice does indeed still own the bitcoin.

For the centralized solution, this role could be played by Alice’s bank, who she must inform in order for Bob to accept the transaction. Later, Carol will only accept that her transaction is valid when Alice’s bank approves it. Of course, they will not do this, since Alice has already spent the bitcoin. This solution removes the freedom from Alice to double spend her coins by, instead, placing the trust in her bank that they would not authorise such a thing.

With a decentralized asset such as Bitcoin, we do not want to place trust to record all transactions with a single party. Instead, the transaction between Alice and Bob must be publicly announced to the network. Bob will only procede with the transaction after sufficient network nodes accept it as valid. Then, when Carol transmits her transaction, the network will not accept it, since it has already been recorded that Alice has spent her bitcoin.

This is not an easy thing to pull off in a decentralized network. All nodes must come to a consensus as to the precise state, and ownership of all bitcoin in existence. Alice could submit both transactions simultaneously to different nodes. When contradictory data is submitted, the network needs to agree which is correct and which will be rejected. Furthermore, the recorded information should be immutable, so that once a transaction is confirmed, then it can never be undone. We cannot assume that all nodes are good actors either. Alice, and her accomplices, could be actively participating in the network to spread false information in order to replace her original transaction with Bob by the later one with Carol. This behaviour of the system, where it continues to perform correctly even when individual components are unreliable, is known as Byzantine fault tolerance.

Blockchains are the solution employed by cryptocurrencies. As new transactions are submitted, additional blocks recording these are appended to the chain. The proof of work (or alternative) protocol is used to allow all nodes to come to consensus and ensure immutability of the blockchain. Individual actors are not easily able to change the state of already-confirmed transactions. To do such a thing would require the bad actors to all work together, and to gain an overall majority of the hashpower of the network. It should be noted that, very occasionally, double spends do occur. However, this only usually happens for transactions in blocks very near the top of the chain. Transactions which have been ‘confirmed’, by having several blocks added on top of them in the chain, are rarely if ever undone.

Proof of Work

bitcoin miners
A bitcoin mining farm.

Here’s an interesting experiment. Go to any Bitcoin block explorer, and look at some blocks. I chose the recent block numbers (or heights) 686710 through 686719. Next, look at their hashes. These are 256 bit numbers, usually expressed as length 64 hexadecimal strings and, for the heights I selected, they are:

000000000000000000044e63ddeb30d097e0b3ccd9cca2069137cb7297e424bd
0000000000000000000230e3d3dea9fbbb65723ca07a33c1b9b3089c994983d9
0000000000000000000074c2db5661b85341d10e106e2e773549a38e1ec4d16c
0000000000000000000688941d5031bd7167880b62b333f274e61cc8e381a028
00000000000000000004aa907cf6a1e9d44e60ec4638242be5d767a0df07f772
0000000000000000000cbf470e7497e224c598609d72c7921991aec121433883
0000000000000000000b1a18922652ebc989f899b59b050dd0a9f6a312fa5998
0000000000000000000655ec73770127f0d28937af9d6413237f46592a215340
0000000000000000000a6e8c366aa51b534ce5ab399e9e8c72df290873bb9f76
000000000000000000001ded7e91b5d29a08e8166044ef3fc06a0944e9877a95

One thing immediately stands out. All of the hashes start with a lot of zeros. Statistically, this should be virtually impossible unless the blocks have been chosen specifically to have such unlikely hash values. Interpreting the 256 bit strings as binary integers and dividing through by 2256 gives a number between 0 and 1 (which I will denote by p). For the hash of an arbitrary block of data, the p values will be uniformly distributed on the unit interval but, for the blocks above, they are:

height p
686710 3.56e-24
686711 1.81e-24
686712 3.77e-25
686713 5.40e-24
686714 3.86e-24
686715 1.06e-23
686716 9.18e-24
686717 5.24e-24
686718 8.63e-24
686719 9.67e-26

All of these values are miniscule, being less than about 10-23. By chance, this can only happen with probability 10-23 independently for each block. In fact, due to the pseudorandom properties of the SHA256 hash function, there is really only one way that this can happen. Many many different blocks must have been produced each time — of the order of 1023 of them — with only those having small hash values being transmitted to the network and accepted as valid.

This is, of course, the proof of work (POW) protocol, or consensus mechanism. It ensures that miners who create new Bitcoin blocks have to perform significant work, regulating the rate of block production and, vitally, ensuring immutability of the blockchain. Once a block has been added to the chain, and is already underneath several others (i.e., has several confirmations), then it is virtually impossible for it to be altered. This would require redoing all of the proof of work for the block in question and for all blocks above it, and doing this quickly enough to catch up with the main chain. Continue reading “Proof of Work” →

Block Hashes

The application of hash functions that I want to describe in this post, is as the glue used to hold together the blocks in a blockchain. Put another way, it is a hash function that puts the chain into blockchain.

blockchain

A blockchain is just an ordered sequence of blocks of data, with new blocks constantly getting added. While it needs to be flexible enough that new blocks can be added, it also requires immutability, so that already existing blocks are never altered. This is achieved with the help of hash functions. The idea is that every block contains a field which is set to the hash of the previous block. The initial or genesis block is the only one without a previous block to refer to so, for that one only, its previous block hash field is set to zero. An example of a blockchain containing only 5 blocks is shown in figure 1 below.

block hashes
Figure 1: A blockchain held together by a hash function.

The rectangles labelled Bn refer to the blocks, which contain data including one field taking the value h(Bn-1), which is the hash of Bn-1. Finally, we compute the hash of last block, h(B5), which serves as an identifier for the blockchain. In the case of Bitcoin, these are double (repeated) SHA256 hashes, and the blocks used here are actually the block headers. The header contains only a hash (specifically, the Merkle root) of the transactions instead of the transaction data itself, so is much smaller than the entire block. Otherwise, it makes no conceptual difference. Continue reading “Block Hashes” →

The UTXO Model

utxo

Any digital currency requires a method of representing quantities of the asset held by any parties, and transactions of these. The two main methods are the account model and the utxo (unspent transaction output) model, the latter of which is used by Bitcoin and which I will describe here.

I start with the idea of a transaction, which is simply a block of data containing a list of zero or more outputs and a list of zero or more inputs. Each of the outputs needs to contain a nonnegative number giving the associated quantity of the asset, and each of the inputs needs to contain a reference to the output of another transaction which it is spending. Note that it is not necessary for the inputs to contain the quantity, since this will be provided by the transaction output that it references. Each of the transaction outputs (txo) can only occur as an input of another transaction at most once. It must also be possible to arrange the transactions in order so that each input can only reference the output of an earlier transaction. By linking the inputs of each transaction with the referenced outputs, we obtain what is referred to as a directed acyclic graph (DAG).

transactions DAG
Figure 1: Transactions connected to form a directed acyclic graph.

Figure 1 gives an example with 6 transactions in total. The first two have no inputs but have outputs summing to 10, so both create 10 bitcoins out of nothing. The remaining transactions have the sum of their output quantities equal to the sum of their input quantities, so redistribute bitcoin but do not destroy or create any. Continue reading “The UTXO Model” →

Representing Value

rai stone
An 8 foot rai stone used as currency by inhabitants of the Yap islands. Image obtained from Wikipedia under GFDL license.

I start this blog by considering the following very basic question. How can we represent and transact value? A store-of-value asset or currency, whether it is Bitcoin, Ether, the US dollar, gold, or whatever else, has to have and maintain value to be useful. The dictionary definition of the word ‘value’ is not a lot of help: “the regard that something is held to deserve; the importance, worth, or usefulness of something”. This is rather circular. To be useful as a currency, we want an asset to have value but, to have value, it needs to be useful.

Consequently, I will take a slightly different tack. Rather than saying how to make something have value, I consider the bare minimum properties that an asset should have in order to be able to be used to represent value. Whether or not people then want to assign it some value is up to them.

I start with the idea of ownership. This does seem to be central to the ability to represent value. If you cannot exclusively own an asset, then you cannot use it to represent any value that you may want to store. If anyone can just take the asset from you, then can it ever be considered as yours in the first place?

Before anyone complains that this seems a rather individualistic idea of value (property is theft!), let me point a few things out. A public park is valuable, and is a community asset. However, this is a different type of value from that which is represented by money or a store-of-value asset. A park has utility. You can sit in it and enjoy the sun, kick a ball around, or go for a walk. When it comes to paying the park-keeper for cutting the grass, emptying the bins, cleaning out the public toilets, or other tedious tasks, then he or she will probably appreciate being paid in some asset which they can actually own and use to better the lives of themselves and their family. Similarly, the shops in your local high street may be valuable to the community, but if you were to simply pay the shelf-stackers by letting them visit the high street, which they can do anyway, then it would be difficult to find people to do the job. The value that we are interested in here is the more abstract kind, used as a medium of exchange or store-of-value, which can be held by an individual or organization with the aim of exchanging for something with utility when desired.

With the above explanations out of the way, any meaningful idea of ownership of a store-of-value asset or medium of exchange requires the following.

  • The holder of an asset should be able to prove ownership.
  • The holder should be able to transfer ownership to another party.

The second of these properties does imply the first since, transferring ownership will involve proving that you were the owner prior to the transaction. This is only half of the equation though. Just as important as what holding an asset allows you to do, is what not holding the asset stops you from doing.

  • No-one other than the holder of an asset should be able to prove ownership.
  • No-one other than the holder should be able to transfer ownership.
  • Supply of the asset should be limited.

Continue reading “Representing Value” →