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 --]
next reply other threads:[~2021-05-25 14:34 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-05-25 14:27 Murch [this message]
2021-05-29 6:32 ` Antoine Riard
2021-05-29 15:04 ` Jorge Timón
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=25ab1452-78a8-90f1-9b47-8de050d632d2@murch.one \
--to=murch@murch$(echo .)one \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=clara@chaincode$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox