1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
Return-Path: <murch@murch.one>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138])
by lists.linuxfoundation.org (Postfix) with ESMTP id 6DB3DC0001
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 25 May 2021 14:34:04 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp1.osuosl.org (Postfix) with ESMTP id 5CB3E83C7F
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 25 May 2021 14:34:04 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: 0.802
X-Spam-Level:
X-Spam-Status: No, score=0.802 tagged_above=-999 required=5
tests=[BAYES_50=0.8, SPF_HELO_NONE=0.001, SPF_NONE=0.001]
autolearn=ham autolearn_force=no
Received: from smtp1.osuosl.org ([127.0.0.1])
by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id hTUUhgEsGyS8
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 25 May 2021 14:34:03 +0000 (UTC)
X-Greylist: delayed 00:06:40 by SQLgrey-1.8.0
Received: from farbauti.uberspace.de (farbauti.uberspace.de [185.26.156.235])
by smtp1.osuosl.org (Postfix) with ESMTPS id 9915383C44
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 25 May 2021 14:34:02 +0000 (UTC)
Received: (qmail 7984 invoked from network); 25 May 2021 14:27:18 -0000
Received: from localhost (HELO localhost) (127.0.0.1)
by farbauti.uberspace.de with SMTP; 25 May 2021 14:27:18 -0000
To: bitcoin-dev@lists.linuxfoundation.org
From: Murch <murch@murch.one>
Autocrypt: addr=murch@murch.one; keydata=
xsFNBFol4bABEACs1I2t7Z5/PBoRD+hMdg6uXcw3AfYuhRuhvDPo18PfJdiQ0CxKimcvkGIc
+tb7lvQ2vVzIuVDCj+6Jjx527arVXKsmzWYgOAPem8I8WICXhb67CsNrmAKN91UHTyay3+ao
WX1O3ZG3EodHAlEkJGMIE/+Ca0EfjDGmTXhGDzLxJB/0bE88h4Q3Rk3WshXjtzzgKrolW0+c
V+AYZ0XUY2L5zPxhIYccUFsD1p3AL0Ysiy6qpthVKQ+irbRW6HTZHHjit7uyfonESI02wp2Q
izqZf/VrQ1vlijqFxEuWhHsVbDgYrK4Ssx+lpmB2KD4PcswAeQ4torPb9q8ufz0Mof/ZwLIP
F4+LBVSi081T9IM7vUPcuTbwZPBqxBHWFHCeeaYlMpE5Od8/8rj4XyMMUSDlGtdKMQW2GdDI
ZcLF23gZ53unmegXqFdE1OytTvNyRBg6QwPFsbXUpLdJJE7mI9RQH8yTH1RCoRY1JLE0ko9H
iTGU+RsW4ApEvfFhnUJMP2vPxTfgqnSJ7WIRGL4nGicbqGyPlRAXHR15G38B0IzURY5GZIz+
meGSLoT06nUD7eSSJpuaNeMDxV7rq/eVcDjSmCN2AQ+DpsL1bIf+Ta+P6iNlorLH+gdFQN+w
eAfcaSKz4QjLyodmitqfGnN9vyitywSiofieNtwJnDUixiDkHwARAQABzRdNdXJjaCA8bXVy
Y2hAbXVyY2gub25lPsLBqwQTAQoAPgIbAQULCQgHAgYVCgkICwIEFgIDAQIeAQIXgBYhBIJF
bsJi0I1WfC8YR6z9uTqRddyrBQJffdldBQkHRloiACEJEKz9uTqRddyrFiEEgkVuwmLQjVZ8
LxhHrP25OpF13KsQjg/9EG5uM2xj/KW4nvkGcQUb3VPfqZ7nSifW/eeNk7dwlAJsTQK/h7HW
pLCx9ZTp60+pPXGfV198Ly2FWWnQIJNc3ey7jbi3lV/EYhdByTwsjmCYwTKnnNIfZovKLxfr
Ssiy4CxTGwGapwsI1Y/qdyxZC0QT/DoMtLhAKaJWbxAKvASySxAdbaL+ldSXm+bGw8cZ8ozL
qkfGie7nsgqN31jCD/2xQVHe322gHohVp1f2QFPZ96imaTs57wEHmtsfrFCNDVVqz3hDO8zI
YjAAnjoHSjm002EYbPEw/4LFCGjmLD7szhS1Fu9n4ZRr1nuydictfKaplOX/h4KrkKB94/ZH
ec8uZOUCCRf02C/+CPlEa5a/Q5hAC1wuSPiTgqrxzxa3zkB8GyUdtNLENW6AfOlAEHDNWdFH
ZWGfjlLw2k5w8Y+tPHKop4pjgmgur1H5jtpSmwDKpJ4RCEumAdW/lsz0iP5EiwNi9ub75Lww
wl/64PquP2G6rK9PhsHrJJuvUP15Mpa13msHHVk+bAQjzvkFQhqaiJSSgEZhSX5LOMBxV3oW
QyJIXeot38CgGRU/64gT33aC78saTzrn68ToGoiDQ0OZAh1I3bZrWhgjcn57QUeFodeGuqYi
4gi8aCe9KG6pH9KjBtwbyc/HOJXBEHyV4lLuRIav734dV2e5lpe7fP/OwU0EWiXingEQANyn
b+VH35bihNX8YJLws+wIJl6ZM5XPQDIYjxqkTnAXWtiOWiolHFz/4dvhATW8JKvPQqhK/5Zw
dzDeJRZUbtAO80eJCDaNziMpZxZNaKcRwRzaygYALn73UigVskTp7uX37oaaWLY9TmWoljoY
n495tKm0C/nfWmTgk0aCR+evCzlr1WjrgAP9dCwLwvrY73uAbdeLwpZ08eH5fdFjRKnkYoV9
mFQNqKaqrO0Gper871R+Xm3bq2L8iadhv8/10ubnpnjpfd5U2emy/6GkkO87JlzGZd8x4iYn
RX5ZmIq9f+nPCweZx5ioCNx7RPoYVMqzUANYHd6WvjN6I8vvmT87d95uDR67WpsoNQ40jMQ1
20JvsSm/hPJIzS/eoqb/dmLA83ZtN4/jdRCJkaBVrf8ofLGG4aPlplyexaZ1+ziWKFLaw2fd
bbMgA5r3qqvRWWwHdk3529wTs7B7NKKvxVgD4//EFktHc7OoBvmFpLnn0F1qHEv6U4xVsvx3
DUxu87BXrr6CEfgzD8rc5TY8Lh8Z+8dZdmwUmgNvLFPLkmEOR9EMkc2V6h4LTxZmubH5oQcw
LN9sMOsnSs4AI8Z2oF+1KEW+srWfaiNOLAqvlrlvkSXvAntYKXO7ktFq5sUoJUOYwsZg5RWr
Aguas+VDUvGl/x4/+eScDzaNpIm+YLrjABEBAAHCw+AEGAEKACYCGwIWIQSCRW7CYtCNVnwv
GEes/bk6kXXcqwUCX1w/1QUJB0W1NwJuCRCs/bk6kXXcq8GLIAQZAQoAHRYhBDX0raYj65/j
o7x+9nugNcpbkBcTBQJaJeKeACEJEHugNcpbkBcTFiEENfStpiPrn+OjvH72e6A1yluQFxNY
vQ/9HhFcU8GPekMESYgrbA+o4XXPHuSqhwWDFs2W0+MNoRnJrU/cyGn54xHV08+0bqKqJkZU
ktZckLONeRg8V4hCyFh0eR4Fy3L5cpYf2dIyZtu9X7ltPDb8OSoiqaSs+v1Vbo9+UtBhJWbH
SCSHOy6yZ713yHxei03/ibvd+6LZCUUHioNj5WNaSPJO3T4C36eGXAwhJ6LubhRxKs77K2i6
HCxZfHHJD3YaLS+NHmoNcqLitLaBB3TFQAgEyR0r/9EIsNemS3XOYa3lda68aQXpCKacrvbK
Aw74gXEYppB+NHETICkrr2qnebit01GdnMwfVfd4cCSxqXvGJjWO7/NP6XgGZGlJJzMggLWx
bHriefZoppAXHYO+hLiNg+AQeAS9h7kb0a06BqJhE2Wvt2iQWJsUsRaKX+KUUo7QoaNSb4gb
KtDrCfNHYgniXiz9XLOILoj2JbgD4LNc4+6cVM6Ys8mnOyNEaOyn7caiMhrMEVE6UjfJ4TYH
60AjXHdFln52OzLbWIcGuCagpQoAWrbcVLUVM5B5Oq2YCirQdARSPFFDATcDtjNWL4QkJDxm
J9CrzJs3j04wwvLPVOAwJuXCPvpvXYiRJ4gV+8VYdr3WfCXP1DVt/pmhjgvy2yefutTS6lKk
QDfDPVPFOPG9ab6ywQpZ6jMeVf0hEGjO4EYF7t8WIQSCRW7CYtCNVnwvGEes/bk6kXXcq/IC
D/47Bz9GzBsmggRkg6LxGwNe9yJ2RFQRDIAKjxWtLzP0OjrBGmAuhgu5ZlRgYG2QbjSOHIF7
uXVgSrTAZqH42FDHFUADbqY+tjiMhcC3P71U2onPUqrVk4T36kU+p1dx74yez6k1iyFLVaf/
u7y1wdQyUyN/eysqltHWiW8hWNhfqRiNkG6yW/+Z+39BNe2fBIsplk/EM6QTbfMrWWPbDUjK
wMAqfrNS3zbZGfCYcwlfBAYbPLO4BflZ1/NsAdZL4ESzADsfqL+2XLp7t0A4xDG/SmjbLYY+
x56ACAYASgW3kw4nhwY9pcvepKwe1pEI0t91uOc8mxBi7LRXPB8+qzvT2/NmeSnCW8JrRJfW
CzO7r1flgWLkt5ZvX/4hwpda+0cQ45UPFAlc+B+pzCGCZ2FhLIau3dxihdHOBd6WC1yoAp4l
C/AObltCqfLNA/NCVfxq7fKL3XWq10U9PyTQjHzeEm+AVI/YD0TaTB3b+USxAFHaHCSbCYPd
y4i4qRH6eCIDe7+nVGes+3rsKNcmt/qXP8nJAkgaHrvFqsmyQxUg8H/SfEZfR5qeOkTWQVG4
QaK7p80Ox/RYN2YlxFqPCkWF/DmNPVgoEoNWvHSdMXQUwyQUsrgVicw2/Rs5tZA+SL24n8mI
K9CFPjcfI6gCV0XyUEEOeVs3iko0cPiTcqkZQ87BTQRaJeLFARAAxS3lRM7evKZCvSSwcD6V
O9P37Zq2nZae0Xdy39Nkjlmvqi0Tx7E2lKUnNRJye1e6v/Cu9rwAiJBGQpoJL1WHPKAm78pN
uC1X2c0Dkk8agDV4nv79CoKw2roaMkQOiIAZ04niwK+OCYmyIpqDLiZBY96O3f0k47wMMpUh
gcnbASBjXvYR7CLJElnrUc2k9Jspwaw8lwAYll3Q2nUBN6ka6YkGGOB9oSBA1+akCeQ4rnA8
9eOFs8YKqndgsA8Hjr1HF6uZ1ssXPHW9ap0CNXOdZdD0l8FYCeCHjstaglgfNdF82CJ+MT4Z
CyUUJZPnZGBkTN0MPbAWtmqRmLCfMgd9VE85W1RW5MDX0xto89HhOtH9ryMzzlGCUTKkP+YP
I85c9219cuCWgQP6BslpXT53MWYqFf4QBZ2otqSHSM8m3PxfcGMbIcXJqSxCBnexBIMLxxJi
ZFYzN/isicZgaHEgBT2sqe1jQvFp4GAV/bIsUuLkU1HZqclUS+f42kTt3+kDNTJmO/v99MX/
8IREkfshc2KPGB75o5RP4WklhbwEimUyTUtx6h1EfKQm8hy8RbF4Digv/b4p2Bs+Qp7b2g3T
u7oSvdUo6PDJ5YU6dW2fugQLQYx/b7w/C9cI7Yw/fkWwFyO7Nr8vK4rwy1RxLRkCZyujkcby
mf6pCNmfDAh+oAEAEQEAAcLBkwQYAQoAJgIbDBYhBIJFbsJi0I1WfC8YR6z9uTqRddyrBQJf
XD/ZBQkHRbUQACEJEKz9uTqRddyrFiEEgkVuwmLQjVZ8LxhHrP25OpF13KvUqg//beWWxeGb
a7/VPym+a+RFBE2JZO+jzY/ASxdrDxO3fLVZDyhH+kyGK03Lphflo9q1E6tPD5zu/UwmJ6HE
efy2Yp40sxBrJy6Wlq/ZNPJCDcwdineAEVRHkyIN55lLGaxa6HyHUbg3dqG7YJRlYm4R58Z0
EGJoB1Nl7SZ6KpRvXAbafPrjlHXFtsPl0sXa02eSKrbvhhTTvu5JALwrN+290pLsmNbOTFFe
Tm3kfU2gYyNM9G9ZZJ0Ul3sZ2rmZCc0oFkPURoObq/qu+FHmRfgfGw7AU/6c8/AHIcA+NqbJ
aXlv8XuGr5SkzmIiOkRgW/6ztINCX0N0AzR47M6qyJNkIah5StPntMWWnv8WJIEuIjjb0adm
t1P9Qj3WSoh4ah2jlm1zCKkx432mQJG6cMTn0rqV30z8clDTyACSPfz1p7GbjeDN5YseUYSV
qJEq2YjrWP0LIXJZOHO5i8QTVf4kVwyzIW6fnAReYaToPHogqV0uB/gsRKN8OmyTQy3PqzkJ
6JrJHAS+FTUJdGhngrvfPltYQS80d1y6FF8OnWRdRbA3pTEWZaqoXXJ261VsP1U8CoLoP/RC
lF5cl1GWZPYw4delMX0gDc1L82Eg7J4++C40I2/FlLnKBZURVHltxUQh/5aEH7Ig2IdOLmyf
tDXvC72WMEBAtk8MrkM3e3dPg6E=
Message-ID: <25ab1452-78a8-90f1-9b47-8de050d632d2@murch.one>
Date: Tue, 25 May 2021 10:27:06 -0400
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
Thunderbird/68.10.0
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature";
boundary="QNBtipzX3w0P8SVnTdKRn2POWzVfjk6pW"
Cc: clara@chaincode.com
Subject: [bitcoin-dev] Improvement on Blockbuilding
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 25 May 2021 14:34:04 -0000
This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--QNBtipzX3w0P8SVnTdKRn2POWzVfjk6pW
Content-Type: multipart/mixed; boundary="iEp97cqTsUT4pazMjdS1IYGtZVlgv4aS0";
protected-headers="v1"
From: Murch <murch@murch.one>
To: bitcoin-dev@lists.linuxfoundation.org
Cc: clara@chaincode.com
Message-ID: <25ab1452-78a8-90f1-9b47-8de050d632d2@murch.one>
Subject: Improvement on Blockbuilding
--iEp97cqTsUT4pazMjdS1IYGtZVlgv4aS0
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: quoted-printable
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=E2=80=99s effective fee rate in the context of its unconfirme=
d
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:
=E2=80=A2 B is a descendant of A
=E2=80=A2 C is a descendant of B
=E2=80=A2 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-candi=
date-set-based-block-building-md
Research Code:
https://github.com/Xekyo/blockbuilding
--iEp97cqTsUT4pazMjdS1IYGtZVlgv4aS0--
--QNBtipzX3w0P8SVnTdKRn2POWzVfjk6pW
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQIzBAEBCAAdFiEENfStpiPrn+OjvH72e6A1yluQFxMFAmCtCUAACgkQe6A1yluQ
FxOe3A//TTTMY9fTSloAit4s0sLN8kYvkuBydWT56e8cY7wGJV7PltIV2Xy5Rt4K
A+2XVGh4xJjctg2W0mibysbP71LJ5RyTZ24PY03A5adLGr/TYtNRFLN7cjqpuayl
ht4B8N5xa6o8QBR3X6I99mr/Zif03syHk4vPOZ6Rx1dEd2GZhVwYGi/6oNJBTRfq
iFiPPliRX1Gk1uLLNwTUWzjjEwVt6fzKFIbLhvq464IH/VDsdDYndIhSqVItvMkg
Io6PfBcBZRjA1crQwzoNEzMf7dG2WfYc+bT2d8VgGHwqnSrcQz8EFh7cAmzUS5D+
xYYVM8WloFz7y6PL0XSnoAVERuLr0xnoUj9BIIw6k0rqd2bVtxdBG++k40R/JG3L
M7e5EJbbVJemtDIvqaibEXiijTuUUivhVK5ClRhK5jXKrYML49qlKBwOkpdihg3W
6cYhyGL81vLE99BdkhrineYnVDgIrHWQnKYiOMWB6JR/KonlVRA09Ld93W6H4AQq
rZBR7CprYNzeqjpF1pn+hqJpOK6LTXLLEdsRluCC0AB9zKlpE7NsBVwTC5/YYgV7
8HrhsWO3oCK10hC558C01oeXmAU/jdUy6o8Ca7mGtK5GC7rjXduFpo8NjR14QR3q
uzPV1jyBxIhYhq0r7CLWCuaGylFh+oQXDohN9KTvpm/7xvYZ27o=
=I6SY
-----END PGP SIGNATURE-----
--QNBtipzX3w0P8SVnTdKRn2POWzVfjk6pW--
|
