BUIP010 (passed): Xtreme Thinblocks

[Peter Tschipper]

I recently played with indexing tx hashes from the main blockchain. There are no two different hashes having the same first eight bytes. There are more than 100 000 000 tx hashes without single 64 bit collision. This isn't a proof of no collision in future, but it shows how good the 64 bit tx hashes are.

(In contrast, 160 bit hashes of BTC addresses often collide even with equal first 18-19 bytes, being different only at several last bits.)

Thanks for the info...
We've coded it to handle any collisions even though they will likely never happen.

But that is strange about the 160 bit hashes, would like to know more...

 

[cypherdoc]

http://bitcoinrelaynetwork.org/stats.html

 

[Peter Tschipper]

@cypherdoc Thanks the for the link, I had already seen it but it's not very well stated as to what the data means. From what I can tell though it looks like it's taking them about 1 second to relay their blocks. I'm not sure about that though.

 

[cypherdoc]

@Peter Tschipper

i can't make sense of it either.

 

[rha]

That sounds really weird - is the hash function that bad or have these addresses been designed that way? Do you have examples?

Example:
https://blockchain.info/pl/address/0b5b85544ea2ddff03a3eeb3c2f6bf579206a428
https://blockchain.info/pl/address/0b5b85544ea2ddff03a3eeb3c2f6bf579206a430
Both are legitimate, having 0.0001 BTC each.
Probably someone played with hashing - both addresses are specific:
12345678912345678912345678913HPoG2
[URL='https://blockchain.info/pl/address/1234567891234567891234567891wBd7RE']1234567891234567891234567891wBd7RE[/URL]

 

[solex]

@rha
Isn't the longest vanity text about 9 or 10 characters, and its infeasible to make them longer?
https://vanitypool.appspot.com/solvedWork

 

[YarkoL]

Or those might be just made up addresses without private keys, the amount in them burned.

 

[cypherdoc]

@solex

i remember 5 characters being the maximum characters for safety. which is why i generated 1cypher...

 

[solex]

Right, so btc addresses with a similar high degree of order which then causes more frequent (address) hash collisions can't have spendable tx-outputs unlocked, and are a curiosity, not a concern for xtreme thin blocks with short tx hashes.

 

[rha]

Yes, it's quite possible they are artificial, without private keys (known to the creator).
Other addresses with hashes of equal first 19 bytes looks artificially (often containing texts).
Yet they exists in the blockchain and we have to cope with them.

As for transactions, in the first 386480 blocks I've found just these transaction pairs having first six bytes equal:

a8e63b8a1a090bb65b47c926e00f22c84a1b92165422907674c00d38c7c77ecd
75c0fda944198b022e849af52c5123a6e392b53a87fa8434f0850d38c7c77ecd

d758bb988360c0d91bb5e67208613767b159fe2d31aba4493a17f72d3cb31d16
18f046e3966937573334265ff3118bbdcdcd073127ecb68edd48f72d3cb31d16

4512be15ff9f70b442a2fb4de30fc5e675bbb36c5b4b92e671b1de09c7f7dbbf
48e7f38c26dc1865205c8ca83689752c8108a7dbc88d446432a8de09c7f7dbbf

04c91b1d39f41e8301f19b1cf107e837e45e2a2d8dd0fbfc5aadfe722268c54d
2e1342f4570fcc186036e99801b2ece0e402165497b8f87a52fdfe722268c54d

49fbdb7b6b79689e038a1dae3e875a3968415a5c1de6e91f5b3b207451cc5ad6
5addfcf66b3b0e74b4f827b9311817012050fdf3736f9e28af3a207451cc5ad6

74f1372bbbd56bcb33e3b1caefc5f2e0c1e6b1eb015d3d1f7006be1c1ce8888e
100a5477190de7b6ffcae8d125cdb6e774c29974ec9d75c6ef04be1c1ce8888e

d0b9be9c454108d6e601fabdf954b662a11659792fb87f115118b5d6dc790428
a2f4caef4292d3c447cf359aa4e75e8f126c9261eb08445cb83db5d6dc790428

b6e4c065b26cf3b026f15a67c662c1df600ca3b0c2847e45af9e3b23cd3803a7
95c4e2bc7ad45b8ee3c33230d1bd31b6b605323f4fb33e7c71e33b23cd3803a7

9b466b10676c5037f97fc9eab81e5c652860d8a2100760984f4a39a373de6ca4
e6568d7da46e84da1b326e45f62fad8eac663e2ce19b8c59790f39a373de6ca4


By the way, in the first 386480 blocks block hashes collides with three first bytes 4469 times, with four first bytes 31 times and there are no blocks with the same first five bytes. (I count each colliding bit, so there are less colliding hash pairs than these numbers.)
[doublepost=1453929401][/doublepost](It's little endian so "first" bytes are to the left.)

 

[dgenr8]

So, if XT proceeds with dagurval's XT-thinblocks solution is there an advantage if BU supported this as well? Such that a BU client will default to Xtreme thin blocks when connecting to another node which supports it (likely just BU at present), but will then revert to using XT-thinblocks as a backup?

I think that would be very good, and a patch supporting Xtreme thin blocks against XT would be welcome as well.

 

[solex]

@dgenr8
That's great! If you or dagurval were to raise a BUIP for it then @theZerg will review before opening it for public comment and vote. Ours are not as structured as Core's BIPs as we feel the spirit of an initiative is more important than the minutiae of form-filling detail.

EDIT: based on this comment

You are basically voting on whether BU should provide a separate, optimized block transmission protocol or not.

@dagurval No separate BUIP is required as the functionality of XT-thinblocks is covered by BUIP010, looks like they can be bundled together.

 

[YarkoL]

Yes, it's quite possible they are artificial, without private keys (known to the creator).

And to the creator only...

The transaction data was interesting too!

 

[theZerg]

I recommend that we vote FOR this proposal. Remember that you are not voting on specific technical details (like the txn hash bit length) -- I'll work with the patch submitter and anyone else interested to flesh these out.

You are basically voting on whether BU should provide a separate, optimized block transmission protocol or not.

 

[solex]

VOTING IS OPEN for this BUIP

If you are in the membership then please go to this thread to cast your vote:

### VOTING IS OPEN for BUIPs 2, 4, 5, 10 & 13 ###

 

[solex]

Voting for BUIP010 is now closed

 

[YarkoL]

bluematt on Xtreme thinblocks:

 

[Peter R]

@YarkoL

What does he mean by "include lots of fallbacks and extra RTT-s, which is the primary concern with block-relay-times"?

And what exactly is he saying is braindead? Bloom filters, or the relay code he wrote?

 

[Peter Tschipper]

@Peter R

They are always trying to take the discussion back to talking about the relay for miners which is not what we're doing here with Xtreme Thinblocks, at least not yet. All we're focused on right now is getting the p2p network to the point where it can scale and building a foundation for more scaling solutions. But that said, I think we may already be faster or close to what Matt's relay network is doing for the miners. They erroneously think that an occasional extra round trip necessarily means slower performance. Because of the latency issues, the biggest problem with performance here is the size of the package. If the package is small, and we are efficient, we can do and extra round trip (maybe several) before they're even done one direct trip with a larger package.

Also, on the p2p network we don't have to be perfect. If we can propagate a block of *any* size to the entire network in 5 seconds or 10 seconds that's all we need. We don't have to worry about every tenth of a second for that. For the miners, sure, every tenth is important but, to say it again, that's not what we're focused on here. Matt's relay network is being used for the miners, what we're doing here is for the p2p network, to get larger blocks to relay quickly so that the nodes can get ready for the next block coming and have plenty of time in between to process and relay transactions

If we don't put in technologies that allow the p2p network to scale then we can't expect the miners to mine larger blocks. Obviously those at Blockstream don't want that and that's why I think they always try to divert the discussion back to Matt's relay network, as though to say, we already have the relay network so why bother working on p2p, it's pure FUD and obfuscation of the issue.

 

[Peter R]

@Peter Tschipper

Thanks for the info! I take it then that RTTs means re-transmissions.

I think it's partly FUD and obfuscation, but I've also noticed that the Blockstream guys have trouble thinking probabilistically. They want everything to be black and white and a solution like Xthin that puts things in Bin 1 99% of the time and Bin 2 1% of the time confuses them. They would prefer a solution that puts things in Bin 3 100% of the time, even if the average performance were worse. My hunch is that they're thinking "adversarially" and extrapolate the worst-case scenarios without assessing the probability that these scenarios ever occur (e.g., it is possible that 100 Xthin blocks in a row would require multiple round trips and happen in such a way that affects every node at the same time too!).

But the more I think about Xthin blocks, the more I think it's the natural way forward. My current "dream solution" is building subchains using Xthin to communicate the Δ-blocks.