Subject: Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

From: ZmnSCPxj <[email-masked]>
Date: Fri, 24 May 2019 04:15:45 +0000

> For better or for worse, without an OP_PUBKEYTWEEK operation available, the more interesting recursive-covenants remain largely out of reach, with the exception of a recursive covenant that is only able to send back to its own address, possibly abusing its own TXO value as a state variable.

After some thinking, I may have devised a way to achieve the more interesting Turing-complete system (where each "loop through" requires paying a fee to miners, akin to Ethereum Gas, and thus a good way to build new footguns) even without `OP_PUBKEYTWEAK`.

I observe the following:

1.  `OP_CHECKSIGFROMSTACK` can introspect into the transaction *doing the spend* by giving the transaction (minus witness) as part of the witness (i.e. quining).
2.  The above can be leveraged to introspect into the transaction *being spent* by giving that transaction *being spent* (minus witness) as part of the witness stack.
    This is because the transaction *doing the spend* commits to the transaction *being spent* by referring to its txid.
    We can concatenate the bits of the previous transaction and confirm that it is indeed the transaction *being spent* by hashing and comparing that to the txid in the input of the transaction *doing the spend*.
3.  The transaction *being spent* can contain an `OP_RETURN` output that contains the previous state (or a commitment to the previous state if it is too large to fit in an `OP_RETURN`, again requiring that the previous state be given as part of the witness).
    Since it can be introspected, a script can acquire a "previous state" data.
4.  The transaction *doing the spend* can also contain an `OP_RETURN` with the next state (or commitment to next state).
5.  The rest of the script can then determine if the transition from "previous state" to "next state" is valid.
6.  The script can impose that the same script is paid to by introspecting the transaction *being spent* to get at a commitment to itself.

The above seems enough to create a potentially unbound loop, bound only by the amount of money you are willing to spend on fees operating that loop.
The "state" would be the memory of your virtual machine, and the SCRIPT validates the execution of one iteration of the interpreter loop, and that would be enough to create a Turing-complete system within Bitcoin.
With MAST, you can compress branches not taken, reducing the number of operations you have to expose at each iteration.

I admit *creating* this by hand will probably be very difficult, but that should be doable with an army of lower-level cognition agents.
(disclaimer: I am not an AI with an army of lower-level cognition agents and I can completely and totally pass the Turing test)

Regards,
ZmnSCPxj