Building a Turing machine on Bitcoin Cash (NSFW)
2018-11-30Disclaimer: This post contains some profanities, which are used for naming esoteric languages. I neither support nor endorse this, it's just what it is.
In my previous post, I showed how we can do looping transactions on the Bitcoin Cash blockchain. Unfortunately, this caused some confusion, as people initially believed OP_CHECKDATASIG allowed to loop within Bitcoin Script.
This is not true, with the scheme I showed we can only loop using a new transaction for each loop. People claiming CSW was right about OP_CHECKDATASIG introducing loops IN Script are wrong. It's just false. The idea that you could call another transaction by checking a signature is just ludicrous.
To keep the loops spinning, you have to feed it with more Satoshis each loop, which is similar to Ethereums Gas limit. So that's fine!
Onto our next challenge: Proving turing completeness!
In that post I claimed that "we've just accidentally proved Script to be Turing complete" but didn't add any rigorous proof, other than something along the lines of "Look, it's a loop!".
It's actually pretty easiy for something to become Turing complete, and we have to be extra careful not to accidentially make something Turing complete. Conway's Game Of Life is Turing complete, as is the Rule 110 cellular automaton. The creator of Bitcoin Script was very careful not to make it Turing complete, so that it would be easy to check the script's execution costs.
A simple way to show Turing completeness is by simulating a Turing machine. For that, we'll pick a derivative of Smallfuck, an esoteric programming language, which has been shown to be Turing complete. If we can simulate that on Bitcoin, we know it's Turing complete.
Smallfuck
Smallfuck has a tape with bits (0 or 1) and a pointer that points to one of those bits. The pointer can be moved and flip bits around.
It has the following commands:
>Move pointer right<Move pointer left*Flip current cell[Jump past matching]if cell under pointer is 0]Jump back to matching[
I'll change the rules slightly to make it easier to implement. <position> is a 2 byte number in little endian, and _ is some arbitrary, ignored, byte:
>__Move pointer right<__Move pointer left*__Flip current cell[<position>Jump to<position>if cell under pointer is 0]<position>Jump to<position>unconditionally
This actually makes the language more expressive and powerful, so it would also be Turing complete. To move the tape pointer, we have to step in multiples of 3 as each instruction is 3 bytes in size.
Encoding
We need four things for our turing machine:
- The program to be executed
- The instruction pointer
- The current tape
- The tape pointer
The first of those is fixed, the others potentially change after each step.
We'll put the program directly into the output script and the others will be put into the OP_RETURN part of the transaction.
Code
In my last post I showed how to do a transaction that has to spin indefinitely. For that we'll assume we have a function decomposePreimage which decomposes the preimage.
contract ForeverTheSame() { challenge spend(PubKey pk, Sig sig, bin preimageSerialized) { verify checkSig(sig, pk); verify checkDataSig(sig, preimageSerialized, pk); Preimage preimage = decomposePreimage(preimageSerialized); verify hash256(preimage.value . preimage.scriptCode) == preimage.hashOutputs; } }
Now we can extend this to the following:
contract TuringMachine(bin program, // <-- program for the machine to execute bin opReturnHeader, // ^-- what we have to prepend to our machine state for OP_RETURN bin hashSendTheMoneyBack // ^-- output script for claiming the machines money once finished ) { challenge step(PubKey pk, Sig sig, bin preimageSerialized, bin previousTxBefore, bin instructionPointer, bin tapePointer, bin tape, bin previousTxAfter, bin previousTxOutpointIndex) { verify checkSig(sig, pk); verify checkDataSig(sig, preimageSerialized, pk); Preimage preimage = decomposePreimage(preimageSerialized); verify hash256(previousTxBefore . instructionPointer . tapePointer . tape . previousTxAfter) . previousTxOutpointIndex == preimage.outpoint; // ^-- need to verify OP_RETURN of the previous transaction actually // matches inputs if (bin2num(instructionPointer) == size(program)) { // ^-- program terminated, can now send the money back. verify hashSendTheMoneyBack == preimage.hashOutputs; } else { bin [_, tail] = program @ instructionPointer; bin [instruction, _] = tail @ 3; // <-- take the first 3 bytes bin [instructionCode, instructionPosition] = instruction @ 1; // ^-- split into 1 byte and 2 bytes bin [tapeBefore, tapeAfter] = tape @ bin2num(tapePointer); bin [value, tapeTail] = tapeAfter @ 1; // ^-- extract the currently pointed to value bin outputPreamble = preimage.value . preimage.scriptCode . 0x0000000000000000 . opReturnHeader; if (instructionCode == 0x3e) { // '>' encoded bin newInstructionPointer = num2bin(bin2num(instructionPointer) + 3, 2); // ^-- move instruction pointer bin newTapePointer = num2bin(bin2num(tapePointer) + 1, 2); // ^-- move one to the right on the tape verify hash256(outputPreamble . newInstructionPointer . // <-- move instruction pointer newTapePointer . // <-- move tape pointer tape) == preimage.hashOutputs; } else if (instructionCode == 0x3c) { // '<' encoded bin newInstructionPointer = num2bin(bin2num(instructionPointer) + 3, 2); bin newTapePointer = num2bin(bin2num(tapePointer) - 1, 2); // ^-- move one to the right on the tape verify hash256(outputPreamble . newInstructionPointer . // <-- move instruction pointer newTapePointer . // <-- move tape pointer tape) == preimage.hashOutputs; } else if (instructionCode == 0x2a) { // '*' encoded bin newInstructionPointer = num2bin(bin2num(instructionPointer) + 3, 2); bin newValue = value ^ 0x01; // flip bit verify hash256(outputPreamble . newInstructionPointer . // <-- move instruction pointer tapePointer . // <-- keep tape pointer tapeBefore . newValue . tapeAfter // <-- update tape ) == preimage.hashOutputs; } else if (instructionCode == 0x5b) { // '[' encoded if (value = 0x00) { verify hash256(outputPreamble . instructionPosition . // <-- jump instruction pointer tapePointer . tape) == preimage.hashOutputs; } else { bin newInstructionPointer = num2bin(bin2num(instructionPointer) + 3, 2); verify hash256(outputPreamble . newInstructionPointer . // <-- move instruction pointer tapePointer . tape) == preimage.hashOutputs; } } else if (instructionCode == 0x5d) { // ']' encoded verify hash256(outputPreamble . instructionPosition . // <-- jump instruction pointer tapePointer . tape) == preimage.hashOutputs; } else { verify false; // <-- invalid opcode } } } }
Ouch. That's quite a bit. Let's go through it.
Verify tape, instruction pointer and tape pointer
verify hash256(previousTxBefore . instructionPointer . tapePointer . tape . previousTxAfter) . previousTxOutpointIndex == preimage.outpoint;
This asserts that the state of the machine - i.e. the instruction and tape pointer as well as the tape - we've been given are in fact part of the previous transaction, which should be in the OP_RETURN part.
Handle termination
if (bin2num(instructionPointer) == size(program)) { // <-- program terminated, can now send the money back. verify hashSendTheMoneyBack == preimage.hashOutputs; }
Our program might have terminated, which means the instruction pointer is right behind the program, like when the needle of a phonograph moves off the record.
Extract instruction code and tape value
bin [_, tail] = program @ instructionPointer; bin [instruction, _] = tail @ 3; // <-- take the first 3 bytes bin [instructionCode, instructionPosition] = instruction @ 1; // ^-- split into 1 byte (instructionCode) and 2 bytes (instructionPosition) bin [tapeBefore, tapeAfter] = tape @ bin2num(tapePointer); bin [value, tapeTail] = tapeAfter @ 1; // <-- extract the currently pointed to value
Next we disassemble our tape and program, to find out our current instruction (i.e. its code and where to jump to, if we must) and the current value on the tape.
Build output block preamble
bin outputPreamble = preimage.value . preimage.scriptCode . 0x0000000000000000 . opReturnHeader;
To make life easier for us, we add a "preamble" that we prepend in front of the actual state of the machine. We'll use that below all the time. The transaction should have 2 outputs, one which continues the execution of the machine and one which encodes the state of the machine.
Case 1. >: Move tape pointer to the right
if (instructionCode == 0x3e) { // '>' encoded
We check for the case '>', ...
bin newInstructionPointer = num2bin(bin2num(instructionPointer) + 3, 2); // ^-- move instruction pointer
... and move the instruction pointer 3 bytes to the right. As defined above, our instructions all take 3 bytes. After we execute an instruction, we move over to the next after that.
bin newTapePointer = num2bin(bin2num(tapePointer) + 1, 2); // ^-- move one to the right on the tape
We then move the tape pointer one to the right, as defined in the instruction.
verify hash256(outputPreamble . newInstructionPointer . // <-- move instruction pointer newTapePointer . // <-- move tape pointer tape) == preimage.hashOutputs;
And finally, we verify that the transaction actually moves the instruction pointer and tape pointer to the right.
Case 2. <: Move tape pointer to the left
This is the same as Case 2, only that the tape pointer is moved to the left instead.
bin newTapePointer = num2bin(bin2num(tapePointer) - 1, 2);
Case 3. *: Flip the bit under the instruction pointer
As before, we move the instruction pointer to the right:
bin newInstructionPointer = num2bin(bin2num(instructionPointer) + 3, 2);
Then we flip the bit at the current tape position (extracted above), ...
bin newValue = value ^ 0x01; // flip bit
... and verify the transaction actually flips the bit.
verify hash256(outputPreamble . newInstructionPointer . // <-- move instruction pointer tapePointer . // <-- keep tape pointer tapeBefore . newValue . tapeAfter // <-- update tape ) == preimage.hashOutputs;
Case 4. [: Jump conditionally
For this we have two cases:
if (value = 0x00) { verify hash256(outputPreamble . instructionPosition . // <-- jump instruction pointer tapePointer . tape) == preimage.hashOutputs; }
The first case happens when the current value is 0. Then we jump to the position defined in the instruction, instructionPosition, which we've extracted earlier.
The other case:
else { bin newInstructionPointer = num2bin(bin2num(instructionPointer) + 3, 2); verify hash256(outputPreamble . newInstructionPointer . // <-- move instruction pointer tapePointer . tape) == preimage.hashOutputs; }
Here, we just move the instruction pointer one to the right.
Case 5. ]: Jump unconditionally
And finally, the unconditional branch. It's the same as in the first branch of the previous instruction code.
verify hash256(outputPreamble . instructionPosition . // <-- jump instruction pointer tapePointer . tape) == preimage.hashOutputs;
Conclusion
We've shown that it's possible to build a Turing machine, Smallfuck to be precise, on top of Bitcoin, using OP_CHECKDATASIG and one transaction for each execution step. This means Bitcoin is indeed Turing complete!
But there's more. We could optimize the current code we have to get a real, fully fledged and operational Bitcoin Virtual Machine. It could be very similar to Ethereum's EVM, but with something much better than a gas limit, a pay-for-each-execution-step model. The possibilities this offers are myriad.