Table of Contents
Many DeFi projects seem focused on at least one of two aims. Lots of folks want to reproduce USD without needing to hold all the USD as backing. And an awful lot of others want to synthesize risk-free yield without a central party like a government or central bank.
But nobody has succeeded at either, despite herculean efforts and a shockingly large slice of DeFi aiming at these two problems. Why? Sometimes it takes a long long time for human society to figure out the answer to a difficult-but-interesting question. Famously Fermat’s Last Theorem took 358 years to prove correct. But is keeping at it, grinding out ever-more-elaborate schemes, really the right answer for DeFi? Sometimes lack of ingenuity is not the real problem. Sometimes the thing you want cannot be built. And so it is with these two products.
A lot of math, and science in general, is about well-posed questions where the answer is “sorry you can’t do that.” The idea it is possible to categorically rule out certain objects, procedures or other things people want goes back at least to the ancient Greeks who knew the square root of 2 could not be expressed as a fraction and suspected one could not “square the circle.” In the early 20th century these ideas were extended into logic and what later came to be called the “theory of computation,” when Godel proved limits on proving systems of the type we all learned in math class and Turing proved limits on the capabilities of machines we now call “computers.” This concept also exists in economics, perhaps most famously with the Mundell-Fleming Trilemma, which constrains policymaker freedom in managing economies.
Recently we, along with two co-authors, released two papers extending these results into the DeFi space. While hardly as groundbreaking as the work referenced above – think of our work more like extending the square root of 2 proof to the square roots of 3 and 5 – these results do have important implications for DeFi in general.
So here let’s run through a sketch of how we prove these things and then discuss a bit what this means. This is not a technical treatment – read the real papers for that.
Ruling out solutions you’ve never even imagined
The first concept we need to get our head around is the idea we can make categorical statements about programs we’ve never seen. Actually even more than that: we can make categorical statements about programs that haven’t been written yet.
Turing proved, for a general purpose programming language, that it is impossible to write a program that determines if another program finishes running within a finite amount of time. This is, in some ways, the reason your computer freezing and crashing will always be an issue: we cannot find so-called “infinite loops” and the like, programmatically, 100% of the time. If you want to learn how to prove that you can go read this standard textbook which also happens to be both freely-available and written by the man who taught me. The original presentation is “this paper here, that has a title I can barely understand” from this scene in a movie about Alan Turing’s role in breaking the Nazi’s Enigma code.
Here, let’s just accept this is true. If you think you’ve written a program that can check some kind of very general validity of other arbitrary programs then either A) You’ve made a mistake; B) The scheme does not cover as wide a range of input programs as you expect; or C) There is a black box in there somewhere you are just guessing you can figure out later. “C” is the most common answer in practice. And we see so many DeFi projects that aspire to something they cannot yet promise with a plan to “figure it out later.”
Sometimes that is perfectly acceptable. Whatever is going on at Tesla the cars clearly work and over time will get better. That does not mean it’s a good (or bad) business – but there is no reason to question whether the cars themselves will get a bit more efficient, and the self-driving a bit smarter, ever year. We are not talking about incremental engineering improvements here but rather whether something can be done at all.
Government bonds as halting detectors
Issuing a risk-free bond is a promise about the future: the promise that you will, with certainty, make the interest payments and then return the principal. On a decentralized permissionless platform all promises about the future need to take account of code written in the future. And if you are going to be risk-free you need to build some kind of “default detector” that prevents interacting with new smart contracts that cause a default.
But can we build such a detector? No. Consider any blob of smart contact code (in Solidity, Rust, or whatever language you like). Find every spot that code terminates. Now insert something that causes a default right before termination. For example: start with some wallet you control that contains 1 token and, just before every endpoint, try to transfer 2 units out.
This transformation works just fine on any code at all. So if you can detect defaults in the output of this program, voila, you’ve solved the halting problem. This is not cause to rejoice. Recall we have no idea how to build this detector. Rather than some great accomplishment we have instead proved no such detector can be built. This technique of “reduction to halting” is standard theoretical computer science and taught during the intro theory course at every CS department in the world (many of which use the textbook linked above).
If solving your problem is the same as solving the “Halting Problem” then you are out of luck; your problem cannot be solved. Technically it is “undecideable” which means there is no way to always generate a “yes” or “no” in finite time. In markets we call that sort of situation “risky.”
Stablecoins
Stablecoins have a similar problem. But we need a tiny bit more machinery to see it. One often-overlooked requirement for stablecoins is that they redeem “quickly.” If we allow a stablecoin to take as long as it likes it’s not very useful. See this horse? I can promise to turn it into 1 unit of anything if you give me infinite time. We need some kind of time limit.
Unfortunately a fancy version of Turing’s Halting result called “Rice’s Theorem” says that not only is it impossible to prove something stops within finite time, it’s impossible, in general, to prove an arbitrary program finishes within X units of time. You can probably see where this is going.
A stablecoin with 100 units outstanding and only 90 in reserve might run in to trouble. At some point you’re going to need to go out into the DeFi world to make up those 10 units. And it is impossible to prove any given scheme – remember this is the future so we need to build a checking facility now to protect our precious stablecoin in the future – will finish within the time limit. Now apply the same sort of logic we used for risk-free bonds and we see it’s not possible to make these things truly reliable. It might work. But, again, it is “risky.”
So?
We can draw quite a few conclusions from here. First, nobody is going to successfully design the ideal form of risk-free yield or some kind of super-efficient stablecoin. Second, any product that looks as though it might have accomplished these tasks contains hidden risks. Third, these things are going to get banned eventually.
Fourth, and perhaps most importantly as far as future developments are concerned, quite a few other projects in DeFi target literally impossible dreams. We aren’t going to list them here…mainly because the list is so long. Some attempts will simply fail and fade away. Others will explode spectacularly. After all what was the LUNA explosion except a realization of this impossibility result. And lastly, and certainly most interestingly, there is a pretty good chance some project founders who put forth their CS academic credentials when fundraising are going to face some interesting questions.
We can’t prove the existence of future investor lawsuits of course. But it feels a pretty safe bet.
