Skip to content

Instantly share code, notes, and snippets.

@nothingmuch
Last active August 20, 2018 19:50
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nothingmuch/d63a4cd402d314404f91acc14df242eb to your computer and use it in GitHub Desktop.
Save nothingmuch/d63a4cd402d314404f91acc14df242eb to your computer and use it in GitHub Desktop.

turing completeness is needed if a contract can only be specified in terms of a universal turing machine acting on some input, i.e. some equivalent of an eval function, but a blockchain can never reach consensus on a predicate that doesn't halt

specifying predicates as total functions guarantees by construction that any specifiable predicate is will terminate over the entire domain of possible inputs

logically it follows that you only really need a total language to specify arbitrary predicates, but in practice that might still not be enough because even if a predicate provably terminates, it doesn't mean it does so in a reasonable time frame, nor does it guarantee that the input domain is sufficient for specifying all the things a blockchain might reach consensus about

an ideal language for such transactions would therefore not only guarantee termination, it would also give strong bounds on the complexity, be efficient to evaluate in practice, and place no arbitrary restrictions on the input domain, but this is a unicorn...

bitcoin script enforces totality by simply not having any looping constructs, which limits expressive power, and so even with arbitrary inputs, there is a strong bound on the number of computational steps.

if you allow more flexibility, for example if you allow primitive recursive functions to be defined you can do something like restrict the syntax, so e.g. loops are allowed, but all # of iterations must have a known upper bound, or you can guarantee this by adding compound data types to the inputs, and using structural recursion (any recursive function cannot recurse on its input without destructuring).

there are other ways of proving totality, but i think the crux is specifying up front a restricted class of functions, that is still sufficient for modeling all economically relevant conditions over which humans might want to achieve consensus, which is a far messier problem than that of sorting functions into computational classes

so yes, it's an important field of research, but i think it's less about complexity theory, and more about what are blockchains even for, simplicity is able to express all finitary functions, i.e. inputs must be fully specified using its types. i'm inclined to agree this is sufficient for smart contracts, because in order to reach consensus, it makes sense to know what we're reaching consensus about, and if we can only agree on a part of it, then there's no real point in agreeing to agree about inputs we don't yet know.

curiously this relates to fauxtoshi's claims of bitcoin being turing complete, but in his "analysis" function evaluation is redefined to span multiple transactions, effectively a way of sneaking in deferment of inputs by moving the goal posts...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment