Date: Tue, 7 Feb 2023 13:46:22 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Yuval Kogman <nothingmuch@woobling.org>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <Y+JWLsc80gxL4kpG@camus>
References: <CAAQdECCH=YOcu4g6Ku1_G4CnRg6rsaFPFPwbABx9aZin9A8+2A@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
 protocol="application/pgp-signature"; boundary="bAgrOVScsKO5Sq5R"
Content-Disposition: inline
In-Reply-To: <CAAQdECCH=YOcu4g6Ku1_G4CnRg6rsaFPFPwbABx9aZin9A8+2A@mail.gmail.com>
Subject: Re: [bitcoin-dev] Unenforceable fee obligations in multiparty
 protocols with Taproot inputs
Precedence: list


--bAgrOVScsKO5Sq5R
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Tue, Feb 07, 2023 at 04:49:28AM +0200, Yuval Kogman via bitcoin-dev wrot=
e:
>=20
> 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 mul=
tiparty
> 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,

--=20
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


--bAgrOVScsKO5Sq5R
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQEzBAEBCAAdFiEEkPnKPD7Je+ki35VexYjWPOQbl8EFAmPiVi0ACgkQxYjWPOQb
l8H24gf+Ml1E9iSksNjlM1kzIZmSh6eB8kq2JHLz/hrzlrqAPRAHnqLNNepkJGkE
CRj8nf5qC1fkymozOulE3safWKE+8dgA6DmWtV4Jv4fB5h+UEmGyqZDmV8tDtSng
aJMvxZ+5VizTZoBUk9+wW24p1Mfb3UtFCD5LQUrohFXMd2m4/Vx5WS0iT5zFgI6e
bH99gDKvsaK3DlSj0uqSEP/rZ1gbiOFv6hZvDchk6b1yn6E0aaNHhAITVrkxSfA0
fsVxvqSeEhdGa7OW7+cH8Z23VGfpNKRtEdtPOTbwb/DRNMUdN+jFgosj12sijil7
8NDlf2XZi1s4xJyVGRxugvS78TJAgQ==
=+Q0Y
-----END PGP SIGNATURE-----

--bAgrOVScsKO5Sq5R--