BUIP010 (passed): Xtreme Thinblocks

[Peter Tschipper]

@solex @YarkoL

I've been able to successfully test using 64 bit transaction hashes so I updated this BUIP to include those changes with a re-branded name that I think is more interesting and applicable. I still have to add some handling in the code for hash collisions and test it out but so far I haven't seen any collisions and all looks well running this over night. I'll be testing today and then release an update to my repo tomorrow for anyone that wants to compile it and test it out.

 

[Peter Tschipper]

@solex @YarkoL @jtoomim @theZerg and everybody else.

Xtreme Thinblocks is ready. If you want to help to test or try it out you can grab the copy from my repo and add the following to your bicoin.conf so it will grab xthinblocks from my node that's already running. If you want to look up the nodes on https://bitnodes.21.co/ you can search by looking up the protocol version which is 80000.

connect-thinblock=96.54.102.88:8333
debug=thin

https://github.com/ptschip/bitcoin/tree/xthinblocks

@YarkoL I've switched my thinblock node to an xthinblock node so you won't get thinblocks anymore until you upgrade but you should still be getting regular blocks.

 

[solex]

@Gavin Andresen
Would you be kind enough to review the xthinblocks code and comment, as well as those named above?
If this gets passed by the membership then it will eventually become part of BU.

@freetrader your opinion is welcome too. I see this as complementing the blocktorrent work. It provides a solution now, and IMHO both could remain supported indefinitely giving node users choice of efficient block propagation method.

@Peter Tschipper
Good rebranding! Is there a feel for the probability of collisions with the shorter hashes?

 

[YarkoL]

@YarkoL I've switched my thinblock node to an xthinblock node so you won't get thinblocks anymore until you upgrade but you should still be getting regular blocks.

Ok, will upgrade ASAP. Again thousand thanks for your work so far, I have a feeling this could be big stuff!

 

[sickpig]

@Peter Tschipper impressive work! In the next few days I'm going fire up a thinblock node to help testing. Is there anything I've to do in particular to stress test the code properly?

 

[Peter Tschipper]

@solex so far I haven't seen any collisions but the code is there and tested to handle them. However I should probably dust off the math books and calculate the probability of collision more thoroughly but it's going to be highly unlikely. A 64bit hash is 2^64 -1 so it's a big number well beyond a 1000 quadrillion...but with thousands and perhaps 10's of thousands of tx's in the mempool that probability will be somewhat more likely. But as I said, the code will just re-request a regular thinblock if that happens. I'll have to dig up a formula to figure that out unless someone else has it handy.
[doublepost=1453328951][/doublepost]@sickpig nothing much to do as far as the block downloads are concerned but the relaying part you can try to break. Such as, what happens if you use connect-thinblock to a node that doesn't support thinblocks (that one should give you an error message in the log) and you can try out basically anything you want to try and break it. Turn off your computer for a while, do blocks get downloaded when you start up again and thinblocks eventually. Right now thinblocks will only be downloaded when were close to syncing the chain < 2 away. So testing more the functional side while at the same time you can check the logs occasionally for TX HASH COLLISIONS, I don't think you'll see any, ever, but I'd really like to know if there are any and any other strange behaviors you might come across. Thanks so much !

 

[YarkoL]

A 64bit hash is 2^64 -1 so it's a big number well beyond a 1000 quadrillion...but with thousands and perhaps 10's of thousands of tx's in the mempool that probability will be somewhat more likely. But as I said, the code will just re-request a regular thinblock if that happens. I'll have to dig up a formula to figure that out unless someone else has it handy.

I played with the python script in this page and came up with these numbers:
- the probability that 10000 (ten thousand) 64bit hashes are all unique is
0.9999999997289521
-the probability that 100000 (hundred thousand) 64bit hashes are all unique is
0.9999999728949731

 

[Peter Tschipper]

@YarkoL Thanks for those numbers...

 

[theZerg]

Starting to catch up after my vacation. .. how can we artificially cause a collision to prove it works in that case?

 

[YarkoL]

Starting to catch up after my vacation. .. how can we artificially cause a collision to prove it works in that case?

Unit test with a collision setup and assert of XThinBlock.collision flag. Leave it to me

 

[Peter Tschipper]

@theZerg I tested it by editing the code to make sure the pathways would work but it would be good to have the unit test. Sounds like @YarkoL is working on it...

Also, I think there's an attack vector that needs to be filled regarding the xblock_tx transaction. Someone could just repeatedly ask for that over and over tying up the network connection. I'll work on that today, it should be an easy fix.
[doublepost=1453383655,1453382536][/doublepost]@YarkoL Just in case you were not aware, there are two place we can have collisions. One just before we send the xthinblock (collision within the block tx's) and then also when we receive (collision in the mempool) which is checked in the strCommand == "xthinblock" section of main.cpp

 

[Peter Tschipper]

I pushed up some DOS protection to the xthinblocks repo for the "get_xblocktx" transaction using the same 10 minute decay window used in -limitfreerelay. Basically if we get more than 20 requests in a 10 minute window then we'll disconnect them

 

[YarkoL]

Block #394471 from f2pool almost hit the ceiling. According to Blockchain.info it was 976.5625 KB, but my client printed it as 1MB

But no worries matey, XThinblocks to the rescue:

2016-01-22 15:44:00 Thinblock compression: 1% of 1000000 bytes Txs in block: 1993 Txs in mempool: 4232 Collision: 0

 

[Peter Tschipper]

@theZerg

I built a version that uses 16bit Tx hashes in order to test the hash collisions. It seems to work and flags the hash collisions and acts appropriately in sending a regular thinblock instead. I'll keep running it for the next day or so and see what happens.

Anyone that wants to play with it you can find it at

https://github.com/ptschip/bitcoin/tree/xthinblocks16bit

 

[YarkoL]

@Peter Tschipper
Got an idea. If the 16b hashes collide, it then falls back to "basic" thinblock like it did with 64b hashes. How about making it so that it will instead try 32b instead? and if again collision then 64b. And standard thinblock as a last resort.
So we would have three maps for each partial hash length and the length would be passed to cheaphash function as a parameter. Does that make sense?
I think we could also pass the length as a parameter to the thinblock constructor and so have only one class and one message.

 

[Peter Tschipper]

@YarkoL

hmmmmmm....nice idea.

I've been debating on whether to go to 32bit hashes for the "wow" factor, I think they would work for a year or two but then thought the idea of having to upgrade might give our critics fuel to shoot us down, BUT your idea is maybe a way around that. My two concerns are the added complexity (not really that big a deal) but secondly what about DOS...is there an attack vector here? (Something to think about.)

Based on what you said above, maybe this will work.
.
We could start with 32bit hashes, make it hard coded as the starting point. Then if it gets a collision (or maybe more than 1 collision per day or week etc..), up it automatically to 40bit, then 48, then 56 then 64 (maybe have the settings persist between startups - a little more work there). We could also add a config option to set the starting point manually to whatever is wanted as long as its above the minimum. That gets us around having to have to watch for collisions and make code changes and upgrade at some point in the future while giving us the smallest possible block.

I do wonder if we should be keeping the first roll out as simple as possible. Assuming this BUIP gets approved. Is this better left for phase 2 (a separate BUIP) or do we go for the gold!?

 

[solex]

This is all good thinking and I like it a lot, i.e. start at say, 48bit, and increase by 16b if a collision is seen in a week, or decrease if not, min 16b and max 128b (then standard blocks) although that would surely indicate an attack is in progress.

But this stepping might be best for version 2, and I tend to agree the first implementation should be as simple and robust as possible. The 12x gain is still phenomenally good, i.e. a 2MB Classic block being sent in a 160KB message. That makes it so obvious that keeping the 1MB is not only pointless, but truly stupid.

 

[Peter Tschipper]

@YarkoL If you're up for it you could take on phase 2 (its really your idea), write up the BUIP and do the coding? I could help out with any testing down the road...

 

[YarkoL]

@Peter Tschipper
Sure.
I think it could actually simplify the code by removing the repeating parts, and using only one "thinblocks" message. Unless there is a gotcha, I'm still not that well acquainted with the code.

also I think even one map will suffice from 64b partial hashes to 256b hashes, and we just read different lengths of the 64b hash during lookup.

 

[awemany]

Hey @Peter Tschipper, so this is one of those things that was completely off my radar given all the other political BTC news that pulled me.


So it sounds like we have working code that cuts bandwidth roughly in half? Absolutely awesome.

Awesome work, I really want to look into this, as soon as I have some more free time! The last thing I faintly remember was 'someone worked on thin blocks for XT, but then the nodes randomly locked up and no one could find the bug until the next release'. I was like, cool, need to look into what is going on. Part of me also always wanted to work on this problem, though it looks like that is solved now.

Again: This is great!