Return-Path: Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id D4515C087F for ; Sun, 1 Dec 2019 16:18:21 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id C1B9E850DC for ; Sun, 1 Dec 2019 16:18:21 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id V7HvHkIjFrNX for ; Sun, 1 Dec 2019 16:18:20 +0000 (UTC) X-Greylist: delayed 00:08:14 by SQLgrey-1.7.6 Received: from mail-io1-f51.google.com (mail-io1-f51.google.com [209.85.166.51]) by fraxinus.osuosl.org (Postfix) with ESMTPS id 17E1285092 for ; Sun, 1 Dec 2019 16:18:20 +0000 (UTC) Received: by mail-io1-f51.google.com with SMTP id k24so26855873ioc.4 for ; Sun, 01 Dec 2019 08:18:20 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream.io; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=zbf5+WNF57UIRjE6NpepU2FLxE09ApCgWiINImn35nc=; b=WY4H+Ix9w0+1yctXjA2GL3eIvfxv2rFjbAmHqhc3pY8IiViKeqk+1W5cHzC6OTOZpz iw4v6sEWy+AJ9B1+2sQKNKR4vLBvhtzYh0k/xXlwgjLZlHLOm7/xqTKMG5RSVHX8arnA CFxcurF5gZR/jC1Z6OB9qi23cKA7U4crqrsfI= 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=zbf5+WNF57UIRjE6NpepU2FLxE09ApCgWiINImn35nc=; b=kfqpd0HpzbZ1HJvHPD8LGUXkoPgJ+1/AX6eEuSrCylJ035ttv++hhHcu35Jewa3mxq Jjcnsc8Rrr6auOKrMZP2TxVOysKKgY2uNFWWccqIblB7JDCOjOfbnf+yus9EYNqrd0Tb VgjvqRa6KTVLthkDzuKnWNXbOFjtcYJkKDwi371Abug22PQLZlaxAIx2eNgOq2wEVX3X a1PCMCyS34YGjDwba/U7BL7tpdB2d6IibBZIGo/5DH5xYJrnVAsVv8bwfphNuPyU7WbD Ky1FybzRRXQwF3o3Z7srceU+60lkkod/HQRVina2H/sDIMYGFO3qxSyTJNNjBt6YLUbe cnlQ== X-Gm-Message-State: APjAAAUVYmna43h0rWjNAf6spA0OfhGHS5TuuAvWKQo+xxZ/MdLlQYzt kdo0G8yFDLNV/xZH3Kp0rAudjbZlwkuNPBEBBK9Mvw== X-Google-Smtp-Source: APXvYqymjbEr7YXlzQ9pRWZrej2YG3GIJNwRMAaoZK4BBqjVnMO+wU0g+G+OT0Sbxc86n8/ekFz+Wv9OtU/n+sQe0ak= X-Received: by 2002:a6b:710f:: with SMTP id q15mr25664465iog.103.1575216605640; Sun, 01 Dec 2019 08:10:05 -0800 (PST) MIME-Version: 1.0 References: <20191128080659.msrpdpcjhhvbqtv2@erisian.com.au> In-Reply-To: <20191128080659.msrpdpcjhhvbqtv2@erisian.com.au> From: "Russell O'Connor" Date: Sun, 1 Dec 2019 11:09:54 -0500 Message-ID: To: Anthony Towns Content-Type: multipart/alternative; boundary="0000000000003953730598a6b26c" Cc: Bitcoin Protocol Discussion , Pieter Wuille Subject: Re: [bitcoin-dev] Signing CHECKSIG position in Tapscript 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, 01 Dec 2019 16:18:21 -0000 --0000000000003953730598a6b26c Content-Type: text/plain; charset="UTF-8" On Thu, Nov 28, 2019 at 3:07 AM Anthony Towns wrote: > FWIW, there's discussion of this at > http://www.erisian.com.au/taproot-bip-review/log-2019-11-28.html#l-65 > I think variants like signing the position of the enclosing OP_IF/OP_NOTIF/OP_ELSE of the OP_IF/OP_NOTIF/OP_ELSE block that the checksig is within, or signing the byte offset instead of the opcode number offset are all fine. In particular, signing the enclosing OP_IF... would allow sharing of the hashed signed data in a normal multisig sequence of operations. Below I'll continue to refer to my proposal as signing the CHECKSIG position, but please take it to mean any of these proposed, semantically equivalent, realizations of this idea. I also think that it is quite reasonable to have a sighash flag control whether or not the signature covers the CHECKSIG position or not, with SIGHASH_ALL including the CHECKSIG position. > First, it seems like a bad idea for Alice to have put funds behind a > script she doesn't understand in the first place. There's plenty of > scripts that are analysable, so just not using ones that are too hard to > analyse sure seems like an option. > I don't think this is true in general. When constructing a script it seems quite reasonable for one party to come to the table with their own custom script that they want to use because they have some sort of 7-of-11 scheme but in one of those cases is really a 2-of-3 and another is 5-of-6. The point is that you shouldn't need to decode their exact policy in order to collaborate with them. This notion is captured quite clearly in the MAST aspect of taproot. In many circumstances, it is sufficient for you to know that there exists a branch that contains a particular script without need to know what every branch contains. Because we include the tapleaf in the signature, we already prevent this signature copying attack against attempts to transplant one's signature from one tapleaf to another. My proposal is to simply extend this same protection to branches within a single tapscript. Second, if there are many branches in the script, it's probably more > efficient to do them via different branches in the merkle tree, which > at least for this purpose would make them easier to analyse as well > (since you can analyse them independently). > Of course this should be done when practical. This point isn't under dispute. > Third, if you are doing something crazy complex where a particular key > could appear in different CHECKSIG operators and they should have > independent signatures, that seems like you're at the level of > complexity where learning about CODESEPARATOR is a reasonable thing to > do. > So while I agree that learning about CODESEPARATOR is a reasonable thing to do, given that I haven't heard the CODESEPARATOR being proposed as protection against this sort of signature-copying attack before and given the subtle nature of the issue, I'm not sure people will know to use it to protect themselves. We should aim for a Script design that makes the cheaper default Script programming choices the safer one. On the other hand, in a previous thread a while ago I was also arguing that sophisticated people are plausibly using CODESEPARATOR today, hidden away in unredeemed P2SH UTXOs. So perhaps I'm right about at least one of these two points. :) I think CODESEPARATOR is a better solution to this problem anyway. In > particular, consider a "leaf path root OP_MERKLEPATHVERIFY" opcode, > and a script that says "anyone in group A can spend if the preimage for > X is revelaed, anyone in group B can spend unconditionally": > > IF HASH160 x EQUALVERIFY groupa ELSE groupb ENDIF > MERKLEPATHVERIFY CHECKSIG > > spendable by > > siga keya path preimagex 1 > > or > > sigb keyb path 0 > > With your proposed semantics, if my pubkey is in both groups, my signature > will sign for position 10, and still be valid on either path, even if > the signature commits to the CHECKSIG position. > > I could fix my script either by having two CHECKSIG opcodes (one for > each branch) and also duplicating the MERKLEPATHVERIFY; or I could > add a CODESEPARATOR in either IF branch. > > (Or I could just not reuse the exact same pubkey across groups; or I could > have two separate scripts: "HASH160 x EQUALVERIFY groupa MERKLEPATHVERIFY > CHECKSIG" and "groupb MERKLEPATHVERIFY CHECKSIG") > I admit my proposal doesn't automatically prevent this signature-copying attack against every Script template. To be fully effective you need to be aware of this signature-copying attack vector to ensure your scripts are designed so that your CHECKSIG operations are protected by being within the IF block that does the verification of the hash-preimage. My thinking is that my proposal is effective enough to save most people most of the time, even if it doesn't save everyone all the time, all while having no significant burden otherwise. Therefore, I don't think your point that there still exists a Script where a signature copying attack can be performed is adequate by itself to dismiss my proposal. However if you believe that if we don't save everyone all the time then there is no point in trying, or if you believe that signing the CHECKSIG position probably will not protect most users most of the time, or if you believe the burden on all the other cases is too great, then maybe it is better to rely on people using CODESEPARATOR. Given that MAST design of taproot greatly reduces this problem compared to legacy script, I suppose you could argue that "the burden on all the other cases is too great" simply because you believe the problematic situation is now extremely rare. I still think we ought to choose designs that are safer by default and include as much user intention within the signed data as we can reasonably get away, and use other sighash flags for those cases when we need to exclude data from the signature. In particular, imagine a world where CODESEPARATOR never existed. We have this signature copying attack to deal with, and we are designing a new Segwit version in which we can now address the problem. One proposal that someone comes up with is to sign the CHECKSIG position (or sign the enclosing OP_IF/OP_ELSE... position), maybe using a SIGHASH flag to optionally disable it. Someone else comes up with a proposal to add new "CODESEPARATOR" opcode which requires adding a new piece of state to the Script interpreter (the only non-stack based piece of state) to track the last executed CODESEPARATOR position and include that in the signature. Would you really prefer the CODESEPARATOR proposal? > > I believe that it would be safer, and less surprising to users, to > always sign > > the CHECKSIG position by default. > > > As a side benefit, we get to eliminate CODESEPARATOR, removing a fairly > awkward > > opcode from this script version. > > As it stands, ANYPREVOUTANYSCRIPT proposes to not sign the script code > (allowing the signature to be reused in different scripts) but does > continue signing the CODESEPARATOR position, allowing you to optionally > restrict how flexibly you can reuse signatures. That seems like a better > tradeoff than having ANYPREVOUTANYSCRIPT signatures commit to the CHECKSIG > position which would make it a fair bit harder to design scripts that > can share signatures, or not having any way to restrict which scripts > the signature could apply to other than changing the pubkey. > Um, I believe that signing the CODESEPERATOR position without signing the script code is nonsensical. You are talking about signing a piece of data without an interpretation of its meaning. Recall that originally CODESEPARTOR would let you sign a suffix of the Script program. In the context of signing the whole script (which is always signed indirectly as part of the txid in legacy signatures) signing the offset into that scripts contains just as much information as signing a script suffix, while being constant sized. When you remove the Script from the data being signed, signing an offset is no longer equivalent to signing a Script suffix, and an offset into an unknown data structure is a meaningless value by itself. There is no way that you should be signing CODESEPARATOR position without also covering the Script with the signature. --0000000000003953730598a6b26c Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


=
On Thu, Nov 28, 2019 at 3:07 AM Antho= ny Towns <aj@eris= ian.com.au> wrote:
FWIW, there's discussion of this at
http://www.erisian.com.au/tapro= ot-bip-review/log-2019-11-28.html#l-65

<= div>I think variants like signing the position of the enclosing OP_IF/OP_NO= TIF/OP_ELSE of the OP_IF/OP_NOTIF/OP_ELSE block that the checksig is within= , or signing the byte offset instead of the opcode number offset are all fi= ne.=C2=A0 In particular, signing the enclosing OP_IF... would allow sharing= of the hashed signed data in a normal multisig sequence of operations.=C2= =A0 Below I'll continue to refer to my proposal as signing the CHECKSIG= position, but please take it to mean any of these proposed, semantically e= quivalent, realizations of this idea.

I also think= that it is quite reasonable to have a sighash flag control whether or not = the signature covers the CHECKSIG position or not, with SIGHASH_ALL includi= ng the CHECKSIG position.
=C2=A0
First, it seems like a bad idea for Alice to have put funds behind a
script she doesn't understand in the first place. There's plenty of=
scripts that are analysable, so just not using ones that are too hard to analyse sure seems like an option.

I do= n't think this is true in general.=C2=A0 When constructing a script it = seems quite reasonable for one party to come to the table with their own cu= stom script that they want to use because they have some sort of 7-of-11 sc= heme but in one of those cases is really a 2-of-3 and another is 5-of-6.=C2= =A0 The point is that you shouldn't need to decode their exact policy i= n order to collaborate with them.=C2=A0 This notion is captured quite clear= ly in the MAST aspect of taproot.=C2=A0 In many circumstances, it is suffic= ient for you to know that there exists a branch that contains a particular = script without need to know what every branch contains.=C2=A0 Because we in= clude the tapleaf in the signature, we already prevent this signature copyi= ng attack against attempts to transplant one's signature from one taple= af to another.=C2=A0 My proposal is to simply extend this same protection t= o branches within a single tapscript.

Second, if there are many branches in the script, it's probably more efficient to do them via different branches in the merkle tree, which
at least for this purpose would make them easier to analyse as well
(since you can analyse them independently).

=
Of course this should be done when practical.=C2=A0 This point isn'= ;t under dispute.
=C2=A0
Third, if you are doing something crazy complex where a particular key
could appear in different CHECKSIG operators and they should have
independent signatures, that seems like you're at the level of
complexity where learning about CODESEPARATOR is a reasonable thing to
do.

So while I agree that learning abou= t CODESEPARATOR is a reasonable thing to do, given that I haven't heard= the CODESEPARATOR being proposed as protection against this sort of signat= ure-copying attack before and given the subtle nature of the issue, I'm= not sure people will know to use it to protect themselves.=C2=A0 We should= aim for a Script design that makes the cheaper default Script programming = choices the safer one.

On the other hand, in a pr= evious thread a while ago I was also arguing that sophisticated people are = plausibly using CODESEPARATOR today, hidden away in unredeemed P2SH UTXOs.= =C2=A0 So perhaps I'm right about at least one of these two points. :)<= br>

I think CODESEPARATOR is a better solution to this problem anyway. In
particular, consider a "leaf path root OP_MERKLEPATHVERIFY" opcod= e,
and a script that says "anyone in group A can spend if the preimage fo= r
X is revelaed, anyone in group B can spend unconditionally":

=C2=A0IF HASH160 x EQUALVERIFY groupa ELSE groupb ENDIF
=C2=A0MERKLEPATHVERIFY CHECKSIG

spendable by

=C2=A0siga keya path preimagex 1

or

=C2=A0sigb keyb path 0

With your proposed semantics, if my pubkey is in both groups, my signature<= br> will sign for position 10, and still be valid on either path, even if
the signature commits to the CHECKSIG position.

I could fix my script either by having two CHECKSIG opcodes (one for
each branch) and also duplicating the MERKLEPATHVERIFY; or I could
add a CODESEPARATOR in either IF branch.

(Or I could just not reuse the exact same pubkey across groups; or I could<= br> have two separate scripts: "HASH160 x EQUALVERIFY groupa MERKLEPATHVER= IFY
CHECKSIG" and "groupb MERKLEPATHVERIFY CHECKSIG")

I admit my proposal doesn't = automatically prevent this signature-copying attack against every Script te= mplate.=C2=A0 To be fully effective you need to be aware of this signature-= copying attack vector to ensure your scripts are designed so that your CHEC= KSIG operations are protected by being within the IF block that does the ve= rification of the hash-preimage.=C2=A0 My thinking is that my proposal is e= ffective enough to save most people most of the time, even if it doesn'= t save everyone all the time, all while having no significant burden otherw= ise.=C2=A0 Therefore, I don't think your point that there still exists = a Script where a signature copying attack can be performed is adequate by i= tself to dismiss my proposal.=C2=A0 However if you believe that if we don&#= 39;t save everyone all the time then there is no point in trying, or if you= believe that signing the CHECKSIG position probably will not protect most = users most of the time, or if you believe the burden on all the other cases= is too great, then maybe it is better to rely on people using CODESEPARATO= R.

Given that MAST design of taproot greatly reduces thi= s problem compared to legacy script, I suppose you could argue that "t= he burden on all the other cases is too great" simply because you beli= eve the problematic situation is now extremely rare.

I still think we ought to choose designs that are safer by default and i= nclude as much user intention within the signed data as we can reasonably g= et away, and use other sighash flags for those cases when we need to exclud= e data from the signature.

In particular, imag= ine a world where CODESEPARATOR never existed.=C2=A0 We have this signature= copying attack to deal with, and we are designing a new Segwit version in = which we can now address the problem.=C2=A0 One proposal that someone comes= up with is to sign the CHECKSIG position (or sign the enclosing OP_IF/OP_E= LSE... position), maybe using a SIGHASH flag to optionally disable it.=C2= =A0 Someone else comes up with a proposal to add new "CODESEPARATOR&qu= ot; opcode which requires adding a new piece of state to the Script interpr= eter (the only non-stack based piece of state) to track the last executed C= ODESEPARATOR position and include that in the signature.=C2=A0 Would you re= ally prefer the CODESEPARATOR proposal?
=C2=A0
> I believe that it would be safer, and less surprising to users, to alw= ays sign
> the CHECKSIG position by default.

> As a side benefit, we get to eliminate CODESEPARATOR, removing a fairl= y awkward
> opcode from this script version.

As it stands, ANYPREVOUTANYSCRIPT proposes to not sign the script code
(allowing the signature to be reused in different scripts) but does
continue signing the CODESEPARATOR position, allowing you to optionally
restrict how flexibly you can reuse signatures. That seems like a better tradeoff than having ANYPREVOUTANYSCRIPT signatures commit to the CHECKSIG<= br> position which would make it a fair bit harder to design scripts that
can share signatures, or not having any way to restrict which scripts
the signature could apply to other than changing the pubkey.

Um, I believe that signing the CODESEPERATOR positio= n without signing the script code is nonsensical.=C2=A0 You are talking abo= ut signing a piece of data without an interpretation of its meaning.
<= div>
Recall that originally CODESEPARTOR would let you sign a= suffix of the Script program.=C2=A0 In the context of signing the whole sc= ript (which is always signed indirectly as part of the txid in legacy signa= tures) signing the offset into that scripts contains just as much informati= on as signing a script suffix, while being constant sized.=C2=A0 When you r= emove the Script from the data being signed, signing an offset is no longer= equivalent to signing a Script suffix, and an offset into an unknown data = structure is a meaningless value by itself.=C2=A0 There is no way that you = should be signing CODESEPARATOR position without also covering the Script w= ith the signature.
--0000000000003953730598a6b26c--