MIME-Version: 1.0
References: <CAMZUoK=pkZuovtifBzdqhoyegzG+9hRTFEc7fG9nZPDK4KbU3w@mail.gmail.com>
 <87leymuiu8.fsf@rustcorp.com.au>
 <CAD5xwhgP2_51Dvar0f1tsMrCXZ61W9-HnLgR45D-54Oc7-X1ag@mail.gmail.com>
 <87k0dwr015.fsf@rustcorp.com.au>
 <CAD5xwhi4y1NiZ__c1WY-rCV3XBzN5yxY1Zox6Mc1FTjxUhXK9A@mail.gmail.com>
 <87a6err1h5.fsf@rustcorp.com.au>
In-Reply-To: <87a6err1h5.fsf@rustcorp.com.au>
From: "Russell O'Connor" <roconnor@blockstream.com>
Date: Tue, 15 Feb 2022 23:10:19 -0500
Message-ID: <CAMZUoKm3vQDOQ1PiMBhyJz+m9G+RsDSvZ0k-QwoW5+HMbkUOQw@mail.gmail.com>
To: Rusty Russell <rusty@rustcorp.com.au>
Content-Type: multipart/alternative; boundary="0000000000008c1a8905d81ad4c4"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] TXHASH + CHECKSIGFROMSTACKVERIFY in lieu of CTV
	and ANYPREVOUT
Precedence: list

--0000000000008c1a8905d81ad4c4
Content-Type: text/plain; charset="UTF-8"

On Tue, Feb 15, 2022 at 10:45 PM Rusty Russell <rusty@rustcorp.com.au>
wrote:

> Jeremy Rubin <jeremy.l.rubin@gmail.com> writes:
> > Hi Rusty,
> >
> > Please see my post in the other email thread
> >
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/019886.html
> >
> > The differences in this regard are several, and worth understanding
> beyond
> > "you can iterate CTV". I'd note a few clear examples for showing that
> "CTV
> > is just as powerful" is not a valid claim:
> >
> > 1) CTV requires the contract to be fully enumerated and is non-recursive.
> > For example, a simple contract that allows n participants to take an
> action
> > in any order requires factorially many pre-computations, not just linear
> or
> > constant. For reference, 24! is about 2**80. Whereas for a more
> > interpretive covenant -- which is often introduced with the features for
> > recursion -- you can compute the programs for these addresses in constant
> > time.
> > 2) CTV requires the contract to be fully enumerated: For example, a
> simple
> > contract one could write is "Output 0 script matches Output 1", and the
> set
> > of outcomes is again unbounded a-priori. With CTV you need to know the
> set
> > of pairs you'd like to be able to expand to a-priori
> > 3) Combining 1 and 2, you could imagine recursing on an open-ended thing
> > like creating many identical outputs over time but not constraining what
> > those outputs are. E.g., Output 0 matches Input 0, Output 1 matches
> Output
> > 2.
>
> Oh agreed.  It was distinction of "recursive" vs "not recursive" which
> was less useful in this context.
>
> "limited to complete enumeration" is the more useful distinction: it's a
> bright line between CTV and TXHASH IMHO.
>

If TXHASH is limited to requiring the flags be included in the hash (as is
done with sighash) I believe TXHASH has the same "up front" nature that CTV
has.

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

<div dir=3D"ltr"><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail=
_attr">On Tue, Feb 15, 2022 at 10:45 PM Rusty Russell &lt;<a href=3D"mailto=
:rusty@rustcorp.com.au">rusty@rustcorp.com.au</a>&gt; wrote:<br></div><bloc=
kquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:=
1px solid rgb(204,204,204);padding-left:1ex">Jeremy Rubin &lt;<a href=3D"ma=
ilto:jeremy.l.rubin@gmail.com" target=3D"_blank">jeremy.l.rubin@gmail.com</=
a>&gt; writes:<br>
&gt; Hi Rusty,<br>
&gt;<br>
&gt; Please see my post in the other email thread<br>
&gt; <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/202=
2-February/019886.html" rel=3D"noreferrer" target=3D"_blank">https://lists.=
linuxfoundation.org/pipermail/bitcoin-dev/2022-February/019886.html</a><br>
&gt;<br>
&gt; The differences in this regard are several, and worth understanding be=
yond<br>
&gt; &quot;you can iterate CTV&quot;. I&#39;d note a few clear examples for=
 showing that &quot;CTV<br>
&gt; is just as powerful&quot; is not a valid claim:<br>
&gt;<br>
&gt; 1) CTV requires the contract to be fully enumerated and is non-recursi=
ve.<br>
&gt; For example, a simple contract that allows n participants to take an a=
ction<br>
&gt; in any order requires factorially many pre-computations, not just line=
ar or<br>
&gt; constant. For reference, 24! is about 2**80. Whereas for a more<br>
&gt; interpretive covenant -- which is often introduced with the features f=
or<br>
&gt; recursion -- you can compute the programs for these addresses in const=
ant<br>
&gt; time.<br>
&gt; 2) CTV requires the contract to be fully enumerated: For example, a si=
mple<br>
&gt; contract one could write is &quot;Output 0 script matches Output 1&quo=
t;, and the set<br>
&gt; of outcomes is again unbounded a-priori. With CTV you need to know the=
 set<br>
&gt; of pairs you&#39;d like to be able to expand to a-priori<br>
&gt; 3) Combining 1 and 2, you could imagine recursing on an open-ended thi=
ng<br>
&gt; like creating many identical outputs over time but not constraining wh=
at<br>
&gt; those outputs are. E.g., Output 0 matches Input 0, Output 1 matches Ou=
tput<br>
&gt; 2.<br>
<br>
Oh agreed.=C2=A0 It was distinction of &quot;recursive&quot; vs &quot;not r=
ecursive&quot; which<br>
was less useful in this context.<br>
<br>
&quot;limited to complete enumeration&quot; is the more useful distinction:=
 it&#39;s a<br>
bright line between CTV and TXHASH IMHO.<br></blockquote><div><br></div><di=
v>If TXHASH is limited to requiring the flags be included in the hash (as i=
s done with sighash) I believe TXHASH has the same &quot;up front&quot; nat=
ure that CTV has.<br></div></div></div>

--0000000000008c1a8905d81ad4c4--