Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 7F03AC000E for ; Sun, 4 Jul 2021 19:03:55 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 511F28367B for ; Sun, 4 Jul 2021 19:03:55 +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: smtp1.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=blockstream-com.20150623.gappssmtp.com Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id AiC9aXLI1XFX for ; Sun, 4 Jul 2021 19:03:54 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-qk1-x72d.google.com (mail-qk1-x72d.google.com [IPv6:2607:f8b0:4864:20::72d]) by smtp1.osuosl.org (Postfix) with ESMTPS id E08E683673 for ; Sun, 4 Jul 2021 19:03:53 +0000 (UTC) Received: by mail-qk1-x72d.google.com with SMTP id a4so7015449qkn.11 for ; Sun, 04 Jul 2021 12:03:53 -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=SRzLkGGCLQz+Aljo8t/edE523FnW54OjnTKN1dMgK0w=; b=xni8HeFYoYqzZ8f/N7n90gfFFnI9uXSCELMsMMEtjj+jIGy6Ytk39gwHt5ieviVnrM Z6lcvDv4X5IXZAjJ1VwYPehLKBGPVZMvUU19SB0Tm0gvzbsjB5WFltAX5+2e+07zOx3C Vl+CTBVs+1mXkTQPzYkZlHMLqt8r49TD+JANC5SZTRDVyr3vk6A6IrYCdJ88rP/mC1o4 FRLsqtge1XadumYSqEDY11uFBbzz7P4fPKL5oKkTrQkRN3QriugEUzp7kbgKkzbBBhmC X65XB09HnCO91wkdkRKbJ4LWHAkErHYx9SEXQ1lrmO1FBZ+qBY0NxiSV0jyxjiwO2NQ7 JnDw== 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=SRzLkGGCLQz+Aljo8t/edE523FnW54OjnTKN1dMgK0w=; b=ndrdXw4AyuQ2W3oPTgAd4Vrr1tbXj5+h6RYLHvPllBhJ9lTRSberV7yj7Jw7KfH4om bdDCZmFrO83M5xlBDLO7k7neQ6T8nO9Mq6m77Lcyi3ElrHxNDrS2sJ7VYAQPiXQFo3Cl 9G+rfIQCVOvOXDBnVNyW8CG002P7k+5RA1/d38+s8xmSpSQQcDGu09r4M888Gzh+5sqk uwhnfJiytq+jgZb5XrIoj8IaKTZHAJ3Ew1Dplym6/YNWpM+awPSrsdI8n5TGd5I+kh3t qi+xDGZi0ci2KVX8z0FnTHqOi2YU4osfcJxzWnBSO6CaFi/koFYDoft46fTbFG+99XCj BlHg== X-Gm-Message-State: AOAM530ZrvqoFArqafFcHvkjOE3ZCqeJ732oPaVYHse+JeLXb87rw67P /mbbEMacrqbQHxbGzLW9EBjap/sq5rKYMtZEKwY88Q== X-Google-Smtp-Source: ABdhPJx7e8YBI0L35HKlB+lSqXhjh9AkwiqAHi92uWNNwfAPLRw3LSnrauk/kjh65/mSyl18u6t1SiN0OQYHL65av0I= X-Received: by 2002:a05:620a:19a2:: with SMTP id bm34mr9234430qkb.330.1625425432406; Sun, 04 Jul 2021 12:03:52 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: "Russell O'Connor" Date: Sun, 4 Jul 2021 15:03:40 -0400 Message-ID: To: Jeremy Content-Type: multipart/alternative; boundary="0000000000008201d305c650d9ae" Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] 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: Sun, 04 Jul 2021 19:03:55 -0000 --0000000000008201d305c650d9ae Content-Type: text/plain; charset="UTF-8" On Sun, Jul 4, 2021 at 1:30 PM Jeremy wrote: > I don't really see the point of CHECKSIGFROMSTACKADD since it's not bound > to the txdata? When might you use this? > I don't feel strongly about *ADD. I just figured it might be useful to do a 2-of-3 between Alice, Bob and an Oracle signed value. But I don't have any particular use case in mind. Either way the *ADD functionality can be replicated by various SWAPs and ADDs etc, so we could just leave it out until it is wanted. > And yes -- "Add OP_CHECKSIGFROMSTACK and OP_CHECKSIGFROMSTACKVERIFY to > follow the semantics from bip340-342 when witness program is v1." is a bit > light on detail for what the BIP would end up looking like. If you're able > to open up the design process a bit more on that it would be good as I > think there are some topics worth discussing at large before things proceed > with Elements (assuming feature compatibility remains a goal). > I'm certainly open to a wider design process. We can open a specific issue on the Elements repo. That said, I don't see a particularly wide design space on this front. > The non-prehashed argument seems OK (at the cost of an extra byte...) but > are there specific applications for !=32 arguments? I can't think of a > particular one beyond perhaps efficiency. Can we safely use 0-520 byte > arguments? > One of the reasons given in the issue (yes, the thread there is very long) was that hashing the message requires the hash to be collision resistant while if you give the message directly it only requires the hash to be "random-prefix" collision / preimage resistant. For example SHA-1 is clearly not collision resistant but it appears to still be random-prefix collision resistant AFAIU. Another reason is that it allows for extremely fast signing oracles because and R value and the midstate of the hash can be precomputed all the way upto the application prefix, and if the message being signed is less than 55 bytes or so, the signing cost can be as low as one compression function and a little bit of non-EC modular arithmetic to compute S. If the message were required to be prehashed, then it would take a minimum of 2 compression function calls to sign, nearly doubling the signing time needed for the fast oracle. Even if BIP-0340 kept its requirements that the message be exactly 32 bytes, I would still be inclined to design CHECKSIGFROMSTACK for tapscript to take the 32-byte message from the stack instead of hashing a message itself (BIP-0340 does it's own hashing, so prehashing the message isn't a security concern in the same way it is for ECDSA.) This would keep the message off the blockchain, saving space and adding some amount of privacy and making the operation compatible with rolling SHA256 opcodes. But given that BIP-0340 is going to be extended to support non-32 byte messages, then there is no reason to impose a message length restriction on CHECKSIGFROMSTACK. Yes the operation will still be subject to stack item length restrictions. This is something script writers will have to be aware of, but I see little reason to support messages split across multiple stack items when we expect, by far, most messages to be 32-bytes, and I expect those rare non-32 byte messages are expected to be reasonably short. > Also do you have thoughts on the other questions i posed above? E.g. > splitting R/S could be helpful w/o CAT. > Regarding internal pubkeys and invalid pubkeys, I see no reason to deviate from whatever tapscript CHECKSIG* do. Regarding splitting R/S, This is harder because Elements does have CAT and I think we should add CAT to Bitcoin too. This game of trying to prevent covenants by restricting script to the point where we are not even allowed to have a CAT operation is a losing game. It's just a matter of time before we accidently introduce some way to enable covenants anyways, and it is not worth cutting off vast amounts of functionality in pursuit of this questionable goal. And I say this as someone who was originally of the opinion that we should be very very cautious before enabling new expressivity such as covenants. All the scary scenarios of covenants that I am aware of can be more easily, cheaply, and flexibility implemented by just having a counterparty in a multi-party signature that enforces their own policy that they only sign transactions that pay to outputs that they remain a party to. And even if scary covenants were scarier than what can already be done by multisig and policy, I still don't think they are scary enough to warrant keeping CAT disabled. So I don't think we should get fancy with CHECKSIGFROMSTACK. Just take a normal 64-byte signature value as a stack item. But I don't feel strongly about this, and I wouldn't oppose splitting R and S in Bitcoin if that is where consensus lies. --0000000000008201d305c650d9ae Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Sun, Jul 4, 2021 at 1:30 PM Jeremy <jlrubin@mit.edu> wrote:
I don't really see the point of CHECKSIGFROMSTACKADD since it's no= t bound to the txdata? When might you use this?

I don't feel strongly about *ADD.=C2=A0 I ju= st figured it might be useful to do a 2-of-3 between Alice, Bob and an Orac= le signed value.=C2=A0 But I don't have any particular use case in mind= .=C2=A0 Either way the *ADD functionality can be replicated by various SWAP= s and ADDs etc, so we could just leave it out until it is wanted.
=
=C2=A0
And yes -- "Add OP_CHECKSI= GFROMSTACK and OP_CHECKSIGFROMSTACKVERIFY to follow the semantics from bip3= 40-342 when witness program is v1." is a bit light on detail for what = the BIP would end up looking like. If you're able to open up the design process a bit more on that it would be good = as I think there are some topics worth discussing at large before things pr= oceed with Elements (assuming feature compatibility remains a goal).=

I'm certainly open t= o a wider design process.=C2=A0 We can open a specific issue on the Element= s repo.=C2=A0 That said, I don't see a particularly wide design space o= n this front.
=C2=A0
The= non-prehashed=C2=A0argument seems OK (at the cost of an extra byte...) but= are there specific applications for !=3D32 arguments? I can't think of= a particular one beyond perhaps efficiency. Can we safely use 0-520 byte a= rguments?

One of th= e reasons given in the issue (yes, the thread there is very long) was that = hashing the message requires the hash to be collision resistant while if yo= u give the message directly it only requires the hash to be "random-pr= efix" collision / preimage resistant.=C2=A0 For example SHA-1 is clear= ly not collision resistant but it appears to still be random-prefix collisi= on resistant AFAIU.=C2=A0 Another reason is that it allows for extremely fa= st signing oracles because and R value and the midstate of the hash can be = precomputed all the way upto the application prefix, and if the message bei= ng signed is less than 55 bytes or so, the signing cost can be as low as on= e compression function and a little bit of non-EC modular arithmetic to com= pute S.=C2=A0 If the message were required to be prehashed, then it would t= ake a minimum of 2 compression function calls to sign, nearly doubling the = signing time needed for the fast oracle.

Even = if BIP-0340 kept its requirements that the message be exactly 32 bytes, I w= ould still be inclined to design CHECKSIGFROMSTACK for tapscript to take th= e 32-byte message from the stack instead of hashing a message itself (BIP-0= 340 does it's own hashing, so prehashing the message isn't a securi= ty concern in the same way it is for ECDSA.)=C2=A0 This would keep the mess= age off the blockchain, saving space and adding some amount of privacy and = making the operation compatible with rolling SHA256 opcodes.=C2=A0 But give= n that BIP-0340 is going to be extended to support non-32 byte messages, th= en there is no reason to impose a message length restriction on CHECKSIGFRO= MSTACK.=C2=A0 Yes the operation will still be subject to stack item length = restrictions.=C2=A0 This is something script writers will have to be aware = of, but I see little reason to support messages split across multiple stack= items when we expect, by far, most messages to be 32-bytes, and I expect t= hose rare non-32 byte messages are expected to be reasonably short.
=C2=A0
Also do you have thought= s on the other questions i posed above? E.g. splitting R/S could be helpful= w/o CAT.

Regarding= =C2=A0 internal pubkeys and invalid pubkeys, I see no reason to deviate fro= m whatever tapscript CHECKSIG* do.

Regarding split= ting R/S, This is harder because Elements does have CAT and I think we shou= ld add CAT to Bitcoin too.=C2=A0 This game of trying to prevent covenants b= y restricting script to the point where we are not even allowed to have a C= AT operation is a losing game.=C2=A0 It's just a matter of time before = we accidently introduce some way to enable covenants anyways, and it is not= worth cutting off vast amounts of functionality in pursuit of this questio= nable goal.=C2=A0 And I say this as someone who was originally of the opini= on that we should be very very cautious before enabling new expressivity su= ch as covenants.=C2=A0 All the scary scenarios of covenants that I am aware= of can be more easily, cheaply, and flexibility implemented by just having= a counterparty in a multi-party signature that enforces their own policy t= hat they only sign transactions that pay to outputs that they remain a part= y to.=C2=A0 And even if scary covenants were scarier than what can already = be done by multisig and policy, I still don't think they are scary enou= gh to warrant keeping CAT disabled.

So I don&#= 39;t think we should get fancy with CHECKSIGFROMSTACK.=C2=A0 Just take a no= rmal 64-byte signature value as a stack item.=C2=A0 But I don't feel st= rongly about this, and I wouldn't oppose splitting R and S in Bitcoin i= f that is where consensus lies.
=C2=A0
--0000000000008201d305c650d9ae--