Date: Fri, 24 May 2019 04:15:45 +0000
To: Russell O'Connor <roconnor@blockstream.io>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <CCdF2y99R_xiyrtQ3F80GDSpQVWJztgS71HaHXEHq1cZmj0om0Ge7yMEtx_QY4MMOD6qHT1YE3cn-3o-wVWWS3KatMQE8W-GJnolna_prsI=@protonmail.com>
In-Reply-To: <CAMZUoK=0YhqxguphmaKsMGZCy_NYVE_i53qGBfPVES=GAYTy1g@mail.gmail.com>
References: <CAMZUoK=0YhqxguphmaKsMGZCy_NYVE_i53qGBfPVES=GAYTy1g@mail.gmail.com>
Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK
Precedence: list

> For better or for worse, without an OP_PUBKEYTWEEK operation available, t=
he more interesting recursive-covenants remain largely out of reach, with t=
he 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 interesti=
ng 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 s=
pend* 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 sp=
ent* by giving that transaction *being spent* (minus witness) as part of th=
e witness stack.
    This is because the transaction *doing the spend* commits to the transa=
ction *being spent* by referring to its txid.
    We can concatenate the bits of the previous transaction and confirm tha=
t 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 co=
ntains the previous state (or a commitment to the previous state if it is t=
oo 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" d=
ata.
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 "previ=
ous 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 val=
idates the execution of one iteration of the interpreter loop, and that wou=
ld be enough to create a Turing-complete system within Bitcoin.
With MAST, you can compress branches not taken, reducing the number of oper=
ations you have to expose at each iteration.

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


Regards,
ZmnSCPxj