On Not Being Immutable

Economist 2/1/25

Regulation of cryptocurrencies was an issue in last November's US election. Molly White documented the immense sums the industry devoted to electing a crypto-friendly Congress, and converting Trump's skepticism into enthusiasm. They had two goals, pumping the price and avoiding any regulation that would hamper them ripping off the suckers.

Back in November of 2022 I added an entry to this blog's list of Impossibilities for The Compliance-Innovation Trade-off from the team at ChainArgos. It started:

tl;dr: DeFi cannot be permissionless, allow arbitrary innovation and comply with any meaningful regulations. You can only choose two of those properties. If you accept a limited form of innovation you can have two-and-a-half of them.

Fundamental results in logic and computer science impose a trade-off on any permissionless system’s ability to both permit innovation and achieve compliance with non-trivial regulations. This result depends only on long-settled concepts and the assumption a financial system must provide a logically consistent view of payments and balances to users.

This is a semi-technical treatment, with more formal work proceeding elsewhere.

Two years later, the "more formal work" has finally been published in a peer-reviewed Nature Publishing journal, Scientific Reports, which claims to be the 5^th most cited journal in the world. Jonathan Reiter tells me that, although the publishing process took two years, it did make the result better.

Below the fold I discuss Tradeoffs in automated financial regulation of decentralized finance due to limits on mutable turing machines by Ben Charoenwong, Robert M. Kirby & Jonathan Reiter.

This team were pioneers in applying fundamental computer science theorems to blockchain-based systems, starting in April 2022 with The Consequences of Scalable Blockchains in which they showed that implementing an Ethereum-like system whose performance in all cases is guaranteed to be faster than any single node in the network is equivalent to solving the great unsolved problem in the theory of computation, nicknamed P vs. NP. And thus that if it were implemented, the same technique could break all current cryptography, including that underlying Ethereum.

But, I believe, they were not the first. That appears to have been Tjaden Hess, River Keefer, and Emin Gün Sirer in Ethereum's DAO Wars Soft Fork is a Potential DoS Vector (28^th June 2016), which applied the "halting problem" to "smart contracts" when analyzing possible defenses against DOS attacks on a "soft fork" of Ethereum proposed in response to "The DAO".

Charoenwong et al's abstract states:

We examine which decentralized finance architectures enable meaningful regulation by combining financial and computational theory. We show via deduction that a decentralized and permissionless Turing-complete system cannot provably comply with regulations concerning anti-money laundering, know-your-client obligations, some securities restrictions and forms of exchange control. Any system that claims to follow regulations must choose either a form of permission or a less-than-Turing-complete update facility. Compliant decentralized systems can be constructed only by compromising on the richness of permissible changes. Regulatory authorities must accept new tradeoffs that limit their enforcement powers if they want to approve permissionless platforms formally. Our analysis demonstrates that the fundamental constraints of computation theory have direct implications for financial regulation. By mapping regulatory requirements onto computational models, we characterize which types of automated compliance are achievable and which are provably impossible. This framework allows us to move beyond traditional debates about regulatory effectiveness to establish concrete boundaries for automated enforcement.

They summarize the fundamental problem for the automation of DeFi regulation:

DeFi features some computationally challenging properties: (1) Turing-complete programming, (2) permissionless access to both transact and publish code and (3) selectively immutable code. The permissionless mutability of the system combined with the Turing completeness motivates our inquiry. A system running Turing-complete code where updates can be published permissionlessly cannot make any guarantees about its future behavior, a conclusion from early work on Universal Turing Machines (UTM).

Despite this, they show that if it is possible to enforce less-than-Turing-complete programming:

it is possible to construct both (1) classes of algorithms that can make credible promises and (2) restricted update mechanisms that enable credible promises. In other words, DeFi platforms can provide compliant services like traditional centralized providers through fully automatic mechanisms.

What exaxctly do they mean by "compliant"?

Consider an economy modeled as a Turing Machine, where the machine’s state corresponds to the state of the real economy. We formalize compliance as a property of system state transitions that can be verified mechanically, following Theorem 5.8.5 of Savage. Specifically, a compliant system is one where no sequence of permitted operations can result in a state that violates predefined regulatory constraints set by an external regulator.

They translate this into economic terms:

For example, if a regulation prohibits transactions with certain addresses, compliance means no sequence of permitted operations can transfer value to those addresses, either directly or indirectly. Similarly a regulator may impose requirements on intermediaries transacting in certain assets or products akin to depository receipts for those assets. Compliance would then require ensuring one does not unknowingly transact in “products akin to depository receipts” for a given list of assets.

Because they model regulated systems in terms of states and the transitions between them, they can apply results from compputer science:

This formulation maps to well-known results in computability, such as the Halting Problem and the more general impossibility known as Rice’s Theorem: No algorithm exists to determine from the description of a [Turing Machine] whether or not the language it accepts falls into any proper subset of the recursively enumerable languages. In other words, we cannot categorize arbitrary programs into specific subsets automatically and reliably. In financial regulation, the canonical “proper subset” is a ban on interacting with a given address: interactions involving a banned address are forbidden, and the acceptable subset of states includes no such transfers.

They proceed to use cryptocurrency "mixers" as an example. They explain that Rice's Theorem means that because any general description of "mixers" defines a "proper subset" of all programs, and thus there is no automatic or reliable method by which a "smart contract" can be assessed against the general description.

Of course, as Justice Potter Stewart famously said "I know it when I see it". Human regulators will have no difficulty in recognizing a "smart contract" as a mixer, if only because in order to function it needs liquidity. To attract it the "smart contract" needs to advertise its service. So can the regulators ban interactions with the specific addresses of the mixers they recognize? Charoenwong et al make two arguments

First, this severely limits the regulator’s power from regulating a mutable set of protocols to only specific ones. In other words, what is often called “principles-based” regulations (as opposed to rules-based regulations) are impossible. We cannot ban “mixers” generally – we can only ban “mixers A, B and C.” In some sense, this is akin to banning specific means of murder rather than simply banning murder, no matter the means.

Then they introduce the time element inherent in human regulation:

Second, and more importantly, we cannot enforce even these more straightforward rules reliably. Consider these steps:

1. Deploy a new, confusingly-coded, “mixer” labeled X
2. Send funds to the mixer X
3. Withdraw from the mixer X and feed into the mixer A
4. Withdraw from the mixer A and feed into the mixer X
5. Withdraw from the mixer X and spend freely

This procedure works because we cannot identify arbitrary mixers, so we are free to deploy and then use them before they get put on the banned list. As a result, the regulator cannot even ban all interaction with enumerated mixers – it can only reliably ban some forms of interaction. This result is a severe limit on regulatory power.

If we consider that compliance exists in an automated form, operating on publicly available data in real-time, anyone accepting that final transfer must operate in a compliant fashion. If, instead, the plan is to decide these things later based on non-mechanical analysis, we are simply operating a conventional legal system with some more computers involved. Concretely, if that last transfer can be ruled illegal after the fact, it was never an automated financial system.

This result generalizes to services other than mixers. Rice's Theorem means it isn't possible to ban a class of services, and banning individual services identified by humans will always be behind the curve.

The authors illustrate the application of their result with real-world examples of regulatory failure:

These case studies-The DAO, Beanstalk Finance, Compound, Terra/LUNA, and MakerDAO-collectively illustrate the practical manifestations of our paper’s theoretical findings. Each example demonstrates a different facet of the challenges in implementing reliable, automated compliance mechanisms in decentralized, Turing- complete systems. From governance attacks to stablecoin collapses and liquidation issues, these incidents underscore the impossibility of guaranteeing specific regulatory outcomes without compromising system flexibility or introducing external interventions.

The authors argue that there are two ways to construct a system that does allow automated regulation, by making it permissioned rather than permissionless, or by enforcing a non-Turing-complete language for the "smart contracts". In practice many cryptocurrencies are permissioned — in Decentralized Systems Aren't I pointed out that:

The fact that the coins ranked 3, 6 and 7 by "market cap" don't even claim to be decentralized shows that decentralization is irrelevant to cryptocurrency users.

There are many examples of cryptocurrency systems that claim to be decentralized but are actually permissioned. Patrick Tan described one in Binance Built a Blockchain, Except it Didn’t:

For all its claims of promoting decentralization, Binance runs two “blockchains” that are not just highly centralized, but regularly alter history, undermining one of the core tenets of the blockchain — immutability.

The authors' example of a non-Turing-complete language is:

Consider a scripting language where we cannot have variables. A simple “splitting the tab” contract might look like:
This is dangerous if we have a regulation that certain addresses cannot be paid. The issues raised surrounding the DAO hack, discussed above, apply here. But what if the only way to transfer a token is to call SendTo and that function looks like:
There is no issue if a function only calls RealSendTo from SendTo. In such cases, the regulator’s responsibility is to maintain the BannedList, and the system is permissioned.

Their example of a system that is not-Turing-complete is not useful, because it requires BannedList to be a constant. As they point out, if the system is to be useful, BannedList must be a variable that is updated by the regulator, and thus the system is permissioned. It may well be that, because BannedList is a variable, that the system is Turing-complete after all. I can't do the analysis to determine if this is the case, but it is known that even a small number of variables makes a system Turing-complete.

Thus the paper is somewhat misleading, in the sense that it reads as if regulated systems can be either permissioned or not-Turing-complete, but it fails to provide an example of a system that is permissionless and not-Turing-complete. The example that looks as if it is going to be not-Turing-complete but permissionless seems to be permissioned and not-Turing-complete.

I would argue somewhat differently:

• Charoenwong et al show that a permissionless, Turing-complete system cannot be regulated.
• In the real world no-one is going to cripple their system by making it not-Turing-complete.
• Even if a not-Turing-complete system could be built it isn't clear that it would be useful.
• In essence, the regulatory act of enforcing that a system is, and remains, not-Turing-complete is permissioning the system.
• Thus in practice permissionless systems cannot be regulated.

JPMorgan

While Charoenwong et al's paper is of theoretical interest, in the two years since their initial post it has been overtaken by events. Craig Coben asks Has Michael Saylor’s ‘infinite money glitch’ run into a hitch?:

Reflexivity has been MicroStrategy’s secret sauce. The company prints equity or equity-linked securities to buy bitcoin, boosting bitcoin’s price, which in turn inflates MicroStrategy valuation. This allows it to issue more stock and repeat the cycle.

This MonoStrategy has enabled MicroStrategy to acquire 2.25 per cent of all bitcoin in existence, a hoard worth around $46bn at current prices. The company trades at nearly double the value of its underlying bitcoin holdings, a testament to belief of some investors in Michael Saylor’s project.
...
As long as the stock trades at a premium to its bitcoin holdings, the company can keep issuing novel securities and finding new buyers. Meanwhile, with MicroStrategy comprising a sizeable portion of crypto inflows (28 per cent in 2024, according to JPMorgan), it has helped sustain bitcoin’s ascent.

Both our co-Presidents are heavily invested in pumping cryptocurrencies. The new administration is planning to solve the Greater Fool Supply-Chain Crisis by turning the Federal government into the greater fool of last resort by establishing the strategic Bitcoin reserve. What better greater fool than one who can print his own money? The result is that the S.E.C. Moves to Scale Back Its Crypto Enforcement Efforts, as Matthew Goldstein, Eric Lipton and David Yaffe-Bellany report:

The Securities and Exchange Commission is moving to scale back a special unit of more than 50 lawyers and staff members that had been dedicated to bringing crypto enforcement actions, five people with knowledge of the matter said.

Source

Even if it were possible to regulate real-world cryptocurrencies, there no longer appears to be any political support for doing so. And thus Michael P. Regan reports on A Sunday Night Flash Crash in the ‘Most Insane Casino Ever Created’:

a major flash crash in Ether as leveraged positions were liquidated served as a stark reminder of how digital-asset markets still lack almost all of the guardrails installed on traditional markets over the years due to various misadventures that hurt investors. The second-largest token was down a bit as traditional markets opened for trading Monday morning in Asia, reacting to concerns about US tariffs against Canada and Mexico. Then in a matter of minutes its losses extended to about 27%, before quickly recovering.
...
There’s no indication that any of that is likely to change anytime soon. So Sunday night’s price action in Ether – and similar dives in a slew of other altcoins and memecoins – serves as a reminder that for better or worse this asset class still exists far outside of the padded walls of traditional markets, regardless of how much tradfi embraces it.