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>
In-Reply-To: <5keA_aPvmCO5yBh_mBQ6Z5SwnnvEW0T-3vahesaDh57f-qv4FbG1SFAzDvT3rFhre6kFl282VsxV_pynwn_CdvF7fzH2q9NW1ZQHPH1pmdo=@protonmail.com>
From: "Russell O'Connor" <roconnor@blockstream.com>
Date: Mon, 5 Jul 2021 13:20:22 -0400
Message-ID: <CAMZUoKnuRXNG1pyupHrL+Wo80TXTbADVrexoB=+BKC633v-qMw@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000df411705c6638560"
Subject: Re: [bitcoin-dev] Unlimited covenants,
 was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin
Precedence: list

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

Hi ZmnSCPxj,

I don't believe we need to ban Turing completeness for the sake of banning
Turing completeness.  My concerns have always been around ensuring that
transaction and block validation is not unduly burdensome for nodes.  So
for Bitcoin Script, we want to bound the amount of resources needed to
execute it, preferably as a linear function of weight[1], and preferably
have it clear what the evaluation costs are going to be prior to
evaluation[2].  We also want to keep Script execution as a pure function of
the transaction data so that nodes do not need to reevaluate their mempool
on every new block.  For consensus purposes we prefer to have simple
primitive operations that have clear and precise semantics that are as
likely as possible to be reimplemented correctly if they are reimplemented
(or at least let us not make this problem worse than it already is).  In
particular, Script needs to be easy to parse to avoid weird parsing
machines that lead to security vulnerabilities within node software.

While the above design constraints imply a prohibition on Turing complete
computation within a single Script, they do not imply a prohibition on
arbitrary, covenant-enabled computations that spans across multiple
transactions.  Neither would these constraints prohibit some kind of STARK
or SNARK tapleaf version that was somehow capable of succinctly
representing arbitrary computations, so long as validation costs remain
bounded.

And while it is true that covenant-enabled computations could allow users
to put their funds at risk through weird machines that manipulate their
money on the blockchain, as longs as that weirdness stays at that level of
the abstract Bitcoin Script machine, then I suppose it is *caveat emptor*;
don't send your funds to random unverified Bitcoin Scripts, advice that is
already the case today.  We can keep that potential weirdness at bay by
keeping Script simple, and maintaining our understanding that the Script
programs (like the rest of the blockchain data) are untrusted inputs and
they need to be validated and scrutinized before interpretation.

[1] In tapscript I believe all operations are linear time with the
exception of OP_ROLL.  However OP_ROLL is still constrained by global
limits on stack size, etc.
[2] In Bitcoin Script, without loops of any kind, every opcode is evaluated
at most once, so counting opcodes is an easy way to put an upper bound on
your costs before evaluation.

On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Dave,
>
> > On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> >
> > > However, I think the broader community is unconvinced by the cost
> benefit
> > > of arbitrary covenants. See
> > >
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > > as a recent example. Therefore as a critical part of building
> consensus on
> > > various techniques I've worked to emphasize that specific additions do
> not
> > > entail risk of accidentally introducing more than was bargained for to
> > > respect the concerns of others.
> >
> > Respecting the concerns of others doesn't require lobotomizing useful
> > tools. Being respectful can also be accomplished by politely showing
> > that their concerns are unfounded (or at least less severe than they
> > thought). This is almost always the better course IMO---it takes much
> > more effort to satisfy additional engineering constraints (and prove to
> > reviewers that you've done so!) than it does to simply discuss those
> > concerns with reasonable stakeholders. As a demonstration, let's look
> > at the concerns from Shinobi's post linked above:
> >
> > They seem to be worried that some Bitcoin users will choose to accept
> > coins that can't subsequently be fungibily mixed with other bitcoins.
> > But that's already been the case for a decade: users can accept altcoins
> > that are non-fungible with bitcoins.
> >
> > They talk about covenants where spending is controlled by governments,
> > but that seems to me exactly like China's CBDC trial.
> >
> > They talk about exchanges depositing users' BTC into a covenant, but
> > that's just a variation on the classic not-your-keys-not-your-bitcoins
> > problem. For all you know, your local exchange is keeping most of its
> > BTC balance commitments in ETH or USDT.
> >
> > To me, it seems like the worst-case problems Shinobi describes with
> > covenants are some of the same problems that already exist with
> > altcoins. I don't see how recursive covenants could make any of those
> > problems worse, and so I don't see any point in limiting Bitcoin's
> > flexibility to avoid those problems when there are so many interesting
> > and useful things that unlimited covenants could do.
>
> The "altcoins are even worse" argument does seem quite convincing, and if
> Bitcoin can survive altcoins, surely it can survive covenants too?
>
> In before "turns out covenants are the next ICO".
> i.e. ICOs are just colored coins, which are useful for keeping track of
> various stuff, but have then been used as a vehicle to scam people.
> But I suppose that is a problem that humans will always have: limited
> cognition, so that *good* popular things that are outside your specific
> field of study are indistinguishable from *bad* popular things.
> So perhaps it should not be a concern on a technical level.
> Maybe we should instead make articles about covenants so boring nobody
> will hype about it (^^;)v.
>
> Increased functionality implies increased processing, and hopefully
> computation devices are getting cheap enough that the increased processing
> implied by new features should not be too onerous.
>
>
>
> To my mind, an "inescapable" covenant (i.e. one that requires the output
> to be paid to the same covenant) is basically a Turing machine, and
> equivalent to a `while (true);` loop.
> In a `while (true);` loop, the state of the machine reverts back to the
> same state, and it repeats again.
> In an inescpable covenant, the control of some amount of funds reverts
> back to the same controlling SCRIPT, and it repeats again.
> Yes, you can certainly add more functionality on top of that loop, just
> think of program main loops for games or daemons, which are, in essence,
> "just" `while (true) ...`.
> But basically, such unbounded infinite loops are possible only under
> Turing machines, thus I consider covenants to be Turing-complete.
> Principle of Least Power should make us wonder if we need full Turing
> machines for the functionality.
>
> On the other hand --- codata processing *does* allow for unbounded loops,
> without requiring full Turing-completeness; they just require total
> functionality, not partial (and Turing-completeness is partial, not total).
> Basically, data structures are unbounded storage, while codata structures
> are unbounded processing.
> Perhaps covenants can encode an upper bound on the number of recursions,
> which prevents full Turing-completeness while allowing for a large number
> of use-cases.
>
> (if the above paragraph makes no sense to you, hopefully this Wikipedia
> article will help:
> https://en.wikipedia.org/wiki/Total_functional_programming )
> (basically my argument here is based on academic programming stuff, and
> might not actually matter in real life)
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr"><div>Hi ZmnSCPxj,</div><div><br></div><div>I don&#39;t bel=
ieve we need to ban Turing completeness for the sake of banning Turing comp=
leteness.=C2=A0 My concerns have always been around ensuring that transacti=
on and block validation is not unduly burdensome for nodes.=C2=A0 So for Bi=
tcoin Script, we want to bound the amount of resources needed to execute it=
, preferably as a linear function of weight[1], and preferably have it clea=
r what the evaluation costs are going to be prior to evaluation[2].=C2=A0 W=
e also want to keep Script execution as a pure function of the transaction =
data so that nodes do not need to reevaluate their mempool on every new blo=
ck.=C2=A0 For consensus purposes we prefer to have simple primitive operati=
ons that have clear and precise semantics that are as likely as possible to=
 be reimplemented correctly if they are reimplemented (or at least let us n=
ot make this problem worse than it already is).=C2=A0 In particular, Script=
 needs to be easy to parse to avoid weird parsing machines that lead to sec=
urity vulnerabilities within node software.<br></div><div><br></div><div>Wh=
ile the above design constraints imply a prohibition on Turing complete com=
putation within a single Script, they do not imply a prohibition on arbitra=
ry, covenant-enabled computations that spans across multiple transactions.=
=C2=A0 Neither would these constraints prohibit some kind of STARK or SNARK=
 tapleaf version that was somehow capable of succinctly representing arbitr=
ary computations, so long as validation costs remain bounded.</div><div><br=
></div><div>And while it is true that covenant-enabled computations could a=
llow users to put their funds at risk through weird machines that manipulat=
e their money on the blockchain, as longs as that weirdness stays at that l=
evel of the abstract Bitcoin Script machine, then I suppose it is <i>caveat=
 emptor</i>; don&#39;t send your funds to random unverified Bitcoin Scripts=
, advice that is already the case today.=C2=A0 We can keep that potential w=
eirdness at bay by keeping Script simple, and maintaining our understanding=
 that the Script programs (like the rest of the blockchain data) are untrus=
ted inputs and they need to be validated and scrutinized before interpretat=
ion.<br></div><div><br></div><div>[1] In tapscript I believe all operations=
 are linear time with the exception of OP_ROLL.=C2=A0 However OP_ROLL is st=
ill constrained by global limits on stack size, etc.</div><div>[2] In Bitco=
in Script, without loops of any kind, every opcode is evaluated at most onc=
e, so counting opcodes is an easy way to put an upper bound on your costs b=
efore evaluation.<br></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" =
class=3D"gmail_attr">On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-de=
v &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@=
lists.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmai=
l_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,20=
4,204);padding-left:1ex">Good morning Dave,<br>
<br>
&gt; On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:<br>
&gt;<br>
&gt; &gt; However, I think the broader community is unconvinced by the cost=
 benefit<br>
&gt; &gt; of arbitrary covenants. See<br>
&gt; &gt; <a href=3D"https://medium.com/block-digest-mempool/my-worries-abo=
ut-too-generalized-covenants-5eff33affbb6" rel=3D"noreferrer" target=3D"_bl=
ank">https://medium.com/block-digest-mempool/my-worries-about-too-generaliz=
ed-covenants-5eff33affbb6</a><br>
&gt; &gt; as a recent example. Therefore as a critical part of building con=
sensus on<br>
&gt; &gt; various techniques I&#39;ve worked to emphasize that specific add=
itions do not<br>
&gt; &gt; entail risk of accidentally introducing more than was bargained f=
or to<br>
&gt; &gt; respect the concerns of others.<br>
&gt;<br>
&gt; Respecting the concerns of others doesn&#39;t require lobotomizing use=
ful<br>
&gt; tools. Being respectful can also be accomplished by politely showing<b=
r>
&gt; that their concerns are unfounded (or at least less severe than they<b=
r>
&gt; thought). This is almost always the better course IMO---it takes much<=
br>
&gt; more effort to satisfy additional engineering constraints (and prove t=
o<br>
&gt; reviewers that you&#39;ve done so!) than it does to simply discuss tho=
se<br>
&gt; concerns with reasonable stakeholders. As a demonstration, let&#39;s l=
ook<br>
&gt; at the concerns from Shinobi&#39;s post linked above:<br>
&gt;<br>
&gt; They seem to be worried that some Bitcoin users will choose to accept<=
br>
&gt; coins that can&#39;t subsequently be fungibily mixed with other bitcoi=
ns.<br>
&gt; But that&#39;s already been the case for a decade: users can accept al=
tcoins<br>
&gt; that are non-fungible with bitcoins.<br>
&gt;<br>
&gt; They talk about covenants where spending is controlled by governments,=
<br>
&gt; but that seems to me exactly like China&#39;s CBDC trial.<br>
&gt;<br>
&gt; They talk about exchanges depositing users&#39; BTC into a covenant, b=
ut<br>
&gt; that&#39;s just a variation on the classic not-your-keys-not-your-bitc=
oins<br>
&gt; problem. For all you know, your local exchange is keeping most of its<=
br>
&gt; BTC balance commitments in ETH or USDT.<br>
&gt;<br>
&gt; To me, it seems like the worst-case problems Shinobi describes with<br=
>
&gt; covenants are some of the same problems that already exist with<br>
&gt; altcoins. I don&#39;t see how recursive covenants could make any of th=
ose<br>
&gt; problems worse, and so I don&#39;t see any point in limiting Bitcoin&#=
39;s<br>
&gt; flexibility to avoid those problems when there are so many interesting=
<br>
&gt; and useful things that unlimited covenants could do.<br>
<br>
The &quot;altcoins are even worse&quot; argument does seem quite convincing=
, and if Bitcoin can survive altcoins, surely it can survive covenants too?=
<br>
<br>
In before &quot;turns out covenants are the next ICO&quot;.<br>
i.e. ICOs are just colored coins, which are useful for keeping track of var=
ious stuff, but have then been used as a vehicle to scam people.<br>
But I suppose that is a problem that humans will always have: limited cogni=
tion, so that *good* popular things that are outside your specific field of=
 study are indistinguishable from *bad* popular things.<br>
So perhaps it should not be a concern on a technical level.<br>
Maybe we should instead make articles about covenants so boring nobody will=
 hype about it (^^;)v.<br>
<br>
Increased functionality implies increased processing, and hopefully computa=
tion devices are getting cheap enough that the increased processing implied=
 by new features should not be too onerous.<br>
<br>
<br>
<br>
To my mind, an &quot;inescapable&quot; covenant (i.e. one that requires the=
 output to be paid to the same covenant) is basically a Turing machine, and=
 equivalent to a `while (true);` loop.<br>
In a `while (true);` loop, the state of the machine reverts back to the sam=
e state, and it repeats again.<br>
In an inescpable covenant, the control of some amount of funds reverts back=
 to the same controlling SCRIPT, and it repeats again.<br>
Yes, you can certainly add more functionality on top of that loop, just thi=
nk of program main loops for games or daemons, which are, in essence, &quot=
;just&quot; `while (true) ...`.<br>
But basically, such unbounded infinite loops are possible only under Turing=
 machines, thus I consider covenants to be Turing-complete.<br>
Principle of Least Power should make us wonder if we need full Turing machi=
nes for the functionality.<br>
<br>
On the other hand --- codata processing *does* allow for unbounded loops, w=
ithout requiring full Turing-completeness; they just require total function=
ality, not partial (and Turing-completeness is partial, not total).<br>
Basically, data structures are unbounded storage, while codata structures a=
re unbounded processing.<br>
Perhaps covenants can encode an upper bound on the number of recursions, wh=
ich prevents full Turing-completeness while allowing for a large number of =
use-cases.<br>
<br>
(if the above paragraph makes no sense to you, hopefully this Wikipedia art=
icle will help: <a href=3D"https://en.wikipedia.org/wiki/Total_functional_p=
rogramming" rel=3D"noreferrer" target=3D"_blank">https://en.wikipedia.org/w=
iki/Total_functional_programming</a> )<br>
(basically my argument here is based on academic programming stuff, and mig=
ht not actually matter in real life)<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>

--000000000000df411705c6638560--