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"
Subject: Re: [bitcoin-dev] Capping the size of locators [trivial protocol
 change BIP]
Precedence: list

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--