Further work on thin blocks#109
Conversation
|
@jtoomim You did some testing with the original PR. Perhaps this work is of interest to you? |
|
That's an interesting idea, but I don't think the shuffling will work very well. Probabilities are not in your favor. If you're downloading from p peers, and you've downloaded n of m transactions from each peer, then the probability that no transaction is still missing from all peers' data streams is ((n/m)^(1/(p-1)))^(m-n). For n=900, m=1000, p=3, that evaluates to a 0.5% chance that you will have at least one copy of each transaction. You have a 50% chance of having all of the transactions when you've downloaded about 963 of 1000 transactions. Basically, this means you have to download the block around 2.889 times in the average case. Downloading from multiple peers would have some benefits, though. You would get the block when the fastest of the three peers finished uploading it to you. Given how chaotic the Great Firewall of China makes block transfers, this could be useful, as you don't always know which peer is going to have the best bandwidth. The testing I did of thin blocks showed them to be buggy, and it wasn't clear that it was saving any bandwidth or downloading them any faster. A failsafe hack I made for thin blocks can be found here: I added that hack because thin blocks would consistently and repeatedly fail on about 1% of block transfers. I think that the thin blocks patch I tested was actually downloading all of the transactions, and not just the transactions that are missing from the mempool. Matt Corallo thinks that this is due to some changes in how the bloom filters and merkle blocks work in recent versions of BitcoinXT/Core compared to the versions that were running around when most of BitcoinJ was written. I think that thin blocks are probably not worth the effort, since they might not be fixable, and even if they are fixable are far from optimal. Your idea of downloading from multiple peers sounds like you might find this interesting: http://toom.im/blocktorrent/ |
|
Still - yes, worst case is 3x download with 3 parallel downloads. Given that we’re fetching missing txs from 3 nodes that are equally fast and that our node does not have a downward bandwidth limitation, how much faster is downloading all txs in random order from 3 peers rather than downloading all txs from 1 peer? Anyway, worst case is the exception. In most cases we only need a single tx, the coinbase tx. Also the most common occurrence of worst case can be mitigated by not enabling thin blocks until the mempool has warmed up. As for the bug you hacked around, I’m interested to find a block that triggers this problem. Preferably a small one so I can put it into a unit test. Perhaps it can be detected before investing too much time in thin block download? My impression is that thin blocks can be made to work very well. We just need to discover and work around some corner cases. My main issue with the original patch was that it would sometimes request thin block from a very slow peer. This is mitigated now by requesting from several peers - and it works well. In my log file I see that the first node we ask a block from is often not the first to deliver. In some cases, the first one delivers it after we’ve already finished building it with help from the third node! I think blocktorrent is a great idea. |
|
According to my math, if all peers respond at the same speed (i.e. same latency, same bandwidth, and no random packet loss gumming up TCP), then the usual case will be very similar to the worst case.
In theory, and if thin blocks were working, yes. However, from my early testing, it seemed that thin blocks did not have the expected bandwidth savings over regular block transmission, and were instead sending all of the transactions instead of just the missing ones. Matt thinks that this is because the semantics of Bloom filters has changed. This also may have been an artifact of my test setup. Have you tested bandwidth usage of thin vs regular blocks yet? Here's the bug I ran into on testnet3: https://gist.github.com/jtoomim/4ac03b7713c4d1099337 Exception 'CDataStream::read(): end of data' It may depend on the contents of the mempool of the sender, the contents of the mempool of the recipient, the block itself, or some combination. I didn't look into it too much. |
|
I've run a node on the mainnet for 24 hours and collected data for 170 blocks. Here are the results: I think the results are promising. Perhaps more interesting:
This includes blocks from the start where the node had not had the time to warm up mempool. I did not check bandwidth usage. If your experience is that nodes are sending us a lot more txs then we need, then we could extend the protocol to only send us merkleblock + coinbase. We could then request the missing txs after, or request them from the next node to offer us the block. If this data is representative, only merklebloxk + coinebase would be enough in 8 out of 10 blocks. |
|
To gather the data I used this perl hack https://gist.github.com/dagurval/adb7f974f4ed8ddc0548 together with configuration debug=thin |
|
This looks much better than the data I collected. Kudos. An interesting hack might be to take the hash of the block, and if it's even (i.e. LSB == 0), use your thin block code, and if it's odd, use the standard MSG_BLOCK algorithm. That would give you good randomized A-B test data. You could also look at other bits in the hash to tweak other parameters, like the number of peers that you download from. |
|
If you submit a PR into https://github.com/jtoomim/bitcoinxt/tree/fortestnet, I will probably approve it and set it up for testing on testnet with 9 MB blocks. |
|
By the way, you can visualize the data that I collected on https://toom.im/blocktime. Raw logfiles are also available, though they're ... big. JSON statistics here: http://toom.im/files/result.json |
|
OK, I submitted a PR on your fork. That visualisation is great, it would be great if we could get this patch visualised like that. |
|
A critical change is needed to make this work. Thin blocks relies on With a single block containing multiple thousands of transactions, the set needs to be much bigger than that. I discovered this in November 2015 and mentioned it to the core project. They quickly changed the implementation of We need a size bump at a minimum, or to use the rolling bloom filter changes. |
|
Good find. I'll try to cherry pick the relevant commits into this PR. |
|
I've cherry picked the commits in those two PRs (in addition to some commits in bloom leading up to the PR). So now we have rolling bloom filter. I think the 50000 entries constant should probably grow with time, perhaps connectd to the blocksize - but that's for another PR. I have also pushed the commits into my PR on your fortestnet fork @jtoomim |
|
I put a breakpoint where the CDataStream::read() exception that @jtoomim experienced is thrown. It happens when looking up an transaction in relay map. Someone that has more knowledge of this code can perhaps give more insight? Is this a bug by itself? With regards to thin blocks, this exception can probably be caught and simply ignored in TxFinderImpl::operator(). |
|
By the way, I was doing some research on hard forks in altcoins, and I found something that looked oddly familiar: https://dashtalk.org/threads/v0-10-9-x-help-test-rc2-forking-issues.1009/page-2 (dashtalk.org's SSL certificate has expired; you may have to use an insecure browser like Safari to view the link.) This appears to have been a bug in some code that Darkcoin/DASH rolled out in a hard fork. The hard fork itself went okay, but the bug they had in the code caused the network to fragment for a few days, and most people weren't getting new blocks. That is very similar to what could happen with thin blocks if the CDataStream::read() exception isn't fixed. Of course, the same thing could happen if there were a bug in MSG_BLOCK. I think something like the failsafe hack I implemented for thin blocks is a good idea. The code paths need to try multiple transmission methods at least some of the time to avoid bugs like these blocking consensus detection. |
|
The exception does not happen in a critical place at all, as long as it is handled we don't need to switch to a failsafe mode. A fallback to a another transmission mode may be useful, but I want to see a real use case for it first. The CDataStream::read() should not be a problem now. On the thought of transmission modes, I'm wondering about what to do with Core nodes that are configured not to provide merkleblocks (yuck). I'm thinking perhaps there should be two types of thinblock configurations:
|
|
The stored serialized stream appears to be empty. Since the initial serialization is not part of this change, ignoring the error and behaving as though the relay map did not contain the tx seems fine. Other places where the stored stream is accessed are also protected by try/catch blocks. |
|
@dagurval Isn't that what the NODE_BLOOM service bit is for? If they don't support what our local node wants, we can connect to somebody else. |
|
@dgenr8 You're right. I now disconnect outgoing connections that don't support bloom filters. I needed the service bit and protocol version constants, so I also bumped the protocol version and added announcing of the NODE_BLOOM service bit. |
|
@dagurval Do you currently know of a reason not to merge this into a release for general testing? |
|
Yes, it lacks several features:
I'm also thinking we could delay this until Core 0.12 is released, then as people start upgrading, we'll have lots of node that fall within this criteria: If we request thin block only from these nodes, we'll know they have at least 50000 entries in their filterInventoryKnown and won't send us lots of txs we already have. |
|
Rebased. No longer includes cherry-picks:
|
db1b2b1 to
3a4d0cc
Compare
|
@dagurval Needs rebase. |
|
Is a merge OK? For what it's worth, I've been running this PR (before merge) for a few days without any problems. I'll continue testing with the merge. I know of no issues. |
For each 'bit' in the filter we really maintain 2 bits, which store either: 0: not set 1-3: set in generation N After (nElements / 2) insertions, we switch to a new generation, and wipe entries which already had the new generation number, effectively switching from the last 1.5 * nElements set to the last 1.0 * nElements set. This is 25% more space efficient than the previous implementation, and can (at peak) store 1.5 times the requested amount of history (though only 1.0 times the requested history is guaranteed). The existing unit tests should be sufficient.
Mruset setInventoryKnown was reduced to a remarkably small 1000 entries as a side effect of sendbuffer size reductions in 2012. This removes setInventoryKnown filtering from merkleBlock responses because false positives there are especially unattractive and also because I'm not sure if there aren't race conditions around the relay pool that would cause some transactions there to be suppressed. (Also, ProcessGetData was accessing setInventoryKnown without taking the required lock.)
Thin blocks are blocks downloaded using the Bloom filtering protocol, i.e. as lists of hashes rather than full block contents.
…hen -debug=relayperf is specified.
…in parallel. Check for bloom support. Handle more error and corner cases.
Also, unmark peer as having block in flight when switching blocks. Fixes bug where we would disconnect a peer for not providing a block that we knew it wasn't working on anymore.
|
ACK |
I’ve done some further work on @mikehearn's PR #91 . I have refactored some of the logic into its own class and added tests for it. I've also changed some of the networking logic.
The bandwidth aspect isn't what is most interesting to me, but the possibility of fetching new blocks faster is. With thin blocks we can fetch a block from multiple peers where we in most cases still will be using less or same bandwidth as before. So I've changed the logic so that a we fetch new thin blocks from the first few nodes who offer this. The nodes will then be racing to provide the merkleblock and help each other to fulfil the missing transactions. How many nodes we fetch from simultaneously can be set with -thin-blocks-max-parallel. For old behaviour set to 1.
I'm creating this PR to see -- is there any interest? I'd like help for testing and finding flaws. I've only done a little testing on my single node on testnet3.