Subject: Re: [bitcoin-dev] Signing CHECKSIG position in Tapscript

From: "Russell O'Connor" <[email-masked]>
Date: Sun, 1 Dec 2019 11:09:54 -0500

On Thu, Nov 28, 2019 at 3:07 AM Anthony Towns <[email-masked]> 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.