đź“… Original date posted:2021-05-25
đź“ť Original message: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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20210525/6e8d2ba1/attachment.sig>;
Murch [ARCHIVE] /
npub148…ftkk4
2023-06-07 22:54:06
in reply to nevent1q…jvha
Author Public Key
npub148nv6ef02rzspkm4wszntt77m9k80plvtgaxwrg9amxch2cmge0qxftkk4Published at
2023-06-07 22:54:06Event JSON
{
"id": "f5febfcbbb1e2f9a02699288b592f15cac55ffe2862a66203a7006ee95df2c53",
"pubkey": "a9e6cd652f50c500db75740535afded96c7787ec5a3a670d05eecd8bab1b465e",
"created_at": 1686178446,
"kind": 1,
"tags": [
[
"e",
"9c9197103990b8dbfafd668ee8928a1d95368a445acb222938d299e777b530ef",
"",
"reply"
],
[
"p",
"a23dbf6c6cc83e14cc3df4e56cc71845f611908084cfe620e83e40c06ccdd3d0"
]
],
"content": "📅 Original date posted:2021-05-25\n📝 Original message:Hi Bitcoin Devs,\n\nWe are writing to share with you a suggested improvement to the current\nbitcoin core block building algorithm. In short, currently Bitcoin Core\nuses a straightforward greedy algorithm which evaluates each\ntransaction’s effective fee rate in the context of its unconfirmed\nancestors. This overlooks situations in which multiple descendant\ntransactions could be grouped with their shared ancestors to form a more\nattractive transaction set for block inclusion.\n\nFor example, if we have 4 transactions A,B,C, and D, with fee rates and\nweights as follows\n\nTx Fee Weight\nA 5 1\nB 10 1\nC 15 1\nD 14 1\n\nAnd dependencies:\n• B is a descendant of A\n• C is a descendant of B\n• D is a descendant of A\nThe current algorithm will consider {A,B,C} best which has an effective\nfee rate of 10. Our suggested algorithm will also consider {A,B,C,D},\nwhich has an effective fee rate of 11.\n\nExperimental data shows that our suggested algorithm did better on more\nthan 94% of blocks (99% for times of high congestion). We have also\ncompared the results to CBC and SAT Linear Programming solvers. The LP\nsolvers did slightly better, at the price of longer running times. Greg\nMaxwell has also studied LP solvers in the past, and his results suggest\nthat better running times are possible.\n\nThe full details are given in this document, and we are happy to hear\nany comment, critic or suggestion!\n\nBest,\nMark and Clara\n\nFull details:\nhttps://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbfaf2#file-candidate-set-based-block-building-md\n\nResearch Code:\nhttps://github.com/Xekyo/blockbuilding\n\n-------------- next part --------------\nA non-text attachment was scrubbed...\nName: signature.asc\nType: application/pgp-signature\nSize: 833 bytes\nDesc: OpenPGP digital signature\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20210525/6e8d2ba1/attachment.sig\u003e",
"sig": "85b039497f57bee98f2ddcee19d1d0954b448edc2c6525fd595d6d4a275ab6b8999b29c57aa3aabe06f20efc903fcb027c6f9e151e144e31920b895c36c6a468"
}