A more scalable approach to thinblocks (ready for testing)

[Peter Tschipper]

Hi All,

Although there has been a lot of hard effort applied to this problem, I
don't beleive the current approach to thinblocks to be scalable in the
long run, even it could work. The basic reason being the number of
rounds trips needed to get all the transaction data is too many to
achieve any kind of useful performance. Furthermore when tx rates are
in the 100's or 1000's of transactions per second, mempools will be much
further out of sync. I don't believe you could get everything you
needed in any reasonable amount of time, if at all under those
conditions. And on top of that the merkleblock is problematic. While a
valuable goal, I think part of the problem here is trying to make this
work with clients that are already out there when what is really needed
is a break from the past. A new protocol version and new classes of
transactions.

Reference implementation:
https://github.com/ptschip/bitcoinxt/tree/thinblocks
* still using Mike Hearn's block re-assembly code and with a few
other snippets.
* and dagurval's suggestion to add the coinbase tx to every thinblock.
(If you want to test you'll need two nodes running, with one
connected to the other, as it has its own protocol version)


The reference implementation works in the following way. (Only one
round trip is required).

Node A is behind by one block and makes a thinblock request to Node B in
the following way:
1) Node A creates a bloom filter seeded with the contents of its memory
pool
2) Node A sends the bloom filter along with a getdata to Node B
3) Node B sends back a "thinblock" (class CThinBlock) transaction
which contains the block header information, all the transaction hashes
in the block, and any transactions that do not match the bloom filter
that Node A has sent.
4) Node A receives the "thinblock" and reconstructs the block.

Although I have only tested this for a few days, I have yet to see this
fail and yet to see a re-request for transactions however if the need
should arise for re-requesting transactions then the following will occur.

5) If there are still any transactions missing then a "CThinBlockTx"
transaction is sent from from Node A. This contains a map of the
missing transaction hashes seeded with null tx's.
6) Node B upon receiving the CThinBlockTx request will take the object
and fill in the transaction blanks, getting the transactions from the
block on disk rather that memory (in this way we can be sure the tx's
are there as they may already have been purged from memory). Once the
blanks are filled in the object is sent back to Node A and the block
reconstructed. As I've said, I've tested that this works but have yet
to see it needed, and again, just one round trip to get all re-requested
transactions.

In the long run, IMO this is much more scalable solution as we only need
one round trip and we avoid the problematic use of a merkleblock. Also
the generation of the bloom filter is fast and the structure is not
overly large. A casual observation showed a 50MB memory pool yeilding a
10KB bloom filter or thereabouts (some tuning may be possible to get
that lower). Thinblocks coming back are typically 20 to 50KB in size
and missing 1 to 10 transactions.

If you find this interesting and worthwhile I'll be happy to submit a PR.

And here are some typical numbers after the mempool has warmed up...

2016-01-01 09:33:47 Sending thinblock - thinblock size: 43020 vs block
size: 605766 => tx hashes: 1337 transactions: 1
2016-01-01 09:55:34 Sending thinblock - thinblock size: 50044 vs block
size: 763098 => tx hashes: 1539 transactions: 2
2016-01-01 09:57:30 Sending thinblock - thinblock size: 14623 vs block
size: 180801 => tx hashes: 355 transactions: 2
2016-01-01 10:11:52 Sending thinblock - thinblock size: 32877 vs block
size: 484331 => tx hashes: 1018 transactions: 1
2016-01-01 10:18:02 Sending thinblock - thinblock size: 22159 vs block
size: 285710 => tx hashes: 505 transactions: 5
2016-01-01 10:41:55 Sending thinblock - thinblock size: 64589 vs block
size: 952085 => tx hashes: 2011 transactions: 1
2016-01-01 10:45:06 Sending thinblock - thinblock size: 14005 vs block
size: 192031 => tx hashes: 349 transactions: 4
2016-01-01 11:11:51 Sending thinblock - thinblock size: 68531 vs block
size: 932644 => tx hashes: 2134 transactions: 1
2016-01-01 11:17:44 Sending thinblock - thinblock size: 24239 vs block
size: 542876 => tx hashes: 719 transactions: 2
2016-01-01 11:21:50 Sending thinblock - thinblock size: 44481 vs block
size: 178405 => tx hashes: 355 transactions: 21
2016-01-01 11:27:48 Sending thinblock - thinblock size: 18532 vs block
size: 252596 => tx hashes: 460 transactions: 5
2016-01-01 11:31:52 Sending thinblock - thinblock size: 21316 vs block
size: 260582 => tx hashes: 458 transactions: 6
2016-01-01 11:51:50 Sending thinblock - thinblock size: 47692 vs block
size: 792155 => tx hashes: 1483 transactions: 1
2016-01-01 12:03:24 Sending thinblock - thinblock size: 49549 vs block
size: 385895 => tx hashes: 890 transactions: 11
2016-01-01 12:12:29 Sending thinblock - thinblock size: 28845 vs block
size: 668592 => tx hashes: 892 transactions: 1
2016-01-01 12:14:41 Sending thinblock - thinblock size: 28585 vs block
size: 142093 => tx hashes: 232 transactions: 10
2016-01-01 12:42:55 Sending thinblock - thinblock size: 67693 vs block
size: 999851 => tx hashes: 2106 transactions: 1
2016-01-01 12:46:31 Sending thinblock - thinblock size: 16815 vs block
size: 381712 => tx hashes: 518 transactions: 1
2016-01-01 12:48:21 Sending thinblock - thinblock size: 71075 vs block
size: 249546 => tx hashes: 350 transactions: 6
2016-01-01 12:49:00 Sending thinblock - thinblock size: 49443 vs block
size: 248150 => tx hashes: 31 transactions: 6
2016-01-01 12:49:55 Sending thinblock - thinblock size: 3211 vs block
size: 239966 => tx hashes: 91 transactions: 1

[David de Kloet]

How does this relate to IBLT?

Is it supposed to be a simpler alternative only to be used until IBLT is ready?

Or is it superior to IBLT?

Or does it solve a different problem and can be used in addition to IBLT?

One thought about the proposal. If it never re-requests any transactions, doesn't that mean it could be more efficient by using a smaller bloom filter and just occasionally doing re-requests?

[Mike Hearn]

Although there has been a lot of hard effort applied to this problem, I
don't beleive the current approach to thinblocks to be scalable in the
long run, even it could work.

Thin blocks are not meant to be a solution that works forever. There are no such things. It's merely meant to be the next step - the next easiest thing to implement and deploy. People have been talking about other approaches like IBLTs etc for a long time but only thin blocks is implemented.

 

Furthermore when tx rates are in the 100's or 1000's of transactions per second, mempools will be much further out of sync.

I see no reason why mempool sync would be worse with higher traffic rates assuming blocks only include transactions that are, say, >5 seconds old.

 

Thinblocks coming back are typically 20 to 50KB in size and missing 1 to 10 transactions.

 

I believe that someone (Tom?) discovered that thin blocks sometimes sends more transactions than it needs to because the setInventoryKnown is limited to an absurdly small number. Bumping the limit on that by 30x or so would be a quick fix. It only stores hashes, which don't take much memory. You could try that and then see if the repeated transactions go away (when connected to a peer that has the fix).

Obviously then you're not going to get as much bandwidth savings when connected to Core simply because Core will forget that it sent you a transaction so fast. But I think a more complicated fix was checked into Core as well, so eventually that problem would go away.

[Peter Tschipper]

On 02/01/2016 4:47 AM, David de Kloet wrote:

How does this relate to IBLT?

Is it supposed to be a simpler alternative only to be used until IBLT is ready?

Or is it superior to IBLT?

Or does it solve a different problem and can be used in addition to IBLT?

I haven't actually crunched numbers but I would think an IBLT structure would have to be larger than a bloom filter as it contains additional data.  I know many tout IBLT as the grand solution but I don't see why it would be better for our needs than just a simple bloom filter.   However, the one thing that does come to mind though is that we can build the IBLT as transactions are coming in and also delete from it as they are being purged from the mempool but creating a bloom filter is so fast I don't know there is much benefit there and perhaps the reverse when you take into account the size of the IBLT filter that has to be sent.  But I have no data make a claim either way.

One thought about the proposal. If it never re-requests any transactions, doesn't that mean it could be more efficient by using a smaller bloom filter and just occasionally doing re-requests?

That's an area I havn't started to tune yet...I think the bloom filter could be smaller but I just wanted to use something that worked.

But to your other point...I think it's very important not to re-request transactions if one of the the main points of thinkblocks is to keep response times low.

--
You received this message because you are subscribed to the Google Groups "bitcoin-xt" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoin-xt+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Peter Tschipper]

On 02/01/2016 5:21 AM, Mike Hearn wrote:

Although there has been a lot of hard effort applied to this problem, I
don't beleive the current approach to thinblocks to be scalable in the
long run, even it could work.

Thin blocks are not meant to be a solution that works forever. There are no such things. It's merely meant to be the next step - the next easiest thing to implement and deploy. People have been talking about other approaches like IBLTs etc for a long time but only thin blocks is implemented.

Furthermore when tx rates are in the 100's or 1000's of transactions per second, mempools will be much further out of sync.

I see no reason why mempool sync would be worse with higher traffic rates assuming blocks only include transactions that are, say, >5 seconds old.

Well, I guess we can agree to disagree but I find it a stretch to think our mempools will all be in sync under that kind of load.   But, it's not just that the mempools will be out of sync or not, but under that kind of load it will be difficult to re-request and retrieve transactions in a timely manner in order to build the thinblock.   Keeping the re-requesting of transactions from occuring is in my view imperative in the long run.  Sure, perhaps now we can get away with it, but even that remains to be seen.

[Tom Harding]

On 1/2/2016 5:21 AM, Mike Hearn wrote:
>
> I believe that someone (Tom?) discovered that thin blocks sometimes
> sends more transactions than it needs to because the setInventoryKnown
> is limited to an absurdly small number. Bumping the limit on that by
> 30x or so would be a quick fix.
>

@dagurval Increased it 50X and switched the implementation from a set to
a rolling bloom filter.

[Mike Hearn]

Well, I guess we can agree to disagree but I find it a stretch to think our mempools will all be in sync under that kind of load.

Why? How it would make any difference?

 

But, it's not just that the mempools will be out of sync or not, but under that kind of load it will be difficult to re-request and retrieve transactions in a timely manner in order to build the thinblock.

Why? 1000 tx/sec is not an especially troublesome load for any machine of reasonable power. Please see:

https://en.bitcoin.it/w/index.php?title=Scalability&oldid=58839

There are some very strange ideas floating around about what computers can do. At Google I routinely handled and wrote servers that could do 10,000qps on a handful of cores without breaking a sweat.

[Tom Harding]

On 1/1/2016 6:36 PM, Peter Tschipper wrote:
> I think part of the problem here is trying to make this
> work with clients that are already out there when what is really needed
> is a break from the past.

Isn't working with clients that are already out there the biggest
advantage of thin blocks, vs. other network compression ideas?

A person or company who is stuck behind a slow network link has no
control over what software his peers run. Thin blocks work without the
other guy having to do anything.

Anything that requires changes on both sides is going to be tough to
roll out for a minority client like XT.

[Jonathan Toomim]

My opinion is that we should be focusing on Blocktorrent  as it's going to be way better. In particular, blocktorrent is going to be much better at crossing the GFW due to the ability to use UDP and the multipath routing. 

Isn't working with clients that are already out there the biggest
advantage of thin blocks, vs. other network compression ideas?

People can upgrade, especially if there's a huge performance benefit.

[Jonathan Toomim]

I agree with Mike. 1000 tps would come close to saturating a single core due to ECDSA verification times and UTXO lookup, but as long as we have some reasonable threading going on, it should be fine. Even if not, 1k tps shouldn't completely saturate a single core.

Consider: a 1 MB block currently takes under 1 second to verify on most machines. A 1 MB block typically contains around 2k transactions. Verification is currently mostly single-threaded. Verification will be much faster once libsecp256k1 is used.

Most transactions that are more than about 5-10 seconds old will have reached all mempools. Eviction may have removed the txs from some.

[Peter Tschipper]

On 02/01/2016 3:59 PM, Mike Hearn wrote:

Well, I guess we can agree to disagree but I find it a stretch to think our mempools will all be in sync under that kind of load.

Why? How it would make any difference?

 

But, it's not just that the mempools will be out of sync or not, but under that kind of load it will be difficult to re-request and retrieve transactions in a timely manner in order to build the thinblock.

Why? 1000 tx/sec is not an especially troublesome load for any machine of reasonable power. Please see:

Sure we can download the transactions eventually...And I'm talking specifically about the re-requesting of transactions  for the thinblock....the point is that the usefullness of this thinblock strategy depends soley on how fast you can re-request those transactions.  I don't see that as a very fast process if we do it one transaction at at time, even under current conditions it's variable and quite slow at times and is dependant on how busy the system is during the re-request, how many peers, how many messages queued up, locking issues, new connections coming in, someone doing rate limiting downloads which boggs down your send queue.  That's why I say it's best to avoid the re-requesting of transactions and do a single round trip instead.  There are a number of variables at play, not just the speed of the computer. 

https://en.bitcoin.it/w/index.php?title=Scalability&oldid=58839

There are some very strange ideas floating around about what computers can do. At Google I routinely handled and wrote servers that could do 10,000qps on a handful of cores without breaking a sweat.

[Tom Zander]

On Saturday 02 Jan 2016 20:33:45 Peter Tschipper wrote:
> I don't see that as a very fast process if we do it one
> transaction at at time, even under current conditions it's variable and
> quite slow at times and is dependant on how busy the system is during
> the re-request, how many peers, how many messages queued up, locking
> issues, new connections coming in, someone doing rate limiting downloads
> which boggs down your send queue. That's why I say it's best to avoid
> the re-requesting of transactions and do a single round trip instead.
> There are a number of variables at play, not just the speed of the
> computer.

So, what you are saying is that the network stack being non-deterministic and
not having weighted connections is in need of fixing before this hack can
reach its potential.
And if we have a better network layer, then we likely don't need that hack
anymore.

Is that a fair understanding of what you are saying?

[Jonathan Toomim]

It sounds like you guys are starting to talk about something that's getting closer and closer to blocktorrent. Why not just help me implement blocktorrent? That way, we can use UDP to avoid deadlocks caused by packet loss, we can write our stack to request more data from faster peers, we can set up code to negotiate how much data can be sent without it being requested (latency vs. traffic tradeoffs), we can work on even better compression techniques (like 4 bytes of the hash instead of the full hash) with good error detection, and we can start uploading before we've finished downloading.

I think I'm going to start working on the code today. Find me in #bitcoinxt if you want to join.

[Peter Tschipper]

No, I'm not saying that at all.

What I'm trying to get at is that the PR currently being worked on can
not be relied on to deliver a consistent perfomance of sending and
receiving a thinblock. It will probably work well 8 times out of 10 and
durguval has suggested and I beleive that from my own observations to be
true as well. That means 8 times out of 10 you probably won't need to
re-request transactions. But Therin lies the problem. 20% of the time
you will have to re-request but the condition of the bitcoin network is
not controllable, predicatable or knowable at any point in time like it
is in a test lab. It is in a constant state of flux. You may get those
re-reqests quickly or not - I have seen re-reqests take 30 seconds or
more! I don't find that inspiring and I don't see why that would
inspire any of the miners to use XT any more than now knowing that block
transmission would be possibly worse 20% of the time.

I know this is somewhat long but bear with me and I'll give you a real
world example which is serves as a good analogy to what I'm getting at.

Many years ago, I was responsible for the performance and scalability
testing/tuning of a new call center system. We had a great lab,
everything controlled, everything just like production. We went through
the hoops of testing/tuning and finally the system was rolled out as a
success. Months later the company decided to roll out a new satellite
call center. Rather than setting it up just like that other call center
they decided to save some money and use the same database, accessing it
over the corporate WAN. I mean what could go wrong, sure there was some
latency but they did all the calculations, the theory was sound. So
they rolled it out and very quickly it went very wrong...It was
completely unusable, the peformance was horrendous. So in we came to
find out what was going on...well it turned out there was something that
never showed up in our "controlled" lab setting, under high latency the
app didn't work well because the developers were pulling back database
records "one at a time"...rather than doing a batch fetch. Too many
round trips. Sound familiar? And that was on a corporate WAN which is
slower than a LAN, but not as unpredicatable as the Internet (never mind
the backend of the bitcoin messaging system which needs a bit of a
re-write IMO). That's why I keep pushing for doing only one round trip
for something as critical as block propagation which keeps us, as much
as is possible, from being at the mercy of uncontrollable and unknowable
conditions.






>

[Peter Tschipper]

I'm skeptical it could work but sometimes when we start building things,
instead of theorizing, we find out they are actually possible. I'm
curious and would like to see a proof of concept. I don't know enough
about block torrent to make a good analysis but one question that comes
to mind is the following. How would a block propagation occur? The
block is created but how do the nodes know they are to start downloading
slices of the block. Or in other words, how would that block get
advertised to the other nodes that there is a file to download and how
fast/slow is that process of advertising going to be?

[Peter Tschipper]

Here are some more test results from the bloom filter tuning from
yesterday for the proof of concept.

Basically I was able to get the size of the bloom filter required to be
just 1/10 of what was being used. At 1/20 the size I started to see
some re-requests of tx's although not many. With a mem-pool right now
of over 200 MB (22500 transactions) the bloom filter is only 3KB in
size. That means we would roughly be able to support a memory pool of
2GB using this approach, before having to bump the maximum 36000 item
limit on the bloom filters that we currently have.

Here are again some results from the last few hours. Just eyeballing
it, it looks like thinblocks are about 1/10 to 1/20 the size of a
regular block without needing to re-request any tx's. Response times
from the creation of the bloom filter , the sending of the request, the
return of the thinblock are subsecond. (not having milliseconds in the
logfile I can not get more granularity on response times)



2016-01-03 08:27:55 Sending thinblock - thinblock size: 9033 vs block
size: 110793 => tx hashes: 142 transactions: 4
2016-01-03 08:29:52 Sending thinblock - thinblock size: 7147 vs block
size: 167485 => tx hashes: 215 transactions: 1
2016-01-03 08:37:56 Sending thinblock - thinblock size: 24620 vs block
size: 499460 => tx hashes: 762 transactions: 1
2016-01-03 08:41:28 Sending thinblock - thinblock size: 7499 vs block
size: 186066 => tx hashes: 226 transactions: 1
2016-01-03 08:41:43 Sending thinblock - thinblock size: 6027 vs block
size: 240754 => tx hashes: 179 transactions: 1
2016-01-03 08:48:08 Sending thinblock - thinblock size: 16746 vs block
size: 317092 => tx hashes: 515 transactions: 1
2016-01-03 08:51:02 Sending thinblock - thinblock size: 5266 vs block
size: 121946 => tx hashes: 157 transactions: 1
2016-01-03 08:51:23 Sending thinblock - thinblock size: 274 vs block
size: 209 => tx hashes: 1 transactions: 1
2016-01-03 09:19:55 Sending thinblock - thinblock size: 75629 vs block
size: 997265 => tx hashes: 2354 transactions: 1
2016-01-03 10:00:26 Sending thinblock - thinblock size: 72493 vs block
size: 749183 => tx hashes: 2257 transactions: 1
2016-01-03 10:41:30 Sending thinblock - thinblock size: 77856 vs block
size: 934265 => tx hashes: 2425 transactions: 1
2016-01-03 11:07:28 Sending thinblock - thinblock size: 67423 vs block
size: 949069 => tx hashes: 2098 transactions: 1
2016-01-03 11:10:48 Sending thinblock - thinblock size: 46989 vs block
size: 999974 => tx hashes: 1459 transactions: 1
2016-01-03 11:22:26 Sending thinblock - thinblock size: 39980 vs block
size: 995115 => tx hashes: 1242 transactions: 1
2016-01-03 11:25:58 Sending thinblock - thinblock size: 14067 vs block
size: 932716 => tx hashes: 432 transactions: 1
2016-01-03 11:32:46 Sending thinblock - thinblock size: 27860 vs block
size: 757520 => tx hashes: 863 transactions: 1
2016-01-03 11:35:06 Sending thinblock - thinblock size: 8017 vs block
size: 189451 => tx hashes: 243 transactions: 1
2016-01-03 11:45:00 Sending thinblock - thinblock size: 30466 vs block
size: 539103 => tx hashes: 943 transactions: 1
2016-01-03 11:45:50 Sending thinblock - thinblock size: 1970 vs block
size: 64508 => tx hashes: 54 transactions: 1
2016-01-03 11:56:48 Sending thinblock - thinblock size: 31692 vs block
size: 536985 => tx hashes: 983 transactions: 1
2016-01-03 12:03:56 Sending thinblock - thinblock size: 26794 vs block
size: 482127 => tx hashes: 829 transactions: 1
2016-01-03 12:04:06 Sending thinblock - thinblock size: 273 vs block
size: 208 => tx hashes: 1 transactions: 1
2016-01-03 12:11:36 Sending thinblock - thinblock size: 23449 vs block
size: 389445 => tx hashes: 621 transactions: 1
2016-01-03 12:17:05 Sending thinblock - thinblock size: 22220 vs block
size: 389933 => tx hashes: 687 transactions: 1
2016-01-03 12:28:57 Sending thinblock - thinblock size: 32979 vs block
size: 541396 => tx hashes: 1023 transactions: 1
2016-01-03 12:29:04 Sending thinblock - thinblock size: 3178 vs block
size: 108423 => tx hashes: 92 transactions: 1
2016-01-03 12:38:05 Sending thinblock - thinblock size: 25687 vs block
size: 450724 => tx hashes: 795 transactions: 1
2016-01-03 12:43:59 Sending thinblock - thinblock size: 15180 vs block
size: 322569 => tx hashes: 467 transactions: 1
2016-01-03 13:03:01 Sending thinblock - thinblock size: 47980 vs block
size: 858441 => tx hashes: 1492 transactions: 1
2016-01-03 13:40:30 Sending thinblock - thinblock size: 54828 vs block
size: 771972 => tx hashes: 1706 transactions: 1
2016-01-03 13:43:46 Sending thinblock - thinblock size: 54828 vs block
size: 771972 => tx hashes: 1706 transactions: 1
2016-01-03 13:54:00 Sending thinblock - thinblock size: 39324 vs block
size: 590128 => tx hashes: 1189 transactions: 4