Introduce a maximum size for locators. #13907

1. 
   gmaxwell commented at 9:11 PM on August 7, 2018: contributor

   The largest sensible size for a locator is log in the number of blocks. But, as noted by Coinr8d on BCT a maximum size message could encode a hundred thousand locators. If height were used to limit the messages that could open new attacks where peers on long low diff forks would get disconnected and end up stuck.

   Ideally, nodes first first learn to limit the size of locators they send before limiting what would be processed, but common implementations back off with an exponent of 2 and have an implicit limit of 2^32 blocks, so they already cannot produce locators over some size.

   Locators are cheap to process so allowing a few more is harmless, so this sets the maximum to 64-- which is enough for blockchains with 2^64 blocks before the get overhead starts increasing.

2. 
   gmaxwell commented at 9:14 PM on August 7, 2018: contributor

   Evoskuil is of the belief that some bitcoinj nodes were sending locators of size 100. If so, I'll probably suggest that we just increase this number to 100 to accommodate them rather than delay putting in a limit just to get a somewhat tighter one.

   I'd be thankful if some people with lots of inbound connections could run this with net logging and report back if anyone is getting disconnected and with what sizes.

3. MarcoFalke added this to the milestone 0.18.0 on Aug 7, 2018
4. MarcoFalke removed this from the milestone 0.18.0 on Aug 7, 2018
5. fanquake added the label P2P on Aug 7, 2018
6. in src/net_processing.cpp:2023 in 65d92ad20d outdated

   2017 | @@ -2018,6 +2018,12 @@ bool static ProcessMessage(CNode* pfrom, const std::string& strCommand, CDataStr
   2018 |          uint256 hashStop;
   2019 |          vRecv >> locator >> hashStop;
   2020 |  
   2021 | +        if (locator.vHave.size() > MAX_LOCATOR_SZ) {
   2022 | +            LogPrint(BCLog::NET, "getblocks locator size %lld > %d, disconnect peer=%d\n", locator.vHave.size(), MAX_LOCATOR_SZ, pfrom->GetId());
   2023 | +            pfrom->fDisconnect = true;
   

   ---

   ---

   

   domob1812 commented at 6:58 AM on August 8, 2018:

   Is there a specific reason why you use fDisconnect here, rather than Misbehaving as in many other places around here? If there is, perhaps adding a comment would be helpful to future readers of the code (it would certainly be useful to me right now).

   ---

   

   gmaxwell commented at 1:39 PM on August 8, 2018:

   Because I don't see any particular reason to ban the peer. We only need to disconnect rather than just ignoring the message because the peer might be counting on our response and ignoring it could make it get stuck when otherwise it might make progress with someone else.

   We similarly disconnect for some messges when OutboundTargetReached, when we're limited and someone requests a block before the limited horizon, when the peer requests BIP37 services that we're not offering, etc.

   ---

   

   domob1812 commented at 6:08 AM on August 10, 2018:

   Makes sense, thanks for the clarification!

7. laanwj added this to the milestone 0.17.0 on Aug 8, 2018
8. 
   laanwj commented at 7:56 AM on August 8, 2018: member

   utACK, looks like a good (and straightforward) precaution to me

9. in src/net_processing.cpp:2021 in 65d92ad20d outdated

   2017 | @@ -2018,6 +2018,12 @@ bool static ProcessMessage(CNode* pfrom, const std::string& strCommand, CDataStr
   2018 |          uint256 hashStop;
   2019 |          vRecv >> locator >> hashStop;
   2020 |  
   2021 | +        if (locator.vHave.size() > MAX_LOCATOR_SZ) {
   

   ---

   ---

   

   MarcoFalke commented at 2:58 PM on August 8, 2018:

   Note that your BIP says: "A locator included in a getblock or getheaders message may include no more than 64 hashes, including the final hash_stop hash", so unless I am mistaken, the > should be replaced with a >=?

   ---

   

   gmaxwell commented at 5:51 PM on August 8, 2018:

   Yes, if we end up following the BIP. I'm giving it about equal odds that we need to use a threshold higher than the BIP for now, after we see whats showing up on the network.

10. 
    MarcoFalke commented at 3:00 PM on August 8, 2018: member

    utACK 65d92ad20d153d2525e978dc9622d38b2b6dfa25 beside my question if this should be implemented according to the BIP draft at https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-August/016285.html

11. 
    jnewbery commented at 5:46 PM on August 8, 2018: member

    Seems reasonable. Tested ACK 65d92ad20d153d2525e978dc9622d38b2b6dfa25 (just tested the getheaders logic). Functional test here: https://github.com/jnewbery/bitcoin/tree/pr13907.1 (commit https://github.com/jnewbery/bitcoin/commit/377b1a6af4b1ad7d23e3185930d8fe3d664393dc)

12. 
    MarcoFalke commented at 7:27 PM on August 8, 2018: member

    @jnewbery FYI I have also written a test this morning, that additionally covers the case of blocks as well as a positive and negative test outcome: 917fb38397

13. 
    jnewbery commented at 8:17 PM on August 8, 2018: member

    @MarcoFalke - your test looks great. I've left a few comments on there. Once those are addressed, @gmaxwell should add your commit to this PR.

14. Introduce a maximum size for locators.

    The largest sensible size for a locator is log in the number of blocks.
     But, as noted by Coinr8d on BCT a maximum size message could encode a
     hundred thousand locators.  If height were used to limit the messages
     that could open new attacks where peers on long low diff forks would
     get disconnected and end up stuck.
    
    Ideally, nodes first first learn to limit the size of locators they
     send before limiting what would be processed, but common implementations
     back off with an exponent of 2 and have an implicit limit of 2^32
     blocks, so they already cannot produce locators over some size.
    
    This sets the limit to an absurdly high amount of 101 in order to
     maximize compatibility with existing software.

    e254ff5d53
15. 
    gmaxwell commented at 8:59 PM on August 9, 2018: contributor

    Sipa's observations show that there is software using 101, so I've updated to that size. The larger locators are stupid and pointless, but the harm in permitting them is negligible.

16. gmaxwell renamed this:
    Introduce a maximum size of 64 for locators.
    Introduce a maximum size for locators.
    on Aug 9, 2018
17. 
    achow101 commented at 9:11 PM on August 9, 2018: member

    utACK e254ff5d53b79bee29203b965fca572f218bff54

18. 
    DrahtBot commented at 10:54 PM on August 9, 2018: member

    <!--e57a25ab6845829454e8d69fc972939a-->Note to reviewers: This pull request conflicts with the following ones:

    • #13915 ([qa] Add test for max number of entries in locator by MarcoFalke)

    If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

19. 
    MarcoFalke commented at 1:56 AM on August 10, 2018: member

    re-utACK e254ff5d53b79bee29203b965fca572f218bff54 (Only change is 64->101)

20. 
    sdaftuar commented at 5:37 PM on August 10, 2018: member

    utACK

21. 
    laanwj commented at 5:52 PM on August 10, 2018: member

    utACK e254ff5d53b79bee29203b965fca572f218bff54

22. laanwj merged this on Aug 10, 2018
23. laanwj closed this on Aug 10, 2018

    ---

24. laanwj referenced this in commit 48bf8ff5b1 on Aug 10, 2018
25. MarcoFalke referenced this in commit a04888a075 on Aug 11, 2018
26. 
    AliAshrafD commented at 2:17 PM on August 12, 2018: none

    Actually the maximum number of supplied hashes for the current network height could exceed 190 as the algorithm produces 10*log2(nChainHeight), as it has been discussed earlier in btctalk thread.

    Plus, to avoid playing with this constant every few months, a safe_threshold has been suggested to be added, for the main chain height to become two times larger, like a decade later, this number would be 200.

    So, I suggest 200 for this constant, given we are ok to revise this number every 1-2 years.

27. 
    AliAshrafD commented at 9:18 AM on August 13, 2018: none

    Above 10*log2(n) is an upper bound. The algorithm generates less hashes for smaller heights, e.g. for a chain with 10 blocks we get 10 hashes instead of 34 but for 1,000,000 blocks it is 160 which is much closer to 200.

    Any way, for current height we need 150 hashes in block locator to represent the active chain.

28. 
    gmaxwell commented at 3:39 PM on August 13, 2018: contributor

    It does not produce 10*log2(n), https://github.com/bitcoin/bitcoin/blob/master/src/chain.cpp#L30. Cheers.

29. sipa added the label Needs release notes on Aug 14, 2018
30. 
    AliAshrafD commented at 4:05 PM on August 14, 2018: none

    I just checked. Right! It is 10+log2(n), Now 101 seems to be TOO large, Anyway, I'm trying to establish a boundary for the actual chain height, as an independent issue. Given it is possible, any Idea about a possible application for such a boundary? After all this BIP sets a boundary of 2^90 already, I'm thinking of a more accurate, time dependent boundary.

31. 
    sipa commented at 4:07 PM on August 14, 2018: member

    @AliAshrafD 101 was chosen here because we observed other implementations producing such large locators, and there is little reason to break compatibility.

32. 
    AliAshrafD commented at 4:19 PM on August 14, 2018: none

    @sipa Although I'v not checked how bitcoinj reaches 100, no matter 40 or 101 or even 200 as long we are talking about locator issue. I'm just mentioning a more general problem: How large block chain can be at any given time? asking about any ideas about the possible applications of a hypothetical solution .

33. 
    sipa commented at 4:27 PM on August 14, 2018: member

    @AliAshrafD That's a very interesting theoretical question, but it seems completely off topic here.

34. 
    AliAshrafD commented at 4:34 PM on August 14, 2018: none

    @sipa Well not completely off topic. By setting MAX_LOCATOR_SZ = 101, we are putting a cap on the maximum block height to be 2^90 forever, Aren't we? Still, I admit it is good enough for the problem of interest ;) just asking for other max-chain-height related issues if any.

35. 
    achow101 commented at 6:24 PM on August 14, 2018: member

    @AliAshrafD No, this is not a consensus rule, this is only relay. The limit can be changed in the future with some smart behavior as to know how large of locators a node can support (a new protocol version would probably be needed in that case). Perhaps there should be some check to make sure the maximum locator size is not exceeded. If it is, more message can just be sent.

36. 
    sipa commented at 6:27 PM on August 14, 2018: member

    Also, 2⁹⁰ blocks is enough for 1.8 trillion times the age of the universe. I think we'll be fine.

37. 
    AliAshrafD commented at 11:12 AM on August 16, 2018: none

    @ahow101 , @sipa I understand the block locator problem is solved, just curious about other max-chain-height related issues. I just published my work regarding this issue on btctalk, you are welcome to make any comments there. Thank you. https://bitcointalk.org/index.php?topic=4905698.msg44176636#msg44176636

38. jnewbery locked this on Aug 16, 2018
39. 
    jnewbery commented at 11:22 AM on August 16, 2018: member

    Locking this since it's wandered off. Thanks to all for your comments!

40. fanquake removed the label Needs release note on Mar 20, 2019

Contributors

gmaxwelldomob1812laanwjMarcoFalkejnewberyachow101DrahtBotsdaftuarAliAshrafDsipa

Milestone
0.17.0