Impossibilities

I'm starting to see a series of papers each showing that some assertion about the cryptocurrency ecosystem that crypto-bros make can't be true. I wrote about the first one I noticed in Ethereum Has Issues, but I have since seen several more. Below the fold I briefly review them, I'll update this post if I see more to maintain a chronological list of these research results.

The list so far is:

1. Blockchain Economics by Joseph Abadi and Markus Brunnermeier (18^th June 2018) introduced the Blockchain Trilemma:
   

   The ideal qualities of any recordkeeping system are (i) correctness, (ii) decentralization, and (iii) cost efficiency. We point out a Blockchain Trilemma: no ledger can satisfy all three properties simultaneously.

2. Bitcoin: A Natural Oligopoly by Nick Arnosti and S. Matthew Weinberg (21 November 2018) formalizes my observation in 2014's Economies of Scale in Peer-to-Peer Networks that economies of scale drive centralization:
   

   (a) ... if miner j has costs that are (e.g.) 20% lower than those of miner i, then miner j must control at least 20% of the total mining power. (b) In the presence of economies of scale (α>1), every market participant has a market share of at least 1−1/α, implying that the market features at most α/(α−1) miners in total.

3. Impossibility of Full Decentralization in Permissionless Blockchains by Yujin Kwon et al (1^st September 2019) provides a different formalization of the idea that economies of scale drive centralization by introducing the concept of the "Sybil cost":
   

   the blockchain system should be able to assign a positive Sybil cost, where the Sybil cost is defined as the difference between the cost for one participant running multiple nodes and the total cost for multiple participants each running one node.
   ...
   Considering the current gap between the rich and poor, this result implies that it is almost impossible for a system without Sybil costs to achieve good decentralization. In addition, because it is yet unknown how to assign a Sybil cost without relying on a TTP [Trusted Third Party] in blockchains, it also represents that currently, a contradiction between achieving good decentralization in the consensus protocol and not relying on a TTP exists.

4. SoK: Communication Across Distributed Ledgers by Alexei Zamyatin, Mustafa Al-Bassam, Dionysis Zindros, Eleftherios Kokoris-Kogias, Pedro Moreno-Sanchez, Aggelos Kiayias, and William J. Knottenbelt (2^nd October 2019, updated 5^th February 2021, also here) shows the impossibility of trustless cross-chain communication:
   

   Since the inception of Bitcoin, a plethora of distributed ledgers differing in design and purpose has been created. While by design, blockchains provide no means to securely communicate with external systems, numerous attempts towards trustless cross-chain communication have been proposed over the years. Today, cross-chain communication (CCC) plays a fundamental role in cryptocurrency exchanges, scalability efforts via sharding, extension of existing systems through sidechains, and bootstrapping of new blockchains. Unfortunately, existing proposals are designed ad-hoc for specific use-cases, making it hard to gain confidence in their correctness and composability. We provide the first systematic exposition of cross-chain communication protocols.
   
   We formalize the underlying research problem and show that CCC is impossible without a trusted third party, contrary to common beliefs in the blockchain community. With this result in mind, we develop a framework to design new and evaluate existing CCC protocols, focusing on the inherent trust assumptions thereof, and derive a classification covering the field of cross-chain communication to date. We conclude by discussing open challenges for CCC research and the implications of interoperability on the security and privacy of blockchains.

   They show the impossibility by reducing CCC to the Fair Exchange problem:
   

   On a high level, an exchange between two (or more) parties is considered fair if either both parties receive the item they expect, or neither do. Fair exchange can be considered a sub-problem of fair secure computation, and is known to be impossible without a trusted third party

   Their analysis is informed by their earlier work implementing Xclaim, described in Xclaim: Trustless, Interoperable, Cryptocurrency-Backed Assets by Alexei Zamyatin, Dominik Harz, Joshua Lind, Panayiotis Panayiotou, Arthur Gervais and William Knottenbelt (6^th July 2018):
   

   We present Xclaim: the first generic framework for achieving trustless and efficient cross-chain exchanges using cryptocurrency- backed assets (CBAs). Xclaim offers protocols for issuing, transferring, swapping and redeeming CBAs securely in a non-interactive manner on existing blockchains. We instantiate Xclaim between Bitcoin and Ethereum and evaluate our implementation; it costs less than USD 0.50 to issue an arbitrary amount of Bitcoin-backed tokens on Ethereum. We show Xclaim is not only faster, but also significantly cheaper than atomic cross-chain swaps. Finally, Xclaim is compatible with the majority of existing blockchains without modification, and enables several novel cryptocurrency applications, such as cross- chain payment channels and efficient multi-party swaps.

5. High-frequency trading on decentralized on-chain exchanges by L. Zhou, K. Qin, C. F. Torres, D. V. Le, and A. Gervais (29^th September 2020) points out a problem facing "decentralized exchanges" (DEX):
   

   Our work, sheds light on a dilemma facing DEXs: if the default slippage is set too low, the DEX is not scalable (i.e. only supports few trades per block), if the default slippage is too high, adversaries can profit.

6. Responsible Vulnerability Disclosure in Cryptocurrencies by Rainer Böhme, Lisa Eckey, Tyler Moore, Neha Narula, Tim Ruffing & Aviv Zohar (October 2020) see also Rethinking Responsible Disclosure for Cryptocurrency Security by Stewart Baker (8^th September 2022). Both essentially argue that it is impossible for a trustless, decentralized system to prevent the inevitable vulnerabilities being exploited before they can be fixed. My restatement of their argument is:
   
   • Cryptocurrencies are supposed to be decentralized and trustless.
   • Their implementations will, like all software, have vulnerabilities.
   • There will be a delay between discovery of a vulnerability and the deployment of a fix to the majority of the network nodes.
   • If, during this delay, a bad actor finds out about the vulnerability, it will be exploited.
   • Thus if the vulnerability is not to be exploited its knowledge must be restricted to trusted developers who are able to upgrade vulnerable software without revealing their true purpose (i.e. the vulnerability). This violates the goals of trustlessness and decentralization.
   Both Böhme et al and Baker provide examples of the problem in practice.
7. Irrationality, Extortion, or Trusted Third-parties: Why it is Impossible to Buy and Sell Physical Goods Securely on the Blockchain by Amir Kafshdar Goharshady (19^th October 2021) reveals a major flaw in the use of cryptocurrencies as currencies rather than as gambling chips:
   

   Suppose that Alice plans to buy a physical good from Bob over a programmable Blockchain. Alice does not trust Bob, so she is not willing to pay before the good is delivered off-chain. Similarly, Bob does not trust Alice, so he is not willing to deliver the good before getting paid on-chain. Moreover, they are not inclined to use the services of a trusted third-party. Traditionally, such scenarios are handled by game-theoretic escrow smart contracts, such as BitHalo. In this work, we first show that the common method for this problem suffers from a major flaw which can be exploited by Bob in order to extort Alice. We also show that, unlike the case of auctions, this flaw cannot be addressed by a commitment-scheme-based approach. We then provide a much more general result: assuming that the two sides are rational actors and the smart contract language is Turing-complete, there is no escrow smart contract that can facilitate this exchange without either relying on third parties or enabling at least one side to extort the other.

8. The Consequences of Scalable Blockchains on Datafinnovation's blog (1^st April 2022) shows 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:
   

   What we are going to do here is pretty simple:
   

   1. Describe some thing a scalable blockchain could do.
   2. Prove that thing is NP-Complete.
   3. Show how, if you have such a blockchain, you can right now break hash functions and public-key cryptography and constructively prove P=NP.

   If you build this thing you can break nearly all the major protocols out there — blockchains, banks, SSL, RSA, nearly everything — right now.

   NB: it appears that the first application of computer science impossibility results to cryptocurrencies was in Ethereum's DAO Wars Soft Fork is a Potential DoS Vector by Tjaden Hess, River Keefer, and Emin Gün Sirer (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".
9. Sharding Is Also NP-Complete by Datafinnovation (2^nd April2022) uses the same proof technique to show that sharding is subject to the same worst-case problem as scaling a single blockchain:
   

   The point of this post is not that sharding is useless. Sharding certainly helps sometimes. It might even help “on average.” But this is a hard problem. This leaves us with two choices:
   

   1. Scalable solutions which are prone to accidents
   2. Truly reliable scalability but P=NP etc

   What do I mean by accidents? Systems that fall over when they are overloaded. Whether that is exploding block times or proper crashing or whatever else is a software engineering question rather than a math one. But something bad. Mitigation is a requirement if you want a robust system because you can’t engineer around this challenge and still have the cryptography.

10. Positive Risk-Free Interest Rates in Decentralized Finance by Ben Charoenwong, Robert M. Kirby, and Jonathan Reiter (14^th April 2022) is summarized in Impossibility of DeFi Risk-Free Rates:
    

    This paper explores the idea of risk-free rates in trustless DeFi systems. The main result is that it is impossible, under a clearly stated set of conditions, to generate conventional risk-free rates.

    The paper uses a model:
    

    representing a large class of existing decentralized consensus algorithms [to show] that a positive risk-free rate is not possible. This places strong bounds on what decentralized financial products can be built and constrains the shape of future developments in DeFi. Among other limitations, our results reveal that markets in DeFi are incomplete.

    The paper was updated on 28^th August 2022.
11. Blockchain scalability and the fragmentation of crypto by Frederic Boissay et al (7^th June 2022) formalizes and extends the argument I made in Fixed Supply, Variable Demand (3^rd May 2022):
    

    To maintain a system of decentralised consensus on a blockchain, self-interested validators need to be rewarded for recording transactions. Achieving sufficiently high rewards requires the maximum number of transactions per block to be limited. As transactions near this limit, congestion increases the cost of transactions exponentially. While congestion and the associated high fees are needed to incentivise validators, users are induced to seek out alternative chains. This leads to a system of parallel blockchains that cannot harness network effects, raising concerns about the governance and safety of the entire system.

12. Decentralized Stablecoin Design by Ben Charoenwong, Robert M. Kirby, and Jonathan Reiter (28^th August 2022) uses the halting problem and Goharshady (2021) to investigate the stability of metastablecoins that are not fully backed by fiat held by a trusted party:
    

    Our methodology is as follows. First, we present a product with definitions taken from an economics context. This product may or may not have some desirable property. The question of whether it has the property is then formulated as a decision problem. Then, we use the theory of computation to reduce the problem using isomorphism and show that the reduced decision problem is undecidable based on the large extant literature on computer science. Finally, we then conclude that due to the undecidability, constructing such a product which provably satisfies the desirable property is impossible.

    They are careful not to over-sell their results:

    a caveat of our results is that the theoretical results pertain to the computational feasibility and provability of the property. It does not imply that a given design will not work for some (possibly very long) period of time. It simply means that we cannot know for sure that it will.

13. The Compliance-Innovation Trade-off (October 31^st 2022) by Datafinnovation describes a generalization of the impossibility proof technique they have used in their previous results. They start from Gödel's incompleteness theorems via the halting problem and Kleene's Recursive predicates and quantifiers which showed that:
    

    all systems that can express arithmetic contain the halting problem and offer the degree of computational power we call Turing-complete today.

    to Rice's theorem which shows:
    

    you cannot write a program that checks if another program has any particular non-trivial property.

    They observe that:
    

    the most powerful sort of computer we can have that doesn’t experience the halting problem and therefore Rice’s extension is known as a linear bounded automaton (LBA).

    They argue thus:
    
    1. We want to mechanize finance
    2. Finance needs arithmetic
    3. Godel tells us if we can do arithmetic we need to choose if our system is inconsistent or incomplete
    4. We need certainty over whether a given payment was made and around account balances, so we cannot pick inconsistency and therefore choose incompleteness
    5. Kleene tells us our system has the halting problem and all that comes with it
    6. We can then copy Savage’s proof for Rice’s theorem and adopt that result
    Thus the properties of the finance system cannot be checked automatically. The code can be reviewed, but if it calls external functions nothing can be proven. Even if it doesn't, unless either it is immutable, or if any changes are implemented using an LBA, nothing can be proven.
    
    They conclude:
    

    Permissionless systems that offer changeability >LBA cannot credibly comply with any regulations.
    
    Permissioned systems can — to the extent we trust whoever set up the system and does the permissioning going forward.

    The team has expanded and formalized this argument in Decentralized Finance and Financial Regulation: Limits On Mutable Turing Machines by Ben Charoenwong, Robert M. Kirby, and Jonathan Reiter. Their abstract reads:
    

    Our study combines financial regulation and computer science concepts to identify which decentralized finance architectures allow meaningful regulations. We show via deduction that a decentralized and permissionless Turing-complete system cannot provably comply with existing financial regulations related to anti-money laundering (AML) and know-your-client (KYC) obligations. 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 trade-offs that limit their enforcement powers if they want to approve permissionless platforms formally.

14. An impossibility theorem on truth-telling in fully decentralized systems (August 2023) by Rodney Garratt and Cyril Monnet of the Bank for International Settlements examines the "oracle problem". They write (my emphasis):
    

    This paper considers a situation where multiple individuals seek to enter into agreements based on the outcome of a real-world event, but there is no trusted party (i.e., contractible source) that can be used to determine payoffs. In this case, payoffs must be based on some form of collective agreement on the true state of the world. By appealing to three basic properties, anonymity, neutrality, and monotonicity, we can restrict attention to majority voting. In this environment, agents report the truth that is most beneficial for them. Incentives to reward consensus do not necessarily make things better. Rather, they lead to a situation that is akin to a beauty contest `a la Keynes (1936), in which agents report what they think the majority of other agents will report. With or without reporting incentives, the report of the true state that results from majority voting does not depend upon the true state.

    Their conclusion is important:
    

    A completely decentralized system can only function well when agents have no stake in it. While we express this result as an impossibility theorem, it really points to the limit of decentralization: the decentralization of the truth has to be handed to a group of agents who have no other stake in what the truth is than the payment they receive to do their jobs. This opens the door to a free rider problem and the so-called oracle problem.

    In the real world it is easy to see that actors who do have a stake in what the "truth" is can use out-of-band (or even in-band) mechanisms such as bribery to create stakes for the agents.
15. The abstract of Blockchain Tracing & Determinism by DataFinnovation is:
    

    Much like phrenology, blockchain tracing has seeped into jurisprudence and been undeservedly elevated to the level of forensic science. But is it sufficiently deterministic to be employed so unabashedly?

    They go on to write:
    

    Here we are going to explore this confusion around the term “deterministic,” clarify concepts so we can move beyond colloquial vocabulary, and discuss how most blockchain tracing tools in use are deterministic under some definitions and non-deterministic under others.
    
    To oversimplify, a deterministic system is one where the same set of inputs to the system, yields the same set of outputs.

    It is extremely difficult to ensure that a series of blockchain traces have the same set of inputs.