Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 6DB3DC0001 for ; 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 ; 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 ; 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 ; 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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--