Sounds really interesting, thanks. Making CPFP reliable would be very nice
in my opinion.

On Sat, May 29, 2021, 14:24 Antoine Riard via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Mark and Clara,
>
> Great research, thanks for it!
>
> Few questions out of mind after a first read.
>
> > This approach enables block building to consider Child Pays For Parent
> (CPFP) constellations.
>
> I think that's a really interesting point, it's likely that such
> transaction graphs with multiple disjunctive branches become far more
> regular in the future. One can think about OP_CTV's style
> congestion-tree, LN's splicing or chain of coinjoins. If this phenomenon
> happens, can you expect CSB feerate perf to improve ?
>
> > CSB is more complex and requires more computation
>
> Let's say a malicious miner identifies and connects to its competitors'
> mempools then starts to broadcast to them hard-to-traverse CPFP
> constellations. Doing so, this malicious miner would prevent them either
> from assembling block templates at all or slow down their assemblage
> computation enough to gain an advantage in fee collection. Following
> current mempools limits, it would be relevant to know by how much CSB makes
> that kind of DoS possible/efficient.
>
> > From the point of view of global blockspace demand, if miners generally
> became DPFA-sensitive,
> it could encourage creation of additional transactions for the sole
> purpose of bumping stuck ancestors.
>
> As ASB's ancestor set and CSB's candidate set, a fee bidder, we'll have to
> pay the feerate to cover the new transaction fields, high enough to catch
> up with the already-present feerate set ? Likely more feerate efficient to
> RBF the first child, though you have to swallow the replacement feerate
> penalty (default 1 sat/vbyte iirc)
>
> Antoine
>
> Le mar. 25 mai 2021 à 10:34, Murch via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> a écrit :
>
>> Hi Bitcoin Devs,
>>
>> We are writing to share with you a suggested improvement to the current
>> bitcoin core block building algorithm. In short, currently Bitcoin Core
>> uses a straightforward greedy algorithm which evaluates each
>> transaction’s effective fee rate in the context of its unconfirmed
>> ancestors. This overlooks situations in which multiple descendant
>> transactions could be grouped with their shared ancestors to form a more
>> attractive transaction set for block inclusion.
>>
>> For example, if we have 4 transactions A,B,C, and D, with fee rates and
>> weights as follows
>>
>> Tx Fee Weight
>> A    5    1
>> B   10    1
>> C   15    1
>> D   14    1
>>
>> And dependencies:
>> • B is a descendant of A
>> • C is a descendant of B
>> • D is a descendant of A
>> The current algorithm will consider {A,B,C} best which has an effective
>> fee rate of 10. Our suggested algorithm will also consider {A,B,C,D},
>> which has an effective fee rate of 11.
>>
>> Experimental data shows that our suggested algorithm did better on more
>> than 94% of blocks (99% for times of high congestion). We have also
>> compared the results to CBC and SAT Linear Programming solvers. The LP
>> solvers did slightly better, at the price of longer running times. Greg
>> Maxwell has also studied LP solvers in the past, and his results suggest
>> that better running times are possible.
>>
>> The full details are given in this document, and we are happy to hear
>> any comment, critic or suggestion!
>>
>> Best,
>> Mark and Clara
>>
>> Full details:
>>
>> https://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbfaf2#file-candidate-set-based-block-building-md
>>
>> Research Code:
>> https://github.com/Xekyo/blockbuilding
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>