Subject: Re: [bitcoin-dev] Unenforceable fee obligations in multiparty protocols with Taproot inputs

From: Andrew Poelstra <[email-masked]>
Date: Tue, 7 Feb 2023 13:46:22 +0000

On Tue, Feb 07, 2023 at 04:49:28AM +0200, Yuval Kogman via bitcoin-dev wrote:
> 
> Since Taproot (more generally any kind of MAST) spends have variable size which
> depends on the path being used, the last such input to be signed in a multiparty
> transaction can always use a larger than estimated signature to unfairly extract
> a fee contribution from the other parties to the transaction (keeping the
> absolute fees the same and reducing the feerate for the transaction).
>

Using Miniscript [1] it is possible for all participants to determine
the maximum witness size of the tree, which can bound the size of this
attack. In fact, they can bound the size *given that their own signature
is used*, or subject to other whatever other conditions they would like,
and only sign under those conditions.

Furthermore, under Taproot individual signatures have a maximum size of
65 bytes; an "attacker" can reduce this to 64 by not including a sighash
flag, but he has one byte of play. (Pre-Taproot signatures could take up
to 73 bytes with significant room to reduce this by using crypto tricks
and/or grinding).

Peter Todd also suggests in this thread that the use of uncompressed
keys can cause "surprise" witness inflation, but (a) since segwit
uncompressed keys are also banned, so keys are a fixed 33 bytes (32 in
Taproot), and (b) we expect users of Miniscript to always know all the
keys used in a script that they're signing. Except perhaps in obscure
cases where, say, the "victim" is a somewhat passive countersigner of
a transaction, e.g. BitGo, ... in which case they're not the one putting
up fees or with an interest in the transaction going through.

With Miniscript, the problem is narrower:

* There is some more-expensive branch that could be taken without
  Alice's signature. In which case Alice is only signing at all to
  optimistically reduce the witness size... but she cannot assume
  that she is going to be successful!

  Notably, in this case Alice does not really have any interest in the
  coins, in the sense that they can move entirely without her consent,
  so it's hard to imagine that she has an interest in the transaction's
  speedy confirmation.

* There is some more-expensive branch that could be taken by moving
  Alice's signature. This is the case that you identify in the thread.

While the attack remains in both cases, fortunately Miniscript gives
Alice the tools to (a) determine which, if any, case applies to the
script under question, and (b) determine what the maximum witness size
might be, and just sign assuming that, treating any savings as "bonus".

[1] https://bitcoin.sipa.be/miniscript/
[2] In Taproot, if you want to prevent signatures migrating to another
    branch or within a branch, you can use the CODESEPARATOR opcode
    which was redisegned in Taproot for exactly this purpose... we
    really did about witness malleation in its design!

    If you want to prevent signatures from moving around *within* a
    branch,

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster