public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* Re: [bitcoin-dev] RBF Pinning with Counterparties and Competing Interest
@ 2020-04-22 22:53 Matt Corallo
  2020-04-23  9:59 ` David A. Harding
  0 siblings, 1 reply; 26+ messages in thread
From: Matt Corallo @ 2020-04-22 22:53 UTC (permalink / raw)
  To: David A. Harding; +Cc: Bitcoin Protocol Discussion, lightning-dev

Hmm, that's an interesting suggestion, it definitely raises the bar for attack execution rather significantly. Because lightning (and other second-layer systems) already relies heavily on uncensored access to blockchain data, its reasonable to extend the "if you don't have enough blocks, aggressively query various sources to find new blocks, or, really just do it always" solution to "also send relevant transactions while we're at it".

Sadly, unlike for block data, there is no consensus mechanism for nodes to ensure the transactions in their mempools are the same as others. Thus, if you focus on sending the pinning transaction to miner nodes directly (which isn't trivial, but also not nearly as hard as it sounds), you could still pull off the attack. However, to do it now, you'd need to
wait for your counterparty to broadcast the corresponding timeout transaction (once it is confirmable, and can thus get into mempools), turning the whole thing into a mempool-acceptance race. Luckily there isn’t much cost to *trying*, though it’s less likely you’ll succeed.

There are also practical design issues - if you’re claiming multiple HTLC output in a single transaction the node would need to provide reject messages for each input which is conflicted, something which we’d need to think hard about the DoS implications of.

In any case, while it’s definitely better than nothing, it’s unclear if it’s really the kind of thing I’d want to rely on for my own funds.

Matt


> On 4/22/20 2:24 PM, David A. Harding wrote:
>> On Mon, Apr 20, 2020 at 10:43:14PM -0400, Matt Corallo via Lightning-dev wrote:
>> A lightning counterparty (C, who received the HTLC from B, who
>> received it from A) today could, if B broadcasts the commitment
>> transaction, spend an HTLC using the preimage with a low-fee,
>> RBF-disabled transaction.  After a few blocks, A could claim the HTLC
>> from B via the timeout mechanism, and then after a few days, C could
>> get the HTLC-claiming transaction mined via some out-of-band agreement
>> with a small miner. This leaves B short the HTLC value.
> 
> IIUC, the main problem is honest Bob will broadcast a transaction
> without realizing it conflicts with a pinned transaction that's already
> in most node's mempools.  If Bob knew about the pinned transaction and
> could get a copy of it, he'd be fine.
> 
> In that case, would it be worth re-implementing something like a BIP61
> reject message but with an extension that returns the txids of any
> conflicts?  For example, when Bob connects to a bunch of Bitcoin nodes
> and sends his conflicting transaction, the nodes would reply with
> something like "rejected: code 123: conflicts with txid 0123...cdef".
> Bob could then reply with a a getdata('tx', '0123...cdef') to get the
> pinned transaction, parse out its preimage, and resolve the HTLC.
> 
> This approach isn't perfect (if it even makes sense at all---I could be
> misunderstanding the problem) because one of the problems that caused
> BIP61 to be disabled in Bitcoin Core was its unreliability, but I think
> if Bob had at least one honest peer that had the pinned transaction in
> its mempool and which implemented reject-with-conflicting-txid, Bob
> might be ok.
> 
> -Dave



^ permalink raw reply	[flat|nested] 26+ messages in thread
* Re: [bitcoin-dev] RBF Pinning with Counterparties and Competing Interest
@ 2020-04-22 23:13 Olaoluwa Osuntokun
  2020-04-22 23:20 ` Matt Corallo
  0 siblings, 1 reply; 26+ messages in thread
From: Olaoluwa Osuntokun @ 2020-04-22 23:13 UTC (permalink / raw)
  To: Matt Corallo; +Cc: Bitcoin Protocol Discussion, lightning-dev

[-- Attachment #1: Type: text/plain, Size: 8561 bytes --]

> This seems like a somewhat unnecessary drive-by insult of a project you
> don't contribute to, but feel free to start with a concrete suggestion
> here :).

This wasn't intended as an insult at all. I'm simply saying if there's
concern about worst case eviction/replacement, optimizations likely exist.
Other developers that are interested in more complex multi-transaction
contracts have realized this as well, and there're various open PRs that
attempt to propose such optimizations [1].

> Hmm, maybe the proposal wasn't clear. The idea isn't to add signatures to
> braodcasted transactions, but instead to CPFP a maybe-broadcasted
> transaction by sending a transaction which spends it and seeing if it is
> accepted

Sorry I still don't follow. By "we clearly need to go the other direction -
all HTLC output spends need to be pre-signed.", you don't mean that the HTLC
spends of the non-broadcaster also need to be an off-chain 2-of-2 multi-sig
covenant? If the other party isn't restricted w.r.t _how_ they can spend the
output (non-rbf'd, ect), then I don't see how that addresses anything.

Also see my mail elsewhere in the thread that the other party is actually
forced to spend their HTLC output using an RBF-replaceable transaction. With
that, I think we're all good here? In the end both sides have the ability to
raise the fee rate of their spending transactions with the highest winning.
As long as one of them confirms within the CLTV-delta, then everyone is
made whole.


[1]: https://github.com/bitcoin/bitcoin/pull/18191


On Wed, Apr 22, 2020 at 9:50 AM Matt Corallo <lf-lists@mattcorallo•com>
wrote:

> A few replies inline.
>
> On 4/22/20 12:13 AM, Olaoluwa Osuntokun wrote:
> > Hi Matt,
> >
> >
> >> While this is somewhat unintuitive, there are any number of good
> anti-DoS
> >> reasons for this, eg:
> >
> > None of these really strikes me as "good" reasons for this limitation,
> which
> > is at the root of this issue, and will also plague any more complex
> Bitcoin
> > contracts which rely on nested trees of transaction to confirm (CTV,
> Duplex,
> > channel factories, etc). Regarding the various (seemingly arbitrary)
> package
> > limits it's likely the case that any issues w.r.t computational
> complexity
> > that may arise when trying to calculate evictions can be ameliorated with
> > better choice of internal data structures.
> >
> > In the end, the simplest heuristic (accept the higher fee rate package)
> side
> > steps all these issues and is also the most economically rationale from a
> > miner's perspective. Why would one prefer a higher absolute fee package
> > (which could be very large) over another package with a higher total _fee
> > rate_?
>
> This seems like a somewhat unnecessary drive-by insult of a project you
> don't contribute to, but feel free to start with
> a concrete suggestion here :).
>
> >> You'll note that B would be just fine if they had a way to safely
> monitor the
> >> global mempool, and while this seems like a prudent mitigation for
> >> lightning implementations to deploy today, it is itself a quagmire of
> >> complexity
> >
> > Is it really all that complex? Assuming we're talking about just watching
> > for a certain script template (the HTLC scipt) in the mempool to be able
> to
> > pull a pre-image as soon as possible. Early versions of lnd used the
> mempool
> > for commitment broadcast detection (which turned out to be a bad idea so
> we
> > removed it), but at a glance I don't see why watching the mempool is so
> > complex.
>
> Because watching your own mempool is not guaranteed to work, and during
> upgrade cycles that include changes to the
> policy rules an attacker could exploit your upgraded/non-upgraded status
> to perform the same attack.
>
> >> Further, this is a really obnoxious assumption to hoist onto lightning
> >> nodes - having an active full node with an in-sync mempool is a lot more
> >> CPU, bandwidth, and complexity than most lightning users were expecting
> to
> >> face.
> >
> > This would only be a requirement for Lightning nodes that seek to be a
> part
> > of the public routing network with a desire to _forward_ HTLCs. This
> isn't
> > doesn't affect laptops or mobile phones which likely mostly have private
> > channels and don't participate in HTLC forwarding. I think it's pretty
> > reasonable to expect a "proper" routing node on the network to be backed
> by
> > a full-node. The bandwidth concern is valid, but we'd need concrete
> numbers
> > that compare the bandwidth over head of mempool awareness (assuming the
> > latest and greatest mempool syncing) compared with the overhead of the
> > channel update gossip and gossip queries over head which LN nodes face
> today
> > as is to see how much worse off they really would be.
>
> If mempool-watching were practical, maybe, though there are a number of
> folks who are talking about designing
> partially-offline local lightning hubs which would be rendered impractical.
>
> > As detailed a bit below, if nodes watch the mempool, then this class of
> > attack assuming the anchor output format as described in the open
> > lightning-rfc PR is mitigated. At a glance, watching the mempool seems
> like
> > a far less involved process compared to modifying the state machine as
> its
> > defined today. By watching the mempool and implementing the changes in
> > #lightning-rfc/688, then this issue can be mitigated _today_. lnd 0.10
> > doesn't yet watch the mempool (but does include anchors [1]), but unless
> I'm
> > missing something it should be pretty straight forward to add which mor
> or less
> > resolves this issue all together.
> >
> >> not fixing this issue seems to render the whole exercise somewhat
> useless
> >
> > Depends on if one considers watching the mempool a fix. But even with
> that a
> > base version of anchors still resolves a number of issues including:
> > eliminating the commitment fee guessing game, allowing users to pay less
> on
> > force close, being able to coalesce 2nd level HTLC transactions with the
> > same CLTV expiry, and actually being able to reliably enforce multi-hop
> HTLC
> > resolution.
> >
> >> Instead of making the HTLC output spending more free-form with
> >> SIGHASH_ANYONECAN_PAY|SIGHASH_SINGLE, we clearly need to go the other
> >> direction - all HTLC output spends need to be pre-signed.
> >
> > I'm not sure this is actually immediately workable (need to think about
> it
> > more). To see why, remember that the commit_sig message includes HTLC
> > signatures for the _remote_ party's commitment transaction, so they can
> > spend the HTLCs if they broadcast their version of the commitment (force
> > close). If we don't somehow also _gain_ signatures (our new HTLC
> signatures)
> > allowing us to spend HTLCs on _their_ version of the commitment, then if
> > they broadcast that commitment (without revoking), then we're unable to
> > redeem any of those HTLCs at all, possibly losing money.
>
> Hmm, maybe the proposal wasn't clear. The idea isn't to add signatures to
> braodcasted transactions, but instead to CPFP
> a maybe-broadcasted transaction by sending a transaction which spends it
> and seeing if it is accepted. You only need to
> know the transaction's exact format (ie txid, which we do, since we sent a
> signature for it long ago) to do this, you
> don't have to actually *have* the fully-signed transaction (and you don't).
>
> > In an attempt to counteract this, we might say ok, the revoke message
> also
> > now includes HTLC signatures for their new commitment allowing us to
> spend
> > our HTLCs. This resolves things in a weaker security model, but doesn't
> > address the issue generally, as after they receive the commit_sig, they
> can
> > broadcast immediately, again leaving us without a way to redeem our
> HTLCs.
> >
> > I'd need to think about it more, but it seems that following this path
> would
> > require an overhaul in the channel state machine to make presenting a new
> > commitment actually take at least _two phases_ (at least a full round
> trip).
> > The first phase would tender the commitment, but render them unable to
> > broadcast it. The second phase would then <insert something something
> > scriptless scripts here> enter a new sub-protocol which upon conclusion,
> > gives the commitment proposer valid HTLC signatures, and gives the
> responder
> > what they need to be able to broadcast their commitment and claim their
> > HTCLs in an atomic manner.
> >
> > -- Laolu
> >
> > [1]: https://github.com/lightningnetwork/lnd/pull/3821
>

[-- Attachment #2: Type: text/html, Size: 9914 bytes --]

^ permalink raw reply	[flat|nested] 26+ messages in thread
* [bitcoin-dev] RBF Pinning with Counterparties and Competing Interest
@ 2020-04-21  2:43 Matt Corallo
  2020-04-22  4:12 ` [bitcoin-dev] [Lightning-dev] " ZmnSCPxj
  0 siblings, 1 reply; 26+ messages in thread
From: Matt Corallo @ 2020-04-21  2:43 UTC (permalink / raw)
  To: lightning-dev; +Cc: Bitcoin Protocol Discussion

[Hi bitcoin-dev, in lightning-land we recently discovered some quite frustrating issues which I thought may merit
broader discussion]

While reviewing the new anchor outputs spec [1] last week, I discovered it introduced a rather nasty ability for a user
to use RBF Pinning to steal in-flight HTLCs which are being enforced on-chain. Sadly, Antoine pointed out that this is
an issue in today's light as well, though see [2] for qualifications. After some back-and-forth with a few other
lightning folks, it seems clear that there is no easy+sane fix (and the practicality of exploitation today seems
incredibly low), so soliciting ideas publicly may be the best step forward.

I've included lots of background for those who aren't super comfortable with lightning's current design, but if you
already know it well, you can skip at least background 1 & 2.

Background - Lightning's Transactions (you can skip this)
=====================================

As many of you likely know, lightning today does all its update mechanics through:
 a) a 2-of-2 multisig output, locking in the channel,
 b) a "commitment transaction", which spends that output: i) back to its owners, ii) to "HTLC outputs",
 c) HTLC transactions which spend the relevant commitment transaction HTLC outputs.

This somewhat awkward third layer of transactions is required to allow HTLC timeouts to be significantly lower than the
time window during which a counterparty may be punished for broadcasting a revoked state. That is to say, you want to
"lock-in" the resolution of an HTLC output (ie by providing the hash lock preimage on-chain) by a fixed block height
(likely a few hours from the HTLC creation), but the punishment mechanism needs to occur based on a sequence height
(possibly a day or more after transaction broadcast).

As Bitcoin has no covanents, this must occur using pre-signed transactions - namely "HTLC-Success" and "HTLC-Timeout"
transactions, which finalize the resolution of an HTLC, but have a sequence-lock for some time during which the funds
may be taken if they had previously been revoked. To avoid needless delays, if the counterparty which did *not*
broadcast the commitment transaction wishes to claim the HTLC value, they may do so immediately (as there is no reason
to punish the non-broadcaster for having *not* broadcasted a revoked state). Thus, we have four possible HTLC
resolutions depending on the combination of which side broadcast the HTLC and which side sent the HTLC (ie who can claim
it vs who can claim it after time-out):

 1) pre-signed HTLC-Success transaction, providing the preimage in the witness and sent to an output which is sequence-
    locked for some time to provide the non-broadcasting side the opportunity to take the funds,
 2) pre-signed HTLC-Timeout transaction, time-locked to N, providing no preimage, but with a similar sequence lock and
    output as above,
 3) non-pre-signed HTLC claim, providing the preimage in the witness and unencumbered by the broadcaster's signature,
 4) non-pre-signed HTLC timeout, OP_CLTV to N, and similarly unencumbered.

Background 2 - RBF Pinning (you can skip this)
==========================

Bitcoin Core's general policy on RBF transactions is that if a counterparty (either to the transaction, eg in lightning,
or not, eg a P2P node which sees the transaction early) can modify a transaction, especially if they can add an input or
output, they can prevent it from confirming in a world where there exists a mempool (ie in a world where Bitcoin works).
While this is somewhat unintuitive, there are any number of good anti-DoS reasons for this, eg:
 * (ok, this is a bad reason, but) a child transaction could be marked 'non-RBF', which would mean allowing the parent
   be RBF'd would violate the assumptions those who look at the RBF opt-in marking make,
 * a parent may be very large, but low feerate - this requires the RBF attempt to "pay for its own relay" and include a
   large absolute fee just to get into the mempool,
 * one of the various package size limits is at its maximum, and depending on the structure of the package the
   computational complexity of calculation evictions may be more than we want to do for a given transaction.

Background 3 - "The RBF Carve-Out" (you can skip this)
==================================

In today's lightning, we have a negotiation of what we expect the future feerate to be when one party goes to close the
channel. All the pre-signed transactions above are constructed with this fee-rate in mind, and, given they are all
pre-signed, adding additional fee to them is not generally an option. This is obviously a very maddening prediction
game, especially when the security consequences for negotiating a value which is wrong may allow your counterparty to
broadcast and time out HTLCs which you otherwise have the preimage for. To remove this quirk, we came up with an idea a
year or two back now called "anchor outputs" (aka the RBF carve-out for those in Bitcoin-land) - a neat trick to allow
both counterparties to add fees to a transaction which is being broadcast without getting into the quagmire that is RBF
pinning. Specifically, we added a rule to Bitcoin Core which allows for transactions which have a narrow structure to be
CPFP'd trivially by either counterparty, irrespective of what the other counterparty does! In order to meet this
structure, the commitment transaction (b) must have two (potentially-)additional outputs, each which only one side can
spend, and every other output must have a CSV lock associated with it. This is great and there is (finally) movement to
deploy this.

RBF Pinning HTLC Transactions (aka "Oh, wait, I can steal funds, how, now?")
=============================

You'll note that in the discussion of RBF pinning we were pretty broad, and that that discussion seems to in fact cover
our HTLC outputs, at least when spent via (3) or (4). It does, and in fact this is a pretty severe issue in today's
lightning protocol [2]. A lightning counterparty (C, who received the HTLC from B, who received it from A) today could,
if B broadcasts the commitment transaction, spend an HTLC using the preimage with a low-fee, RBF-disabled transaction.
After a few blocks, A could claim the HTLC from B via the timeout mechanism, and then after a few days, C could get the
HTLC-claiming transaction mined via some out-of-band agreement with a small miner. This leaves B short the HTLC value.

You'll note that B would be just fine if they had a way to safely monitor the global mempool, and while this seems like
a prudent mitigation for lightning implementations to deploy today, it is itself a quagmire of complexity, especially
when you consider differences in relay policy during an upgrade cycle and how those may effect propagation through the
P2P network. Further, this is a really obnoxious assumption to hoist onto lightning nodes - having an active full node
with an in-sync mempool is a lot more CPU, bandwidth, and complexity than most lightning users were expecting to face.

It seems highly likely we could come up with some kind of variant of of the RBF Carve-Out to solve this problem, though
probably much more specific to this particular transaction structure - imagine a rule which allowed B to RBF C's low-fee
HTLC claim transaction, without ever seeing it. This could be accomplished by locking down the transaction types in (3)
and (4) by pre-signing them (just, like (1) and (2)) and then using some kind of policy rule to allow only the addition
of additional confirmed inputs and one (small) output. This would mean that B knows that either C's transaction has high
fee, or B's reasonably-higher-fee transaction will meet the RBF rules and replace C's maliciousness.

While the original RBF Carve-Out was a little awkward, its structure was sufficiently generic that other off-chain
protocols could reasonably (need to) take advantage of it, however a rule to address this issue seems like it would need
to be highly tailored to lightning, which doesn't seem acceptable (there appears to be a way to shoehorn the existing
carve-out, but it results in a ton of extra on-chain volume).

Strategies involving full-RBF for transactions not at the top of the mempool, (slow-)full-mempool-sync allowing
mempool-total-fee decreases and relaxations of the RBF rules would be welcome, but without a ton of legwork to include
things like package relay I'm not convinced they would suffice. This of course doesn't even account for the possibility
of similar issues given rely policy differences.

PS For Lightning-Dev Folks (aka "An Alternative Anchor Proposal")
==========================

Given the anchor outputs proposal seeks to expand lightning's security in a world where Bitcoin is running at
steady-state and the mempool reliably has transactions in it, not fixing this issue seems to render the whole exercise
somewhat useless (not to mention that the current design makes this attack more obvious and provides several alternative
paths to exploitation).

An alternative, albeit not ideal anchor outputs proposal is as follows:

 * Instead of making the HTLC output spending more free-form with SIGHASH_ANYONECAN_PAY|SIGHASH_SINGLE, we clearly need
   to go the other direction - all HTLC output spends need to be pre-signed.
 * Sadly, and this really hurts from an on-chain-tx-size perspective, we have to include anchor outputs in the HTLC
   transactions (intuitively I think all of them, but at least HTLC-fulfilling transactions definitely).
 * Our poor B, being exploited, above, will attempt to spend their anchor output with a CPFP even if they aren't sure C
   has broadcast the HTLC-Success transaction! This is fine as B already knows the txid, and just wants to learn whats
   in the witness (assuming there is one).

For those from bitcoin-dev still reading who are thinking "blah, you clearly don't need anything else, you have a
solution!" we're talking about extra outputs out the wazoo for hopefully-unnecessary edge cases involving transactions
entering the mempool which a user wants to avoid confirming! This severely cuts into the lowest-value HTLCs which can be
sent "safely" and adds a significant social cost of extra low-value, possibly-uneconomical outputs in the chain.

Still, lacking a better idea, and with a strong desire to make lightning's security more practical in a world where
Bitcoin miners are paid to operate, we should probably start considering moving forward with this.

Thanks for reading,
Matt

[1] https://github.com/lightningnetwork/lightning-rfc/pull/688

[2] I'll note that while it is a "severe issue", given the general issues with fee-prediction described in background 3,
its pretty hard to argue its really in the scope of the security model of lightning today. If there were an easy fix to
it, we'd have deployed it by now in response to private discussion, but, sadly, there is not.


^ permalink raw reply	[flat|nested] 26+ messages in thread
end of thread, other threads:[~2020-06-24  8:39 UTC | newest]

Thread overview: 26+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-04-22 22:53 [bitcoin-dev] RBF Pinning with Counterparties and Competing Interest Matt Corallo
2020-04-23  9:59 ` David A. Harding
2020-04-23 12:52   ` [bitcoin-dev] [Lightning-dev] " ZmnSCPxj
  -- strict thread matches above, loose matches on Subject: below --
2020-04-22 23:13 [bitcoin-dev] " Olaoluwa Osuntokun
2020-04-22 23:20 ` Matt Corallo
2020-04-22 23:27   ` Olaoluwa Osuntokun
2020-04-23  1:10     ` Matt Corallo
2020-04-23  4:50       ` [bitcoin-dev] [Lightning-dev] " ZmnSCPxj
2020-04-23  6:21         ` Matt Corallo
2020-04-23 12:46           ` ZmnSCPxj
2020-04-23 22:47             ` Matt Corallo
2020-06-19  7:44               ` Bastien TEINTURIER
2020-06-19 19:58                 ` David A. Harding
2020-06-19 20:52                   ` David A. Harding
2020-06-20  8:54                     ` Bastien TEINTURIER
2020-06-20 10:36                       ` David A. Harding
2020-06-20 16:01                         ` ZmnSCPxj
2020-06-21  2:10                           ` ZmnSCPxj
2020-06-22  7:35                         ` Bastien TEINTURIER
2020-06-22  8:15                           ` ZmnSCPxj
2020-06-22  8:25                             ` Bastien TEINTURIER
2020-06-24  8:32                               ` Matt Corallo
2020-04-21  2:43 [bitcoin-dev] " Matt Corallo
2020-04-22  4:12 ` [bitcoin-dev] [Lightning-dev] " ZmnSCPxj
2020-04-22  4:18   ` Olaoluwa Osuntokun
2020-04-22  6:08     ` ZmnSCPxj
2020-04-22  8:01       ` Antoine Riard
2020-04-22  8:55         ` Bastien TEINTURIER
2020-04-22 23:05       ` Olaoluwa Osuntokun
2020-04-22 23:11         ` Olaoluwa Osuntokun
2020-04-22 16:56   ` Matt Corallo

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox