The Compliance-Innovation Trade-off


In 1931 Godel proved that any system capable of expressing arithmetic was either:

  1. Inconsistent: you could prove X and -X were both true
  2. Incomplete: there were valid statements you cannot prove true or false


What does it mean to be trustless? Or to trust? These words are thrown around a lot in crypto but not carefully. So we are going to propose a definition for trust. If you can prove something is true you do not need trust. Trust but verify is more properly classified as a joke — albeit a very Russian one — than a policy. While the precise origin of the phrase is unknown it is connected to both Lenin and Stalin. They are both quite famous but certainly not for being trusting.

Sketch Of Proof

The initial setup:

  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
  1. No. In which case we can prove properties of the system including compliance. But we cannot allow any innovation as new programs cannot be published.
  2. Yes, without restriction. So here we are again screwed. We cannot promise anything because the code can change arbitrarily at any time.
  3. Yes, but only with an LBA. Now we are fine as far as compliance goes but limited on the innovation front because an LBA cannot do as much as , you know, a general purpose computer.


So how does this relate to DeFi? It’s all about who gets to push updates. So let’s consider each case above in turn.

  1. If the system already makes external calls we can make no guarantees to start with.
  2. If arbitrary changes can be pushed then a permissionless system cannot make guarantees because anybody could change it.
  3. If we can only push changes via an LBA the system itself can enforce compliance with policies on a going-forward basis. It can reliably reject changes that would lead to non-compliance. so long as the initial state was compliant.
  4. If the system is immutable it does not matter who can access it — it can never be changed. It remains as compliant as it was on day 1.

Satoshi & The Arrow Of Time

Now we are in a great position to reconsider part of the Bitcoin whitepaper. Satoshi describes the system thus:

General Impossibility

This proof encompasses a huge range of known impossibility results. We started talking about compliance but what we proved concerns any non-trivial subset of the recursively enumerable languages. For anyone that has not studied the theory of computation: that means pretty much any set of rules you can write down.

  1. Trustless & permissionless bridges are impossible
  2. Decentralized & permissionless identity is impossible
  3. Trustless & permissionless escrow is impossible
  4. Decentralized & permissionless risk-free yield is impossible
  5. Decentralized & permissionless stablecoins are impossible
  1. Define the thing you want as a proper subset of the recursively enumerable languages. This sort of exercise is a university first year homework assignment. Read the textbook above.
  2. Link the paper.

This Is Not Deep

What Godel figured out was groundbreaking. Similarly Church and Turing’s work birthed the theory of computation. Kleene and Rice connected and generalized those insights.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store