The Blockchain Immutability Myth

Where flexible thinking is preferable to dogmatism

“The highest good, than which there is no higher, is the blockchain, and consequently it is immutably good, hence truly eternal and truly immortal.” — Saint Augustine, De natura boni, i, 405 C.E. (with minor edits)

If you ask someone well-informed about the characteristics of blockchains, the word “immutable” will invariably appear in the response. In plain English, this word is used to denote something which can never be modified or changed. In a blockchain, it refers to the global log of transactions, which is created by consensus between the chain’s participants. The basic notion is this: once a blockchain transaction has received a sufficient level of validation, some cryptography ensures that it can never be replaced or reversed. This marks blockchains as different from regular files or databases, in which information can be edited and deleted at will. Or so the theory goes.

In the raucous arena of blockchain debate, immutability has become a quasi-religious doctrine – a core belief that must not be shaken or questioned. And just like the doctrines in mainstream religions, members of opposing camps use immutability as a weapon of derision and ridicule. The past year has witnessed two prominent examples:

• Cryptocurrency advocates claiming that immutability can only be achieved through decentralized economic mechanisms such as proof-of-work. From this perspective, private blockchains are laughable because they depend on the collective good behavior of a known group of validators, who clearly cannot be trusted.
• Scorn poured on the idea of an editable (or mutable) blockchain, in which retroactive modifications can be made to the transaction history under certain conditions. Mockers posed the question: What could possibly be the point of a blockchain if its contents can easily be changed?

For those of us on the sidelines, it’s fun to watch the mudslinging. Not least because both of these criticisms are plain wrong, and stem from a fundamental misunderstanding of the nature of immutability in blockchains (and indeed any computer system). For those short on time, here’s the bottom line:

In blockchains, there is no such thing as perfect immutability. The real question is: What are the conditions under which a particular blockchain can and cannot be changed? And do those conditions match the problem we’re trying to solve?

To put it another way, a blockchain’s transactions are not written into the mind of God (with apologies to Augustine above). Instead, the chain’s behavior depends on a network of corporeal computer systems, which will always be vulnerable to destruction or corruption. But before we get into the details of how, let’s proceed by recapping some basics of blockchains themselves.

Blockchains in brief

A blockchain runs on a set of nodes, each of which may be under the control of a separate company or organization. These nodes connect to each other in a dense peer-to-peer network, so that no individual node acts as a central point of control or failure. Each node can generate and digitally sign transactions which represent operations in some kind of ledger or database, and these transactions rapidly propagate to other nodes across the network in a gossip-like way.

Each node independently verifies every new incoming transaction for validity, in terms of: (a) its compliance with the blockchain’s rules, (b) its digital signature and (c) any conflicts with previously seen transactions. If a transaction passes these tests, it enters that node’s local list of provisional unconfirmed transactions (the “memory pool”), and will be forwarded on to its peers. Transactions which fail are rejected outright, while others whose evaluation depends on unseen transactions are placed in a temporary holding area (the “orphan pool”).

At periodic intervals, a new block is generated by one of the “validator” nodes on the network, containing a set of as-yet unconfirmed transactions. Every block has a unique 32-byte identifier called a “hash”, which is determined entirely by the block’s contents. Each block also includes a timestamp and a link to a previous block via its hash, creating a literal “block chain” going back to the very beginning.

Just like transactions, blocks propagate across the network in a peer-to-peer fashion and are independently verified by each node. To be accepted by a node, a block must contain a set of valid transactions which do not conflict with each other or with those in the previous blocks linked. If a block passes this and other tests, it is added to that node’s local copy of the blockchain, and the transactions within are “confirmed”. Any transactions in the node’s memory pool or orphan pool which conflict with those in the new block are immediately discarded.

Every chain employs some sort of strategy to ensure that blocks are generated by a plurality of its participants. This ensures that no individual or small group of nodes can seize control of the blockchain’s contents. Most public blockchains like bitcoin use “proof-of-work” which allows blocks to be created by anyone on the Internet who can solve a pointless and fiendishly difficult mathematical puzzle. By contrast, in private blockchains, blocks tend to be signed by one or more permitted validators, using an appropriate scheme to prevent minority control. Our product MultiChain uses a technique called “mining diversity” which requires a minimum proportion of the permitted validators to participate in order to create a valid chain.

Depending on the consensus mechanism used, two different validator nodes might simultaneously generate conflicting blocks, both of which point to the same previous one. When such a “fork” happens, different nodes in the network will see different blocks first, leading them to have different opinions about the chain’s recent history. These forks are automatically resolved by the blockchain software, with consensus regained once a new block arrives on one of the branches. Nodes that were on the shorter branch automatically rewind their last block and replay the two blocks on the longer one. If we’re really unlucky and both branches are extended simultaneously, the conflict will be resolved after the third block on one branch, or the one after that, and so on. In practice, the probability of a fork persisting drops exponentially as its length increases. In private chains with a limited set of validators, the likelihood can be reduced to zero after a small number of blocks.

Nonetheless, it’s important to remember that each node is running on a computer system owned and controlled by a particular person or organization, so the blockchain cannot force it to do anything. The purpose of the chain is to help honest nodes to stay in sync, but if enough of its participants choose to change the rules, no earthly power can stop them. That’s why we need to stop asking whether a particular blockchain is truly and absolutely immutable, because the answer will always be no. Instead, we should consider the conditions under which a particular blockchain can be modified, and then check if we’re comfortable with those conditions for the use case we have in mind.

Mutability in public chains

Let’s return to the two examples cited in the introduction, in which the doctrine of immutability has been used as a basis for ridicule. We’ll begin with the claim that the consensual validation procedures used in permissioned blockchains cannot bring about the “true immutability” promised by public chains.

This criticism is most easily addressed by pointing to the vulnerability of public blockchains themselves. Take, for example, the Ethereum blockchain, which suffered a devastating exploit in June 2016. Someone found a coding loophole in a smart contract called “The DAO”, in which almost $250 million had been invested, and began draining its funds at speed. While this clearly violated the intentions of the contract’s creators and investors, its terms and conditions relied on the mantra that “code is law”. Law or not, less than a month later, the Ethereum software was updated to prevent the hacker from withdrawing the cryptocurrency “earned”.

Of course, this update could not be enforced, since every Ethereum user controls their own computer. Nonetheless, it was publicly supported by Vitalik Buterin, Ethereum’s founder, as well as many other community leaders. As a result, most users complied, and the blockchain with the new rules kept the name “Ethereum”. A minority disagreed with the change and continued the blockchain according to its original rules, earning the title “Ethereum Classic”. A more accurate choice of names might be “Ethereum compromised” and “Ethereum the pure”. Either way, democracy is democracy, and (the pragmatic and popular) “Ethereum” is now worth over ten times (the idealistic but sidelined) “Ethereum Classic”.

Now let’s consider a less benevolent way in which public blockchain immutability can be undermined. Recall that block creation or “mining” in bitcoin and Ethereum uses a proof-of-work scheme, in which a mathematical problem must be solved in order to generate a block and claim its reward. The value of this reward inevitably turns mining into an arms race, with miners competing to solve the problems faster. To compensate, the network periodically adjusts the difficulty to maintain a constant rate of block creation, once every 10 minutes in bitcoin or 15 seconds in Ethereum.

In the last 5 years, bitcoin’s difficulty has increased by a factor of 350,000×. Today, the vast majority of bitcoin mining takes place on expensive specialized hardware, in locations where the weather is cold and electricity is cheap. For example, $1,089 will buy you an Antminer S9, which mines blocks 10,000 times faster than any desktop computer and burns 10 times more electricity. This is all a long way from the democratic ideals with which bitcoin was created, even if it does make the blockchain extremely secure.

Well, kind of secure. If someone wanted to undermine the immutability of the bitcoin blockchain, here’s how they would do it. First, they would install more mining capacity than the rest of the network put together, creating a so-called “51% attack”. Second, instead of openly participating in the mining process, they would mine their own “secret branch”, containing whichever transactions they approve and censoring the rest. Finally, when the desired amount of time had passed, they would anonymously broadcast their secret branch to the network. Since the attacker has more mining power than the rest of the network, their branch will contain more proof-of-work than the public one. Every bitcoin node will therefore switch over, since the rules of bitcoin state that the more difficult branch wins. Any previously confirmed transactions not in the secret branch will be reversed, and the bitcoin they spent could be sent elsewhere. 

By now, most bitcoin believers will be laughing, because I wrote “install more mining capacity than the rest of the network put together” as if this is trivial to achieve. And they have a point, because of course it’s not easy, otherwise lots of people would already have done it. You need a lot of mining equipment, and a lot of electricity to power it, both of which cost a ton of money. But here’s the inconvenient fact that most bitcoiners brush over: For the government of any mid-size country, the money required is still small change.

Let’s estimate the cost of a 51% attack which reverses a year of bitcoin transactions. At the current bitcoin price of $1500 and reward of 15 bitcoins (including transaction fees) per 10-minute block, miners earn around $1.2 billion per year ($1500 × 15 × 6 × 24 × 365). Assuming (reasonably) that they are not losing money overall, or at least not losing much, this means that total miner expenses must also be in the same range. (I’m simplifying here by amortizing the one-time cost of purchasing mining equipment, but $400 million will buy you enough Antminer 9s to match the current bitcoin network’s mining capacity, so we’re in the right ball park.)

Now think about the reports that bitcoin is being used by Chinese citizens to circumvent their country’s capital controls. And consider further that the Chinese government’s tax revenues are approximately $3 trillion per year. Would a non-democratic country’s government spend 0.04% of its budget to shut down a popular method for illegally taking money out of that country? I wouldn’t claim that the answer is necessarily yes. But if you think the answer is definitely no, you’re being more than a little naive. Especially considering that China reportedly employs 2 million people to police Internet content, which totals $10 billion/year if we assume a low wage of $5,000. That puts the $1.2 billion cost of reversing a year of bitcoin transactions in perspective.

Even this analysis understates the problem, because the Chinese government could undermine the bitcoin network much more easily and cheaply. It appears that the majority of bitcoin mining takes place in China, due to low-cost hydroelectric power and other factors. Given a few tanks and platoons, China’s army could physically seize these bitcoin mining operations, and repurpose them to censor or reverse transactions. While the wider bitcoin world would undoubtedly notice, there’s nothing it could do without fundamentally altering the governance structure (and therefore nature) of bitcoin itself. What was that about censorship free money?

None of this should be construed as a criticism of bitcoin’s design, or a prediction that a network catastrophe will actually happen. The bitcoin blockchain is a remarkable piece of engineering, perhaps even perfect for the purpose its creator(s) had in mind. And if I had to put money on it, I would bet that China and other governments probably won’t attack bitcoin in this way, because it’s not in their ultimate interest to do so. More likely, they’ll focus their wrath on its more untraceable cousins like Dash, Zcash and Monero.

Nonetheless, the mere possibility of this form of interference puts the cryptocurrency immutability doctrine in its place. The bitcoin blockchain and its ilk are not immutable in any perfect or absolute sense. Rather, they are immutable so long as nobody big enough and rich enough decides to destroy them. Still, by relying on the economic cost of subverting the network, cryptocurrency immutability satisfies the specific needs of people who don’t want to trust governments, companies and banks. It may not be perfect, but it’s the best they can do.

Rewriteable private chains

Now let’s move on to private blockchains, designed for the needs of governments and large companies. We can begin by noting that, from the perspective of these organizations, immutability based on proof-of-work is a commercial, legal and regulatory non-starter, because it allows any (sufficiently rich) actor to anonymously attack the network. For institutions, immutability can only be grounded in the good behavior of other similar institutions, with whom they can sign a contract and sue if need be. As a bonus, private blockchains are far less costly to run, since blocks only need a simple digital signature from the nodes that approve them. So long as a majority of validator nodes are following the rules, the end result is stronger and cheaper immutability than any public cryptocurrency can offer.

Of course, immutability is still easy to undermine if all the participants in a chain decide to do so together. Let’s imagine a private blockchain used by six hospitals to aggregate data on infections. A program in one hospital writes a large and erroneous data set to the chain, which is a source of inconvenience for the other participants. A few phone calls later, the IT departments of all the hospitals agree to “rewind” their nodes back one hour, delete the problematic data, and then allow the chain to continue as if nothing happened. If all the hospitals agree to do this, who’s going to stop them? Indeed, apart from the staff involved, who will even know that it happened? (It should be noted that some consensus algorithms like PBFT don’t provide an official mechanism for rollbacks, but this doesn’t help with governance since nodes are still free to bypass the rules.)

Now consider a case where most of a private blockchain’s participants agree to rewind and remove some transaction, but a few withhold their consent. Since every organization’s node is under its ultimate control, nobody can force the minority to join the consensus. However, by sticking to their principles, these users will find themselves on a fork being ignored by everyone else. Like the virtuous proponents of Ethereum Classic, their place in heaven may well be assured. But back here on earth, they will be excluded from the consensus process for which the chain was deployed, and might as well give up completely. The only practical application of transactions outside the consensus is to serve as evidence in a court of law.

With this in mind, let’s talk about the second case in which the doctrine of blockchain immutability has been used to ridicule ideas. Here, we’re referring to Accenture’s idea of using a chameleon hash to enable a block buried deep in a chain to be easily replaced. The primary motivation, as described by David Treat, is to allow an old problematic transaction to be quickly and efficiently removed. Under the scheme, if a block substitution does occur, a “scar” is left behind which all participants can see. (It should be noted that any later transactions that depend on the deleted one would need to be removed as well.)

It’s hard to overstate how many people poured scorn on this idea when it was announced. Twitter and LinkedIn were aghast and aflutter. And I’m not just talking about the crypto crowd, which takes sporting pleasure in mocking anything related to enterprise blockchains. The idea was broadly slammed by private blockchain advocates as well.

And yet, under the right conditions, the idea of allowing blockchains to be modified retroactively via chameleon hashes can make perfect sense. To understand why, we begin with a simple question: in this type of blockchain, who would actually have the power to replace old blocks? Clearly, it can’t be any unidentified network participant, because that would render the chain ungovernable.

The answer is that a chameleon hash can only be used by those who hold its secret key. The key is required to enable a new version of a block, with different transactions, to be given the same chameleon hash as before. Of course, we probably don’t want centralized control in a blockchain, so we can make the scheme stronger by having multiple chameleon hashes per block, each of whose key is held by a different party. Or we might use secret sharing techniques to divide a single chameleon hash key between multiple parties. Either way, the chain can be configured so that a retroactive block substitution can only occur if a majority of key holders approve it. Is this starting to sound familiar?

Allow me to render the parallel more explicit. Let’s say that we share control over chameleon hashes between those same validating nodes which are responsible for block creation. This means that an old block can only be replaced if a majority of validating nodes agree to do so. And yet, as we discussed earlier, any blockchain can already be retroactively modified by a majority of validating nodes, via the rewind and replay mechanism. So in terms of governance, chameleon hashes subject to a validator majority make no difference at all.

If so, why bother with them? The answer is: performance optimization, because chameleon hashes allow old blocks to be substituted in a chain far more efficiently than before. Imagine that we need to remove a transaction from the start of a blockchain that has been running for 5 years. Perhaps this is due to the European Union’s right to be forgotten legislation, which allows individuals to have their personal data removed from companies’ records. Nodes can’t just wipe the offending transaction from their disks, because that would change the corresponding block’s hash and break a link in the chain. The next time the blockchain was scanned or shared, everything would fall apart.

To solve this problem without chameleon hashes, nodes would have to rewrite the early block without the problematic transaction, calculate the block’s new hash, then change the hash embedded in the next block to match. But this would also affect the next block’s own hash, which must be recalculated and updated in the subsequent block, and so on all the way along the chain. While this mechanism is possible in principle, it could take hours or days to complete in a blockchain with millions of blocks and transactions. Even worse, while engaged in this process, a node may be incapable of processing new incoming network activity. So chameleon hashes provide a far more computationally efficient way to achieve the same goal. If you imagine a bad transaction as a rock buried many miles underground, chameleon hashes can teleport the rock to the surface, instead of making us dig all the way down, retrieve the rock, and fill in the hole.

Immutability is nuanced

By reviewing the risks of proof-of-work blockchains and the technical value of chameleon hashes, I hope to have convinced you that blockchain immutability is far more nuanced than a “yes or no” question. To quote Simon Taylor quoting Ian Grigg, the question must always be “who are you and what do you want to achieve?”

For cryptocurrency believers who want to avoid government-issued money and the traditional banking system, it makes perfect sense to believe in a public proof-of-work blockchain, whose immutability rests on economics rather than trusted parties. Even if they must live with the possibility of a large government (or other wealthy actor) bringing down the network, they can take solace in the fact that this would be a painful and expensive operation. And no doubt they hope that cryptocurrencies will only get more secure, as their value and mining capacity continues to grow.

On the other hand, for enterprises and other institutions that want to safely share a database across organizational boundaries, proof-of-work immutability makes no sense at all. Not only is it astoundingly expensive, but it allows any sufficiently motivated participant to anonymously seize control of the chain and censor or reverse transactions. What these users need is immutability grounded in the good behavior of a majority of identified validator nodes, backed by contracts and law.

Finally, for most permissioned blockchain use cases, we probably don’t want validator nodes to be able to easily and cheaply substitute old blocks in the chain. As Dave Birch said at the time, “the way to correct a wrong debit is with a correct credit”, rather than pretending that the debit never took place. Nonetheless, for those cases where we do need the extra flexibility, chameleon hashes help make blockchains a practical choice.