BUIP010 (passed): Xtreme Thinblocks

[awemany]

Thanks for your interesting insights, @Peter R . Curiously, this reminds me of the earlier discussions we had, those of equilibrium blocksize and your initial fee market paper. The one were Greg (somewhere on reddit) seemed to believe that somehow, you can create efficient mempool syncing schemes that are growing less than proportional in the number of transactions flying around.

I argued back then that due to the stochastic nature of transaction submission into and propagation within the network, there is always a certain uncertainty in the mempool. I remember that I pondered whether that stochastic nature is unavoidable, or could be avoided with some fancy scheme. I think it is unavoidable, because the stochastic timing is unavoidable. The only way out would be to atomic-clock timestamp the transactions at the edge of the network when they enter the system (so that each node can decide with a less than function on whether a transaction is before or after a certain point in time, to reduce the transaction set uncertainty towards zero).

However, such a system simply does not work under adversarial conditions (people setting their txn timestamps to whatever value) - as only Bitcoin itself is the system that does the timestamping under adversarial conditions, with its 600s mean resolution.

I expect that, realistically, the mean propagation speed q of a Bitcoin transaction across the globe is on the order of a quarter second minimum, due to processing and speed of light delays. If anyone doubts that figure (which I honestly pulled out of my intuitive ass), I challenge and welcome those to make a more detailed estimate. It is also a parameter that could be measured by cooperating nodes (@theZerg , didn't you do that before?)

The mempool homogeneity is then bounded by

h=1-(q/T)

with T block time (600s). So I expect that mempools will never be more than 99.96% homogeneous.

I think this formula also introduces a trade-off for the efficiency of subchain schemes. A subchain with faster subblocks will lower the denominator and thus increase the mempool decoherence.

I remember that @Gavin Andresen was sympathetic to changing the 600s interval in the past. I think the above needs to be considered as a trade-off, and 600s does look like a pretty sane default in that light. I rather think that something like your subchains scheme (up until the point that they are efficient wrt. mempool decoherence) would help with more instant confirmation.

 

[Peter R]

I like your mempool homogeneity bound calculation! If I superimpose it on my earlier chart for Core's "compact blocks," we see that a second round trip will essentially always be required as the block size gets larger (unlike Xthin). And the existence of the bound seems to be fundamental, because we know that q is at least d/c, where d is the effective diameter of the network and c is the speed of light (the first of which cannot change appreciably and the second of which cannot change at all).

I guess this assumes that the contents of a given block are equally-likely to consist of any subset of transaction in mempool (which is not a perfect assumption), but it still gives us a pretty good estimate I think.

 

[awemany]

I like your mempool homogeneity bound calculation! If I superimpose it on my earlier chart for Core's "compact blocks," we see that a second round trip will essentially always be required as the block size gets larger (unlike Xthin). And the existence of the bound seems to be fundamental, because we know that q is at least d/c, where d is the effective diameter of the network and c is the speed of light (the first of which cannot change appreciably and the second of which cannot change at all).

Yes, that's exactly what I think happens. If we go with the 250ms figure and your above graph, this means that efficient block transmission for Core scheme becomes problematic at about 1500 txn / block (where it reaches 50% chance of 2nd roundtrip).

1500 txn / block amounts to about 2.5 txn/s.

Eerie how their transmission scheme is tuned to the smallblockism that they seem to have in mind for Bitcoin

I guess this assumes that the contents of a given block are equally-likely to consist of any subset of transaction in mempool (which is not a perfect assumption), but it still gives us a pretty good estimate I think.

I actually do not think that matters. If you select any true subset of transactions to include into a block, that simply means you are limiting your effective transaction rate. Just as we have now with Core's imposed 1MB limit. However, the fraction of uncertainty remains because your selected subset still has to have a boundary in time with the given uncertainty q/T >= d/(cT).

Unless you can somehow predict or accurately time transactions . Voluntary, larger full node hubs could establish mutual trust and then chunk up and precisely time transactions (and mutually trust the timestamps!) and decide what comes into which block, and block out any 'SPV' client from freely transmitting transactions. But that's comparable to a centrally administered network anyways, and not Bitcoin.

 

[Peter Tschipper]

@Peter R

Oh, so that's where he was getting the numbers from. Those were pre-release numbers. We were still working on the software at that point and unknown to us, had issues with the orphan cache. It turned out that there were problems in the way Core was deleting orphans from the cache when some random node would disconnect. We tracked it down and fixed the issue before releasing BU12.0. Orphans it turned out are very important to getting xthins to work properly. Firstly the orphan cache defaults were much to small, secondly the disconnect issue would purge many good orphans, and thirdly, the trickle logic is also largely at fault in creating orphans but also it seems the miners do their fair share.

A further note: I believe Core has since fixed their trickle logic for the upcoming release so there should be much fewer orphans but still I don't think they fixed their disconnect issue but I"m not sure. Either way it doesn't affect us as we are getting 99% + efficiency in not doing re-requests. So we basically doing 1.5 round trips - almost all the time. The 66% number is just another out of context comment from GM.

 

[Peter Tschipper]

I expect that, realistically, the mean propagation speed q of a Bitcoin transaction across the globe is on the order of a quarter second minimum, due to processing and speed of light delays. If anyone doubts that figure (which I honestly pulled out of my intuitive ass)

I would like to know if anyone has done any study on this...how fast can a transaction propagate throughout the p2p network. 0.25 seconds sounds on the fast end to me given that just the latency itself through optic fibre is about 100ms to the other side of the planet,, not counting the time spent traversing switches, routers, firewalls etc...and then at least 5 or 6 hops through bitcoin nodes, and then consider large tx's greater than the MTU (> 1500 bytes). But then perhaps 0.25 is not that far off the mark, as you said, for the minimum. I wonder if somebody has a tool that can model that fairly accurately given a certain transaction size?

Something else we could do, coming at it from another angle, is to get actual data from the nodes. A couple of weeks ago I submitted a PR to add transactions/sec output for the node. We could add to that the knowledge of how many tx's were missing for each xthin and then get a general idea for that node how long tx propagation takes. So taking tx's missing / tx/sec...i think would give us the tx propagation time that, that node is experiencing...it would be rough and variable since the tx/sec changes quite a bit over the course of a day but we might be able to compare that with theoretical numbers and come up with a useable model.

Continuing on a different train of thought, we could also add in to the node the entire time it takes to process a transaction from receiving it and putting in queue to finally being accepted by the mempool. That would take a larger effort as we would have to add timestamping to each tx as it comes in (really not a lot of work). But it's something to think about for the future as IMO we will need to get more and more performance data so we tune the code better.

 

[Peter R]

@Peter Tschipper

The only studies I'm aware of that looked at information propagation in the Bitcoin network both focussed on the propagation of blocks. There is this 2012 paper by Decker and Wattenhofer and this 2016 paper from Cornell. If we could perform our own study that specifically examined the propagation of transactions and mempool homogeneity at some point in the future that would be awesome!
[doublepost=1462727762,1462726824][/doublepost]On another topic, regarding TheBlueMatt's comment that:

XtremeThinBlocks use a truncated TXID, which is vulnerable to collision attacks with a complexity of 2**32 (under a seconds work on a modern CPU). cmpct_block uses a salt to to eliminate this attack vector.

Is this math actually correct? We are still using 64-bit hashes, correct?

The attack this salting is designed to prevent is described here in the justification section of BIP 152. Basically, the concern is that an attacker could create lots of un-broadcast TXs until he finds one with a short-ID that matches the short-ID for a transaction already in mempool. If he did this enough--and broadcast all these colliding TXs--he could make it so that collisions are far more likely than we expect due to randomness. The salting proposed in BIP 152 uses information from the new block itself, which makes it impossible for the attacker to scan for collisions ahead of time.

This makes sense, but wouldn't this attack require scanning through 2^64 permutations of a given TX to find a collision [which would take a lot of time--not "under a second" as Matt reported]? I don't see how it can be done any faster, but I'd be happy to be corrected. That being said, there was discussion about moving to 32-bit (or even 24-bit) hashes in the future, in which case I suppose the something like this could be advisable.

EDIT: there is an attack that can be done by generating about 2^32 (rather than 2^64) transactions.

EDIT #2: But you'd still need to make 2^64 comparisons to find the (potential) collision in the set of 2^32 transactions.

EDIT #3: Wrong again. You can maintain a sorted list and do it in ~2^37 operations (see below).

 

[Peter R]

Figure 8 in the Decker and Wattenhofer paper got me wondering if we could combine @Gavin Andresen's header-first block propagation with Xthin to (a) further reduce the propagation impedance and (b) to reduce the latency hit due the Bloom filter. Here's what I'm thinking:

 

[Peter R]

The same diagram for Core's "compact blocks" is convoluted due to the extra round trip required at higher transaction rates:

 

[Peter R]

Of course this isn't quite realistic because the INVs are faster than the other two messages.

 

[Chronos]

Sorry for the beginner's question, but what is the INV message in this diagram? Is it some kind of notification that another block is available? Also, what does "Ver." represent?

 

[Peter R]

The Bitcoin P2P protocol uses the inv/get-data method for communicating blocks and transactions. An "inv" is when a node says "hey, I have this transaction or block, do you want it?" and a get-data message is when the other nodes says "yeah, I want it--please send it to me."

In the above diagram, it's implied that the complete block header is communicated with the "inv."

"Ver." is short for "verification" (the node is verifying the block it just received). "Diff" is short for "difficultly (the node is checking the proof-of-work in the header it just received).

I should add that this isn't presently what we're doing...it's just an idea I had to combine Xthin with header-first propagation.

 

[solex]

@Peter R
Nice graphics as usual.

We are still using 64-bit hashes, correct?

Yes, and i recall you pointed out earlier, this can be squeezed down to give further scope for scalability.

 

[Peter R]

I think I understand TheBlueMatt's comment that:

XtremeThinBlocks use a truncated TXID, which is vulnerable to collision attacks with a complexity of 2**32 (under a seconds work on a modern CPU). cmpct_block uses a salt to to eliminate this attack vector.

The attacker wouldn't find a TX that collides with one already in mempool; instead he would generate two random TXs that collide and broadcast them both. The latter is vastly easier than the former:

- Generate 2^32 random transactions.
- The probability that the 64-bit short hash of any pair of transactions collides is 1 / 2^64.
- But there are m! / [n! (m-n)!] ways of picking n numbers from a set of m numbers.
- For m=2^32 and n=2 this works out to about 2^63 pairs of transactions.
- So the odds are pretty good (~2^63 / 2^64 = 1/2) that you'll find one!

Edit: On second thought, you'd still need to make 2^63 comparisons of the hashes in order to find the collision! So now I'm back to thinking that Matt's math is not correct.

Second edit: Actually, no, you could keep a sorted list of the hashes for each TX you generate and then use binary search to check that list for a collision for each new TX you randomly generate. Performing these operations can probably be reduced to N lg N complexity, which is doable for N ~2^32. In other words, I agree that the attack is feasible (but the complexity is higher than Matt's estimate). [hat tip to Emin Gun Sirer]

 

[Chronos]

So, the result of the attack is that enemy mining pools propagate their blocks with more xthinblock roundtrips? Could this be easily solved with the same salting technique to what cmpct_block proposes?

 

[Peter Tschipper]

@Peter R I understand that someone might do this but why? I don't get how a miner could benefit from creating a block with a collision, wouldn't it just mean they would possibly orphan their own block as it would propagate more slowly? I must be missing something?

Ok, never mind, yes it's possible...what we do in our version for p2p if we see that there's a collision in the mempool is we re-request a full "thinblock" with the full tx hashes...so we end up doing the 2.5 round trips...that's if someone could pull this off. So yeah, for the miners this would be an issue, for p2p it's not IMO.

 

[Peter R]

@Peter Tschipper: Yeah, I don't think this is really that serious of a threat. Firstly, it is not trivial to pull off, unlike what Matt and Greg claimed, although it is still feasible; secondly, even if it is pulled off, then we fall back using longer hashes like you said.

That said, if Core is serious about working with the community to define a protocol that we can all use, why don't we offer to add salting if it makes them happy and gives them a contribution to Xthin that they can hang their hats on?

So, the result of the attack is that enemy mining pools propagate their blocks with more xthinblock roundtrips? Could this be easily solved with the same salting technique to what cmpct_block proposes?

Yes, it could absolutely be solved that way! Remember, compact blocks (low-BW mode) is basically Xthin without the Bloom filters.

In fact, we could view compact blocks as a degenerate case of Xthin, if we had an option to set the Bloom filters support to OFF. With this line of thought, perhaps there's some way we (Unlimited/Core/XT/Classic) can achieve a protocol we're all happy with if we add enough flexibility so that the protocol can be used how Core wants (more round trips but no Bloom filters) or how we want (less rounds trips by using Bloom filters).

 

[sickpig]

@Peter R

it would be a good thing (TM), but considering how gmax and Corallo are reacting to Tom Zander's feedbacks on btc-dev ml I'm not extremely optimist...

Gmax reiterate the same ttitude on r/btc, see:

 

[awemany]

Hey Guys,

there is no real obstacle to implementing/using a per-connection salt, or is there?

I would be very much in favor of that - because I do think that colliding hashes is a very possible and maybe even likely attack scenario - anyone can inject such TXN into the network.

So, I do have to say that Greg is right in asserting this is an attack vector (he's of course, evil and manipulative in his proselytizing in North Korea when he's saying that 'we do not understand this issue').

However, I think it is also just a soft attack, and so far I can only see a possible reduction in service, not an outright denial of service - and miners have some ways to reduce the impact of such an attack.

Finally... Greg, you should like this kind of attack. It allows you to effectively blocksize limit the Bitcoin network by injecting colliding transactions..

 

[Peter Tschipper]

@awemany Right now there is no danger to us...we are only using xthins for p2p for which is was designed and if there is a collision we just re-request a thinblock with 256 bit hashes for an extra round trip.

A little history on this, we had this discussion, a brief one, month's ago and decided not to use a hash index (a different solution) because we were only going to be using BU for p2p and BU was heading down the path of just being a great relay node and there was some discussion about even taking out the BU mining code - if my memory serves me. But now it looks like we've been wanting to promote it as an option for miners using @theZerg 's Xpedited relay. I agree, for a miners relay we need some way of preventing the attack. If Core is using some sort of salt, then we should probably do the same. The only problem I see in implementing this for p2p is that other projects are on the verge of releasing xthins and since we're all using the same service bit we can't just make changes to the underlying messaging without also having to go to a different service bit again and lose the network effect of having all those supporting nodes out there. Unless we can do a coordinated change among the groups.

@dagurval What do you think about this, adding a connection salt in as Core seems to be planning for their Block Relay? Do you have any suggestions around that regarding implementation and rollout?

Just thinking off the top of my head, we could get around the service bit issue, by creating another p2p message which turns on or off salting in a similar way that headers first is implemented in Core. That way we can leave xthins for p2p the way it is but still support salting for nodes or miners that want it and remain backwardly compatible.

 

[awemany]

@Peter Tschipper:

Hmm, but injecting txn with similar-enough hashes would allow an attacker to slow down the block propagation between all BU nodes, or wouldn't it? (Basically causing bandwidth to roughly double)

I don't think that's going to be exploited so much or an issue at all when blocks are 1.5 .. 2MB. But imagine that in the optimistic future, blocks are 100MB, BU has 30% node count and suddenly someone goes and creates a couple TXN similar enough so that the fast propagation fails - that could become somewhat of a problem for the BU part of the network.