path: root/4f/4b6567ca6a7d06b362d40eae1b626ad915921f

Return-Path: <roconnor@blockstream.io>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id D4515C087F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 Sun,  1 Dec 2019 16:18:20 +0000 (UTC)
Received: by mail-io1-f51.google.com with SMTP id k24so26855873ioc.4
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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: <CAMZUoKm7Y8bRJ+hqmvyPwwTWHaMA7JJc5TZdx7Eufax9G0D=Gg@mail.gmail.com>
 <20191128080659.msrpdpcjhhvbqtv2@erisian.com.au>
In-Reply-To: <20191128080659.msrpdpcjhhvbqtv2@erisian.com.au>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Sun, 1 Dec 2019 11:09:54 -0500
Message-ID: <CAMZUoKmYi6btmhN8NmePPZNpPtXwNp=EpyYrxo7P2Ug7fnPSwQ@mail.gmail.com>
To: Anthony Towns <aj@erisian.com.au>
Content-Type: multipart/alternative; boundary="0000000000003953730598a6b26c"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 Pieter Wuille <pieter.wuille@gmail.com>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <aj@erisian.com.au> 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

<div dir=3D"ltr"><div dir=3D"ltr"><br></div><br><div class=3D"gmail_quote">=
<div dir=3D"ltr" class=3D"gmail_attr">On Thu, Nov 28, 2019 at 3:07 AM Antho=
ny Towns &lt;<a href=3D"mailto:aj@erisian.com.au" target=3D"_blank">aj@eris=
ian.com.au</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex">
FWIW, there&#39;s discussion of this at<br>
<a href=3D"http://www.erisian.com.au/taproot-bip-review/log-2019-11-28.html=
#l-65" rel=3D"noreferrer" target=3D"_blank">http://www.erisian.com.au/tapro=
ot-bip-review/log-2019-11-28.html#l-65</a><br></blockquote><div><br></div><=
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&#39;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.</div><div><br></div><div>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.<br></div><div>=C2=A0<br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex">
First, it seems like a bad idea for Alice to have put funds behind a<br>
script she doesn&#39;t understand in the first place. There&#39;s plenty of=
<br>
scripts that are analysable, so just not using ones that are too hard to<br=
>
analyse sure seems like an option.<br></blockquote><div><br></div><div>I do=
n&#39;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&#39;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&#39;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.</div><div><br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex">
Second, if there are many branches in the script, it&#39;s probably more<br=
>
efficient to do them via different branches in the merkle tree, which<br>
at least for this purpose would make them easier to analyse as well<br>
(since you can analyse them independently).<br></blockquote><div><br></div>=
<div>Of course this should be done when practical.=C2=A0 This point isn&#39=
;t under dispute.<br></div><div>=C2=A0</div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204)=
;padding-left:1ex">
Third, if you are doing something crazy complex where a particular key<br>
could appear in different CHECKSIG operators and they should have<br>
independent signatures, that seems like you&#39;re at the level of<br>
complexity where learning about CODESEPARATOR is a reasonable thing to<br>
do.<br></blockquote><div><br></div><div>So while I agree that learning abou=
t CODESEPARATOR is a reasonable thing to do, given that I haven&#39;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&#39;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.</div><div><br></div><div> 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&#39;m right about at least one of these two points. :)<=
br></div><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0=
px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
I think CODESEPARATOR is a better solution to this problem anyway. In<br>
particular, consider a &quot;leaf path root OP_MERKLEPATHVERIFY&quot; opcod=
e,<br>
and a script that says &quot;anyone in group A can spend if the preimage fo=
r<br>
X is revelaed, anyone in group B can spend unconditionally&quot;:<br>
<br>
=C2=A0IF HASH160 x EQUALVERIFY groupa ELSE groupb ENDIF<br>
=C2=A0MERKLEPATHVERIFY CHECKSIG<br>
<br>
spendable by<br>
<br>
=C2=A0siga keya path preimagex 1<br>
<br>
or<br>
<br>
=C2=A0sigb keyb path 0<br>
<br>
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<br>
the signature commits to the CHECKSIG position.<br>
<br>
I could fix my script either by having two CHECKSIG opcodes (one for<br>
each branch) and also duplicating the MERKLEPATHVERIFY; or I could<br>
add a CODESEPARATOR in either IF branch. <br></blockquote><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex">
<br>
(Or I could just not reuse the exact same pubkey across groups; or I could<=
br>
have two separate scripts: &quot;HASH160 x EQUALVERIFY groupa MERKLEPATHVER=
IFY<br>
CHECKSIG&quot; and &quot;groupb MERKLEPATHVERIFY CHECKSIG&quot;)<br></block=
quote><br></div><div class=3D"gmail_quote">I admit my proposal doesn&#39;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&#39;=
t save everyone all the time, all while having no significant burden otherw=
ise.=C2=A0 Therefore, I don&#39;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.<div><br></div><div>Given that MAST design of taproot greatly reduces thi=
s problem compared to legacy script, I suppose you could argue that &quot;t=
he burden on all the other cases is too great&quot; simply because you beli=
eve the problematic situation is now extremely rare.</div><div><br></div><d=
iv>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.<br></div><div><br></div><div>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 &quot;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?<br></div><div>=C2=A0</div><blockquo=
te class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px =
solid rgb(204,204,204);padding-left:1ex">
&gt; I believe that it would be safer, and less surprising to users, to alw=
ays sign<br>
&gt; the CHECKSIG position by default.<br>
<br>
&gt; As a side benefit, we get to eliminate CODESEPARATOR, removing a fairl=
y awkward<br>
&gt; opcode from this script version.<br>
<br>
As it stands, ANYPREVOUTANYSCRIPT proposes to not sign the script code<br>
(allowing the signature to be reused in different scripts) but does<br>
continue signing the CODESEPARATOR position, allowing you to optionally<br>
restrict how flexibly you can reuse signatures. That seems like a better<br=
>
tradeoff than having ANYPREVOUTANYSCRIPT signatures commit to the CHECKSIG<=
br>
position which would make it a fair bit harder to design scripts that<br>
can share signatures, or not having any way to restrict which scripts<br>
the signature could apply to other than changing the pubkey. <br></blockquo=
te><div><br></div><div>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><=
div><br></div><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.<br></div></div></div>

--0000000000003953730598a6b26c--