Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 08978C000E for ; Wed, 7 Jul 2021 14:24:31 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id DE591401BB for ; Wed, 7 Jul 2021 14:24:30 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.9 X-Spam-Level: X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp2.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=blockstream-com.20150623.gappssmtp.com 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 HcGuR-ydIjfj for ; Wed, 7 Jul 2021 14:24:30 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-qv1-xf36.google.com (mail-qv1-xf36.google.com [IPv6:2607:f8b0:4864:20::f36]) by smtp2.osuosl.org (Postfix) with ESMTPS id D38F34002B for ; Wed, 7 Jul 2021 14:24:29 +0000 (UTC) Received: by mail-qv1-xf36.google.com with SMTP id i4so617159qvq.10 for ; Wed, 07 Jul 2021 07:24:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream-com.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=+n3iC7VxtH5jgiLfGJkxnWdOutXUrBsKi+HiuXcXwh0=; b=O4lL9zvyuHNvobqVCjxvOrVgGVV0sKSxesu70dZO391oanNDj21QwLo6SBtkoVMoaV duBO5qoEvL1XxCVO3KVcP2CQ57EOGQwbVQFbafEuMRC5M9iqqj5Y8DW0aMcJpzuJDRLi dT9q+9SAzpeUZnk+QT8wjdBENnUn+DUTmJhGGaYVlfMLxHSZUgOddTrr+1ZZgNPofKVT zbdxKV0wFYa3i2n+WclnWpd8kVrb1wH2PemqFD5oNVQHXii0fgciH/RVeqJ8//rJP7OW 13LceUvot2pnhsWO6/VeAa9EgS3NH7+h9rw6MkpUSEf5zpfk1JLQ6GpadgJ1Y12PAurq PrKQ== 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=+n3iC7VxtH5jgiLfGJkxnWdOutXUrBsKi+HiuXcXwh0=; b=gR7ZoqSClaly3nWYMblYGGSai1fl9BsnOYy2nqV5R3gH5ZL1n7YIheAdNVkL4JG2dv Z6dkwNWMc5OhvY28IKd7uABJc8qK89/1yLs0aWarQ4Ijq09KbijqK5J0sheRo/+Y3P+Q sNr6WTRKMSIZeHxeZcSrwW4lb+qY7NgXcnyq6GT8L9kTFmx/AE5yrz/PcfDgIqtwh4YR P5BZhsmSEdrKfaYOphaLVQy5jpahhQeq9B37PghLhQ3c/5+diucI7fK0QKc1am0MbwvP abezYYbm2Isr/6xpo2K9rYMdp693Nykd9rgZj8L8PTv1x0uIfnsTMX4rHwvJmaWPv4RH yXKw== X-Gm-Message-State: AOAM531JsPPBwxTcGZtFCjZictt+I+ItXDvzlZSHq8jMZTvud5RXDDQk aAaYkuG6FwYB2L1u0b3N+MzvLBvH9K+4xZCA21u9fA== X-Google-Smtp-Source: ABdhPJyE8YpoUzkuib33IlMuIO3dtRPZT24HwKNzpQ/P2d9DnmDpk1zwu+Vrinjqx4Cv+4AuHPjp5Yfc6FXCIkETbfw= X-Received: by 2002:a0c:eb51:: with SMTP id c17mr17804182qvq.13.1625667868605; Wed, 07 Jul 2021 07:24:28 -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: "Russell O'Connor" Date: Wed, 7 Jul 2021 10:24:17 -0400 Message-ID: To: ZmnSCPxj Content-Type: multipart/alternative; boundary="000000000000d4cfa205c6894bae" Cc: Bitcoin Protocol Discussion 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: Wed, 07 Jul 2021 14:24:31 -0000 --000000000000d4cfa205c6894bae Content-Type: text/plain; charset="UTF-8" On Wed, Jul 7, 2021 at 9:12 AM Russell O'Connor wrote: > > On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj 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. > A follow up: Because recursive covenants need to be sent to a new transaction in order to recurse, you might choose to view this stepping mechanism as productive by modeling each transaction step as the continue constructor in your RecResult codata type. Indeed after (drinking coffee and) rereading your mailing list item, it seems that this is the point you were making. So sorry for my hasty response. I believe we are largely in agreement here. --000000000000d4cfa205c6894bae Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Wed, Jul 7, 2021 at 9:12 AM Russell O'Connor <roconnor@blockstream.com> wrote:
=

On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj <ZmnSCPxj@protonmail.com&= gt; 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 T= uring-completeness.

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

The nature of recursive cov= enants is that the program "writes" 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 "evaluating* that next step's source cod= e by creating a valid transaction that spends the generated output.

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's scriptPubKey = from the sighash and "writing" the identical scriptPubKey to one = of its outputs.=C2=A0 That example hardly takes any manipulation at all to = implement.

A follow u= p:=C2=A0 Because recursive covenants need to be sent to a new transaction i= n order to recurse, you might choose to view this stepping mechanism as pro= ductive by modeling each transaction step as the continue constructor in yo= ur RecResult codata type.=C2=A0 Indeed after (drinking coffee and) rereadin= g your mailing list item, it seems that this is the point you were making.<= /div>

So sorry for my hasty response.=C2=A0 I believe we= are largely in agreement here.
--000000000000d4cfa205c6894bae--