Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 24A94C002D for ; Mon, 7 Nov 2022 22:56:14 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id F1788403C5 for ; Mon, 7 Nov 2022 22:56:13 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org F1788403C5 Authentication-Results: smtp4.osuosl.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20210112 header.b=HhmVgmkA X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.098 X-Spam-Level: X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id wLEwjDYymD57 for ; Mon, 7 Nov 2022 22:56:12 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org CCAB040352 Received: from mail-io1-xd2a.google.com (mail-io1-xd2a.google.com [IPv6:2607:f8b0:4864:20::d2a]) by smtp4.osuosl.org (Postfix) with ESMTPS id CCAB040352 for ; Mon, 7 Nov 2022 22:56:11 +0000 (UTC) Received: by mail-io1-xd2a.google.com with SMTP id e189so10173195iof.1 for ; Mon, 07 Nov 2022 14:56:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=81wntnDtpJBHyVGKz6lQpAK/BVOVFfxRMXPXZEru9OE=; b=HhmVgmkAbB72FPlMHghci0CuEtOQMjPVjKZIjiZJpIFumULaQqury/EdfTd27kz1mH ZlX6kPY1ia9P4aKQTE70T7+9lhN7xQcvpiMPyPP2Ic9grnsYDiH8B/AfnWzvNEGu3Qmb 5oC6FLZU75BceIDtD3Z3Rfp8Ub9XVFlR4+yOJJmLy7mT25G4UJXnVISRO1Db/WBwc1RA YmrxghOpT7qE54qz9Or1TXwbnFSEBQMnNU4Yq4LWUXNy0HbquXaCIZON9SzMahsYyl35 jkm2jYJ5qioVE8aKVaYYkEHqhpedF+zhAtXpiV0022/NgoW81mENIyae9Jo+ziafEN+M CMZA== 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=81wntnDtpJBHyVGKz6lQpAK/BVOVFfxRMXPXZEru9OE=; b=OR5yDO3A43P4MRy/q99qay6dCyly7Zk2Um+zo9pJa3MP1rIT1iWr5t0zNnMhrNuOvu FdcVVx2Il7ghJCewonRsFYLPAVRWBMBYfr+QGTyGpMxje2aqud1yCCBtti2KCsWvj/J7 zkXRfcTmkGtJjiXAegHkzL6Zbg0SXc9nqv/I223yAtzyPlKZ5kDLeHF+z2slfiAe8h4W F9AdlooFqg+28g2kIYPHGTIJ3GJ3Uc+xTzJXWMtzmFhcjx1aisPKbA0qC9n+Gr8Uh5hi gPl+APf/53cmnr7pYWEuxpfvWbMfmTqg1m8rmFolspnfUDw2RUugt5lW31RqM3DiwR6G WIdg== X-Gm-Message-State: ACrzQf3zCHA7GiIbxwkvPK4sSYTAlSdfrdVF7xO5SZ+U+0tw3PNZXMfy 9ZOFJ5kL4B5HASrqHL1f/FRQPsy50CQbRm0C9VlcHrY+yVZylA== X-Google-Smtp-Source: AMsMyM72jmiHBqYO/DzJzty43VXsWlBnkdGMNkUkKuQxsiko4BwptiKQ9ich3K+5tY0diRYkZXLdRp/PLE+HOZj8xMk= X-Received: by 2002:a05:6638:31c2:b0:363:496e:b5a1 with SMTP id n2-20020a05663831c200b00363496eb5a1mr31798199jav.237.1667861770680; Mon, 07 Nov 2022 14:56:10 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Antoine Riard Date: Mon, 7 Nov 2022 17:55:59 -0500 Message-ID: To: Peter Todd , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000603df505ece95454" X-Mailman-Approved-At: Mon, 07 Nov 2022 23:14:38 +0000 Subject: Re: [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 07 Nov 2022 22:56:14 -0000 --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 > CheckSig > Else > CheckSequenceVerify > 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
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 int= o the future, spending one or more inputs of the
> transaction with a= sufficiently high fee that it would replace transaction(s)
> attempt= ing to exploit Rule #3 pinning (note how the package limits in Bitcoin
&= gt; Core help here).

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's
replacement rule ("The replacem= ent 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 fu= nded transaction participants. Solving this issue probably requires from th= en 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 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.

Further, I think this solution r= elying on nLocktime doesn'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's funding timeout reco= very mechanism).

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.

Best,
Antoine


Le=C2=A0lun. 7 nov. 2022 =C3=A0=C2=A016:18, Peter Todd via bit= coin-dev <bitco= in-dev@lists.linuxfoundation.org> a =C3=A9crit=C2=A0:
On Mon, Nov 07, 2022 at 03:17:= 29PM -0500, Peter Todd via bitcoin-dev wrote:
> tl;dr: We can remove the problem of Rule #5 pinning by ensuring that a= ll
> transactions in the mempool are always replaceable.

With Rule #5 solved, let's look at the other pinning attack on multi-pa= rty
transactions: BIP-125 Rule #3

tl;dr: In conjunction with full-RBF, nLockTime'd, pre-signed, transacti= ons 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 lo= ck
up funds from the other party by spending their input with a transaction th= at
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'l= l assume that
full-rbf is implemented and all transactions are replaceable.

BIP-125 Rule #3 states that:

=C2=A0 =C2=A0 The replacement transaction pays an absolute fee of at least = the sum paid
=C2=A0 =C2=A0 by the original transactions.

The attack is that the malicious party, who we'll call Mallory, broadca= sts a
transaction spending their input(s) with a low fee rate transaction that= 9;s
potentially quite large, during a time of high mempool demand. Due to the l= ow
fee rate this transaction will take a significant amount of time to mine. T= he
other parties to the transaction - who we'll collectively call Alice - = are now
unable to spend their inputs unless they broadcast a transaction "payi= ng 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= and
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 parties=
we'll call Alice and Bob, the parties genuinely intend for one of two o= utcomes:

1) The multi-party transaction to get mined within N blocks.
2) The transaction to be cancelled (most likely by spending one of the inpu= ts).

We can ensure with high probability that the transaction can be cancelled/m= ined
at some point after N blocks by pre-signing a transaction, with nLockTime s= et
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 Bitco= in
Core help here).

There's a few different ways to implement this, and exactly which one m= akes
sense will depend on the specifics of the multi-party protocol. But the gen= eral
approach is to defeat the attack by ensuring that Mallory will have to pay = 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 re= putable
party (Alice), and an untrusted party (Mallory), Alice could simply require=
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 up = the
protocol, he will be severely punished. Meanwhile, Alice can always cancel = at
no cost.

In a many party transaction where both parties are equally (un)trustworthy = the
protocol could simply have both parties sign a series of transactions,
nLockTimed at decreasingly far into a future, paying a decreasingly amount = of
fees. If either party holds up the transaction intentionally, they'll b= oth 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 implementi= ng
fee discovery with rbf. This approach is easier as the number of parties increases, eg the Wasabi/Joinmarket transactions with hundreds of inputs an= d
outputs: they collectively already have to pay a significant fee to get the=
transaction mined, making the extra poential cost needed to defeat pinning<= br> minimal.


# Coordinator Spent Bonds with Package Relay/Replacement

For schemes with a central semi-trusted coordinator, such as Wasabi coinjoi= ns,
with package relay/replacement we can use a two party punishment transactio= n
consisting of:

=C2=A0 =C2=A0 tx1 - spends Mallory's input to a txout spendable by:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0IF
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0<coordinator> = CheckSig
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Else
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0<delay> CheckS= equenceVerify
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0<mallory> Chec= kSig
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0EndIf

=C2=A0 =C2=A0 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 relea= se tx1
on their own to frame the coordinator. The use of CheckSequenceVerify ensur= es
that if mallory did try to frame the coordinator, they don't have to do=
anything to return the funds to Mallory.

--
http= s://petertodd.org 'peter'[:-1]@petertodd.org
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000603df505ece95454--