[bitcoin-dev] Signing CHECKSIG position in Tapscript

[bitcoin-dev] Signing CHECKSIG position in Tapscript

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 3780 bytes --]

Hi all,

I'd like to revisit an old topic from last year about the data signed in
tapscript signatures <
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-November/016508.html
>.

The current tapscript proposal requires a signature on the last executed
CODESEPRATOR position.  I'd like to propose an amendment whereby instead of
signing the last executed CODESEPRATOR position, we simply always sign the
position of the CHECKSIG (or other signing opcode) being executed. Then we
can deprecate CODESEPARTOR (either by making it OP_SUCCESS, or a nop, or
always fail when executed, or whatever).

The main motivation for this proposal is to increase robustness against
various signature-copying attacks in Scripts that have multiple spending
conditions.  Bitcoin is already robust against attacks where the attacker
attempts to peddle a victim's UTXO as their own and try to copy the
victim's signature from one transaction input to another input.  Because
Bitcoin signatures specify which input within a transaction is being signed
for, such attacks fail (see https://bitcoin.stackexchange.com/a/85665/49364
).

However, unless CODESEPARATOR is explicitly used, there is no protection
against these sorts of attacks when there are multiple participants that
have signing conditions within a single UTXO (or rather within a single
tapleaf in the tapscript case).  As it stands, Bitcoin's signed data only
covers which input is being signed, and not the specific conditions are
being signed for.  So for example, if Alice and Bob are engaged in some
kind of multi-party protocol, and Alice wants to pre-sign a transaction
redeeming a UTXO but subject to the condition that a certain hash-preimage
is revealed, she might verify the Script template shows that the code path
to her public key enforces that the hash pre-image is revealed (using a
toolkit like miniscript can aid in this), and she might make her signature
feeling secure that it, if her signature is used, the required preimage
must be revealed on the blockchain.  But perhaps Bob has masquated Alice's
pubkey as his own, and maybe he has inserted a copy of Alice's pubkey into
a different path of the Script template.  Now Alice's signature can be
copied and used in this alternate path, allowing the UTXO to be redeemed
under circumstances that Alice didn't believe she was authorizing.  In
general, to protect herself, Alice needs to inspect the Script to see if
her pubkey occurs in any other branch.  Given that her pubkey, in
principle, could be derived from a computation rather that pushed directly
into the stack, it is arguably infeasible for Alice to perform the required
check in general.

I believe that it would be safer, and less surprising to users, to always
sign the CHECKSIG position by default.  This will automatically enforce
conditions with the signature in most cases, rather than requiring users to
proactively try to reason if CODESEPARATOR is required for protection
within their protocol or not, and risk having them leave it out for cost
savings when it ends up being required for security after all.

I do not believe signing the CHECKSIG position is an undue burden on those
signers who have no conditions they require enforcement for.  As it stands,
the tapscript proposal already requires the tapleaf_hash value under the
signature; this CHECKSIG position value is simply more of the same kind of
data.  In simple Script templates (e.g. those with only one CHECKSIG
operation) the signed position will be a fixed known value.  Complex Script
templates are precisely the situations where you want to be careful about
enforcement of conditions with your signature.

As a side benefit, we get to eliminate CODESEPARATOR, removing a fairly
awkward opcode from this script version.

[-- Attachment #2: Type: text/html, Size: 4461 bytes --]

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

[Anthony Towns]

On Wed, Nov 27, 2019 at 04:29:32PM -0500, Russell O'Connor via bitcoin-dev wrote:
> The current tapscript proposal requires a signature on the last executed
> CODESEPRATOR position.  I'd like to propose an amendment whereby instead of
> signing the last executed CODESEPRATOR position, we simply always sign the
> position of the CHECKSIG (or other signing opcode) being executed.

FWIW, there's discussion of this at
http://www.erisian.com.au/taproot-bip-review/log-2019-11-28.html#l-65

> However, unless CODESEPARATOR is explicitly used, there is no protection
> against these sorts of attacks when there are multiple participants that have
> signing conditions within a single UTXO (or rather within a single tapleaf in
> the tapscript case).

(You already know this, but:)

With taproot key path spending, the only other conditions that can be
placed on a transaction are nSequence, nLockTime, and the annex, all of
which are committed to via the signature; so I think this concern only
applies to taproot script path spending.

The proposed sighashes for taproot script path spending all commit to
the script being used, so you can't reuse the signature in a different
leaf of the merkle tree of scripts for the UTXO, only in a separate
execution path within the script you're already looking at.

> So for example, if Alice and Bob are engaged in some kind of multi-party
> protocol, and Alice wants to pre-sign a transaction redeeming a UTXO but
> subject to the condition that a certain hash-preimage is revealed, she might
> verify the Script template shows that the code path to her public key enforces
> that the hash pre-image is revealed (using a toolkit like miniscript can aid in
> this), and she might make her signature feeling secure that it, if her
> signature is used, the required preimage must be revealed on the blockchain. 
> But perhaps Bob has masquated Alice's pubkey as his own, and maybe he has
> inserted a copy of Alice's pubkey into a different path of the Script
> template.
>
> Now Alice's signature can be copied and used in this alternate path,
> allowing the UTXO to be redeemed under circumstances that Alice didn't believe
> she was authorizing.  In general, to protect herself, Alice needs to inspect
> the Script to see if her pubkey occurs in any other branch.  Given that her
> pubkey, in principle, could be derived from a computation rather that pushed
> directly into the stack, it is arguably infeasible for Alice to perform the
> required check in general.

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.

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).

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.

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 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.

A hypothetical alternate "codeseparator" design: when script execution
starts, initialise an empty byte string "trace"; each time an opcode
is executed append "0xFF"; each time an opcode is skipped append
"0x00". When a CODESEPARATOR is seen, calculate sha256(trace) and store
it, everytime a CHECKSIG is executed, include the sha256(trace) from the
last CODESEPARATOR in the digest [0]. That should make each checksig
commit to the exact path the script took up to the last CODESEPARATOR
seen. I think it's probably more complex than is really useful though,
so I'm not proposing it seriously.

[0] If there's not been a CODESEPARATOR, then sha256(trace)=sha256("");
    if there's been one CODESEPARATOR and it was the first opcode seen,
    sha256(trace)=sha256("\xff").

Cheers,
aj

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

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 8338 bytes --]

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.

[-- Attachment #2: Type: text/html, Size: 10301 bytes --]

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

[Anthony Towns]

On Sun, Dec 01, 2019 at 11:09:54AM -0500, Russell O'Connor wrote:
> On Thu, Nov 28, 2019 at 3:07 AM Anthony Towns <aj@erisian.com.au> wrote:
>     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.

Hmm, I take the opposite lesson from your scenario -- it's only fine for
people to bring their own 2-of-3 or 5-of-6 or whatever and replace a
simple key if you've got something like miniscript where you understand
the script completely enough that you can be sure those changes are
fine. 

For contrast, with ECDSA and pre-miniscript, the above scenario might
have gone like someone proposing to change:

  7 A B C1 C2 C3 C4 C5 C6 C7 C8 C9 11 CHECKMULTISIG

for something like

  7
  SWAP IF TOALT 2 A1 A2 A3 3 CHECKMULTISIGVERIFY FROMALT 1SUB ENDIF
  SWAP IF TOALT 5 B1 B2 B3 B4 B5 B6 6 CHECKMULTISIGVERIFY FROMALT 1SUB ENDIF
  C1 C2 C3 C4 C5 C6 C7 C8 C9 11 CHECKMULTISIG

but I think you'd want to be pretty sure you can decode those added
policies rather than just accepting it because your "C4" key is still
there. (In particular, any script fragment that uses an opcode that used
to be OP_SUCCESS could have arbitrary effects on the script)

[0]

> 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.

(I'm trying to avoid using MAST in the context of taproot, despite the
backronym, so please excuse the rephrasing--)

I think if you're going to start using a taproot address with multiple
tapscripts, either as a participant in a multiparty smart contract,
or just to have different ways of spending your funds, then you do have
to analyse all the branches to make sure there's no hidden "all the
money goes to the Lizard People" script.

Once you've done that, you can then simplify things -- maybe some
scripts are only useful for other participants in the contract, or maybe
you've got a few different hardware wallets and one only needs to know
about one branch, while the other only needs to know about some other
branch, but you still need to have done the analysis in the first place.

Of course, probably most of the time that "analysis" is just making sure
the scripts match some well known, hardcoded template, as filled out
with various (tweaked) keys that you've checked elsewhere, but that
still ensures you know all the scripts do what you need them too.

>     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

Err? The current behaviour of CODESEP with taproot was first discussed in
[1], which summarised it as "CODESEP -- lets you require different sigs
for different parts of a single script" which seems to me like just a
different way of saying the same thing.

[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-November/016500.html

I don't think tapscript's CODESEP or the current CODESEP can be used
for anything other than preventing a signature from being reused for a
different CHECKSIG operation on the same pubkey within the same script.

> 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.

I think techniques like miniscript and having fixed templates specified
in BIPs and BOLTs and the like are better approaches -- both let you
easily allow a limited set of changes that can be safely made to a policy
(maybe just substituting keys, hashes and times, maybe allowing more
general changes).

> 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. :)

Sounds like an economics argument :)

>      IF HASH160 x EQUALVERIFY groupa ELSE groupb ENDIF
>      MERKLEPATHVERIFY CHECKSIG
>     spendable by
>      siga keya path preimagex 1
>     or
>      sigb keyb path 0
> I admit my proposal doesn't automatically prevent this signature-copying attack
> against every Script template.

Right -- so if you're worried about this sort of attack, you need to
analyse your script to at least be sure that it's not one of these cases
that aren't covered. And if you've got to analyse the script anyway
(which I think you do no matter what), then there's no benefit -- you're
either doing something simple and you're using templates or miniscript
to make the analysis easy; or you're doing something novel and complex,
and you can probably cope with using CODESEP.

(Ultimately I think there's only really two cases where you're
contributing a signature for a tx: either you're a party to the contract,
and you should have fully analysed all the possible ways the utxo could
be spent to make sure the smart contract stuff is correctly implemented
and you can't be cheated; or you're acting as an oracle or similar and
don't really care how the contract goes because you're not a party to
it, in which case people reusing your signature as much as they like is
fine. Hardware wallets don't need to analyse scripts they sign for, eg,
but that's only because for those cases where their owners have done
that first)

> 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.

I agree the burden's pretty minor; but I think having a single value
for the tx digest for each input for SIGHASH_ALL is kind-of nice for
validation; and I think having to pass through a CHECKSIG position
everytime you do a signature is likely to be annoying for implementors
for pretty much zero actual benefit.

> 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.

I'm making two points with that example: (1) it's a case where if
you don't analyse the scripts somehow, you can still be vulnerable to
the attack with your change -- so your change doesn't let you avoid
knowing what scripts do; but also (2) that CODESEP is a marginally more
efficient/general fix the problem. Maybe (1) isn't too important,
because even if it weren't true, I still think you need to know what all
the scripts do, but I think (2)'s still reelevant.

> 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.

As you aluded to in the previous mail; I think the problem's currently
extremely rare and trivially avoidable because we don't really have any
way of manipulating pubkeys -- there's no CAT, EC_ADD/EC_MUL/EC_TWEAK
or MERKLEPATHVERIFY opcode (or actual Merkle Abstract Syntax Trees or
OP_EXEC etc) to make it a dynamic concern rather than a static one.

> 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?

If CODESEP had never existed, I think my first response would be to say
"well, just make sure you don't reuse pubkeys, and because each
bip-schnorr sig commits to the pubkey, problem solved."

There's only two use cases I'm aware of, one is the ridiculous
reveal-a-secret-key-by-forced-nonce-reuse script that's never actually
been implemented [2] and ntumblebit's escrow script [3]. The first of
those requires pubkey recovery so doesn't work with bip-schnorr anyway;
and it's not clear to me whether the second is really reason enough to
justify a dedicated opcode/sighash/etc.

[2] https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000363.html
[3] https://github.com/NTumbleBit/NTumbleBit/blob/master/NTumbleBit/EscrowScriptBuilder.cs

An option would be to remove CODESEP and treat it as OP_SUCCESS -- that
way it could be introduced later with pretty much the exact semantics
that are currently proposed; or with some more useful semantics. That
way we could bring in whatever functionality was actually needed at the
same time as introducing CAT/EC_MUL/etc.

But my default position is to think that the way things currently work is
mostly fine, and we should default ot just keeping the same functionality
-- so SIGHASH_ALL doesn't do anything fancy, but CODESEP can be used to
prevent sig reuse.

>     > 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.

> 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. 
The tapscript implementation isn't intended to be equivalent to signing
a script suffix; all it does is add an index to the digest being signed
so that signatures at different indexes are distinct. That it's
equivalent to the current behaviour is definitely a feature, but I think
that's a surprising coincidence than a useful way of thinking about the
actual usefulness of CODESEP in tapscript...

[4]

> 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.

With ANYPREVOUTANYSCRIPT, you're still differentiating signatures by
index, you just no longer also commit to any of the other details of
the script. That means you can't prevent your signature being reused in
random other scripts someone else designs -- hence the "ANYSCRIPT" part --
but you can prevent any of your funds from going to those addresses, so
that's not really your problem anyway. What it does mean is that you can
prevent your signature from being reused in different scripts you do know
about; eg you might have a UTXO with four different tapscript branches:

     1) OP_1 CHECKSIG
     2) CODESEP OP_1 CHECKSIGVERIFY HASH160 x EQUAL
     3) n CLTV DROP CODESEP OP_1 CHECKSIGVERIFY
     4) k CSV DROP CODESEP OP_1 CHECKSIGVERIFY

(where OP_1 means using the taproot internal pubkey with support for
ANYPREVOUT*) -- that way a signature for either path (1) or (2) is only
valid for that path, but a signature for (3) can be reused for (4)
(or vice-versa), but not (1) or (2); and all those signatures could
be reused for other corresponding scripts, for instance with different
values for x,n,k if desired.

> There is no way that you should be signing CODESEPARATOR position without also
> covering the Script with the signature.

So I think it's more sensible than it seems; and still plausible enough
to leave in. If you don't want to separate your ANYPREVOUT scripts,
you can just not put a CODESEP in -- or at least only put CODESEP after
all your ANYPREVOUT CHECKSIGs; so it doesn't seem like it's creating
any added complexity.

Cheers,
aj

[0] For what it's worth, there's another reason not to allow replacing
    keys in a threshold sig with different policies: if you've got say
    30 people with a majority threshold of 16, then you could two groups
    of 9 people form parties and each agree to all vote along party lines;
    but if you let them replace their keys with multisig policies along
    those lines, you're now enforcing a 10-of-30 policy instead (as long
    as the 10 are 5 from the first party and 5 from the second party)
    and allowing minority control instead of majority rule.

[4] I wonder if it would be worth exploring whether we could do
    something more like the original (presumed) intent of CODESEP, given
    use of NOINPUT/ANYPREVOUT so as not to commit to the full script,
    you could potentially have a SIGHASH that committed to a hash of
    the script that's been executed so far, and also the witness data
    that's been consumed so far, but it would ensure the first part of
    the script behaved exactly as you expected, and allow the rest of
    the script to be arbitrarily weird, and (I think) be efficiently
    implementable. That doesn't give you delegation without the ability
    to also have executable witness data of some sort, but maybe something
    like it is interesting anyway?

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

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 7174 bytes --]

After chatting with andytoshi and others, and some more thinking I've been
convinced that my specific concern about other users masquerading other
people pubkeys as their own in complex scripts is actually a non-issue.

No matter what you write in Script (today), you are limited to expressing
some policy that is logically equivalent to a set of conditions and
signatures on pubkeys that can be expressed in disjunctive normal form.  We
can write such a policy as

(C[1] && PK[1,1] && ... && PK[1,m[1]]) || ... || (C[n] && PK[n,1] && ... &&
PK[n,m[n]])

where C[i] is some conjunction of conditions such as timelock constraints,
or hash-lock constraints or any other kind of proof of publication, and
where PK[i,j] is a requirement of a signature against a specific public key.

From Alice's point of view, she can divide set of clauses under the
disjunction into those that contain a pubkey that she considers (partially)
under her control and those clauses that she does not control (even though
as we shall see those other keys might actually be under Alice's control,
unbeknownst to her). To that end, let us consider a specific representative
policy.

    (C[1] && APK[1]) || (C[2] && APK[2] && BPK[2]) || (C[3] && BPK[3])

where Alice considers herself in control of APK[1] and APK[2], and where
she considers Bob in control of BPK[2] and BPK[3] and where C[1], C[2], and
C[3] are different conditions, let's say three different hash-locks.  We
will also say that Alice has ensured that her pubkeys in different clauses
are different (i.e. APK[1] != APK[2]), but she doesn't make any such
assumption for Bob's keys and neither will we.

When Alice funded this Script, or otherwise accepted it for consideration,
she agreed that she wouldn't control the redemption of the UTXO as long as
the preimage for C[3] is published.  In particular, Alice doesn't even need
to fully decode the Script semantics for that clause beyond determining
that it enforces the C[3] requirement that she cares about. Even if Bob was
masquerading Alice's pubkey as his own (as in BPK[3] = APK[1] or BPK[3] =
APK[2]), and he ends up copying her signature into that clause, Alice ends
up with C[3] published as she originally accepted as a possibility.  Bob
masquerading Alice's pubkey as his own only serves to hamper his own
ability to sign for his clauses (I mean, Bob might be trying to convince
some third party that Alice signed for something she didn't actually sign
for, but such misrepresentations of the meaning of digital signatures is
outside our scope and this just serves as a reminder not to be deceived by
Bob's tricks here).

And the same argument holds for BPK[2].  Even if BPK[2] = APK[1] and Bob
tries to copy Alice's signature into the C[2] condition, he still needs a
countersignature with her APK[2], so Alice remains in control of that
clause.  And if BPK[2] = APK[2] then Bob can only copy Alice's signature on
the C[2] condition, but in that case she has already authorised that
condition.  Again, Bob masquerading Alice's pubkey as his own only serves
to hamper his own ability to sign for his clauses.

So what makes our potential issue here safe, versus the dangers that would
happen in <https://bitcoin.stackexchange.com/a/85665/49364> where Bob
masqurades Alice's UTXO as his own?  The key problem in the UTXO case isn't
so much Bob masquerading Alice's pubkey as his own, as it is an issue with
Alice reusing her pubkeys and Bob taking advantage of that.  We do, in
fact, have exactly the same issue in Script.  If Alice were to reuse
pubkeys such that APK[1] = APK[2], then Bob could take her signature for
C[1] and transplant it to redeem under condition C[2].  We see that it is
imperative that Alice ensures that she doesn't reuse pubkeys that she
considers under her control for different conditions when she wants her
signature to distinguish between them.

For various reasons, some historical, it is much harder to avoid pubkey
reuse for different UTXOs than it is to avoid pubkey reuse within a single
script.  We often use Bitcoin addresses in non-interactive ways, such as
putting them on flyers or painting them on walls and such.  Without a
standard for tweaking such pubkeys in a per-transaction way, we end up with
a lot of pubkey reuse between various UTXOs.  However, within a Script,
avoiding pubkey reuse ought to be easier.  Alice must communicate different
pubkeys intended for different clauses, or if Bob is constructing a whole
complex script on Alice's behalf, he may need to add CODESEPARATORs if
tweaking Alice's pubkey isn't an option.

The conversion of a policy to disjunctive normal form can involve an
exponential blowup (see <
https://en.wikipedia.org/wiki/Disjunctive_normal_form#Conversion_to_DNF>).
For instance, if Alice's policy (not in disjunctive normal form) is of the
form

    (C[1] || D[1]) && ... && (C[n] || D[n]) && APK

where C[i] and D[i] are all distinct hashlocks, we require O(2^n) clauses
to put it in disjunctive normal form.  If Alice wants to create signatures
that are restricted to a specific combination of C[i]'s and D[i]'s, she
needs to use an exponential number of pubkeys, which isn't tractable to do
in Script.  But neither my original proposal nor CODESEPARATOR helps in
this case either because CODESEPARATOR can mark only the last executed
position.  Taproot's MAST (Merklized Alternative Script Tree per aj's
suggestion), can maybe provide a tractable solution to this in cases where
it is applicable.  The MAST is always a disjunction and because the tapleaf
is signed, it is safe to reuse pubkeys between alternative branches.

This analysis suggests that we should amend CODESEPARATORs behaviour to
update an accumulator (presumably a running hash value), so that all
executed CODESEPARATOR positions end up covered by the signature.  That
would provide a solution to the above problem for those cases where
taproot's MAST cannot be used.  I'm not sure if it is better to propose
such an amendment to CODESEPARATOR's behaviour now, or to propose to
soft-fork in such optional behaviour at a later time.

However, what I said above was even too simplified.  In general, a policy
of the form.

    (Exists w[1]. C[1](w[1]) && PK[1,1](w[1]) && ... && PK[1,m[1]](w[1]) ||
... || (Exists w[n]. C[n](w[n]) && PK[n,1](w[n]) && ... && PK[n,m[n]](w[n]))

where each term could possibly be parameterized by some witness value
(though at the moment there isn't enough functionality in Script to
parameterize the pubkeys in any reasonably way and it maybe isn't even
possible to parameterise the conditions in any reasonable way).  In
general, you might want your signature to cover (some function of) this
witness value.  This suggests that we would actually want a CODESEPARATOR
variant that pushes a stack item into the accumulator that gets covered by
the signature rather than pushing the CODESEPARATOR position.  Though at
this point the name CODESEPARATOR is probably not suitable, even if it
subsumes the functionality.  Again, I'm not sure if it is better to propose
such a replacement for CODESEPARATOR's behaviour now, or to propose to
soft-fork in such optional behaviour at a later time.

[-- Attachment #2: Type: text/html, Size: 8126 bytes --]

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

[Anthony Towns]

On Thu, Dec 05, 2019 at 03:24:46PM -0500, Russell O'Connor wrote:

Thanks for the careful write up! That matches what I was thinking.

> This analysis suggests that we should amend CODESEPARATORs behaviour to update
> an accumulator (presumably a running hash value), so that all executed
> CODESEPARATOR positions end up covered by the signature.

On IRC, gmaxwell suggests "OP_BREADCRUMB" as a name for (something like)
this functionality.

(I think it's a barely plausible stretch to use the name "CODESEPARATOR"
for marking a position in the script -- that separates what was before
and after, at least; anything more general seems like it warrants a
better name though)

> That would provide a
> solution to the above problem for those cases where taproot's MAST cannot be
> used.  I'm not sure if it is better to propose such an amendment to
> CODESEPARATOR's behaviour now, or to propose to soft-fork in such optional
> behaviour at a later time.
> However, what I said above was even too simplified.  

FWIW, I think it's too soon to propose this because (a) it's not clear
there's a practical need for it, (b) it's not clear the functionality is
quite right (opcode vs more automatic sighash flag?), and (c) as you say,
it's not clear it's powerful enough.

> In general, a policy of the form.
>     (Exists w[1]. C[1](w[1]) && PK[1,1](w[1]) && ... && PK[1,m[1]](w[1]) || ...
> || (Exists w[n]. C[n](w[n]) && PK[n,1](w[n]) && ... && PK[n,m[n]](w[n]))
> where each term could possibly be parameterized by some witness value (though
> at the moment there isn't enough functionality in Script to parameterize the
> pubkeys in any reasonably way and it maybe isn't even possible to parameterise
> the conditions in any reasonable way).  In general, you might want your
> signature to cover (some function of) this witness value.  This suggests that
> we would actually want a CODESEPARATOR variant that pushes a stack item into
> the accumulator that gets covered by the signature rather than pushing the
> CODESEPARATOR position.  Though at this point the name CODESEPARATOR is
> probably not suitable, even if it subsumes the functionality.

> Again, I'm not
> sure if it is better to propose such a replacement for CODESEPARATOR's
> behaviour now, or to propose to soft-fork in such optional behaviour at a later
> time.

Last bit first, it seems pretty clear to me that this is too novel an
idea to propose it immediately -- we should explore the problem space
more first to see what's the best way of doing it before coding it into
consensus. And (guessing) I think the tapscript upgrade methods should
be fine for handling this later.

I think the annex is also not general enough for what you're thinking
here, in that it wouldn't allow for one signature to constrain the witness
data more than some other signature -- so you'd need to determine all
the constraints for all signatures to finish filling out the annex,
and could only then start signing.

I think you could conceivably do any/all of:

 * commit to a hash of all the witness data that hasn't been popped off
   the stack ("suffix" commitment -- the data will be used by later script
   opcodes)
 * commit to a hash of all the witness data that has been popped off the
   stack ("prefix" commitment -- this is the data that's been used by
   earlier script opcodes)
 * commit to the hash of the current stack

That would be expensive, but still doable as O(1) per opcode / stack
element. I think any other masking would mean you'd have potentially
O(size of witness data) or O(size of stack) runtime per signature which
I think would be unacceptable...

I guess a general implementation to at least think about the possibilities
might be an "OP_DATACOMMIT" opcode that pops an element from the stack,
does hash_"DataCommit"(element), and then any later signatures commit
to that value (maybe with OP_0 OP_DATACOMMIT allowing you to get back to
the default state). You'd either need to write your script carefully to
commit to witness data you're using elsewhere, or have some other new
opcodes to do that more conveniently...

CODESEP at position "x" in the script is equivalent to "<x> DATACOMMIT"
here, I think. "BREADCRUMB .. BREADCRUMB" could be something like:

   OP_0 TOALT [at start of script]
   ..
   FROMALT x CAT SHA256 DUP TOALT DATACOMMIT   
   ..
   FROMALT y CAT SHA256 DUP TOALT DATACOMMIT   

if the altstack was otherwise unused, I guess; so the accumulator
behaviour probably warrants something better.

It also more or less gives you CHECKSIGFROMSTACK behaviour by doing
"SWAP OP_DATACOMMIT OP_CHECKSIG" and a SIGHASH_NONE|ANYPREVOUTANYSCRIPT
signature.

But that seems like a plausible generalisation to think about?

Cheers,
aj