From: Gregory Maxwell <greg@xiph•org>
To: Bitcoin Dev <bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] Capping the size of locators [trivial protocol change BIP]
Date: Mon, 6 Aug 2018 02:15:22 +0000 [thread overview]
Message-ID: <CAAS2fgR=TvME_ps5oXYPeFJyjVZfaAtc=KQb5Ts2WQ4C2uO8+g@mail.gmail.com> (raw)
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.
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.
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.
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.
Cheers,
==Introduction==
===Abstract===
This document proposes limiting the locator messages used in the getblocks
and getheaders to 64 entries and requiring that be ordered by total
work.
===Copyright===
This document is licensed under the 2-clause BSD license.
==Motivation==
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.
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.
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.
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.
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.
== Specification ==
A locator included in a getblock or getheaders message may include no more
than 64 hashes, including the final hash_stop hash. Additionally, the blocks
referenced by the locator must be in order of equal or decreasing total
work.
Sending a locator that violates these requirements may result in normal
processing, the message being ignored, a disconnection, or a ban.
Implementations that seek to handle larger numbers of blocks than afforded
by this limit with an exponent of 2 can adaptively switch to a larger
exponent as required to stay within the limit.
== Acknowledgements ==
Thanks to Coinr8d on bitcointalk for pointing out that node software would
process and respond to locators with about 125,000 hashes in them.
next reply other threads:[~2018-08-06 2:15 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-08-06 2:15 Gregory Maxwell [this message]
2018-08-06 5:29 ` Eric Voskuil
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAAS2fgR=TvME_ps5oXYPeFJyjVZfaAtc=KQb5Ts2WQ4C2uO8+g@mail.gmail.com' \
--to=greg@xiph$(echo .)org \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox