Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 9137FC000E for ; Tue, 6 Jul 2021 06:26:09 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 72F34607AB for ; Tue, 6 Jul 2021 06:26:09 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.098 X-Spam-Level: X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp3.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id zyUiaq99DJn0 for ; Tue, 6 Jul 2021 06:26:07 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-ed1-x534.google.com (mail-ed1-x534.google.com [IPv6:2a00:1450:4864:20::534]) by smtp3.osuosl.org (Postfix) with ESMTPS id 03CF960768 for ; Tue, 6 Jul 2021 06:26:06 +0000 (UTC) Received: by mail-ed1-x534.google.com with SMTP id m1so26447669edq.8 for ; Mon, 05 Jul 2021 23:26:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=zPLDdT9PRXNvgAtZsbJgXlNd3YswMqn/wgJ9xdcmG+I=; b=Qny7cnDZnYhgoCqr4dW6OaRYvnrdWopGguPriXoX6EIMrx9tVOb2rVwyXtBWvfj6o+ MHITHFXGQaIvG5M+GX0iNMAwk1ASylKpFhlLKpyfSDbyzd+LXbG8QH9QkUt3/o8q9Wta LqXUJi+8tHIjXFyLiS2bmBuRqZ06HcGv/d5Oxrg3Sq3rGTSumAaRqX5K8sQGL95aP+yM fuGnzmMowxJdcVQGpPEw6aNS8VE4X6L4jn1iOTULF3DlRiJw8l6XQJ5bIoJoRIbr6UaR q3k6DyJasB7b6CRRnhj8hsnbf44D6lNDtONnjyhZqd38LnKRlbhiT49ViDmjjoxPzgjx Li5g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=zPLDdT9PRXNvgAtZsbJgXlNd3YswMqn/wgJ9xdcmG+I=; b=VWKQnXREzMkPUhZ7j1GpQ8+qWAxPXZJVckvAO1uz7cAfK9QGtaXEtgROUXchXJYt36 3vBLy3iOKyT/KA8DtLq4TRf/IFNPb5Xnqbko7WKRmQ4kPlMwfKUu641E1QrtlbGDZG+o HJR8GX2LJjZNjHWf/zP91qOBACiS+t0Q7GSBDXxqRspoQ+3tKAHY5hKe023o8kACUeBn uZbzRmWQtk07SdkchFXoYfv/lRIYNduathARG0bxRNpaBLsTeCLqbKOdhmUQ+oduav6P aE4GmPHYh/Kue2IKFlzQlEoQRpt7D+glqpkvbRpJhNXtKanwPuCdorqqXP4OmwnHqFnI Fj4Q== X-Gm-Message-State: AOAM531/H4DZ17vISmoiFDPrnzgBkk1oHSjm6un9sYBuBHBi7aKCen9H RGe1LO/8b0yCR8nEzyzaiCZSNBZ/2LFd0jeVSoI= X-Google-Smtp-Source: ABdhPJwsNj/pzfKMq+LZG8raT10LideNfKIYYLwQX0r1lMbjRvjMfLillWvNVFUu5s1z1sb8n2GGexwRkbbGGeEYv1Y= X-Received: by 2002:a05:6402:4388:: with SMTP id o8mr3370643edc.338.1625552765140; Mon, 05 Jul 2021 23:26:05 -0700 (PDT) MIME-Version: 1.0 References: <20210704011341.ddbiruuomqovrjn6@ganymede> <20210704203230.37hlpdyzr4aijiet@ganymede> <5keA_aPvmCO5yBh_mBQ6Z5SwnnvEW0T-3vahesaDh57f-qv4FbG1SFAzDvT3rFhre6kFl282VsxV_pynwn_CdvF7fzH2q9NW1ZQHPH1pmdo=@protonmail.com> In-Reply-To: From: Billy Tetrud Date: Mon, 5 Jul 2021 23:25:48 -0700 Message-ID: To: "Russell O'Connor" , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="00000000000021451105c66e7f32" X-Mailman-Approved-At: Tue, 06 Jul 2021 08:35:55 +0000 Subject: Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 06 Jul 2021 06:26:09 -0000 --00000000000021451105c66e7f32 Content-Type: text/plain; charset="UTF-8" > when people are talking about enabling covenants, we are talking about whether OP_CAT should be allowed or not Are they? Are you implying that anything that enables covenants is equivalent to enabling OP_CAT? Generally when I think about enabling covenants, I'm thinking more about OP_CTV (or some similarly specific opcode ). > OP_TWEAK I wasn't able to find anything about what that is. Would you mind clarifying what that concept is? On Mon, Jul 5, 2021 at 10:20 AM Russell O'Connor via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > 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 >> > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --00000000000021451105c66e7f32 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
>=C2=A0 when people are talking about enabling covenants, we are talking about whet= her OP_CAT should be allowed or not

Are they? Are you im= plying that anything that enables covenants is equivalent to enabling OP_CA= T? Generally when I think about enabling covenants, I'm thinking more a= bout OP_CTV (or some similarly specific = opcode).

> OP_TWEAK=C2=A0

I wasn't able to find anything about=C2=A0what that is. Would y= ou mind clarifying what that concept is?=C2=A0

On Mon, Jul 5, 2021 at = 10:20 AM Russell O'Connor via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org&g= t; wrote:
Hi ZmnSCPxj,

I don't believe w= e need to ban Turing completeness for the sake of banning Turing completene= ss.=C2=A0 My concerns have always been around ensuring that transaction and= block validation is not unduly burdensome for nodes.=C2=A0 So for Bitcoin = Script, we want to bound the amount of resources needed to execute it, pref= erably as a linear function of weight[1], and preferably have it clear what= the evaluation costs are going to be prior to evaluation[2].=C2=A0 We also= want to keep Script execution as a pure function of the transaction data s= o that nodes do not need to reevaluate their mempool on every new block.=C2= =A0 For consensus purposes we prefer to have simple primitive operations th= at have clear and precise semantics that are as likely as possible to be re= implemented correctly if they are reimplemented (or at least let us not mak= e 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 security = vulnerabilities within node software.

While th= e above design constraints imply a prohibition on Turing complete computati= on within a single Script, they do not imply a prohibition on arbitrary, co= venant-enabled computations that spans across multiple transactions.=C2=A0 = Neither would these constraints prohibit some kind of STARK or SNARK taplea= f version that was somehow capable of succinctly representing arbitrary com= putations, so long as validation costs remain bounded.

=
And while it is true that covenant-enabled computations could allow us= ers 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, advic= e that is already the case today.=C2=A0 We can keep that potential weirdnes= s at bay by keeping Script simple, and maintaining our understanding that t= he Script programs (like the rest of the blockchain data) are untrusted inp= uts and they need to be validated and scrutinized before interpretation.

[1] In tapscript I believe all operations are li= near time with the exception of OP_ROLL.=C2=A0 However OP_ROLL is still con= strained by global limits on stack size, etc.
[2] In Bitcoin Scri= pt, without loops of any kind, every opcode is evaluated at most once, so c= ounting opcodes is an easy way to put an upper bound on your costs before e= valuation.

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-generaliz= ed-covenants-5eff33affbb6
> > as a recent example. Therefore as a critical part of building con= sensus on
> > various techniques I've worked to emphasize that specific add= itions do not
> > entail risk of accidentally introducing more than was bargained f= or to
> > respect the concerns of others.
>
> Respecting the concerns of others doesn't require lobotomizing use= ful
> 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<= br> > more effort to satisfy additional engineering constraints (and prove t= o
> reviewers that you've done so!) than it does to simply discuss tho= se
> concerns with reasonable stakeholders. As a demonstration, let's l= ook
> at the concerns from Shinobi's post linked above:
>
> They seem to be worried that some Bitcoin users will choose to accept<= br> > coins that can't subsequently be fungibily mixed with other bitcoi= ns.
> But that's already been the case for a decade: users can accept al= tcoins
> 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, b= ut
> that's just a variation on the classic not-your-keys-not-your-bitc= oins
> problem. For all you know, your local exchange is keeping most of its<= br> > 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 th= ose
> problems worse, and so I don't see any point in limiting Bitcoin&#= 39;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 var= ious 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 cogni= tion, 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 computa= tion 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 sam= e 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 thi= nk 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 machi= nes for the functionality.

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).
Basically, data structures are unbounded storage, while codata structures a= re unbounded processing.
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.

(if the above paragraph makes no sense to you, hopefully this Wikipedia art= icle will help: https://en.wikipedia.org/w= iki/Total_functional_programming )
(basically my argument here is based on academic programming stuff, and mig= ht not actually matter in real life)

Regards,
ZmnSCPxj
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--00000000000021451105c66e7f32--