A recent claim that Bitcoin is Turing-complete has sparked excitement, debate and derision.

Screenshot from 2017-07-20 21-18-35

Screenshot from 2017-07-20 18-49-10

Yet is it really so far-fetched to believe that the Bitcoin scripting language might be Turing-complete?  Consider:

We know that Bitcoin script already contains a second stack so the interpreter could function as a 2PDA which is proven to be equivalent to a Turing Machine.  A new opcode could add support for looping, and the halting problem mitigated with something similar to Ethereum gas.  Useful operations such as CAT, XOR, LSHIFT which have been disabled could be re-enabled.  There might be constraints but the scripting language would be Turing-complete and useful.  If you have any lingering doubts…

Screenshot from 2017-07-22 22-38-57

Some argue, taking Ethereum as an example, that Turing-complete smart contracts are best avoided as they expand the attack surface area and an immature toolchain increases the risk of programmer error.  There’s no doubt that smart contracts must be handled with care, but bugs don’t discriminate — they lurk everywhere.  Here are some critical bugs, found outside the scripting system, which required a chain fork to resolve:

Let’s take a step back and consider the big-picture.  Bitcoin is competing against simple money (traditional fiat) and other forms of payment.  If the plan is to remain simple where is the competitive advantage when rivals are innovating rapidly at scale?

My curiosity was piqued when I heard whispers of the Bitcoin network itself being a Universal Turing Machine.  This might sound like fan fiction but apparently there are two independent papers to be published soon, one from nChain and the other from Clemens Ley of Yours.org.

I’m not privy to any of the research, so here’s how I imagine what a Mythical Bitcoin Turing Machine might look like.

  • The machine requires a set of tools and extensions to orchestrate a large computation to be fulfilled over many transactions.
  • A transaction performs a single step of the larger computation using the scripting system and records the result in a transaction output.
  • Linked transactions form a chain of computational results which a reader can move backwards and forward through, like a tape.
  • Transactions form a directed acyclic graph, making it possible for a computation to access results from other chains.
  • Mining a block represents a compute cycle over many transaction chains, making the machine multi-tape, where the number of tapes is bounded by the block size.

Now, given enough time, even Venus flytraps can evaluate computational predicates over many steps.  So if this Bitcoin machine could be built, what kind of computations would it be best suited for and would it even be practical to run?

Screenshot from 2017-07-20 21-16-28

I’m looking forward to the grand reveal.  In the meantime, to keep busy, I purchased a copy of The Annotated Turing by Charles Petzold, and spent some time manually crafting a Zcash transaction to host programs written in a Turing-complete language.

Quick background: Zcash is a fork of Bitcoin to improve fungibility and privacy through the use of zero-knowledge cryptography.  The transaction I created is known as a shielded transaction, which hides the sender, receiver and amount.  Shielded transactions also feature encrypted memo fields.

Let’s dive into the transaction a little bit (explorer link).  If you’re familiar with Bitcoin JSON-RPC output, you’ll notice the empty vin and vout arrays and the addition of a vjoinsplit array.  Each joinsplit describes a movement of private funds and contains two encrypted memo fields, with each field being 512 bytes long and stored as part of the ciphertexts array.

If you scroll to the right, you shold notice something strange about the ciphertexts.  Encrypted data should be gibberish to the eye but instead you can see a long series of zeros.  If you’re familiar with the Zcash protocol you might recognize the zeros as padding for plaintext data.  Essentially, unencrypted data has been embedded into the blockchain.

This act of graffiti (courtesy of hacking the zcashd client) demonstrates that the memo field can be used not only for secure messaging but also public broadcasting.  Although this deviates from the Zcash Protocol which expects implementations to encrypt the memo field for a recipient, it’s not a consensus rule — so in practice you can use the memo field for anything you like.  In Bitcoin, you can use OP_DROP to embed data rather than OP_RETURN which is limited to 80 bytes per transaction.

Let’s have a look at the plaintext.  We drop the leading byte 0xF5 which specifies the rest of the memo field contains non-UTF 8 data.  Next, we strip off the zero padding.  Finally, we’re left with 256 bytes of data.

This is a program written in a Turing-complete language, but what can it possibly hope to achieve in just 256 bytes?  Take the Ethereum contract below.  It does absolutely nothing and when compiled, the size of the EVM bytecode is 146 bytes.

So let’s find out what this program can do.  On Ubuntu Linux, install some dependencies and then run one of the following one-liners in your terminal.

Amazing, right?!

To think that a tiny 256 byte assembly language program can render a 2 minute long Glitch themed demonstration, with algorithmic music and cellular automaton for visuals…. all running on an 8-bit Commodore 64!  Amazing work by Linus Akesson who explains his work in more detail here.

Repeating the above steps, you’ll find the second memo field contains an even smaller program of just 250 bytes.

Again, impressive stuff.  It’s mesmerizing to watch the brush strokes — art unto itself.

Programmer Jakub ‘Ilmenit’ Debski explains:

“There are 64 pseudo random brush strokes of cycling color. Each stroke is shorter than previous to increase details. Intro code generates set of random numbers starting from initial 32bit seed with Galois LFSRs as a PRNG. This set is used to control direction of brush movement and and starting position… Picture of Mona Lisa (3072 bytes) was compressed to those random brush strokes by external optimization program (a few days of work for modern CPU/GPU combo).” [1][2]

Just to be clear, the shielded transaction and its funds have not been affected in any way by the programs stored in the memo field.  As far as Zcash is concerned, they’re just metadata.  For now.  It’s quite interesting to see how launching an emulator has parallels with new blockchain designs which outsource computation to execution environments, such as Intel’s SGX secure enclave.

I hope the above programs showcase the ingenuity and creativity of programmers when given freedom to find the sweet spot between art and science.  Satoshi would probably agree with this sentiment as the first public release of Bitcoin v0.1 included a poker table!

Now, many have denounced talk of Bitcoin and Turing-completeness as fraudulent nonsense, technobabble and a waste of time.  It’s an understandable reaction given the Satoshi Affair but the truth is that the community’s vitality has been drained after years of toxic battle over the block size.  The mind’s eye now too weary to envisage how Bitcoin’s design might be Turing-complete and its implementation lagging.

Personal computers changed the world and the Commodore 64 remains the best-selling computer model of all time.  Its success due in large part to being sold in everyday retail stores at an affordable price for families.  For Bitcoin to achieve its transformative potential, it’s time to start imagineering a programmable money which can meet the needs and desires of every human on the planet.

Imagineers bring art and science together to turn fantasy into reality and dreams into magic.

Disney Imaginations

I leave you with 64 kilobytes of Rust and C++ wizardry.

Thanks to @radix42, Eran Tromer and Ariel Gabizon for review and watching demos.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s