MIME-Version: 1.0
References: <CAAQdECCH=YOcu4g6Ku1_G4CnRg6rsaFPFPwbABx9aZin9A8+2A@mail.gmail.com>
In-Reply-To: <CAAQdECCH=YOcu4g6Ku1_G4CnRg6rsaFPFPwbABx9aZin9A8+2A@mail.gmail.com>
From: Nadav Ivgi <nadav@shesek.info>
Date: Tue, 7 Feb 2023 11:36:58 +0200
Message-ID: <CAGXD5f3Bu3+BsbRQNcA=eugW7FDdgR0xQdpn66925b4DjRyJeQ@mail.gmail.com>
To: Yuval Kogman <nothingmuch@woobling.org>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000047aba005f418e47e"
Subject: Re: [bitcoin-dev] Unenforceable fee obligations in multiparty
 protocols with Taproot inputs
Precedence: list

--00000000000047aba005f418e47e
Content-Type: text/plain; charset="UTF-8"

> Since Taproot (more generally any kind of MAST) spends have variable size

Isn't this the case with any arbitrary script execution? Non-taproot
P2(W)SH can also have multiple (OP_IF-gated) script branches. For example
with `<pk> CHECKSIG IF SHA256 <hash> EQUALVERIFY ENDIF`, Mallory can
initially demonstrate that she can spend with `FALSE <sig>`, then later
switch to spending with `<some large preimage> TRUE <sig>`. (or I guess
even `DROP <pk> CHECKSIG`, then just switch from DROPing a 0 length item to
a larger one)

It seems that supporting arbitrary scripts would require analyzing them and
verifying that all spend paths are acceptable, with or without Taproot/MAST.

If the goal is to only allow registering simple singlesig-encumbered UTXOs
like P2(W)PKH, the participants could be asked to prove that their P2TR
output commits to an unspendable script path [0].

shesek

[0]
https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#cite_ref-23-0

On Tue, Feb 7, 2023 at 4:59 AM Yuval Kogman via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> ## Summary
>
> 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).
>
> ## Attack Scenario
>
> Alice et al wish to perform a multiparty transaction, such as a CoinJoin or
> lightning dual funding at a relatively high feerate.
>
> Mallory has a P2TR output with a large script spend path, e.g. an ordinal
> inscription commitment transaction output.
>
> Mallory registers this coin as an input into the multiparty transaction
> with a
> fee obligation calculated on the basis of a key spend. When all other
> participants have provided signatures, the script spend path can be used.
>
> Since the absolute fee amount is already committed to by the provided
> (`SIGHASH_ALL`) signatures but the total transaction weight is not,
> Mallory can
> broadcast any valid signatures up to the maximum standard weight and
> minimum
> relay fees, or in collusion with a miner, up to consensus limits.
>
> This effectively steals a fee from Alice et al, as their signatures do not
> commit to a feerate directly or indirectly.
>
> ## Mitigations
>
> ### RBF
>
> All parties could negotiate a (series of) transaction(s) ahead of time at a
> lower feerate, giving a lower bound minimum feerate that Mallory can force.
>
> ### Minimum Weight Before Signing
>
> Enforcing a minimal weight for all non-witness data in the transaction
> before
> the transaction is considered fully constructed can limit the
> effectiveness of
> this attack, since the difference between the predicted weight and the
> maximum
> weight decreases.
>
> ### Trusted Coordinator
>
> In the centralized setting if BIP-322 ownership proofs are required for
> participation and assuming the server can be trusted not to collude with
> Mallory, the server can reject signatures that do not exercise the same
> spend
> path as the ownership proof, which makes the ownership proof a commitment
> to the
> spend weight of the input.
>
> ### Reputation
>
> Multiparty protocols with publicly verifiable protocol transcripts can be
> provided as weak evidence of a history of honest participation in
> multiparty
> transactions.
>
> A ring signature from keys used in the transaction or its transcript
> committing
> to the new proposed transaction can provide weak evidence for the honesty
> of the
> peer.
>
> Such proofs are more compelling to an entity which has participated in
> (one of)
> the transcripts, or proximal transactions. Incentives are theoretically
> aligned
> if public coordinators publish these transcripts as a kind of server
> reputation.
>
> ### Increasing Costliness
>
> A minimum feerate for the previous transaction or a minimum confirmation
> age
> (coindays destroyed implies time value, analogous to fidelity bonds) can be
> required for inputs to be added, in order to make such attacks less
> lucrative
> (but there is still a positive payoff for the attacker).
>
> ### Signature Ordering
>
> Signatures from potentially exploitative inputs can be required ahead of
> legacy
> or SegWit v0 ones. The prescribed order can be determined based on
> reputation or
> costliness as described in the previous paragraphs.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--00000000000047aba005f418e47e
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>&gt; Since Taproot (more generally any kind of MAST) =
spends have variable size</div><div><br></div><div>Isn&#39;t this the case =
with any arbitrary script execution? Non-taproot P2(W)SH can also have mult=
iple (OP_IF-gated) script branches. For example with `&lt;pk&gt; CHECKSIG I=
F SHA256 &lt;hash&gt; EQUALVERIFY ENDIF`, Mallory can initially demonstrate=
 that she can spend with `FALSE &lt;sig&gt;`, then later switch to spending=
 with `&lt;some large preimage&gt; TRUE &lt;sig&gt;`. (or I guess even `DRO=
P &lt;pk&gt; CHECKSIG`, then just switch from DROPing a 0 length item to a =
larger one)</div><div><br></div><div>It seems that supporting arbitrary scr=
ipts would require analyzing them and verifying that all spend paths are ac=
ceptable, with or without Taproot/MAST.</div><div><br></div><div>If the goa=
l is to only allow registering simple singlesig-encumbered UTXOs like P2(W)=
PKH, the participants could be asked to prove that their P2TR output commit=
s to an unspendable script path [0].</div><div><br></div><div></div><div>sh=
esek<br></div><div><br></div><div>[0] <a href=3D"https://github.com/bitcoin=
/bips/blob/master/bip-0341.mediawiki#cite_ref-23-0">https://github.com/bitc=
oin/bips/blob/master/bip-0341.mediawiki#cite_ref-23-0</a></div></div><br><d=
iv class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Tue, Feb =
7, 2023 at 4:59 AM Yuval Kogman via bitcoin-dev &lt;<a href=3D"mailto:bitco=
in-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</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">## S=
ummary<br>
<br>
Since Taproot (more generally any kind of MAST) spends have variable size w=
hich<br>
depends on the path being used, the last such input to be signed in a multi=
party<br>
transaction can always use a larger than estimated signature to unfairly ex=
tract<br>
a fee contribution from the other parties to the transaction (keeping the<b=
r>
absolute fees the same and reducing the feerate for the transaction).<br>
<br>
## Attack Scenario<br>
<br>
Alice et al wish to perform a multiparty transaction, such as a CoinJoin or=
<br>
lightning dual funding at a relatively high feerate.<br>
<br>
Mallory has a P2TR output with a large script spend path, e.g. an ordinal<b=
r>
inscription commitment transaction output.<br>
<br>
Mallory registers this coin as an input into the multiparty transaction wit=
h a<br>
fee obligation calculated on the basis of a key spend. When all other<br>
participants have provided signatures, the script spend path can be used.<b=
r>
<br>
Since the absolute fee amount is already committed to by the provided<br>
(`SIGHASH_ALL`) signatures but the total transaction weight is not, Mallory=
 can<br>
broadcast any valid signatures up to the maximum standard weight and minimu=
m<br>
relay fees, or in collusion with a miner, up to consensus limits.<br>
<br>
This effectively steals a fee from Alice et al, as their signatures do not<=
br>
commit to a feerate directly or indirectly.<br>
<br>
## Mitigations<br>
<br>
### RBF<br>
<br>
All parties could negotiate a (series of) transaction(s) ahead of time at a=
<br>
lower feerate, giving a lower bound minimum feerate that Mallory can force.=
<br>
<br>
### Minimum Weight Before Signing<br>
<br>
Enforcing a minimal weight for all non-witness data in the transaction befo=
re<br>
the transaction is considered fully constructed can limit the effectiveness=
 of<br>
this attack, since the difference between the predicted weight and the maxi=
mum<br>
weight decreases.<br>
<br>
### Trusted Coordinator<br>
<br>
In the centralized setting if BIP-322 ownership proofs are required for<br>
participation and assuming the server can be trusted not to collude with<br=
>
Mallory, the server can reject signatures that do not exercise the same spe=
nd<br>
path as the ownership proof, which makes the ownership proof a commitment t=
o the<br>
spend weight of the input.<br>
<br>
### Reputation<br>
<br>
Multiparty protocols with publicly verifiable protocol transcripts can be<b=
r>
provided as weak evidence of a history of honest participation in multipart=
y<br>
transactions.<br>
<br>
A ring signature from keys used in the transaction or its transcript commit=
ting<br>
to the new proposed transaction can provide weak evidence for the honesty o=
f the<br>
peer.<br>
<br>
Such proofs are more compelling to an entity which has participated in (one=
 of)<br>
the transcripts, or proximal transactions. Incentives are theoretically ali=
gned<br>
if public coordinators publish these transcripts as a kind of server reputa=
tion.<br>
<br>
### Increasing Costliness<br>
<br>
A minimum feerate for the previous transaction or a minimum confirmation ag=
e<br>
(coindays destroyed implies time value, analogous to fidelity bonds) can be=
<br>
required for inputs to be added, in order to make such attacks less lucrati=
ve<br>
(but there is still a positive payoff for the attacker).<br>
<br>
### Signature Ordering<br>
<br>
Signatures from potentially exploitative inputs can be required ahead of le=
gacy<br>
or SegWit v0 ones. The prescribed order can be determined based on reputati=
on or<br>
costliness as described in the previous paragraphs.<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--00000000000047aba005f418e47e--