From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id EB71DBCF for ; 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 ; Mon, 6 Aug 2018 05:29:34 +0000 (UTC) Received: by mail-pf1-f196.google.com with SMTP id x17-v6so6279599pfh.5 for ; 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 (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: From: Eric Voskuil 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: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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: In-Reply-To: --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--