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
|
Return-Path: <eric@voskuil.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id EB71DBCF
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 6 Aug 2018 05:29:34 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pf1-f196.google.com (mail-pf1-f196.google.com
[209.85.210.196])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3AD001A0
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 6 Aug 2018 05:29:34 +0000 (UTC)
Received: by mail-pf1-f196.google.com with SMTP id x17-v6so6279599pfh.5
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 05 Aug 2018 22:29:34 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=voskuil-org.20150623.gappssmtp.com; s=20150623;
h=subject:to:references:from:openpgp:message-id:date:user-agent
:mime-version:in-reply-to;
bh=3P/vFJZPUVmM5PoKDbELbt+ecy9bOWBRPE6UOGGc53A=;
b=cXUbZa8JVGi2v9rQiAcKK+zFiZymGHQOAdmsMyy59tDOre8EeAVyLNTsxcJ3dcHxy+
GZQfxlq5DGczOdY0kRa3/m3bp7OEBPZypGXSUACynXTyhxWmHBkzrCGSnISjVcf1a3Xk
kCg9c+ODyzM3/kXaPaHWzS5eNzNJf+vJWaUs8BXLotYU8yuklX+ph090IG/mlnxithN2
4yKNiQ8MCN6hCWVVT2Zlio0U1Aidu27CJ/MdKU7Rk48f3EIKZdS+61Cmy8m/uHgLCoO5
dGxLC2ZDa0Ll1kRgzgbX6yLVwFCbleUG9Mr5fLH/sR5+Gd9FFULzKXH14qwk5QPu4jz2
aRrw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:subject:to:references:from:openpgp:message-id
:date:user-agent:mime-version:in-reply-to;
bh=3P/vFJZPUVmM5PoKDbELbt+ecy9bOWBRPE6UOGGc53A=;
b=WjwFwDqkV0t8FAyQrSAIpq3d9Zefcy+gw2zXBDGQS4oy1ZJdjt8UYFErYK804P8Y7R
+ByHREu/2iaQNybcMdGs8/BSzAabz1csXg/GZuKLdgp4EwBFAq/WcqU/nTsVY6XeY5Yw
hwLJn2k47aLuV73L7IlfNBsc/D3D9fTjBo/zppM2UzfqgpqfYz1c0GqIGntwagiT1keK
PbV5Zw9hqFOUlTNeykZQ2eNh4/QH+BuBwcBYXKhhf9f7iGUXe+O5XkBosLeF2Ebs+7Ga
NeeAGyhG/UDDsf/g947r7Y5VwN970o6kDlprKVRK8DQhPc2vZtIYim169tIdDHfp23zr
3XqA==
X-Gm-Message-State: AOUpUlGsq7vo8gfvRt75gxC69IhlpXYFEFp5QFgZOMGVETq3gD2dZvD0
g/LX+FXT/ICgniE+E+OAh4TarvVs3q8=
X-Google-Smtp-Source: AAOMgpePrjwf3g5x8xN+SIOmDCgBPlMv/D5lkoDXrsSYILVYTuZKk3W0HzBCW+n9J9UjrwzUROy49A==
X-Received: by 2002:a63:c902:: with SMTP id
o2-v6mr13157196pgg.118.1533533373584;
Sun, 05 Aug 2018 22:29:33 -0700 (PDT)
Received: from ?IPv6:2601:600:a080:16bb:95a7:7d39:1953:2516?
([2601:600:a080:16bb:95a7:7d39:1953:2516])
by smtp.gmail.com with ESMTPSA id
i7-v6sm10538531pgs.17.2018.08.05.22.29.32
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Sun, 05 Aug 2018 22:29:32 -0700 (PDT)
To: bitcoin-dev@lists.linuxfoundation.org
References: <CAAS2fgR=TvME_ps5oXYPeFJyjVZfaAtc=KQb5Ts2WQ4C2uO8+g@mail.gmail.com>
From: Eric Voskuil <eric@voskuil.org>
Openpgp: preference=signencrypt
Message-ID: <6fde4ed2-9b33-95b0-558f-145e43d3bc95@voskuil.org>
Date: Sun, 5 Aug 2018 22:29:31 -0700
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
Thunderbird/52.9.1
MIME-Version: 1.0
In-Reply-To: <CAAS2fgR=TvME_ps5oXYPeFJyjVZfaAtc=KQb5Ts2WQ4C2uO8+g@mail.gmail.com>
Content-Type: multipart/signed; micalg=pgp-sha1;
protocol="application/pgp-signature";
boundary="mmYNc7FQBi3VDpeW1goBFJO5oh5UcnWxY"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Mon, 06 Aug 2018 13:42:32 +0000
Subject: Re: [bitcoin-dev] Capping the size of locators [trivial protocol
change BIP]
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Mon, 06 Aug 2018 05:29:35 -0000
This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--mmYNc7FQBi3VDpeW1goBFJO5oh5UcnWxY
Content-Type: multipart/mixed; boundary="uerAoTbrz6I7WvtuEIvjTstQzvcWDQGV6";
protected-headers="v1"
From: Eric Voskuil <eric@voskuil.org>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <6fde4ed2-9b33-95b0-558f-145e43d3bc95@voskuil.org>
Subject: Re: [bitcoin-dev] Capping the size of locators [trivial protocol
change BIP]
References: <CAAS2fgR=TvME_ps5oXYPeFJyjVZfaAtc=KQb5Ts2WQ4C2uO8+g@mail.gmail.com>
In-Reply-To: <CAAS2fgR=TvME_ps5oXYPeFJyjVZfaAtc=KQb5Ts2WQ4C2uO8+g@mail.gmail.com>
--uerAoTbrz6I7WvtuEIvjTstQzvcWDQGV6
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: quoted-printable
Libbitcoin has implemented a 11 + log2(height) limit since version3 for
this reason. This message can be very costly if not constrained.
The presumed protocol inherently limits valid locator size for a given
recipient. IMO it's worth considering instead describing the expected
semantics of the message and thereby its *inherent* limits. Doing so
gives the recipient an upper bound on valid locator size, eliminating
the need to introduce an arbitrary limit.
I have commonly seen locators with 100 elements, I believe from
BitcoinJ. I recall posting a query on the issue to their IRC but got no
response. So it would seem that a quick survey and a limit of 64 would
not have prevented the issue of concern.
But in any case, I agree that implementations should enforce a limit.
e
On 08/05/2018 07:15 PM, Gregory Maxwell via bitcoin-dev wrote:
> Coinr8d posted on bct that the node software would process large
> locators limited only by the maximum message size yet sensible usage
> of locators only results in messages of log2(n_blocks) size. He was
> concerned that it might be a DOS vulnerability but quick measurements
> indicated to me that it likely wasn't worse than many other protocol
> messages. It still seems silly to allow absurd locators. So I propose
> that the size of locators be limited.
>=20
> However, capping them is a P2P change that could potentially result in
> network splits if older nodes would potentially produce larger
> locators (esp if triggered to produce unexpectedly large ones by
> forks). A quick survey of node software indicated that no software I
> could find would ever produce a locator with more than 42 hashes
> before encountering other limits, so I think a limit of 64 will be
> automatically compatible with all or virtually all nodes on the
> network.
>=20
> I'm bothering writing a BIP because there might be some naive
> implementation lurking out there that sends a crazy number due to
> sub-exponential backoff that would be broken by nodes enforcing a
> limit... particularly since the correct use of locators was never
> previously mandated and might not be obvious to all developers.
>=20
> I take the opportunity to also specify that the locators be correctly
> ordered in terms of total work, but don't specify that they all come
> from the same chain.
>=20
> Cheers,
>=20
> =3D=3DIntroduction=3D=3D
>=20
> =3D=3D=3DAbstract=3D=3D=3D
>=20
> This document proposes limiting the locator messages used in the getblo=
cks
> and getheaders to 64 entries and requiring that be ordered by total
> work.
>=20
> =3D=3D=3DCopyright=3D=3D=3D
>=20
> This document is licensed under the 2-clause BSD license.
>=20
> =3D=3DMotivation=3D=3D
>=20
> The Bitcoin P2P protocol uses a simple and efficient data structure
> to reconcile blockchains between nodes called a locator. A locator
> communicates a list of known hashes which allows a peer to find a
> recent common ancestor between the best chains on two nodes. By
> exponentially increasing the space between each entry, the locator
> allows a log() sized message to find the difference between two nodes
> with only a constant factor overhead.
>=20
> Because short forks are much more common than long forks the typical
> usage of the locator includes a small number of topmost hashes before
> switching to exponential spacing.
>=20
> The original Bitcoin implementation provided no explicit limit to the
> number of hashes in a locator message, allowing for absurd and
> wasteful uses like including
> all hashes in a chain.
>=20
> Although locators are very inexpensive for existing node software to
> process there is no known utility for sending very large locators.
> To reduce the worst case cost of processing a locator message it would
> be useful if the size of locator messages were strictly
> bounded to sensible levels.
>=20
> Common implementations have implicit limitations of 2^32 blocks and an
> exponent of 2 after the first 10 locators and so could never request
> more than 42 hashes in any case.
>=20
> =3D=3D Specification =3D=3D
>=20
> A locator included in a getblock or getheaders message may include no m=
ore
> than 64 hashes, including the final hash_stop hash. Additionally, the b=
locks
> referenced by the locator must be in order of equal or decreasing total=
> work.
>=20
> Sending a locator that violates these requirements may result in normal=
> processing, the message being ignored, a disconnection, or a ban.
>=20
> Implementations that seek to handle larger numbers of blocks than affor=
ded
> by this limit with an exponent of 2 can adaptively switch to a larger
> exponent as required to stay within the limit.
>=20
> =3D=3D Acknowledgements =3D=3D
>=20
> Thanks to Coinr8d on bitcointalk for pointing out that node software wo=
uld
> process and respond to locators with about 125,000 hashes in them.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>=20
--uerAoTbrz6I7WvtuEIvjTstQzvcWDQGV6--
--mmYNc7FQBi3VDpeW1goBFJO5oh5UcnWxY
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (GNU/Linux)
iQEcBAEBAgAGBQJbZ9y7AAoJEDzYwH8LXOFOkQAIAIqR5Nw7b7cff2BF6jJ132Ap
Dl6r67XOAdkDCgdQOeidxbOBdxCwPuPncfoPrtcKeZ4N38BVEh+1YxY9G9FDUOSY
TGyL2lX+gXJcG+7X5qKepzgQS0q6QPCj1EUz/zi4+/oHIvvNC6ok7/PJdwQ9Bs1A
ZKPPwcdelo9eKmOEOkPxLT3X9CQyLGtLHx7RbjeZ6oPh+3k1EVKeMoEeWKqMqYsm
HMZCdnn6KK7iRD4NMYuhRWCQQScnXhqLinGtDVIjvZl1mhNUdexboApF7XmE1Q2p
YacJpXSBdKe/uQ2hkr1MRBZU3bFmx7Ze+6jW4l0BOEy3k74yx+e8B6pOLijuuMs=
=TvFA
-----END PGP SIGNATURE-----
--mmYNc7FQBi3VDpeW1goBFJO5oh5UcnWxY--
|
