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
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
|
Return-Path: <antoine.riard@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 4E626C0001
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 29 May 2021 06:33:08 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp3.osuosl.org (Postfix) with ESMTP id 34BFC60775
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 29 May 2021 06:33:08 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: 0.602
X-Spam-Level:
X-Spam-Status: No, score=0.602 tagged_above=-999 required=5
tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: smtp3.osuosl.org (amavisd-new);
dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp3.osuosl.org ([127.0.0.1])
by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id wuGDZ4kPfT4B
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 29 May 2021 06:33:07 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-wr1-x42a.google.com (mail-wr1-x42a.google.com
[IPv6:2a00:1450:4864:20::42a])
by smtp3.osuosl.org (Postfix) with ESMTPS id B4F32606C0
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 29 May 2021 06:33:06 +0000 (UTC)
Received: by mail-wr1-x42a.google.com with SMTP id x8so5300659wrq.9
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 28 May 2021 23:33:06 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc; bh=kPBZk3/l8XT3KbKIw9ViwaJgPs2EEAUion7L9Twkecs=;
b=BPz9nlc/l+XBRmsT5ZVqx3GgPKd4FkdcUoXV5eMk0ph1aztUfQcOTEQKJQpGeOTPUB
9/2Ir+hx3s77CAu36EtLopnHNhEqgqBH3mirfW8k+KFv/2DP1K3q4wJ9QIhkHM5GMAuO
jGqyOMT2hOKqKOkS6NCL9UWg7R05AjtKcxkmFp8AmHmM3sse1uciU/BF1IM2su6tDDIj
J31pjvJxUC2p/Ft86CSTACFWfCysN20/KHhTzw6Lud+TVqRBHbU81MWCtZ5AbBRY5oXW
BZ2HMwAId1pUmjx8RMzR0oQNda92hiVD7QnNoqhJbnoMTXf/NPJTswvYt4578mICbd9s
Y9BQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to:cc;
bh=kPBZk3/l8XT3KbKIw9ViwaJgPs2EEAUion7L9Twkecs=;
b=JhdCxXBPZ9WwH/snJzg5tYUqaxjcoYC/qy0Lb/qOVeUZtgYkf++HzK+azE+5N0GYkg
isoPioW0UpnrO1PFPNrBfPmc2lz+sEz/NVPtMRHR9htFEprFu9gMqQv0pYMo6Y+u6m0S
tl0ZeG7ybWqmQVoC9tMwawtd/l5ZgNu5rjSJCFSeMRv/JwSK4ERm6V6f4UALdw4iwzu4
6PvrSUaFfJJNx1d6KXVB0jiW8TVobxHWqKlZ+PtTySC0tZz6l+uE80fG4oC0J1BnR3kL
ZvhME32wNQn8E6GyZtv2X7v1AhB1Oe97ivyd0o445mf9V8t5gjHn9dOVezEf2F0ymqYx
R0xQ==
X-Gm-Message-State: AOAM530QLXINf8plvW/xfVKUw9WLphKEbuOWtQTw66O6tDHQIuBzU2MG
l53M+Fd1a9c3/wOSW50MITU1yD48gOBa5xxubU2gjSIN6bKlWA==
X-Google-Smtp-Source: ABdhPJz9tkE1xksiLQtbUVLgdDyxpupg59yLqGNLIPfkrr9EAyzzhYgJobFzqMJj1/PnW72v9kiMKUWZnoabzt4F8kA=
X-Received: by 2002:a05:6000:184a:: with SMTP id
c10mr12871600wri.244.1622269984892;
Fri, 28 May 2021 23:33:04 -0700 (PDT)
MIME-Version: 1.0
References: <25ab1452-78a8-90f1-9b47-8de050d632d2@murch.one>
In-Reply-To: <25ab1452-78a8-90f1-9b47-8de050d632d2@murch.one>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Sat, 29 May 2021 02:32:53 -0400
Message-ID: <CALZpt+Fj4=EiWSR1j65-ucwiTnwgVc-gvLuwaye3zNyApbuxFA@mail.gmail.com>
To: Murch <murch@murch.one>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000002deb8b05c3722afd"
X-Mailman-Approved-At: Sat, 29 May 2021 13:23:40 +0000
Cc: clara@chaincode.com
Subject: Re: [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: Sat, 29 May 2021 06:33:08 -0000
--0000000000002deb8b05c3722afd
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Hi Mark and Clara,
Great research, thanks for it!
Few questions out of mind after a first read.
> This approach enables block building to consider Child Pays For Parent
(CPFP) constellations.
I think that's a really interesting point, it's likely that such
transaction graphs with multiple disjunctive branches become far more
regular in the future. One can think about OP_CTV's style
congestion-tree, LN's splicing or chain of coinjoins. If this phenomenon
happens, can you expect CSB feerate perf to improve ?
> CSB is more complex and requires more computation
Let's say a malicious miner identifies and connects to its competitors'
mempools then starts to broadcast to them hard-to-traverse CPFP
constellations. Doing so, this malicious miner would prevent them either
from assembling block templates at all or slow down their assemblage
computation enough to gain an advantage in fee collection. Following
current mempools limits, it would be relevant to know by how much CSB makes
that kind of DoS possible/efficient.
> From the point of view of global blockspace demand, if miners generally
became DPFA-sensitive,
it could encourage creation of additional transactions for the sole purpose
of bumping stuck ancestors.
As ASB's ancestor set and CSB's candidate set, a fee bidder, we'll have to
pay the feerate to cover the new transaction fields, high enough to catch
up with the already-present feerate set ? Likely more feerate efficient to
RBF the first child, though you have to swallow the replacement feerate
penalty (default 1 sat/vbyte iirc)
Antoine
Le mar. 25 mai 2021 =C3=A0 10:34, Murch via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :
> 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
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--0000000000002deb8b05c3722afd
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Hi Mark and Clara,<br><br>Great research, thanks for it!<b=
r><br>Few questions out of mind after a first read.<br><br>> This approa=
ch enables block building to consider Child Pays For Parent (CPFP) constell=
ations.<br><br>I think that's a really interesting point, it's like=
ly that such transaction graphs with multiple disjunctive branches become f=
ar more regular in the future. One can think about OP_CTV's style<br>co=
ngestion-tree, LN's splicing or chain of coinjoins. If this phenomenon =
happens, can you expect CSB feerate perf to improve ?<br><br>> CSB is mo=
re complex and requires more computation <br><br>Let's say a malicious =
miner identifies and connects to its competitors' mempools then starts =
to broadcast to them hard-to-traverse CPFP constellations. Doing so, this m=
alicious miner would prevent them either from assembling block templates at=
all or slow down their assemblage computation enough to gain an advantage =
in fee collection. Following current mempools limits, it would be relevant =
to know by how much CSB makes that kind of DoS possible/efficient.<br><br>&=
gt; From the point of view of global blockspace demand, if miners generally=
became DPFA-sensitive,<br>it could encourage creation of additional transa=
ctions for the sole purpose of bumping stuck ancestors.<br><br>As ASB's=
ancestor set and CSB's candidate set, a fee bidder, we'll have to =
pay the feerate to cover the new transaction fields, high enough to catch u=
p with the already-present feerate set ? Likely more feerate efficient to R=
BF the first child, though you have to swallow the replacement feerate pena=
lty (default 1 sat/vbyte iirc)<br><br>Antoine<br></div><br><div class=3D"gm=
ail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0mar. 25 mai 2021 =
=C3=A0=C2=A010:34, Murch via bitcoin-dev <<a href=3D"mailto:bitcoin-dev@=
lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>> a =
=C3=A9crit=C2=A0:<br></div><blockquote class=3D"gmail_quote" style=3D"margi=
n:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex=
">Hi Bitcoin Devs,<br>
<br>
We are writing to share with you a suggested improvement to the current<br>
bitcoin core block building algorithm. In short, currently Bitcoin Core<br>
uses a straightforward greedy algorithm which evaluates each<br>
transaction=E2=80=99s effective fee rate in the context of its unconfirmed<=
br>
ancestors. This overlooks situations in which multiple descendant<br>
transactions could be grouped with their shared ancestors to form a more<br=
>
attractive transaction set for block inclusion.<br>
<br>
For example, if we have 4 transactions A,B,C, and D, with fee rates and<br>
weights as follows<br>
<br>
Tx Fee Weight<br>
A=C2=A0 =C2=A0 5=C2=A0 =C2=A0 1<br>
B=C2=A0 =C2=A010=C2=A0 =C2=A0 1<br>
C=C2=A0 =C2=A015=C2=A0 =C2=A0 1<br>
D=C2=A0 =C2=A014=C2=A0 =C2=A0 1<br>
<br>
And dependencies:<br>
=E2=80=A2 B is a descendant of A<br>
=E2=80=A2 C is a descendant of B<br>
=E2=80=A2 D is a descendant of A<br>
The current algorithm will consider {A,B,C} best which has an effective<br>
fee rate of 10. Our suggested algorithm will also consider {A,B,C,D},<br>
which has an effective fee rate of 11.<br>
<br>
Experimental data shows that our suggested algorithm did better on more<br>
than 94% of blocks (99% for times of high congestion). We have also<br>
compared the results to CBC and SAT Linear Programming solvers. The LP<br>
solvers did slightly better, at the price of longer running times. Greg<br>
Maxwell has also studied LP solvers in the past, and his results suggest<br=
>
that better running times are possible.<br>
<br>
The full details are given in this document, and we are happy to hear<br>
any comment, critic or suggestion!<br>
<br>
Best,<br>
Mark and Clara<br>
<br>
Full details:<br>
<a href=3D"https://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbfaf2#f=
ile-candidate-set-based-block-building-md" rel=3D"noreferrer" target=3D"_bl=
ank">https://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbfaf2#file-ca=
ndidate-set-based-block-building-md</a><br>
<br>
Research Code:<br>
<a href=3D"https://github.com/Xekyo/blockbuilding" rel=3D"noreferrer" targe=
t=3D"_blank">https://github.com/Xekyo/blockbuilding</a><br>
<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
--0000000000002deb8b05c3722afd--
|