Chain Reorganizations Part 2

Aventus Network
Aventus Network
Published in
8 min readApr 21, 2021

The following piece is authored by Alex Pinto, Engineering Manager at Aventus, written with the tech-interested Aventus community in mind.

Alex has broad experience in IT and Cyber Security, including software development, academic research, teaching, and management.

Forks‌ ‌and‌ ‌Finality‌ ‌in‌ ‌Blockchains‌ ‌

By Alex Pinto

The‌ ‌‌previous‌ ‌post‌‌ ‌of‌ ‌this‌ ‌series‌ ‌‌focussed‌ ‌on‌ ‌parallel‌ ‌realities,‌ ‌the‌ ‌multiverse‌ ‌and, ‌frankly,‌ ‌concepts‌ ‌more‌ ‌related‌ ‌to‌ ‌Quantum‌ ‌Physics‌ ‌than‌ ‌Computer‌ ‌Science.‌ ‌

Those‌ ‌reading looking for ‌ ‌Blockchain‌ ‌insights may‌ ‌have‌ ‌felt‌ ‌a‌ ‌reality‌ ‌shift.‌‌

There‌ ‌was‌, however, ‌a‌ ‌point‌ ‌to‌ ‌it,‌ ‌and‌ ‌I‌ ‌want‌ ‌to‌ ‌make‌ ‌that point ‌in‌ ‌this‌ ‌post.‌

The point is this: ‌That‌ ‌Blockchains,‌ ‌in‌ ‌a sense,‌ ‌do‌ ‌act‌ ‌like‌ ‌parallel‌ ‌universes.‌

‌Let‌ ‌me‌ ‌explain…

The‌ ‌Nature‌ ‌of‌ ‌Truth‌ ‌in‌ ‌a‌ ‌Blockchain‌ ‌‌

Let’s‌ ‌start‌ ‌with‌ ‌a‌ ‌question.‌ ‌‌

What‌ ‌is‌ ‌unique‌ ‌about‌ ‌blockchains‌ ‌that‌ ‌makes‌ ‌this‌ ‌technology‌ ‌so‌ ‌revolutionary?‌ ‌

In‌ ‌my‌ ‌view,‌ ‌it‌ ‌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‌ ‌nor‌ ‌delete‌ ‌it.‌ ‌ ‌‌

The‌ ‌power‌ ‌of‌ ‌the‌ ‌second‌ ‌point‌ ‌may‌ ‌not‌ ‌be‌ ‌immediately‌ ‌apparent,‌ ‌if‌ ‌you‌ ‌think‌ ‌of‌ ‌the‌ ‌blockchain‌ ‌as‌ ‌merely‌ ‌a‌ ‌database.‌ ‌But‌ ‌for‌ ‌a‌ ‌pointed‌ ‌rebuttal,‌ ‌think‌ ‌of‌ ‌George‌ ‌Orwell’s‌ ‌novel‌ ‌“1984”,‌ ‌where‌ ‌the‌ ‌three‌ ‌superstates‌ ‌routinely‌ ‌change‌ ‌the‌ ‌official‌ ‌history,‌ ‌redefining‌ ‌the‌ ‌account‌ ‌of‌ ‌past‌ ‌events‌ ‌to‌ ‌justify‌ ‌their‌ ‌current‌ ‌political‌ ‌situations.‌ ‌Not‌ ‌to‌ ‌mention‌ ‌the‌ ‌current‌ ‌tendency‌ ‌for‌ ‌fake‌ ‌news‌ ‌in‌ ‌today’s‌ ‌world.‌ ‌This‌ ‌is‌ ‌what‌ ‌blockchains‌ ‌avoid.‌ ‌

How‌ ‌Truth‌ ‌Is‌ ‌Created‌ ‌

‌The‌ ‌properties‌ of universality and permanence ‌don’t‌ ‌just‌ ‌happen‌ ‌by‌ ‌accident.‌ ‌The‌ ‌great‌ ‌innovation‌ ‌of‌ ‌blockchains‌ ‌is‌ ‌to‌ ‌show‌ ‌how‌ ‌they‌ ‌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‌ ‌the‌ ‌network‌ ‌members‌ ‌(aka‌ ‌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, and if they refuse to accept that reality, they will not be able to add blocks to the chain. They will also tend to be ignored by the other nodes when they vote. And so, a chain grows by the consensus of a majority, and peer pressure ensures that the added blocks become the Universal Truth. For this reason, this mechanism is called Consensus Protocol.

A consequence of the above is that to change the accepted truth nodes have to present an alternative history, 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, as I explain below. This is what makes truth immutable.

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 determined by 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, reputation lost can’t easily be regained.

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

Besides the Consensus Protocol, another pillar of Blockchains is the choice rule to resolve forks. Again, there are a few options.

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 is accepted as the Truth by a majority of nodes. And this can be replaced by another chain at some point in the future.

Because forks happen by a chain dividing in 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 lost and not appear in one of the chains although near the fork point many transactions will appear in both.

Consider for example:

A fork in the chain. After blocks A, B, C, two competing chain histories develop. Some, but not all, the transactions are the same in both chains, but they execute in different orders and their result may be different.

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 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 because a quantum experiment has an essentially random outcome, but rather because what has gone before is different.

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.

It’s in this sense I use the metaphor of quantum parallel worlds: in another universe, I will be a football player, or living off-grid, or whatever, as long as there is a different sequence of events in my history that would have led me down that path.

Although this seems extreme, big forks begin with a simple disagreement in one block. After that the whole history is different. If the non-canonical chain is not pruned by all the nodes of the network, 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 is picked as 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

In PoW chains like Bitcoin and Ethereum, this is never really guaranteed. 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 never be reverted 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, malicious voters will be challenged and lose 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.

Follow the Aventus blog and sign up for the Aventus newsletter at aubit.io to stay tuned for the closing episode of this series and more tech-led updates.

--

--

Aventus Network
Aventus Network

Aventus Network belongs to the new generation of composable blockchain networks built for scalability and interoperability.