MIME-Version: 1.0
References: <Y2ln2fJ+8+Q0qS0E@petertodd.org> <Y2l1/qXHxyctU9ir@petertodd.org>
In-Reply-To: <Y2l1/qXHxyctU9ir@petertodd.org>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Mon, 7 Nov 2022 17:55:59 -0500
Message-ID: <CALZpt+GgH7B-sSWndNfrMp8qza=LmZQ6BWGGFjFxcutat7Nxww@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000603df505ece95454"
Subject: Re: [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning
	with nLockTime
Precedence: list

--000000000000603df505ece95454
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Peter,

> We can ensure with high probability that the transaction can be cancelled=
/mined
> at some point after N blocks by pre-signing a transaction, with nLockTime=
 set
> sufficiently far into the future, spending one or more inputs of the
> transaction with a sufficiently high fee that it would replace transactio=
n(s)
> attempting to exploit Rule #3 pinning (note how the package limits in Bit=
coin
> Core help here).

From my understanding, there are many open questions to such a
pre-signed high-fee solution aiming to address Rule #3 pinning.
Determining the high-fee to guarantee replacements with high odds. I
think it should be superior to current top network mempools sat/vb *
MAX_STANDARD_TX_WEIGHT, otherwise an adversary can pin the multi-party
funded transaction on the ground of Core's
replacement rule ("The replacement transaction's feerate is greater
than the feerates of all directly conflicting transactions''). Though
note the difficulty, the sat/vb is an unknown fact at time of
signatures exchange among the multi-party funded transaction
participants. Solving this issue probably requires from then to
overshoot, and adopt a historical worst-case mempool feerate.

This "historically-worst" sat/vb introduces two new issues, first I
think this is an economic lower bound on the funds that can be staked
in the collaborative transaction. Second I believe this constitutes a
griefing vector, where a participant could deliberately pin to inflict
an asymmetric damage, without entering into any fee competition. This
griefing vector could be leveraged as hard as being triggered by a
miner-as-participant in so-called miner harvesting attacks.

Further, I think this solution relying on nLocktime doesn't solve the
timevalue DoS inflicted to the participants UTXOs, until the
pre-signed high-fee transaction is final. If participants prefer to
save the timevalue of their contributed UTXOs over operation success,
a better approach could be for them to unilaterally spend after a
protocol/implementation timepoint (e.g LN's funding timeout recovery
mechanism).

A more workable solution I believe could be simply to rely on
package-relay, an ephemeral anchor output, and a special replacement
regime (e.g nVersion=3D3) to allow the multi-party funded transaction
coordinator to unilateral fee-bump, in a step-by-step approach. I.e
without making assumptions on the knowledge of network mempools and
burning directly the worst amount in fees.

Best,
Antoine


Le lun. 7 nov. 2022 =C3=A0 16:18, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :

> On Mon, Nov 07, 2022 at 03:17:29PM -0500, Peter Todd via bitcoin-dev wrot=
e:
> > tl;dr: We can remove the problem of Rule #5 pinning by ensuring that al=
l
> > transactions in the mempool are always replaceable.
>
> With Rule #5 solved, let's look at the other pinning attack on multi-part=
y
> transactions: BIP-125 Rule #3
>
> tl;dr: In conjunction with full-RBF, nLockTime'd, pre-signed, transaction=
s
> can
> ensure that one party is not forced to pay for all the cost of a rule #3
> replacement.
>
>
> # What is the problem?
>
> When a transaction contains inputs from multiple parties, each party can
> lock
> up funds from the other party by spending their input with a transaction
> that
> is difficult/expensive to replace. Obviously, the clearest example of
> "difficult to
> replace" is a non-BIP-125 (Opt-in-RBF) transaction. But here, we'll assum=
e
> that
> full-rbf is implemented and all transactions are replaceable.
>
> BIP-125 Rule #3 states that:
>
>     The replacement transaction pays an absolute fee of at least the sum
> paid
>     by the original transactions.
>
> The attack is that the malicious party, who we'll call Mallory, broadcast=
s
> a
> transaction spending their input(s) with a low fee rate transaction that'=
s
> potentially quite large, during a time of high mempool demand. Due to the
> low
> fee rate this transaction will take a significant amount of time to mine.
> The
> other parties to the transaction - who we'll collectively call Alice - ar=
e
> now
> unable to spend their inputs unless they broadcast a transaction "paying
> for"
> Mallory's.
>
> This attack works because Mallory doesn't expect the conflicting tx to
> actually
> get mined: he assumes it'll either expire, or Alice will get frustrated a=
nd
> have to double spend it. By simple tying up money, Mallory has caused
> Alice to
> actually lose money.
>
>
> # Fixing the problem with nLockTime
>
> Conversely, in the case of an honest multi-party transaction, whose parti=
es
> we'll call Alice and Bob, the parties genuinely intend for one of two
> outcomes:
>
> 1) The multi-party transaction to get mined within N blocks.
> 2) The transaction to be cancelled (most likely by spending one of the
> inputs).
>
> We can ensure with high probability that the transaction can be
> cancelled/mined
> at some point after N blocks by pre-signing a transaction, with nLockTime
> set
> sufficiently far into the future, spending one or more inputs of the
> transaction with a sufficiently high fee that it would replace
> transaction(s)
> attempting to exploit Rule #3 pinning (note how the package limits in
> Bitcoin
> Core help here).
>
> There's a few different ways to implement this, and exactly which one mak=
es
> sense will depend on the specifics of the multi-party protocol. But the
> general
> approach is to defeat the attack by ensuring that Mallory will have to pa=
y
> the
> cost of getting the multi-party transaction unstuck, at some point in the
> future.
>
> For example, in a two party transaction where there's a clearly more
> reputable
> party (Alice), and an untrusted party (Mallory), Alice could simply requi=
re
> Mallory to provide a nLockTime'd transaction spending only his input to
> fees,
> multiple days into the future. In the unlikely event that Mallory holds u=
p
> the
> protocol, he will be severely punished. Meanwhile, Alice can always cance=
l
> at
> no cost.
>
> In a many party transaction where both parties are equally (un)trustworth=
y
> the
> protocol could simply have both parties sign a series of transactions,
> nLockTimed at decreasingly far into a future, paying a decreasingly amoun=
t
> of
> fees. If either party holds up the transaction intentionally, they'll bot=
h
> pay
> a high cost. But again, at some point Mallory will have paid the full
> price for
> his attack. This approach also has the beneficial side effect of
> implementing
> fee discovery with rbf. This approach is easier as the number of parties
> increases, eg the Wasabi/Joinmarket transactions with hundreds of inputs
> and
> outputs: they collectively already have to pay a significant fee to get t=
he
> transaction mined, making the extra poential cost needed to defeat pinnin=
g
> minimal.
>
>
> # Coordinator Spent Bonds with Package Relay/Replacement
>
> For schemes with a central semi-trusted coordinator, such as Wasabi
> coinjoins,
> with package relay/replacement we can use a two party punishment
> transaction
> consisting of:
>
>     tx1 - spends Mallory's input to a txout spendable by:
>            IF
>                <coordinator> CheckSig
>            Else
>                <delay> CheckSequenceVerify
>                <mallory> CheckSig
>            EndIf
>
>     tx2 - spends tx1 output to as much fees as needed
>
> Whether or not Mallory cheated with a double-spend is provable to third
> parties; the second transaction ensures that Mallory can't simply release
> tx1
> on their own to frame the coordinator. The use of CheckSequenceVerify
> ensures
> that if mallory did try to frame the coordinator, they don't have to do
> anything to return the funds to Mallory.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr"><pre><span style=3D"font-family:arial,sans-serif"><font si=
ze=3D"2">Hi Peter,<br><br>&gt; We can ensure with high probability that the=
 transaction can be cancelled/mined<br>&gt; at some point after N blocks by=
 pre-signing a transaction, with nLockTime set<br>&gt; sufficiently far int=
o the future, spending one or more inputs of the<br>&gt; transaction with a=
 sufficiently high fee that it would replace transaction(s)<br>&gt; attempt=
ing to exploit Rule #3 pinning (note how the package limits in Bitcoin<br>&=
gt; Core help here).<br><br>From my understanding, there are many open ques=
tions to such a pre-signed high-fee solution aiming to address Rule #3 pinn=
ing. Determining the high-fee to guarantee replacements with high odds. I t=
hink it should be superior to current top network mempools sat/vb * MAX_STA=
NDARD_TX_WEIGHT, otherwise an adversary can pin the multi-party funded tran=
saction on the ground of Core&#39;s<br>replacement rule (&quot;The replacem=
ent transaction&#39;s feerate is greater than the feerates of all directly =
conflicting transactions&#39;&#39;). Though note the difficulty, the sat/vb=
 is an unknown fact at time of signatures exchange among the multi-party fu=
nded transaction participants. Solving this issue probably requires from th=
en to overshoot, and adopt a historical worst-case mempool feerate.<br><br>=
This &quot;historically-worst&quot; sat/vb introduces two new issues, first=
 I think this is an economic lower bound on the funds that can be staked in=
 the collaborative transaction. Second I believe this constitutes a griefin=
g vector, where a participant could deliberately pin to inflict an asymmetr=
ic damage, without entering into any fee competition. This griefing vector =
could be leveraged as hard as being triggered by a miner-as-participant in =
so-called miner harvesting attacks.<br><br>Further, I think this solution r=
elying on nLocktime doesn&#39;t solve the timevalue DoS inflicted to the pa=
rticipants UTXOs, until the pre-signed high-fee transaction is final. If pa=
rticipants prefer to save the timevalue of their contributed UTXOs over ope=
ration success, a better approach could be for them to unilaterally spend a=
fter a protocol/implementation timepoint (e.g LN&#39;s funding timeout reco=
very mechanism).<br><br>A more workable solution I believe could be simply =
to rely on package-relay, an ephemeral anchor output, and a special replace=
ment regime (e.g nVersion=3D3) to allow the multi-party funded transaction =
coordinator to unilateral fee-bump, in a step-by-step approach. I.e without=
 making assumptions on the knowledge of network mempools and burning direct=
ly the worst amount in fees.<br><br></font></span></pre><pre><span style=3D=
"font-family:arial,sans-serif"><font size=3D"2">Best,<br>Antoine</font></sp=
an><br></pre></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D=
"gmail_attr">Le=C2=A0lun. 7 nov. 2022 =C3=A0=C2=A016:18, Peter Todd via bit=
coin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitco=
in-dev@lists.linuxfoundation.org</a>&gt; a =C3=A9crit=C2=A0:<br></div><bloc=
kquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:=
1px solid rgb(204,204,204);padding-left:1ex">On Mon, Nov 07, 2022 at 03:17:=
29PM -0500, Peter Todd via bitcoin-dev wrote:<br>
&gt; tl;dr: We can remove the problem of Rule #5 pinning by ensuring that a=
ll<br>
&gt; transactions in the mempool are always replaceable.<br>
<br>
With Rule #5 solved, let&#39;s look at the other pinning attack on multi-pa=
rty<br>
transactions: BIP-125 Rule #3<br>
<br>
tl;dr: In conjunction with full-RBF, nLockTime&#39;d, pre-signed, transacti=
ons can<br>
ensure that one party is not forced to pay for all the cost of a rule #3<br=
>
replacement.<br>
<br>
<br>
# What is the problem?<br>
<br>
When a transaction contains inputs from multiple parties, each party can lo=
ck<br>
up funds from the other party by spending their input with a transaction th=
at<br>
is difficult/expensive to replace. Obviously, the clearest example of &quot=
;difficult to<br>
replace&quot; is a non-BIP-125 (Opt-in-RBF) transaction. But here, we&#39;l=
l assume that<br>
full-rbf is implemented and all transactions are replaceable.<br>
<br>
BIP-125 Rule #3 states that:<br>
<br>
=C2=A0 =C2=A0 The replacement transaction pays an absolute fee of at least =
the sum paid<br>
=C2=A0 =C2=A0 by the original transactions.<br>
<br>
The attack is that the malicious party, who we&#39;ll call Mallory, broadca=
sts a<br>
transaction spending their input(s) with a low fee rate transaction that&#3=
9;s<br>
potentially quite large, during a time of high mempool demand. Due to the l=
ow<br>
fee rate this transaction will take a significant amount of time to mine. T=
he<br>
other parties to the transaction - who we&#39;ll collectively call Alice - =
are now<br>
unable to spend their inputs unless they broadcast a transaction &quot;payi=
ng for&quot;<br>
Mallory&#39;s.<br>
<br>
This attack works because Mallory doesn&#39;t expect the conflicting tx to =
actually<br>
get mined: he assumes it&#39;ll either expire, or Alice will get frustrated=
 and<br>
have to double spend it. By simple tying up money, Mallory has caused Alice=
 to<br>
actually lose money.<br>
<br>
<br>
# Fixing the problem with nLockTime<br>
<br>
Conversely, in the case of an honest multi-party transaction, whose parties=
<br>
we&#39;ll call Alice and Bob, the parties genuinely intend for one of two o=
utcomes:<br>
<br>
1) The multi-party transaction to get mined within N blocks.<br>
2) The transaction to be cancelled (most likely by spending one of the inpu=
ts).<br>
<br>
We can ensure with high probability that the transaction can be cancelled/m=
ined<br>
at some point after N blocks by pre-signing a transaction, with nLockTime s=
et<br>
sufficiently far into the future, spending one or more inputs of the<br>
transaction with a sufficiently high fee that it would replace transaction(=
s)<br>
attempting to exploit Rule #3 pinning (note how the package limits in Bitco=
in<br>
Core help here).<br>
<br>
There&#39;s a few different ways to implement this, and exactly which one m=
akes<br>
sense will depend on the specifics of the multi-party protocol. But the gen=
eral<br>
approach is to defeat the attack by ensuring that Mallory will have to pay =
the<br>
cost of getting the multi-party transaction unstuck, at some point in the<b=
r>
future.<br>
<br>
For example, in a two party transaction where there&#39;s a clearly more re=
putable<br>
party (Alice), and an untrusted party (Mallory), Alice could simply require=
<br>
Mallory to provide a nLockTime&#39;d transaction spending only his input to=
 fees,<br>
multiple days into the future. In the unlikely event that Mallory holds up =
the<br>
protocol, he will be severely punished. Meanwhile, Alice can always cancel =
at<br>
no cost.<br>
<br>
In a many party transaction where both parties are equally (un)trustworthy =
the<br>
protocol could simply have both parties sign a series of transactions,<br>
nLockTimed at decreasingly far into a future, paying a decreasingly amount =
of<br>
fees. If either party holds up the transaction intentionally, they&#39;ll b=
oth pay<br>
a high cost. But again, at some point Mallory will have paid the full price=
 for<br>
his attack. This approach also has the beneficial side effect of implementi=
ng<br>
fee discovery with rbf. This approach is easier as the number of parties<br=
>
increases, eg the Wasabi/Joinmarket transactions with hundreds of inputs an=
d<br>
outputs: they collectively already have to pay a significant fee to get the=
<br>
transaction mined, making the extra poential cost needed to defeat pinning<=
br>
minimal.<br>
<br>
<br>
# Coordinator Spent Bonds with Package Relay/Replacement<br>
<br>
For schemes with a central semi-trusted coordinator, such as Wasabi coinjoi=
ns,<br>
with package relay/replacement we can use a two party punishment transactio=
n<br>
consisting of:<br>
<br>
=C2=A0 =C2=A0 tx1 - spends Mallory&#39;s input to a txout spendable by:<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0IF<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0&lt;coordinator&gt; =
CheckSig<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Else<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0&lt;delay&gt; CheckS=
equenceVerify<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0&lt;mallory&gt; Chec=
kSig<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0EndIf<br>
<br>
=C2=A0 =C2=A0 tx2 - spends tx1 output to as much fees as needed<br>
<br>
Whether or not Mallory cheated with a double-spend is provable to third<br>
parties; the second transaction ensures that Mallory can&#39;t simply relea=
se tx1<br>
on their own to frame the coordinator. The use of CheckSequenceVerify ensur=
es<br>
that if mallory did try to frame the coordinator, they don&#39;t have to do=
<br>
anything to return the funds to Mallory.<br>
<br>
-- <br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> &#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org"=
 rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><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>

--000000000000603df505ece95454--