Efficient synchronisation of nodes with rsync-like algorithm? #3754

Hi,

this is rather a wishlist/idea item than a real bug in Bitcoin. The nodes that I run receive about 99% of the same data that they have in the TXN cache anyways as the new hashed block. For increasing Bitcoins protocol efficiency, I heard about the idea to synchronize different nodes by just transmitting the first couple bytes of each hash in a block and then looking up the corresponding TXN in the cache.

Because there is so much redundancy between the TXN cache and the blocks, I wonder whether an even more efficient synchronization algorithm wouldn't be possible?

I am thinking about transmitting ranges in the TXN hash space, such as 'all TXNs from 1ab3... to 256c..., with resulting hash sum of 678cd651...' that would then be acknowledged or NAK'd by the receiving end. Maybe even going further and selecting transactions from the TXN cache by their fees or other, dynamic selection criteria?

Also, nodes could keep track of the transactions known to be seen by other nodes, to make it even more efficient.

Is such an idea planned or being implemented. Is it worthwhile?

64ffa93def3a829065841d16d9693acc474568bbb144a0189cadf4c968046299

IIRC, the first step that was proposed was to send along the full TXID list. That's already a big improvement on the current state of things (the entire transactions are in the blocks right now), while providing all the information needed to fetch whatever is missing.

As this is more of a theoretical-level brainstorming proposal for the protocol I think you'd have more success on the mailing list than here.

Requesting the TXID list for a block instead of receiving the entire block sounds like an optimization that could help reduce bandwidth up to 50% in case all the transactions were in the local mempool already. It would also possibly speed up the block propagation (less data is transferred BUT an extra roundtrip is needed). P2P protocol support would be needed to receive a list of individual transactions from a block to fill in the missing ones.

Not sure about your query idea of tracking transactions seen by other nodes, that sounds like a lot of extra complexity for little gain. P2P protocols gain from being as simple as possible to avoid complex failure chains and abuses.

This is essentially about finding the right balance between bandwidth usage and latency.

If you have very high bandwidth between nodes, but low latency, then you probably just want to send the entire block, as first sending the txid list and letting the peer query the wanted transactions introduces an extra roundtrip.

I actually experimented with using BIP37 for this purpose (request filtered blocks but with 100% filter), and it was both buggy and very slow. The problem was that the sender doesn't relay transactions again if it know they are already sent, but by the time the receiver requests a block, it may already have forgotten about them. The slowness was likely due to the per-block extra latency.

Keeping the P2P protocol simple is a good point. I am wondering whether there are any efforts that play around with different block transmission schemes?

Would it be possible to implement this in a more open way to be able to have the nodes configure for themselves the most efficient way to transport blocks and to have more experimentation? Like an interface to advertise 'block synchronization capabilities'? This way, people who want to try more experimental schemes of block synchronization could do so, while the main network is stable. High bandwidth nodes could simply clamp down all capabilities so that block synchronization happens just as it does now, whole blocks and no optimizations.

Or would you worry then that too many people 'become experimental' and the complexity would expose the network to a potential exploit/DDOS attack?

Along another line of thought, I am wondering whether it would be a good idea/feasible/wanted to have an interface into the code that would allow to safely query the TXN cache and other potential sources of information that could help in reducing network bandwidth (purely read only) - and have a single method to inject 'new block data'? The injected data would then be hashed and the block hash compared to the injection and that way, this 'block sync injection method' should not adversely affect the main functionality of bitcoin? To be really sure, the injection method could also be rate limited - so in the case that the block injection fails/the block injection network/client goes rogue etc. the main client would fall back onto its usual block transmission scheme.

I am thinking about something where one then could maybe even write something that is completely external to the main bitcoin client for block sync? Could the RPC interface be extended to allow that? Would it be a good idea?

@bc-cb : you mean initial block sync or optimizing the broadcasting of new blocks?

I did some thinking about optimizing new block broadcasts a few days ago: https://gist.github.com/gavinandresen/9603614

@gavinandresen: Oh, cool! So the main devs are working on it :-)

Yes, I meant broadcasting of new blocks. Initial block (re-)sync, I guess rsync etc. could be used? I was pondering about this for a while, due to the high impact on the orphan cost. I read and understood most of the Bitcoin code, but did not yet work on it, so my experience is quite limited - and I would like to know what's going on and what the sentiment is before even starting to even try to implement a patch.

Regarding the more efficient block broadcast: I was thinking about having a flexible scheme where adjacent nodes could potentially apply even more sophisticated selectors to the block transmission, such as 'collect all txns from aaabc.. up to cde345..' or 'all txns with fees in the range xxx ... yyy' or combinations thereof - a have a scheme with potentially multiple round trips.

Of course, this is a lot of complexity and might be completely unneeded and even detrimental to the stability or performance of the network, would it be supported by default. I am thus rather wondering whether it would be possible to have an extension mechanism (maybe through the RPC interface?) to allow bolting on (lets say maybe in an external python process) a 'block transmitter' onto the core client, that it could use with a fall back to the default, full-block transmission?

@bc-cb For initial sync, we only care about maximizing bandwidth (not latency), and there are no separately-relayed transactions to consider reusing (as they wouldn't be accepted anyway). That means that for initial sync, downloading full blocks is by far the best option - anything fancy will just complicate things without benefit.

For downloading new blocks, we really do care about latency as it impacts propagation speed across the network. The question about whether full blocks or something more fancy is better depends on the ratios of bandwidth, latency, block size, processing speed, .... See my comments on @gavinandresen's gist.

Closing, because I've started thinking the issues list shouldn't contain "it'd be nice if..." stuff.

Google search for all the recent discussion on IBLTs and Matt's fast relay code for current thinking.