MIME-Version: 1.0
References: <CAD5xwhjmu-Eee47Ho5eA6E6+aAdnchLU0OVZo=RTHaXnN17x8A@mail.gmail.com>
 <20210704011341.ddbiruuomqovrjn6@ganymede>
 <CAD5xwhimPBEV_tLpSPxs9B+XGUhvPx_dnhok=8=hyksyi4=B6g@mail.gmail.com>
 <20210704203230.37hlpdyzr4aijiet@ganymede>
 <5keA_aPvmCO5yBh_mBQ6Z5SwnnvEW0T-3vahesaDh57f-qv4FbG1SFAzDvT3rFhre6kFl282VsxV_pynwn_CdvF7fzH2q9NW1ZQHPH1pmdo=@protonmail.com>
 <CAMZUoKnuRXNG1pyupHrL+Wo80TXTbADVrexoB=+BKC633v-qMw@mail.gmail.com>
 <u2ETzW2-k7sjRKEz48C2n2QJvmWPVdhZIqtva_KvDNvxNDTVnR2zzYCL2Q8RUVkLm93OMJ2S2GOfUOxmdvNTaCIK1liebb4yvCCBBFB75f0=@protonmail.com>
In-Reply-To: <u2ETzW2-k7sjRKEz48C2n2QJvmWPVdhZIqtva_KvDNvxNDTVnR2zzYCL2Q8RUVkLm93OMJ2S2GOfUOxmdvNTaCIK1liebb4yvCCBBFB75f0=@protonmail.com>
From: "Russell O'Connor" <roconnor@blockstream.com>
Date: Wed, 7 Jul 2021 09:12:58 -0400
Message-ID: <CAMZUoK=rRDV4F7j64gTUqEB9EiBpwhZW6LP-FMR0FxR2Bc4iBw@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000cbb21c05c6884ce2"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Unlimited covenants,
 was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin
Precedence: list

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

On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Russell,
>
> > Hi ZmnSCPxj,
> >
> > I don't believe we need to ban Turing completeness for the sake of
> banning Turing completeness.
>
> Well I believe we should ban partial Turing-completeness, but allow total
> Turing-completeness.
>

Unfortunately, when it comes to cross-transaction computations, it is
infeasible to ban non-terminating computation.

The nature of recursive covenants is that the program "writes" the *source
code* next step of the computation to the scriptPubKey to one of the
outputs of its transaction. Technically speaking it verifies that the
scriptPubKey is a commitment to the source code of the next step of the
program, but morally that is the same as writing the source code.  Then the
next step of the computation is invoked by someone "evaluating* that next
step's source code by creating a valid transaction that spends the
generated output.

The point is this ability to create new source code and then evaluate it
leads to the ability to write universal (i.e non-terminating)
computations.  The only way to prevent it is to ban source code
manipulation, but since Bitcoin Script source code is just a string of
bytes, it would mean banning the manipulation of strings of bytes.  But the
entire Bitcoin Script language works by manipulating strings of bytes
within a stack machine.  Indeed the most trivial of non-terminating
programs can be implemented by extracting the current input's scriptPubKey
from the sighash and "writing" the identical scriptPubKey to one of its
outputs.  That example hardly takes any manipulation at all to implement.

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

<div dir=3D"ltr"><div dir=3D"ltr"><br></div><div class=3D"gmail_quote"><div=
 dir=3D"ltr" class=3D"gmail_attr">On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj =
&lt;<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a>&=
gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0=
px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Good =
morning Russell,<br>
<br>
&gt; Hi ZmnSCPxj,<br>
&gt;<br>
&gt; I don&#39;t believe we need to ban Turing completeness for the sake of=
 banning Turing completeness.<br>
<br>
Well I believe we should ban partial Turing-completeness, but allow total T=
uring-completeness.<br></blockquote><div><br></div><div>Unfortunately, when=
 it comes to cross-transaction computations, it is infeasible to ban non-te=
rminating computation.</div><div><br></div><div>The nature of recursive cov=
enants is that the program &quot;writes&quot; the *source code* next step o=
f the computation to the scriptPubKey to one of the outputs of its transact=
ion. Technically speaking it verifies that the scriptPubKey is a commitment=
 to the source code of the next step of the program, but morally that is th=
e same as writing the source code.=C2=A0 Then the next step of the computat=
ion is invoked by someone &quot;evaluating* that next step&#39;s source cod=
e by creating a valid transaction that spends the generated output.<br></di=
v><div><br></div><div>The point is this ability to create new source code a=
nd then evaluate it leads to the ability to write universal (i.e non-termin=
ating) computations.=C2=A0 The only way to prevent it is to ban source code=
 manipulation, but since Bitcoin Script source code is just a string of byt=
es, it would mean banning the manipulation of strings of bytes.=C2=A0 But t=
he entire Bitcoin Script language works by manipulating strings of bytes wi=
thin a stack machine.=C2=A0 Indeed the most trivial of non-terminating prog=
rams can be implemented by extracting the current input&#39;s scriptPubKey =
from the sighash and &quot;writing&quot; the identical scriptPubKey to one =
of its outputs.=C2=A0 That example hardly takes any manipulation at all to =
implement.<br></div></div></div>

--000000000000cbb21c05c6884ce2--