Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id A3EFDC000B for ; Tue, 15 Feb 2022 19:12:44 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 798AA40385 for ; Tue, 15 Feb 2022 19:12:44 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.899 X-Spam-Level: X-Spam-Status: No, score=-1.899 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_HELO_NONE=0.001, 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.20210112.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 meqXPDDWTGpF for ; Tue, 15 Feb 2022 19:12:42 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-qv1-xf34.google.com (mail-qv1-xf34.google.com [IPv6:2607:f8b0:4864:20::f34]) by smtp2.osuosl.org (Postfix) with ESMTPS id A302040018 for ; Tue, 15 Feb 2022 19:12:42 +0000 (UTC) Received: by mail-qv1-xf34.google.com with SMTP id p7so27228qvk.11 for ; Tue, 15 Feb 2022 11:12:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream-com.20210112.gappssmtp.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=2Pvbh+5LQEcUlsffOMHBCaaBqY3Rpr+5yiWcdiT6rls=; b=08/iXzkmJrH8Q3y7dJn64vuIN6WP9hzoPK1U7QtD8Fs6Bs5vmAyLzcyA1+/+EQX9RQ HS5KdB+3uzZuRJb2BHBHUJgW2I6QktunVeyoXebNwgcuYbmPNvZ6gVNLQl5rBg/iEA7Q auTKxj/hJwP3mc733mggy5AJSnWNTKkJeelFn4021JRWKe0iU4loo2KHdWoYpclRSOuR DCJVczfarcnO/neQH3D76HaGvBZKHZl953BjhEWVOGqEtJj+mqbO3yBQ5vPWBx9zG9Bm QP+TZtCmtqiLazRashchhhqlK6fPxdikFKVNql58O5rpWCEk7d2HQ87y8fZlrHaFlYWt 5z+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=2Pvbh+5LQEcUlsffOMHBCaaBqY3Rpr+5yiWcdiT6rls=; b=O9Mo+CPfcGjsdC8bG+7LdBaMKhdX5c5i76JJoCKG3pc3bAK87l1DyyzDKgF+X26Y0q ZJdij3JlsjZ3woKYTbGVDosPQaoAB+NSKPK2Rm/ERhkuGHADVNvNm2kO90A2KAfMjJGG LM1p8s2NEmLVws3DhK9zMnMRF12s2x9EJrF/iReLaAaNidp0OQvxbDnuRbxxU4uEa5QC aoVyCwTx+8apaAoHC4ija0qI7Rjt7WRdve+XRec9jzOH3Gs7OSZ9vWzO6E/AdgkQBgX1 pGzEOaYywj7zHbd4RXxcNoqttjJ0AGpBQ5pek1Jbgxm5iOGyYqra140GlB5P0v1X8wtC dRqw== X-Gm-Message-State: AOAM532N0X5ZmfAFR0f3x6s8x26wMNBoq+l9xh7fE0k2Yb9HZke/1krw mTvwIldDE//LX0A5Hf2yQEL4DOczieJQNjbqy/w0r209H6w= X-Google-Smtp-Source: ABdhPJwJObAAlfU3BR8QtIuHYxb6FYeKPij1hZl4Zl/wXtOt5wEllrjw6BjNDLf2U06Cu6SoUsPlnXxqW/sg4X/BHFw= X-Received: by 2002:ad4:5b89:: with SMTP id 9mr439874qvp.63.1644952361497; Tue, 15 Feb 2022 11:12:41 -0800 (PST) MIME-Version: 1.0 References: <87leymuiu8.fsf@rustcorp.com.au> <87k0dwr015.fsf@rustcorp.com.au> In-Reply-To: From: "Russell O'Connor" Date: Tue, 15 Feb 2022 14:12:30 -0500 Message-ID: To: Jeremy Rubin Content-Type: multipart/alternative; boundary="0000000000002e0c9405d813511d" Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] TXHASH + CHECKSIGFROMSTACKVERIFY in lieu of CTV and ANYPREVOUT 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, 15 Feb 2022 19:12:44 -0000 --0000000000002e0c9405d813511d Content-Type: text/plain; charset="UTF-8" On Tue, Feb 15, 2022 at 1:57 PM Jeremy Rubin wrote: > 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. > > I think for your point the inverse seems to hold: for the limited > situations we might want to set up, CTV often ends up being sufficient > because usually we can enumerate all the possible outcomes we'd like (or at > least find a mapping onto such a construction). CTV is indeed very > powerful, but as I demonstrated above, not powerful in the same way > ("Complexity Class") that OP_TX or TXHASH might be. > Just to be clear, if OP_TXHASH is restricted to including the flags for the values to be hashed (at least for OP_TXHASH0), we don't appear to enter recursive covenant territory, as long as we remain without OP_CAT. > At the very least we should clearly understand *what* and *why* we are > advocating for more sophisticated designs and have a thorough understanding > of the protocol complexity we are motivated to introduce the expanded > functionality. Further, if one advocates for TX/TXHASH on a featureful > basis, it's at least a technical ACK on the functionality CTV is > introducing (as it is a subset) and perhaps a disagreement on project > management, which I think is worth noting. There is a very wide gap between > "X is unsafe" and "I prefer Y which X is a subset of ''. > I'm certainly of the opinion we should have some feature to enable the commitment of outputs. It seems quite useful in various protocols. --0000000000002e0c9405d813511d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Tue, Feb 15, 2022 at 1:57 PM Jeremy Rubin <jeremy.l.rubin@gmail.com> wrote:
<= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft:1px solid rgb(204,204,204);padding-left:1ex">
Hi Rusty,


The differences in this regard are several, and wor= th 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 require= s factorially many pre-computations, not just linear or constant. For refer= ence, 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 req= uires the contract to be fully enumerated: For example, a simple contract o= ne 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 th= ose outputs are. E.g., Output 0 matches Input 0, Output 1 matches Output 2.=

I think for your point the inverse = seems to hold: for the limited situations we might want to set up, CTV ofte= n ends up being sufficient because usually we can enumerate all the possibl= e outcomes we'd like (or at least find a mapping onto such a constructi= on). CTV is indeed very powerful, but as I demonstrated above, not powerful= in the same way ("Complexity Class") that OP_TX or TXHASH might = be.

Just to be cle= ar, if OP_TXHASH is restricted to including the flags for the values to be = hashed (at least for OP_TXHASH0), we don't appear to enter recursive co= venant territory, as long as we remain without OP_CAT.
=C2=A0=
At the very least we should cl= early understand what=C2=A0and why=C2=A0we are advocating for= more sophisticated designs and have a thorough understanding of the protoc= ol complexity we are motivated to introduce the expanded functionality.=C2= =A0Further, if one advocates for TX/TXHASH on a featureful basis, it's = at least a technical ACK on the functionality CTV is introducing (as it is = a subset) and perhaps a disagreement on project management, which I think i= s worth noting. There is a very wide gap between "X is unsafe" an= d "I prefer Y which X is a subset of ''.
=

I'm certainly of the opinion we = should have some feature to enable the commitment of outputs.=C2=A0 It seem= s quite useful in various protocols.
--0000000000002e0c9405d813511d--