The for loop runs seven times. During each iteration the transaction modifies a set of data provided as input to the transaction. After seven loops, it terminates with a true value and lets the user spend their money.
Introduction
People who develop bitcoin applications are probably familiar with the common observation that bitcoin script is not a turing-complete programming language and does not have loops. This is shorthand for saying bitcoin does not have unbounded loops, that is, all functions written in bitcoin script are guaranteed to “halt” at some point and either return a value or return an error, whereas an unbounded loop might never halt, it might get stuck repeating an action forever.
Unbounded loops are not the most common types of loops used by programmers. (In fact they are quite dangerous and often avoided wherever possible.) Programmers usually use “for” loops instead, or bounded loops, which repeatedly apply some lines of code a certain number of times and then move on to the next lines. It has long been known that it is at least theoretically possible to implement a “for” loop in bitcoin script.
Below I provide an implementation of a for loop in bitcoin script using a construct that emulates a bounded-depth turing machine. To do this, I built a virtual machine in bitcoin script that can perform one of 8 actions depending on the value of 3 binary digits it reads from a tape (an array of stack elements). Actions it can perform include: shift the tape left, shift the tape right, read the next instruction (i.e. the next 3 digits), and modify the tape. Shifting the tape right is done by moving things to the alt stack and shifting it left is done by getting things from the alt stack.
If you pass this virtual machine a tape of 9 bits containing a set of instructions, the virtual machine will execute the instructions on the tape, including the ability to loop by running an instruction that tells it to shift left a certain number of bits, where it encounters another instruction telling it go back where it was and run the first instruction again. If your script doesn’t modify the tape in between those two instructions, it can get stuck in a loop until it consumes all of the virtual machine’s resources, or, if it does modify the tape, you can get it out of the loop after performing one or more functions a limited number of times repeatedly.
The following script is an example of a loop that repeats one time before consuming all of the virtual machine’s resources. It starts off at position 9 on a tape, where it is instructed to go to position 3, where it is instructed to return to position 9, then it loops by following the same sequence of instructions again: it goes to position 3 (based on the instruction at position 9) and then (following the instruction at position 3) it goes back to position 9 again. This basic version does not perform any modifications to the tape so after performing its loop it will halt and crash the virtual machine, which means it cannot be used in a real bitcoin transaction.
Seems like this is not being discussed here for now. Any other platform (Telegram group, etc) where you've posted this and where some knowledgeable people are shining in? Sounds amazing to me, but who am I to say :)
I discussed this at length yesterday and today in the Spacechains telegram group. The consensus seems to be that it was already known that for loops were possible and this particular implementation of them is extremely inefficient. A more efficient way to do an operation multiple times within a bounded range is to simply write it out as many times as you want to run it. E.g. if I want to perform a sha256 hash on something 7 times, I can code it up this way:
See how much less space that took up? My VM-based for loop has 3120 lines of code, each of which eats up space in the blockchain and therefore must be paid for; this alternative version has 8 lines of code. That's because instead of these steps:
bodge together a for loop
set an initial number 7
run a function that performs sha256 on the input and then decrements the initial number
loop back and repeat that function until the initial number is a 0
...I'm just, um, running the function I want 7 times. It's so much easier and more efficient (not to mention way, way cheaper in terms of mining fees).
I think a possible drawback of the "write it out 7 times" method is that if you want to lock up money in a way that someone can only redeem it by performing some set of steps, you have to know in advance exactly what steps they can take, or you must write out a defined number of very specific options for them and put them between "if" tags. ("If the redeemer chooses option 3, run sha256 7 times, then check if the value is the one I was looking for, and if so, let them take the money.")
By doing it my way, with the loops, you give the redeemer a lot more flexibility. The witness program doesn't define the program they want to run, it just gives them access to a number of script functions and a number of loops, and then they can do those operations in any order they want as long as it ends up giving me the result I want.
I think that potentially gives us way more flexibility in terms of giving someone options for redeeming some money via a script without knowing in advance exactly what their script will be. I would love it if this unlocked the potential for things like scripted sidechain pegouts (where you require anyone who wants to take your "peg in" money to supply an SPV proof of some state on the sidechain in order to peg your money out), but that's probably a bit far fetched. In reality I'm not sure this is useful; but it certainly seems cool to me, and it might prove useful with more research.
What use case could take advantage of for loops in Bitcoin?
And what would be the nefarious uses of this one could think of? Does this capability enter the whole covenant discussion? Not implying covenants are nefarious, again, who am I to say :)
TLDR
Introduction
break