path: root/97/a9b05fd568ef4373aa58974bdcc875d400b28d

Return-Path: <nadav@shesek.info>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id D2FA4C002B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue,  7 Feb 2023 09:37:13 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp1.osuosl.org (Postfix) with ESMTP id 9FF7F8125B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue,  7 Feb 2023 09:37:13 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 9FF7F8125B
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.697
X-Spam-Level: 
X-Spam-Status: No, score=-1.697 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_INVALID=0.1, DKIM_SIGNED=0.1,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_NONE=0.001] autolearn=no autolearn_force=no
Received: from smtp1.osuosl.org ([127.0.0.1])
 by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id GGHHr1dt6PcN
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue,  7 Feb 2023 09:37:12 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org D7F3981234
Received: from mail-ed1-x536.google.com (mail-ed1-x536.google.com
 [IPv6:2a00:1450:4864:20::536])
 by smtp1.osuosl.org (Postfix) with ESMTPS id D7F3981234
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue,  7 Feb 2023 09:37:11 +0000 (UTC)
Received: by mail-ed1-x536.google.com with SMTP id ee13so8022949edb.5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 07 Feb 2023 01:37:11 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=shesek.info; s=shesek;
 h=to:subject:message-id:date:from:in-reply-to:references:mime-version
 :from:to:cc:subject:date:message-id:reply-to;
 bh=1H/CDwrnOEMoedqA9LjSrYDbq90D3acKrJwj6qLozQ0=;
 b=PblOJju/Pj9qvb6myv4DvrUbtN0FJ/rxY0Y3XwSbu0EoMuXqtqMDMOgTQA0Na+g+2W
 ZdnB26uZjMgPOGxh0YOJMxDd52dpDIXBViu1kF6nW6fTXXewoQqFxg4AtZ0xKVt/57Tk
 897pUIifZslBB3T+Vh4NveoIyZwjEm8eRw/Bg=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=to:subject:message-id:date:from:in-reply-to:references:mime-version
 :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to;
 bh=1H/CDwrnOEMoedqA9LjSrYDbq90D3acKrJwj6qLozQ0=;
 b=dNC+hLaoLstRJk5jDHT+EO6rRwUCRmBltmSp+gAJtj9dWVzkOTSqOAH3fNZo0IyyGN
 axBJGPVTarvs+s012GJ0yRVRuNT+1fgeX3ziRvIWeyc7QsQ4bZ0zyKP8gxJIh5AG+3Bz
 DruqhP2JpSBjC58+YWVuYyXvLG92vJlaqeNtLGDxP+wTN5J6hKKdMya9j9bZuZxQOV4z
 mVCPlEboAF9NCYsf4IySN3YdLs2A837JqpiOEH/rsdA9nyhlmlzppmhvdOddvcaV5Gxp
 PKEbBDHC6fFiyeYKUBak6KhXN9GPYkexvOXPi0vptz1GKbAOyA47ORGHYUbHP8DDaTMg
 d1bg==
X-Gm-Message-State: AO0yUKUMB7CO3Cx9x504F8s6GckDyQXR5j0RMIymAael+4uWe3BaE+0y
 LVxOifxMqk1hr/f8uDhIlhGUBq+t9vlHlns4igX+JljqpfM6lQvyFJ8=
X-Google-Smtp-Source: AK7set/vlLBL9ragesC9GaNcrWpHjnwRjuAo052ggZaOFhdygrJzlyBGCNQbH0AW+vKdM24Q1+8JhoCxp8kMEtamVUg=
X-Received: by 2002:a50:9e61:0:b0:49c:948d:e8ec with SMTP id
 z88-20020a509e61000000b0049c948de8ecmr405979ede.2.1675762629843; Tue, 07 Feb
 2023 01:37:09 -0800 (PST)
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"
X-Mailman-Approved-At: Tue, 07 Feb 2023 09:58:38 +0000
Subject: Re: [bitcoin-dev] Unenforceable fee obligations in multiparty
 protocols with Taproot inputs
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 07 Feb 2023 09:37:13 -0000

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