path: root/9f/98a7838a8d10f83965088cae2ab1bc6b5a8898

Return-Path: <nadav@shesek.info>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 31A80C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun,  8 May 2022 02:03:41 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 1800440629
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun,  8 May 2022 02:03:41 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.697
X-Spam-Level: 
X-Spam-Status: No, score=-1.697 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_INVALID=0.1, DKIM_SIGNED=0.1,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_NONE=0.001] autolearn=no autolearn_force=no
Authentication-Results: smtp2.osuosl.org (amavisd-new); dkim=neutral
 reason="invalid (public key: not available)" header.d=shesek.info
Received: from smtp2.osuosl.org ([127.0.0.1])
 by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id dKY3d0EeapkJ
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun,  8 May 2022 02:03:38 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-io1-xd2d.google.com (mail-io1-xd2d.google.com
 [IPv6:2607:f8b0:4864:20::d2d])
 by smtp2.osuosl.org (Postfix) with ESMTPS id E1E48401A1
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun,  8 May 2022 02:03:37 +0000 (UTC)
Received: by mail-io1-xd2d.google.com with SMTP id h85so11932720iof.12
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 07 May 2022 19:03:37 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=shesek.info; s=shesek;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=8AXUuxMPjpRYIMW1lmRI1ZiNymLDEPaEdkt/P+vYFt0=;
 b=blsbbz6Me3AlPOBKFLj2GZmYsspZbOWEEDvpsPoXVE68kB9oO0dCah86OUxl4i2fdD
 OIvHnMXDovQ0Wp6U8vPuib7vTAoNy7PpWUCHMMqOGk2AhH0qJaFuKQDsXHlm1cvYBf8e
 WmQZTtRrNjUl3Txd4DPSJ5gDQT8FyWYNmC9zg=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=8AXUuxMPjpRYIMW1lmRI1ZiNymLDEPaEdkt/P+vYFt0=;
 b=bfHtnXW8Hr9nxZFyhSxL4JxR21AWFP0WSManmFe7/NzaIbfUSfkRiaZo4s9MPkQEUV
 wNJ5eQEsIgZoF4ntg6yfTR4oPqengZrPSGSpNZl3v+UiY13s7DgLHVxX8c6iduWeV2XZ
 o4kLm4EfN4QI01vM+Qi0j7qLaerIJ8fGyTvMaawIsyAfkaSlbnDbszLrxeMplkAxzuK7
 7a1zJc/hAp2WGu/9UJrdje1oTlo2RbtJgfbhbY212zZzZyQmubSFCrDHMjYHWKhqdMQ3
 zvcp4CkVK02WDLhvLzHIj5TCwdZ+/f9E0j19YvkqJn3amam3wXA9FVHqjN75jqGcNuWU
 gOXQ==
X-Gm-Message-State: AOAM532oyE+tezGEAheV6HaD+rZxJz4NMhfBu6GE8c+os0vhLRfUGOFh
 LUTQPryqS61SqYHTjf2CGvPHCrbTzkJageS+7iWfp8yIUtPDMhNf
X-Google-Smtp-Source: ABdhPJyRMUk0w6/6HrrnyEMEu1lfqMGeGWT0qipAdzNx88OtaV3DKisshUJiifr2QEA3gPquacAKSjjk5N+1Sa00tLg=
X-Received: by 2002:a05:6638:c3:b0:32a:f5d0:5d58 with SMTP id
 w3-20020a05663800c300b0032af5d05d58mr4700808jao.40.1651975416832; Sat, 07 May
 2022 19:03:36 -0700 (PDT)
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"
X-Mailman-Approved-At: Sun, 08 May 2022 08:07:20 +0000
Subject: Re: [bitcoin-dev] Speedy covenants (OP_CAT2)
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Sun, 08 May 2022 02:03:41 -0000

--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--