This is the second post in a series about Finality in blockchains. It was originally published in the Aventus blog. This is a good time to repost a revision on my blog.
The previous post of this series focussed on parallel realities, the multiverse and, frankly, concepts more related to Quantum Physics than Computer Science. Those readers of mine looking for Blockchain insights may have felt a sudden reality shift. This post aims to correct that feeling by clarifying the main point of that post, that is:
Blockchains act a lot like parallel universes.
Let me explain…
The Nature of Truth in a Blockchain
Since the first blockchains emerged, many people have questioned their purpose or competitive advantage.
So it is worth asking first what is unique about blockchains that make this technology so revolutionary. Others have argued for decentralization, its immutability or ledger-like nature. I would like to put that in more understandable terms.
In my view, the main innovation of blockchain is the construction of absolute truth. There are two main aspects I want to focus on:
●It is universal — A fact in the blockchain is true and unquestionable.
●It is permanent — Once you record a fact (eg a transaction) on a blockchain, it’s “set in stone”. You can’t change it or delete it.
The power of the second point may not be immediately apparent if you think of the blockchain as merely a database. But you only have to think about fake news, the shifting reality under our feet where it feels we can’t trust any source of news to suddenly appreciate the importance of permanence. If you can change which facts are true, you can rewrite history and manipulate entire populations towards a dystopic worldview akin to 1984 where the past no longer objectively exists.
How Truth Is Created
The properties of universality and permanence don’t just happen by accident. Blockchains rules show how these can be enforced. Mostly, it comes down to one mechanism: how to add one block to the chain.
This is the result of a distributed protocol whereby network members grow the chain one block at a time. Blocks numbers are sequential and become the notion of “time” in a blockchain, like time in Lamport’s Logical Clocks.
For a block to be added to the chain, a majority of nodes have to agree. They communicate to other nodes that a new block has been added and is now the head of the chain.
Disagreeing nodes will be caught in a minority. If they refuse to accept that reality, they will lose the ability to add blocks to the chain. Also, other nodes will ignore them when they vote. This means a chain grows by the consensus of a majority, and peer pressure ensures that the added blocks become the Universal Truth.
The consequence is that to change the accepted truth, nodes have to present an alternative history. This requires a different set of blocks that a majority of the nodes agree to. Blockchains include protections to ensure doing this is very hard or undesirable. This is what makes truth immutable.
To create a block you need to own some limited resource
There are a few variants of blockchain technology that can achieve this, based on different limited resources. The main examples are:
- Proof-of-Work (PoW): the limited resource is computing power, ultimately money. You need the computing power of at least half the network to create a false update.
- Proof-of-Stake (PoS): the limited resource is voting stake. Once again, this is most commonly a function of money. You need at least half the invested capital staked to vote for a new chain.
- Proof-of-Authority (PoA): the limited resource is reputation. A single authority can theoretically replace the history of the chain, but such an authority is an Authority by some reason: it has some real-world trust-capital (reputation) that it wants to preserve. Although hard to quantify, it is very difficult to regain lost reputation.
When Does Truth Become Real?
All that said, there is a funny thing with truth in a blockchain. Truth does not happen at once. It forms over time. The picture I painted above, where you add a block to the chain one at a time, is the ideal scenario.
In reality, disconnections happen, as well as timeouts and delays caused by distance and congestion. The set of nodes each member sees changes continually, nodes may become separated from another part of the chain and each subset ends up building parallel competing histories.
There is no real conflict while the sets of nodes remain disjoint, but when they reconnect all which version of Truth should they choose?
Fork Resolution
Blockchains need some rule to choose a single version of Truth when forks happen. This is the second pillar of Blockchains, besides the Consensus Protocol.
Typically, PoW chains like Bitcoin and Ethereum will use the “longest chain wins” rule, picking the chain with more blocks. Another option is to use the one with more effort invested in it, measured by the difficulty of mining each block.
Other technologies can have different rules, like the chain promoted by the most reputable authority. At any moment in time there is a canonical chain that a majority of nodes considers Truth. But this can be replaced by another chain at some point in the future.
Because forks happen when a chain divides into two alternatives at some point, competing chains will always have a common prefix of blocks, ultimately going down to a single genesis block. But in different chains, different transactions appear in each block. Some transactions may even be absent from one of the chains.
Consider for example:
Parallel Worlds and Parallel Timelines
The explanation above is the key to the parallel universes metaphor. We can see each version of the blockchain as the history of one universe. A different chain gives a different account of the historical events after the fork point.
Like a newspaper, each block is just a neat packaging for events that happened over the last hour, day, or week, etc. What matters is what occurred. This is recorded in transactions, and because these happen in a different order in each chain, even though they are alike and have the same inputs, the state when they are executed is different and so the result may be different.
Unlike quantum universes, there is no randomness in blockchains. The reason the result of a transaction differs is not that a quantum experiment has an essentially random outcome, but rather because what has gone before is different.
An Example
For a classic example, consider a bank account with £100 and two transactions: Tx A credits £150, Tx B debits £200. If A is executed before B, both will succeed. If B happens before, then it will be rejected, because there is not enough money to withdraw. Tx A could then fail if the bank’s rules determine that an overdrawn account is temporarily suspended; or succeed, in a universe where the bank does not impose such rules.
In both chains, these transactions refer to the same objects, so in effect, a different sequence of transactions just tells a different history of that account. But, importantly, both histories are equally valid, and both are internally consistent.
Big forks begin with a simple disagreement in one block. After that the whole history is different. If the network nodes don’t prune the non-canonical chain, a schism will form, with a section of the community supporting and growing the alternative chain. Eventually, where there will be two communities, two separate chains and two complete histories of events. Transactions in one will no longer refer to the other, although they’ll both share some common distant history.
For a real-world blockchain example, see Ethereum (ETH) and Ethereum Classic (ETC). And for real real-world examples… well, look down the evolution of species, languages, the emergence and disappearance of nations, etc.
Models of Finality
In a healthy blockchain, forks don’t turn into alternative competing realities. One chain becomes the canonical one, the truth recognized by the community. Others are pruned and forgotten. Nodes who don’t acknowledge the canonical chain relinquish the community.
Probabilistic Finality
PoW chains like Bitcoin and Ethereum can’t really give this guarantee. There is always the possibility of some group of nodes gathering enough computing power to produce a new longer chain that wholesale replaces the canonical one.
This is like a hostile takeover, but because the attackers would have to create more blocks than the canonical one, as time passes the difficulty of doing so increases exponentially and the probability of happening decreases.
In this case, we say finality is probabilistic: given a certain number of blocks after a block is recorded, we can assume that block will be permanent and its transactions are final.
Economic Finality
Another notion is that of economic finality, more used in PoS chains. A creator proposes a block and nodes vote for its correctness. To subvert a chain in this model, an attacker needs to gather enough votes to prevent the inclusion of a good block (incorrect vote) or authorize the creation of a parallel chain, with different blocks at the same height (equivocation) (see this FAQ, “What is “economic finality” in general?”).
If anyone finds these discrepancies, they can challenge the malicious voters and take their stake. Stakes are tuned so that this penalty makes an attack economically so expensive as to be unlikely.
Absolute Finality
This is the kind of finality we have in Substrate-based chains, like Polkadot, Kusama and our very own AvN.
It stems from a technological decision in the chain’s protocols that, after a given point, the chain is immutable. Periodically, a dedicated distributed protocol determines the number of the last finalized block. Blocks after this level can still be reorganized, and have different transactions in an alternative chain, but those before are immutable forever.
Wrapping It Up
So, that turned out to be a long-ish explanation of the issues of finality and forks in blockchains. Next time, I will focus on the time-travelling bug and how we fixed it in the AvN. It is the sort of thing everyone building a blockchain has to contend with because forks are a common occurrence and a fact of life when dealing with blockchains.
I hope you enjoyed this post. Let me know your opinions below.