MIME-Version: 1.0
References: <CABm2gDoivzQKFr6KqeqW6+Lx7xFVprRCUAn1k3X6P29NPzw+yQ@mail.gmail.com>
 <1JO1xrnJ9GwGM4TgLH_rL_LpnZgSb1SyeEOJ9Gzc1VMbKUrmxSh-zUXKwFNvp_5wyiDtRviOf-gRJbrfbhOJl-qym1eEHXpoDAgjE9juucw=@protonmail.com>
 <CABm2gDrdwMjLu=i0p2m4SZ_91xpr-RvwSSWOnS9jhaQ3uaCxPA@mail.gmail.com>
 <CiNPwh37hW6iDk3mMg6G2QWMPS5ADUvSdySnNp6esOaloiVyoPwHGxOMLyG6mMGQnyf4iGcch12XfmOB2WnFcETwFwvRTSNSeBu27G9Cju8=@protonmail.com>
In-Reply-To: <CiNPwh37hW6iDk3mMg6G2QWMPS5ADUvSdySnNp6esOaloiVyoPwHGxOMLyG6mMGQnyf4iGcch12XfmOB2WnFcETwFwvRTSNSeBu27G9Cju8=@protonmail.com>
From: Nadav Ivgi <nadav@shesek.info>
Date: Sun, 8 May 2022 05:03:25 +0300
Message-ID: <CAGXD5f2vLaZgEUG7eu6S9YQSSLeJ0LAM+i2o1ngVb=VmxS3Rrg@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000e5fc7805de767fb7"
Subject: Re: [bitcoin-dev] Speedy covenants (OP_CAT2)
Precedence: list

--000000000000e5fc7805de767fb7
Content-Type: text/plain; charset="UTF-8"

On Sat, May 7, 2022 at 5:08 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> * Even ***with*** `OP_CAT`, the following will enable non-recursive
covenants without enabling recursive covenants:
>  * `OP_CTV`, ...
> * With `OP_CAT`, the following would enable recursive covenants:
>  * `OP_CHECKSIGFROMSTACK`, ...

Why does CTV+CAT not enable recursive covenants while CSFS+CAT does?

CTV+CAT lets you similarly assert against the outputs and verify that they
match some dynamically constructed script.

Is it because CTV does not let you have a verified copy of the input's
prevout scriptPubKey on the stack [0], while with OP_CSFS you can because
the signature hash covers it?

But you don't actually need this for recursion. Instead of having the user
supply the script in the witness stack and verifying it against the input
to obtain the quine, the script can simply contain a copy of itself as an
initial push (minus this push). You can then reconstruct the full script
quine using OP_CAT, as a PUSH(<script>) followed by the literal <script>.

When I started experimenting with recursive covenants on liquid, I started
with the approach of verifying user-supplied witness data against the
input. It ended up being quite complex and verbose with taproot, because
you have to compute the tagged taptree hash from the tapscript and
TWEAKVERIFY it against the prevout's taproot output key (which also
requires the internal key and parity flag, provided as two extra witness
elements by the user).

I then realized that it is much simpler to have the tapscript hold a copy
of itself, that it's as safe and that it reduces the witness size cost
(because you don't need to do the entire taproot dance to verify the
tapscript), and switched to this approach.

Here are two examples of recursive covenants using this approach that I
played with (for liquid, rough sketches, very lightly tested and has some
known issues. the $label thing is a scriptwiz notation and can be ignored):

https://gist.github.com/shesek/be910619b247ce5e1aedd84e9ba9db42 (auction)
https://gist.github.com/shesek/ede9ca921a394580b23d301b8d84deea (listed
price sale with royalty)
(And here's the second example written in Minsc:
https://min.sc/next/#gist=e1c9914b4cb940137122d6d30972c25c)

shesek

[0] It does not cover it, and it cannot be done even by providing the full
prev tx because the prevout txid is not covered either.


On Sat, May 7, 2022 at 5:08 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Jorge,
>
> > Thanks a lot for the many clarifications.
> > Yeah, I forgot it wasn't OP_CAT alone, but in combination with other
> things.
> > I guess this wouldn't be a covenants proposal then.
> > But simplicity would enable covenants too indeed, no?
> > Or did I get that wrong too?
>
> Yes, it would enable covenants.
>
> However, it could also enable *recursive* covenants, depending on what
> introspection operations are actually implemented (though maybe not?
> Russell O'Connor should be the one that answers this).
>
> It is helpful to delineate between non-recursive covenants from recursive
> covenants.
>
> * Even ***with*** `OP_CAT`, the following will enable non-recursive
> covenants without enabling recursive covenants:
>   * `OP_CTV`
>   * `SIGHASH_ANYPREVOUT`
> * With `OP_CAT`, the following would enable recursive covenants:
>   * `OP_EVAL`
>   * `OP_CHECKSIGFROMSTACK`
>   * `OP_TX`/`OP_TXHASH`
>   * ...possibly more.
>     * It is actually *easier* to *design* an opcode which inadvertently
> supports recursive covenants than to design one which avoids recursive
> covenants.
>
> Recursive covenants are very near to true Turing-completeness.
> We want to avoid Turing-completeness due to the halting problem being
> unsolvable for Turing-complete languages.
> That is, given just a program, we cannot determine for sure if for all
> possible inputs, it will terminate.
> It is important in our context (Bitcoin) that any SCRIPT programs we write
> *must* terminate, or else we run the risk of a DoS on the network.
>
> A fair amount of this is theoretical crap, but if you want to split hairs,
> recursive covenants are *not* Turing-complete, but are instead total
> functional programming with codata.
>
> As a very rough bastardization, a program written in a total functional
> programming language with codata will always assuredly terminate.
> However, the return value of a total functional programming language with
> codata can be another program.
> An external program (written in a Turing-complete language) could then
> just keep invoking the interpreter of the total functional programming
> language with codata (taking the output program and running it, taking
> *its* output program and running it, ad infinitum, thus effectively able to
> loop indefinitely.
>
> Translated to Bitcoin transactions, a recursive covenant system can force
> an output to be spent only if the output is spent on a transaction where
> one of the outputs is the same covenant (possibly with tweaks).
> Then an external program can keep passing the output program to the
> Bitcoin SCRIPT interpreter --- by building transactions that spend the
> previous output.
>
> This behavior is still of concern.
> It may be possible to attack the network by eroding its supply, by such a
> recursive covenant.
>
> --
>
> Common reactions:
>
> * We can just limit the number of opcodes we can process and then fail it
> if it takes too many operations!
>   That way we can avoid DoS!
>   * Yes, this indeed drops it from Turing-complete to total, possibly
> total functional programming **without** codata.
>     But if it is possible to treat data as code, it may drop it "total but
> with codata" instead (i.e. recursive covenants).
>     But if you want to avoid recursive covenants while allowing recursive
> ones (i.e. equivalent to total without codata), may I suggest you instead
> look at `OP_CTV` and `SIGHASH_ANYPREVOUT`?
>
> * What is so wrong with total-with-codata anyway??
>   So what if the recursive covenant could potentially consume all
> Bitcoins, nobody will pay to it except as a novelty!!
>   If you want to burn your funds, 1BitcoinEater willingly accepts it!
>   * The burden of proof-of-safety is on the proposer, so if you have some
> proof that total-with-codata is safe, by construction, then sure, we can
> add opcodes that may enable recursive covenants, and add `OP_CAT` back in
> too.
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--000000000000e5fc7805de767fb7
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr">On Sat, May 7, 2022 at 5:08 PM ZmnSCPxj v=
ia bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org"=
 target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:</di=
v><div dir=3D"ltr">&gt; * Even ***with*** `OP_CAT`, the following will enab=
le non-recursive covenants without enabling recursive covenants:<br><div>&g=
t;=C2=A0 * `OP_CTV`, ...<br></div>&gt; * With `OP_CAT`, the following would=
 enable recursive covenants:<br><div>&gt;=C2=A0 * `OP_CHECKSIGFROMSTACK`, .=
..</div><div><br></div><div>Why does CTV+CAT not enable recursive covenants=
 while CSFS+CAT does?</div><div><br></div><div>CTV+CAT lets you similarly a=
ssert against the outputs and verify that they match some dynamically const=
ructed script.<br></div><div><br></div><div>Is it because CTV does not let =
you have a verified copy of the  input&#39;s prevout scriptPubKey on the st=
ack [0], while with OP_CSFS you can because the signature hash covers it?</=
div><div><br></div><div>But you don&#39;t actually need this for recursion.=
 Instead of having the user supply the script in the witness stack and veri=
fying it against the input to obtain the quine, the script can simply conta=
in a copy of itself as an initial push (minus this push). You can then reco=
nstruct the full script quine using OP_CAT, as a PUSH(&lt;script&gt;) follo=
wed by the literal &lt;script&gt;.</div><div><br></div><div>When I started =
experimenting with recursive covenants on liquid, I started with the approa=
ch of verifying user-supplied witness data against the input. It ended up b=
eing quite complex and verbose with taproot, because you have to compute th=
e tagged taptree hash from the tapscript and TWEAKVERIFY it against the pre=
vout&#39;s taproot output key (which also requires the internal key and par=
ity flag, provided as two extra witness elements by the user).</div><div><b=
r></div><div>I then realized that it is much simpler to have the tapscript =
hold a copy of itself, that it&#39;s as safe and that it reduces the witnes=
s size cost (because you don&#39;t need to do the entire taproot dance to v=
erify the tapscript), and switched to this approach.<br></div><div><br></di=
v><div>Here are two examples of recursive covenants using this approach tha=
t I played with (for liquid, rough sketches, very lightly tested and has so=
me known issues. the $label thing is a scriptwiz notation and can be ignore=
d):</div><div><br></div><div><a href=3D"https://gist.github.com/shesek/be91=
0619b247ce5e1aedd84e9ba9db42">https://gist.github.com/shesek/be910619b247ce=
5e1aedd84e9ba9db42</a> (auction)<br></div><div><a href=3D"https://gist.gith=
ub.com/shesek/ede9ca921a394580b23d301b8d84deea">https://gist.github.com/she=
sek/ede9ca921a394580b23d301b8d84deea</a> (listed price sale with royalty)<b=
r></div><div></div><div>(And here&#39;s the second example written in Minsc=
: <a href=3D"https://min.sc/next/#gist=3De1c9914b4cb940137122d6d30972c25c">=
https://min.sc/next/#gist=3De1c9914b4cb940137122d6d30972c25c</a>)</div><div=
><br></div><div>shesek<br></div></div><div><br></div><div>[0] It does not c=
over it, and it cannot be done even by providing the full prev tx because t=
he prevout txid is not covered either.</div><div><br></div><div><br></div><=
div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sat, May=
 7, 2022 at 5:08 PM ZmnSCPxj via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-=
dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfou=
ndation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex">Good morning Jorge,<br>
<br>
&gt; Thanks a lot for the many clarifications.<br>
&gt; Yeah, I forgot it wasn&#39;t OP_CAT alone, but in combination with oth=
er things.<br>
&gt; I guess this wouldn&#39;t be a covenants proposal then.<br>
&gt; But simplicity would enable covenants too indeed, no?<br>
&gt; Or did I get that wrong too?<br>
<br>
Yes, it would enable covenants.<br>
<br>
However, it could also enable *recursive* covenants, depending on what intr=
ospection operations are actually implemented (though maybe not? Russell O&=
#39;Connor should be the one that answers this).<br>
<br>
It is helpful to delineate between non-recursive covenants from recursive c=
ovenants.<br>
<br>
* Even ***with*** `OP_CAT`, the following will enable non-recursive covenan=
ts without enabling recursive covenants:<br>
=C2=A0 * `OP_CTV`<br>
=C2=A0 * `SIGHASH_ANYPREVOUT`<br>
* With `OP_CAT`, the following would enable recursive covenants:<br>
=C2=A0 * `OP_EVAL`<br>
=C2=A0 * `OP_CHECKSIGFROMSTACK`<br>
=C2=A0 * `OP_TX`/`OP_TXHASH`<br>
=C2=A0 * ...possibly more.<br>
=C2=A0 =C2=A0 * It is actually *easier* to *design* an opcode which inadver=
tently supports recursive covenants than to design one which avoids recursi=
ve covenants.<br>
<br>
Recursive covenants are very near to true Turing-completeness.<br>
We want to avoid Turing-completeness due to the halting problem being unsol=
vable for Turing-complete languages.<br>
That is, given just a program, we cannot determine for sure if for all poss=
ible inputs, it will terminate.<br>
It is important in our context (Bitcoin) that any SCRIPT programs we write =
*must* terminate, or else we run the risk of a DoS on the network.<br>
<br>
A fair amount of this is theoretical crap, but if you want to split hairs, =
recursive covenants are *not* Turing-complete, but are instead total functi=
onal programming with codata.<br>
<br>
As a very rough bastardization, a program written in a total functional pro=
gramming language with codata will always assuredly terminate.<br>
However, the return value of a total functional programming language with c=
odata can be another program.<br>
An external program (written in a Turing-complete language) could then just=
 keep invoking the interpreter of the total functional programming language=
 with codata (taking the output program and running it, taking *its* output=
 program and running it, ad infinitum, thus effectively able to loop indefi=
nitely.<br>
<br>
Translated to Bitcoin transactions, a recursive covenant system can force a=
n output to be spent only if the output is spent on a transaction where one=
 of the outputs is the same covenant (possibly with tweaks).<br>
Then an external program can keep passing the output program to the Bitcoin=
 SCRIPT interpreter --- by building transactions that spend the previous ou=
tput.<br>
<br>
This behavior is still of concern.<br>
It may be possible to attack the network by eroding its supply, by such a r=
ecursive covenant.<br>
<br>
--<br>
<br>
Common reactions:<br>
<br>
* We can just limit the number of opcodes we can process and then fail it i=
f it takes too many operations!<br>
=C2=A0 That way we can avoid DoS!<br>
=C2=A0 * Yes, this indeed drops it from Turing-complete to total, possibly =
total functional programming **without** codata.<br>
=C2=A0 =C2=A0 But if it is possible to treat data as code, it may drop it &=
quot;total but with codata&quot; instead (i.e. recursive covenants).<br>
=C2=A0 =C2=A0 But if you want to avoid recursive covenants while allowing r=
ecursive ones (i.e. equivalent to total without codata), may I suggest you =
instead look at `OP_CTV` and `SIGHASH_ANYPREVOUT`?<br>
<br>
* What is so wrong with total-with-codata anyway??<br>
=C2=A0 So what if the recursive covenant could potentially consume all Bitc=
oins, nobody will pay to it except as a novelty!!<br>
=C2=A0 If you want to burn your funds, 1BitcoinEater willingly accepts it!<=
br>
=C2=A0 * The burden of proof-of-safety is on the proposer, so if you have s=
ome proof that total-with-codata is safe, by construction, then sure, we ca=
n add opcodes that may enable recursive covenants, and add `OP_CAT` back in=
 too.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
</div>

--000000000000e5fc7805de767fb7--