A goal of a distributed consensus system is to provide some sort of guarantee that once a certain number of items have been added to a chain after block B, that the only way for B to somehow not end up in the long-term agreed-upon chain is for a large number of people to use a lot of money to undo all of the changes after B. This guarantee is called “Economic Finality”, and it turns out that at least in theory there is no guaranteed finality, rather,finality is always probabilistic.
Even in non-distributed system, there is no guarantee that any canonical ledger will remain so. Counter-examples of any attempted proof, however unlikely, can always be found. A general proof might go something like: “If everybody who knows the steps necessary for accessing the ledger are struck by lightning at the same time, then that ledger will cease to exist”.
Finality in Proof of Work
In proof of work (PoW), blocks are never completely guaranteed to remain on the blockchain, but in practice we say that 6 confirmations (that is, enough time passes such that the longest chain has height `height(B) + 6`) is enough for a client to feel confident that B will remain as part of the canonical chain.
This leads us to a more formalized, first flavor of economic finality (from PoS FAQ):
A block can be economically finalized if a sufficient number of validators have signed cryptoeconomic claims of the form “I agree to lose X in all histories where block B is not included”. This gives clients assurance that either (i) B is part of the canonical chain, or (ii) validators lost a large amount of money in order to trick them into thinking that this is the case.
Let’s see the unliklihood of an attacker who controls 25% of the network’s hashpower in successfully rewriting the history without B, which was first described here by Vitalik Buterin.
We can model the situation as a random walk, where the attacker begins with a score of -6 (corresponding to the number of blocks the attacker must outpace the rest of the network in order to have participated in the canonical chain without B).
At each step, the attacker has a 25% chance of adding the next block, and some other validator on the network has a 75% chance. The odds that the process ever reaches 0 is then (0.25 / 0.75)^6 ~= 0.00137.
As a sidenote, it is very unlikely that any validator would ever obtain enough hashpower to create an energy footprint equal to 25% that of Ireland.
Given an attacker’s control of hashrate a, we can see that (a / (1 – a))^N approaches, but never reaches 0, and there is never a complete guarantee that a block will remain part of the blockchain.