[bitcoin-dev] Improvement on Blockbuilding

From: Murch <murch@murch•one>
To: bitcoin-dev@lists•linuxfoundation.org
Cc: clara@chaincode•com
Subject: [bitcoin-dev] Improvement on Blockbuilding
Date: Tue, 25 May 2021 10:27:06 -0400	[thread overview]
Message-ID: <25ab1452-78a8-90f1-9b47-8de050d632d2@murch.one> (raw)

[-- Attachment #1.1: Type: text/plain, Size: 1663 bytes --]

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

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]