Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Introduce a maximum size for locators. #13907

Merged
merged 1 commit into from Aug 10, 2018
Merged

Introduce a maximum size for locators. #13907

merged 1 commit into from Aug 10, 2018

Conversation

gmaxwell
Copy link
Contributor

@gmaxwell gmaxwell commented Aug 7, 2018

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.

@gmaxwell
Copy link
Contributor Author

gmaxwell commented Aug 7, 2018

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.

@maflcko maflcko modified the milestone: 0.18.0 Aug 7, 2018
@fanquake fanquake added the P2P label Aug 7, 2018
@@ -2018,6 +2018,12 @@ bool static ProcessMessage(CNode* pfrom, const std::string& strCommand, CDataStr
uint256 hashStop;
vRecv >> locator >> hashStop;

if (locator.vHave.size() > MAX_LOCATOR_SZ) {
LogPrint(BCLog::NET, "getblocks locator size %lld > %d, disconnect peer=%d\n", locator.vHave.size(), MAX_LOCATOR_SZ, pfrom->GetId());
pfrom->fDisconnect = true;
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Makes sense, thanks for the clarification!

@laanwj laanwj added this to the 0.17.0 milestone Aug 8, 2018
@laanwj
Copy link
Member

laanwj commented Aug 8, 2018

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

@@ -2018,6 +2018,12 @@ bool static ProcessMessage(CNode* pfrom, const std::string& strCommand, CDataStr
uint256 hashStop;
vRecv >> locator >> hashStop;

if (locator.vHave.size() > MAX_LOCATOR_SZ) {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

@maflcko
Copy link
Member

maflcko commented Aug 8, 2018

utACK 65d92ad 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

@jnewbery
Copy link
Contributor

jnewbery commented Aug 8, 2018

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

@maflcko
Copy link
Member

maflcko commented Aug 8, 2018

@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

@jnewbery
Copy link
Contributor

jnewbery commented Aug 8, 2018

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

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.
@gmaxwell
Copy link
Contributor Author

gmaxwell commented Aug 9, 2018

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.

@gmaxwell gmaxwell changed the title Introduce a maximum size of 64 for locators. Introduce a maximum size for locators. Aug 9, 2018
@achow101
Copy link
Member

achow101 commented Aug 9, 2018

utACK e254ff5

@DrahtBot
Copy link
Contributor

DrahtBot commented Aug 9, 2018

Note to reviewers: This pull request conflicts with the following ones:

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.

@maflcko
Copy link
Member

maflcko commented Aug 10, 2018

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

@sdaftuar
Copy link
Member

utACK

@laanwj
Copy link
Member

laanwj commented Aug 10, 2018

utACK e254ff5

@laanwj laanwj merged commit e254ff5 into bitcoin:master Aug 10, 2018
laanwj added a commit that referenced this pull request Aug 10, 2018
e254ff5 Introduce a maximum size for locators. (Gregory Maxwell)

Pull request description:

  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.

Tree-SHA512: da28df9c46c988980da861046c62e6e7f93d0eaab3083d32e408d1062f45c00316d5e1754127e808c1feb424fa8e00e5a91aea2cc3b80326b71c148696f7cdb3
maflcko pushed a commit that referenced this pull request Aug 11, 2018
fa85c98 qa: Add p2p_invalid_locator test (MarcoFalke)

Pull request description:

  Should not be merged *before* #13907

Tree-SHA512: a67ca407854c421ed20a184d0b0dc90085aed3e3431d9652a107fa3022244767e67f67e50449b7e95721f56906836b134615875f28a21e8a012eb22cfe6a66a5
@AliAshrafD
Copy link

AliAshrafD commented Aug 12, 2018

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.

@AliAshrafD
Copy link

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.

@gmaxwell
Copy link
Contributor Author

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

@AliAshrafD
Copy link

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.

@sipa
Copy link
Member

sipa commented Aug 14, 2018

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

@AliAshrafD
Copy link

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

@sipa
Copy link
Member

sipa commented Aug 14, 2018

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

@AliAshrafD
Copy link

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

@achow101
Copy link
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.

@sipa
Copy link
Member

sipa commented Aug 14, 2018

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

@AliAshrafD
Copy link

AliAshrafD commented Aug 16, 2018

@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

@bitcoin bitcoin locked as off-topic and limited conversation to collaborators Aug 16, 2018
@jnewbery
Copy link
Contributor

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

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet