 Show Posts
|
|
Pages: [1]
|
|
I'm sorry I was not yet able to provide the data. It would take me little more time to get to this again, but I can see Greg published a proposal and also implemented a fix that was already merged into bitcoin core. Thus it feels not so important any more to provide the data as the problem, if there was one, has been solved.
Thank you Greg for your time you put into this.
I will thus only try to provide the data later if someone requests it again.
|
|
|
|
|
One more thing why this is not equivalent of sending many small messages – when you send a lot of messages, you acquire the lock for very short time and then you release it so you are giving other threads a chance to do their work, whereas when I force you to grab the lock for a longer time, everyone else waiting for this lock is just waiting.
|
|
|
|
Looking up an entry is O(1) -- just a trivial hashing operation and one or two pointer chases.
So basically what you're saying is that you can make the node do a memory access per 32 bytes sent, but virtually any network message also does that. E.g. getblock <random number>.
Locators have no reason to be larger than O(log(blocks)), so indeed it's silly that you can send a big one... but I wouldn't expect it to be interesting. Alternatively, you could consider what is the difference between sending 100k at once vs 20 (a totally reasonable number) many times? Only a trivial amount of network overhead and perhaps a couple milliseconds of blocking other peers whos message handling would otherwise be interleaved. If you benchmark it and find out that its significantly slower per byte sent then other arbitrary messages I'd be interested to hear... but without a benchmark I don't find this interesting enough to check myself.
There are a billion and one things that are conjecturally slow, but most of them are not actually slow (and more than a few things that seem fast are actually slow). Anyone can speculate, testing is what is actually valuable.
Thank you for your reply, it sounds reasonable that you want to see the actual numbers, so eventually I will try to provide them. The reason why I am not looking at it is from the perspective of sending a large number of small messages is that I understand denial of service attacks as attacks which require spending significantly less resources on one side and significantly more on the other side, which I believe would not be the case in case of many small messages, because the attacker would need to send the message and the approximately the same amount of work would be done on the node's side plus a single operation such as lookup. So if the lookup itself is not significantly more expensive than sending the message (which I guess is actually the opposite), there is no great disproportion of the work of the attacker and the node. But in case of big block locator, the amount of work on the attacker side to prepare and send seems to be significantly lower than what needs to be done on the node side. And also the preparation of the block locator is amortised if the attacker just reuses the prepared block locator for sending multiple messages of same content. I expect the attacker to be able to construct a block locator smartly so that it takes much more than the average time to lookup each of the hashes in it. I will need to look into the actual implementation of the hash table in C++ to be able to find the bucket with most collisions and then probably finding couple of those big buckets to mess up little bit with CPU caches. This should give me the worst possible lookup times for each item. |
|
|
|
|
Bumping with hope that more people will check and either confirm or disprove.
|
|
|
|
|
Maybe also notably, Altcoins that forked out of bitcoin long time ago, may still have maximum size of the network message set to 32 MB, which makes the problem for them eight times worse.
|
|
|
|
|
Thanks for the review, I think I will wait for more people to check it out and confirm if this is valid before pushing it further. I'm also unaware of the absolute cost of a single hash table look up in C++. Still gut feeling is that hundred thousand of those can take some time and it seems completely unnecessary to allow locators to have more than a hundred of items.
|
|
|
|
Small correction. The limit of what a node replies to a GETHEADERS message can be found here - in net_processing.cpp: // we must use CBlocks, as CBlockHeaders won't include the 0x00 nTx count at the end
std::vector<CBlock> vHeaders;
int nLimit = MAX_HEADERS_RESULTS;
LogPrint(BCLog::NET, "getheaders %d to %s from peer=%d\n", (pindex ? pindex->nHeight : -1), hashStop.IsNull() ? "end" : hashStop.ToString(), pfrom->GetId());
for (; pindex; pindex = chainActive.Next(pindex))
{
vHeaders.push_back(pindex->GetBlockHeader());
if (--nLimit <= 0 || pindex->GetBlockHash() == hashStop)
break;
} You can request as much as you want, you will not get back more than MAX_HEADERS_RESULTS nor will the node process more than that. But this code is executed AFTER FindForkInGlobalIndex is called. I'm talking about FindForkInGlobalIndex itself. |
|
|
|
I'm trying to understand the getheaders protocol message and how bitcoin core operates when it receives one. FindForkInGlobalIndex is being called when the locator is present the message. This message seems to go through all hashes inside of the locator and make a hash table look up to see if we know the hash.
In the seem to me that an attacker can send us this protocol message with bogus hashes and the only limit I can see is the peer to peer network protocol message size limit of 4,000,000 bytes. This translates to roughly 125,000 hashes inside of the locator.
Therefore it seems that it is possible for the attacker to make us perform that many hash table look up operations while holding cs_main lock.
Is this really possible or am I missing something? If it is possible, is it not a denial service vector?
Not possible, you can only request 10 unconnecting headers announcements before a DOS limiter kicks in. The variable (static const int MAX_UNCONNECTING_HEADERS = 10) limiting this is hard coded in validation.h. Just do a "grep MAX_UNCONNECTING_HEADERS * -r" to see where the it's actually getting limited ... hint: in net_processing.cpp  Sorry, I fail to see that. The constant is used in ProcessHeadersMessage, which seems to have nothing to do with processing of getheaders protocol message (which starts on line 2029). |
|
|
|
Thanks for reply. I admit that my C++ is not very good, so I could be missing something or misreading something. However, I can't see what you say in the code. In primitives\block.h we have struct CBlockLocator
{
std::vector<uint256> vHave;
CBlockLocator() {}
explicit CBlockLocator(const std::vector<uint256>& vHaveIn) : vHave(vHaveIn) {}
ADD_SERIALIZE_METHODS;
template <typename Stream, typename Operation>
inline void SerializationOp(Stream& s, Operation ser_action) {
int nVersion = s.GetVersion();
if (!(s.GetType() & SER_GETHASH))
READWRITE(nVersion);
READWRITE(vHave);
}
So it seems there is no filtering on serialization - i.e. it looks like "what comes from network is going directly to the object instance". So if I read it correctly - if I send 100k hashes in locator, this object will be initialized with all of them. Then in validation.cpp we have CBlockIndex* FindForkInGlobalIndex(const CChain& chain, const CBlockLocator& locator)
{
AssertLockHeld(cs_main);
// Find the latest block common to locator and chain - we expect that
// locator.vHave is sorted descending by height.
for (const uint256& hash : locator.vHave) {
CBlockIndex* pindex = LookupBlockIndex(hash);
if (pindex) {
if (chain.Contains(pindex))
return pindex;
if (pindex->GetAncestor(chain.Height()) == chain.Tip()) {
return chain.Tip();
}
}
}
return chain.Genesis();
}
so that looks to me like we go through all of them and we do lookups and we only have further processing when it is found. What I don't see then is where this is implemented: because the client software doesn't check all the hashes exhaustively |
|
|
|
|
I'm trying to understand the getheaders protocol message and how bitcoin core operates when it receives one. FindForkInGlobalIndex is being called when the locator is present the message. This message seems to go through all hashes inside of the locator and make a hash table look up to see if we know the hash.
In the seem to me that an attacker can send us this protocol message with bogus hashes and the only limit I can see is the peer to peer network protocol message size limit of 4,000,000 bytes. This translates to roughly 125,000 hashes inside of the locator.
Therefore it seems that it is possible for the attacker to make us perform that many hash table look up operations while holding cs_main lock.
Is this really possible or am I missing something? If it is possible, is it not a denial service vector?
|
|
|
|
|
Yes, still looking. I will announce in this thread if I find one
|
|
|
|
|
Hello everyone,
I'm looking for a person who is passionate in blockchain technologies, understands bitcoin protocol, can read and write C#, and is able and passionate to write technical documentation with perfect English and lovely charts and schemas.
At first this is for one-time job, but a long-term cooperation is also possible if we like each other. You will need to be able to communicate in English in frequent video calls. You are create technical documentation directly related to blockchain protocols and crypto currencies related topics such as cryptography. You will also read code in C# maybe even write some code depending on your skills.
It is a bonus if you are familiar with bitcoin source code in C++, or if you can at least read C++ code.
If you're just a technical documentarist, the reward for your work will be up to a $50 equivalent in crypto currency per hour. If you are also a developer or if you can help with technical research, the reward can go easily over one bitcoin per month. Please note that writing the documentation is the topmost priority here, if you're just a developer, please do not apply.
In your application, please mention how many hours per week can you be available, right which country are you from, which languages do you speak on which level, estimate your develop skills in C#, estimate your blockchain technology knowledge, and let me know if you are looking just for a single job or a long term commitment. I will be happy to talk with you on Skype about this job in a short interview.
It would be great if you could present some of your past work - a code in C# and/or documentation or a White Paper that you wrote. Note that I'm not looking for designer but not expected to be able to create technical charts.
Please note that if you think bcash is a good project or a good idea, you don't need to apply.
|
|
|
|
|
