The following transaction on bitcoin’s testnet blockchain demonstrates that it is possible to execute a “for” loop in bitcoin script: https://blockstream.info/testnet/tx/a9bdc7db7c722d4d3cf9689510aa7817a611855e6367bbd5b58b30388fbca8aa?expand

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.

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.

For example, these two forum threads (from 2021 and 2022) point out that it is at least possible in theory, though as far as I know no one has actually done it yet: https://bitcoin.stackexchange.com/questions/111337/loops-in-bitcoin-scripting/ https://www.quora.com/Since-Bitcoin-is-not-Turing-complete-does-this-mean-no-for-loops-or-loops-of-any-kind-is-allowed-in-the-bitcoin-core-codebase

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.