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
>