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 E9E38DC5 for ; Mon, 6 Aug 2018 02:15:24 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ua0-f176.google.com (mail-ua0-f176.google.com [209.85.217.176]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6D5691A0 for ; Mon, 6 Aug 2018 02:15:24 +0000 (UTC) Received: by mail-ua0-f176.google.com with SMTP id w7-v6so10420341uan.9 for ; Sun, 05 Aug 2018 19:15:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:from:date:message-id:subject:to; bh=QScDwjF2pOW3i7Xsp9lKNik6YUNcKGNGXqZXBHup4RI=; b=iwRrZdepHBOSoxvqwFua9wzdHqf35JQa/MWPF5Q5ld55zTeRNfFke1ShdfkiWw3uz5 WcTK3dUAYSF4T3S9Czk0UKVfHb4xD862vYC2OoEPiUxun7IsullB8UHN1NYs0kHc7lT/ KlRGywZAc//BjCNmJwKMAMiJiaCqQo0n9BI5yZ3TDT1Y7IuZsQZZOjf0U0UVO0Kb/frM sqgWCIp7A0KUXV2oUQunHWViL1Mm+9Iz/IsCrg4Z3uo9u0Of3jA17LW5qEzePH3l2DDh oJr5MRPtzJruGlsM7TkpNAmrmJbdcfPnKMLNN9NU7htLy8VW7zp0GKu1CecNd3PzjeLj ooqQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:from:date:message-id:subject :to; bh=QScDwjF2pOW3i7Xsp9lKNik6YUNcKGNGXqZXBHup4RI=; b=R1ubY+7ulhcIL/eer7LLs6H/ZpymORqu9ki1IAcEtxrdbGjEduDBGSofLkgvka8OG6 SGxxUj6geF3FErjC9JV2pfkn+HZsmWlCZb2shRklZh95u1mGI/Tj42S82/nZHJHjAkgT TurkVGboaHcgsgfTmrf8ldMsNdK76bANAoZYxRBn5H/9RrhAOTER0HjXvJ11Z3bXy32/ lMpVIqqsvIzfN8jJifel1zSg3WeslbDpbLfrSBnMTj2MDTf6NvVeZnIqXLdK+EeclkSY NMjBDSaSa9UOg9XTqHl0n8xLV1NycAGDsk4O279LPZZ9WtuRF5OSu+hDOBh9RYKM2QRR mcpA== X-Gm-Message-State: AOUpUlEysRQZjRlJGw7C1EPnmq4Ci7lxptws0VAsgcU2hczbhIIxnTJU eMPJWp0Wlkgx5Xcgf8/TXb79IpBqqKz64aFG81ydE+1W X-Google-Smtp-Source: AAOMgpd8AJW7nP5KpGyicjFs5hnvrkPi9Lu1Yzau8PmX8qSgGH1wXpc6UyfmluZUCjuhlyXi7UC5Jwaa9zxHoKfHwEk= X-Received: by 2002:ab0:19c2:: with SMTP id r2-v6mr9148182uai.75.1533521723279; Sun, 05 Aug 2018 19:15:23 -0700 (PDT) MIME-Version: 1.0 Sender: gmaxwell@gmail.com Received: by 2002:a67:6c5:0:0:0:0:0 with HTTP; Sun, 5 Aug 2018 19:15:22 -0700 (PDT) From: Gregory Maxwell Date: Mon, 6 Aug 2018 02:15:22 +0000 X-Google-Sender-Auth: 2QCPNjLSPiMKGGWfg0FypFJrNbQ Message-ID: To: Bitcoin Dev Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, 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 Subject: [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 02:15:25 -0000 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.