Re: [bitcoin-dev] [Lightning-dev] CPFP Carve-Out for Fee-Prediction Issues in Contracting Applications (eg Lightning)

From: Jeremy <jlrubin@mit•edu>
To: Matt Corallo <lf-lists@mattcorallo•com>
Cc: Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>,
	lightning-dev <lightning-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] [Lightning-dev] CPFP Carve-Out for Fee-Prediction Issues in Contracting Applications (eg Lightning)
Date: Sun, 27 Oct 2019 12:13:09 -0700	[thread overview]
Message-ID: <CAD5xwhhK4xexDe=aBv78BsK5BvE=4S0OcqeXYHVAfN3wTOr51Q@mail.gmail.com> (raw)
In-Reply-To: <6728FF51-E378-4AED-99BA-ECB83688AA9C@mattcorallo.com>

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

Johan,

The issues with mempool limits for OP_SECURETHEBAG are related, but have
distinct solutions.

There are two main categories of mempool issues at stake. One is relay
cost, the other is mempool walking.

In terms of relay cost, if an ancestor can be replaced, it will invalidate
all it's children, meaning that no one paid for that broadcasting. This can
be fixed by appropriately assessing Replace By Fee update fees to
encapsulate all descendants, but there are some tricky edge cases that make
this non-obvious to do.

The other issue is walking the mempool -- many of the algorithms we use in
the mempool can be N log N or N^2 in the number of descendants. (simple
example: an input chain of length N to a fan out of N outputs that are all
spent, is O(N^2) to look up ancestors per-child, unless we're caching).

The other sort of walking issue is where the indegree or outdegree for a
transaction is high. Then when we are computing descendants or ancestors we
will need to visit it multiple times. To avoid re-expanding a node, we
currently cache it with a set. This uses O(N) extra memory and makes O(N
Log N) (we use std::set not unordered_set) comparisons.

I just opened a PR which should help with some of the walking issues by
allowing us to cheaply cache which nodes we've visited on a run. It makes a
lot of previously O(N log N) stuff O(N) and doesn't allocate as much new
memory. See: https://github.com/bitcoin/bitcoin/pull/17268.

Now, for OP_SECURETHEBAG we want a particular property that is very
different from with lightning htlcs (as is). We want that an unlimited
number of child OP_SECURETHEBAG txns may extend from a confirmed
OP_SECURETHEBAG, and then at the leaf nodes, we want the same rule as
lightning (one dangling unconfirmed to permit channels).

OP_SECURETHEBAG can help with the LN issue by putting all HTLCS into a tree
where they are individualized leaf nodes with a preceding CSV. Then, the
above fix would ensure each HTLC always has time to close properly as they
would have individualized lockpoints. This is desirable for some additional
reasons and not for others, but it should "work".

--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>

On Fri, Oct 25, 2019 at 10:31 AM Matt Corallo <lf-lists@mattcorallo•com>
wrote:

> I don’te see how? Let’s imagine Party A has two spendable outputs, now
> they stuff the package size on one of their spendable outlets until it is
> right at the limit, add one more on their other output (to meet the
> Carve-Out), and now Party B can’t do anything.
>
> On Oct 24, 2019, at 21:05, Johan Torås Halseth <johanth@gmail•com> wrote:
>
> 
> It essentially changes the rule to always allow CPFP-ing the commitment as
> long as there is an output available without any descendants. It changes
> the commitment from "you always need at least, and exactly, one non-CSV
> output per party. " to "you always need at least one non-CSV output per
> party. "
>
> I realize these limits are there for a reason though, but I'm wondering if
> could relax them. Also now that jeremyrubin has expressed problems with the
> current mempool limits.
>
> On Thu, Oct 24, 2019 at 11:25 PM Matt Corallo <lf-lists@mattcorallo•com>
> wrote:
>
>> I may be missing something, but I'm not sure how this changes anything?
>>
>> If you have a commitment transaction, you always need at least, and
>> exactly, one non-CSV output per party. The fact that there is a size
>> limitation on the transaction that spends for carve-out purposes only
>> effects how many other inputs/outputs you can add, but somehow I doubt
>> its ever going to be a large enough number to matter.
>>
>> Matt
>>
>> On 10/24/19 1:49 PM, Johan Torås Halseth wrote:
>> > Reviving this old thread now that the recently released RC for bitcoind
>> > 0.19 includes the above mentioned carve-out rule.
>> >
>> > In an attempt to pave the way for more robust CPFP of on-chain contracts
>> > (Lightning commitment transactions), the carve-out rule was added in
>> > https://github.com/bitcoin/bitcoin/pull/15681. However, having worked
>> on
>> > an implementation of a new commitment format for utilizing the Bring
>> > Your Own Fees strategy using CPFP, I’m wondering if the special case
>> > rule should have been relaxed a bit, to avoid the need for adding a 1
>> > CSV to all outputs (in case of Lightning this means HTLC scripts would
>> > need to be changed to add the CSV delay).
>> >
>> > Instead, what about letting the rule be
>> >
>> > The last transaction which is added to a package of dependent
>> > transactions in the mempool must:
>> >   * Have no more than one unconfirmed parent.
>> >
>> > This would of course allow adding a large transaction to each output of
>> > the unconfirmed parent, which in effect would allow an attacker to
>> > exceed the MAX_PACKAGE_VIRTUAL_SIZE limit in some cases. However, is
>> > this a problem with the current mempool acceptance code in bitcoind? I
>> > would imagine evicting transactions based on feerate when the max
>> > mempool size is met handles this, but I’m asking since it seems like
>> > there has been several changes to the acceptance code and eviction
>> > policy since the limit was first introduced.
>> >
>> > - Johan
>> >
>> >
>> > On Wed, Feb 13, 2019 at 6:57 AM Rusty Russell <rusty@rustcorp•com.au
>> > <mailto:rusty@rustcorp•com.au>> wrote:
>> >
>> >     Matt Corallo <lf-lists@mattcorallo•com
>> >     <mailto:lf-lists@mattcorallo•com>> writes:
>> >     >>> Thus, even if you imagine a steady-state mempool growth, unless
>> the
>> >     >>> "near the top of the mempool" criteria is "near the top of the
>> next
>> >     >>> block" (which is obviously *not* incentive-compatible)
>> >     >>
>> >     >> I was defining "top of mempool" as "in the first 4 MSipa", ie.
>> next
>> >     >> block, and assumed you'd only allow RBF if the old package wasn't
>> >     in the
>> >     >> top and the replacement would be.  That seems incentive
>> >     compatible; more
>> >     >> than the current scheme?
>> >     >
>> >     > My point was, because of block time variance, even that criteria
>> >     doesn't hold up. If you assume a steady flow of new transactions and
>> >     one or two blocks come in "late", suddenly "top 4MWeight" isn't
>> >     likely to get confirmed until a few blocks come in "early". Given
>> >     block variance within a 12 block window, this is a relatively likely
>> >     scenario.
>> >
>> >     [ Digging through old mail. ]
>> >
>> >     Doesn't really matter.  Lightning close algorithm would be:
>> >
>> >     1.  Give bitcoind unileratal close.
>> >     2.  Ask bitcoind what current expidited fee is (or survey your
>> mempool).
>> >     3.  Give bitcoind child "push" tx at that total feerate.
>> >     4.  If next block doesn't contain unilateral close tx, goto 2.
>> >
>> >     In this case, if you allow a simpified RBF where 'you can replace if
>> >     1. feerate is higher, 2. new tx is in first 4Msipa of mempool, 3.
>> >     old tx isnt',
>> >     it works.
>> >
>> >     It allows someone 100k of free tx spam, sure.  But it's simple.
>> >
>> >     We could further restrict it by marking the unilateral close
>> somehow to
>> >     say "gonna be pushed" and further limiting the child tx weight (say,
>> >     5kSipa?) in that case.
>> >
>> >     Cheers,
>> >     Rusty.
>> >     _______________________________________________
>> >     Lightning-dev mailing list
>> >     Lightning-dev@lists•linuxfoundation.org
>> >     <mailto:Lightning-dev@lists•linuxfoundation.org>
>> >     https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>> >
>>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>

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