maximum unconfirmed transactions

[David Rabahy]

I hunted around some but didn't find a topic documenting maximum unconfirmed transactions https://blockchain.info/unconfirmed-transactions.  I've watched for only a short while and saw it peak around 2,690 just before block 280873 was added to the chain (thank you Slush) after some 48 minutes had elapsed from the previous block.

Little things like this entertain me.  What is the maximum anyone has observed so far?

[solex]

I hunted around some but didn't find a topic documenting maximum unconfirmed transactions https://blockchain.info/unconfirmed-transactions.  I've watched for only a short while and saw it peak around 2,690 just before block 280873 was added to the chain (thank you Slush) after some 48 minutes had elapsed from the previous block.

Little things like this entertain me.  What is the maximum anyone has observed so far?

There was 11,979 pending on April 8th last year. I think it was a (failed) spam attack.
http://www.flickr.com/photos/93641348@N04/8629120233/

[David Rabahy]

Wow!  Has anyone considered what a functional maximum might be?  I mean, how  many does it take to hit the limit above which the software fails?

[David Rabahy]

Per https://blockchain.info/unconfirmed-transactions, at height 346151, we have a recent count of unconfirmed transactions around 5,700 and rising fast.  Does anyone chart the unconfirmed count over time?

[shorena]

Per https://blockchain.info/unconfirmed-transactions, at height 346151, we have a recent count of unconfirmed transactions around 5,700 and rising fast.  Does anyone chart the unconfirmed count over time?

I have seen >11k in the recent past, charts here -> http://213.165.91.169/

some snapshots:

[David Rabahy]

Sweet.  So, since a single 1MB block can clear something like 2,400 transactions, it might take 5 or more blocks to clear a backlog of 12,000 transactions (if no more are flowing in (unlikely)).  Suppose we have a steady workload of 1,200 new transactions flowing in, in that situation it will take 10 blocks to clear the backlog;

average time	incoming	backlog
0	...	12,000
10m	1,200	10,800
20m	1,200	9,600
30m	1,200	8,400
40m	1,200	7,200
50m	1,200	6,000
60m	1,200	4,800
70m	1,200	3,600
80m	1,200	2,400
90m	1,200	1,200
100m	1,200	small

This is an unlikely scenario.  Clearly some burst of incoming transactions built up the backlog.  Every additional burst exceeding 2,400 per 10 minutes will grow the backlog more.

[David Rabahy]

I've created a Google Sheet https://docs.google.com/spreadsheets/d/1lD50Q_NQOHAQk-q3X1hxh_Dlg-4SAujc1pa3UR4gVs0 to provide a tool for exploring backlogs.

[true-asset]

Is there graceful handling of that boundary case where miners run out of memory trying to queue too many unconfirmed transactions in Bitcoin Core 0.10?

[zetaray]

It must take a dev or a pool operator to answer this. What is the theoretical maximum of the memory pool? It should be well above 20,000. If we are getting close to the max, we should have heard about it more.

[David Rabahy]

If the average transaction is 400 bytes then 20,000 transactions would only take up 8,000,000 bytes or about 8MB.  I just bet the memory pool is much larger than that.

[Cryddit]

It's a mistake to think it's just the bursty rate of transactions that cause big backlogs occasionally; transactions are fairly steady most of the time compared to the block rate.

Sometimes it's a couple of hours until the next block, and sometimes it's about ten seconds until the next block.  

The biggest backlogs usually happen when three or four blocks in a row have taken a long time to solve.  Especially if they were found by miners who don't wanna build blocks more than a quarter-megabyte big, although that's much less a concern once header-first block transmission is solved.

But yeah, the transaction rate is very bursty.  And once in a while you get a whole lot of  transactions during a several-hour period where you get very few blocks.

[David Rabahy]

One wonders if the block interval distribution pattern, although designed to target a 10 minute average, changes as the difficulty increases.  Where's the median?  What is the standard deviation?  Although it is mostly academic since the effective average suffices to analyze the backlog over long enough periods of time.  Then again a focus on the peaks to avoid breaking the memory pool is worth the effort.

The most provocative point is the one about miners constraining their block size; why do they do it?  What advantage do they gain?  Where can I learn more about header-first block transmission?

[winchancer]

Thanks for the info!

[shorena]

One wonders if the block interval distribution pattern, although designed to target a 10 minute average, changes as the difficulty increases.  Where's the median?  What is the standard deviation?  Although it is mostly academic since the effective average suffices to analyze the backlog over long enough periods of time.  Then again a focus on the peaks to avoid breaking the memory pool is worth the effort.

The most provocative point is the one about miners constraining their block size; why do they do it?  What advantage do they gain?  Where can I learn more about header-first block transmission?

I think you are looking for O(1) Propagation -> https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2

Miners are limiting their block size for two (possibly more) reasons.

The first is from very blurry memory and is probably wrong, so I will not even start to explain it in order to avoid confusion. Its related to a blocks merkle root IIRC.

The second is that a block has to propage through the network in order to be accepted by other miners. The propagation takes time depending on the available bandwith and the size of the block. Its pretty easy to understand. 1MB takes longer to transfer than a few kbytes, thus a smaller block size reduces the chance for a split and orphans.

[Cryddit]

The most provocative point is the one about miners constraining their block size; why do they do it?  What advantage do they gain?  Where can I learn more about header-first block transmission?

Up until v 0.10.0 (the most recent release) miners had a problem making their blocks too big because big blocks propagated across the networks more slowly. This meant that if two miners found a block at the same time or close to the same time, the one with the smaller block was more likely to reach more of the network faster, making the other block an orphan.  Since an orphan block gets no block subsidy, the miners were looking at a situation where larger blocks actually reduced their profits measurably.

But v 0.10.0 Introduces header-first block transmission, which means now miners that find a block can just transmit the header.  And the headers are about the same size, so the orphan risk is now the same regardless of how full the block may be. It's also more efficient because the tx are already out there circulating - all the nodes have them in the mempool.  Once the nodes get the header, they can build the block themselves - maybe requesting a few tx they don't already have from peers. 

There is also a slight issue with the Merkle trees, as Shorena pointed out:  The merkle trees that bitcoin builds for its blocks have "steps" in size where they're most efficient (and most secure!) for a number of transactions which is a power of two.  So some miners will build, say, a block of 128 transactions rather than 200, or 256 transactions rather than 310,  first because if you can't fill the next power of 2, the bigger merkle tree is being used inefficiently and second because if you can't fill the next power of 2, then one side of the merkle tree is built from far fewer transactions and unbalanced, so it becomes potentially easier to analyze or predict.  But no ways to attack anything we care about based on this imbalance have yet been identified. 

[DeathAndTaxes]

But v 0.10.0 Introduces header-first block transmission, which means now miners that find a block can just transmit the header.  And the headers are about the same size, so the orphan risk is now the same regardless of how full the block may be. It's also more efficient because the tx are already out there circulating - all the nodes have them in the mempool.  Once the nodes get the header, they can build the block themselves - maybe requesting a few tx they don't already have from peers.  

v0.10.0 doesn't speed up block propagation times.  The header first protocol is to allow new nodes (or nodes rejoining the network) to find the longest chain quicker.  Nodes can sync up to the best chaintip using headers first, and download missing blocks in parallel across multiple peers.  This spreads out the load on the network and allows faster syncing times but it doesn't speed up mining at all.  'Headers first' isn't 'headers only', the next step is to download the block 'body' and that takes just as long.

Related to but separate from 'header first' is IBLT which will allow O(1) propagation of blocks if the other nodes already have all the txns in the block in their local memory pool.  Even with IBLT a receiving node can't request the missing txns because IBLT only helps them identify the txns in the block if they already have them.   If they are missing one or more they will know that but they won't know which specific txns they are missing.  IBLT can be considered a 'header + metadata' message*.  Using the meta data and the same deterministic transaction sorting used by both nodes will allow the receiving node to determine the txns in the block if the receive node has a superset of the block txns in its memory pool*. IBLT hasn't be implemented in v0.10.0.  Right now larger blocks still carry a larger orphan 'cost' than smaller blocks.

* In practice it is probably going to be more complex.   Those not interested in the complexity can just abstract it as header + metadata but a node finding a new block can't definitely know which txns other nodes currently have in their memory pool.  IBLT will probably be more like 'header + metadata + full low-propagation txns'.  The mining node will include in the message the txns that are unlikely to be in the memory pool of the receiving node to avoid IBLT failing.  Anything which is non-standard is unlikely to be in the memory pool of any node following standard rules.  The mining node can't change that.  If they relay the non-standard txn in advance of the block most nodes will simply drop it.  Stale txns (very old unconfirmed txns) may also be dropped by nodes to save space in the memory pool.  If the mining nodes is aware of unconfirmed double spends then it should expect that some portion of the network is unaware of the txn in its block so that would be another txn to include the full txns.  In the future there may be other reasons why a txn isn't well propagated.  It may become complicated if the memory pool becomes very large and different nodes retain different subsets of it to conserve resources.  Still IBLT has the ability to significantly reduce the propagation delay even if only used for a subset of the block txns.  It doesn't however allow a receiving node to know which txns it is missing and thus it can't request missing txns.

[Cryddit]

v0.10.0 doesn't speed up block propagation times.  The header first protocol is to allow new nodes (or nodes rejoining the network) to find the longest chain quicker.  New nodes can sync up headers first.  Find the longest chain and then allows download missing blocks in parallel across multiple peers.  This spreads out the load on the network and allows faster syncing times but it doesn't speed up mining at all.  'Headers first' isn't 'headers only', the next step is to download the block 'body' and that takes just as long.

Aw crap, I thought that headers-first applied to new blocks too.  Looks like I gave it too much credit. 

Still, headers-first is an awesome improvement.  It shortens the chain download time dramatically.

[solex]

Even with IBLT a receiving node can't request the missing txns because IBLT only helps them identify the txns in the block if they already have them.   If they are missing one or more they will know that but they won't know which specific txns they are missing.  IBLT can be considered a 'header + metadata' message*.  Using the meta data and the same deterministic transaction sorting used by both nodes will allow the receiving node to determine the txns in the block if the receive node has a superset of the block txns in its memory pool*.

* In practice it is probably going to be more complex.   Those not interested in the complexity can just abstract it as header + metadata but a node finding a new block can't definitely know which txns other nodes currently have in their memory pool.  IBLT will probably be more like 'header + metadata + full low-propagation txns'.  The mining node will include in the message the txns that are unlikely to be in the memory pool of the receiving node to avoid IBLT failing.  Anything which is non-standard is unlikely to be in the memory pool of any node following standard rules.  The mining node can't change that.  If they relay the non-standard txn in advance of the block most nodes will simply drop it.  Stale txns (very old unconfirmed txns) may also be dropped by nodes to save space in the memory pool.  If the mining nodes is aware of unconfirmed double spends then it should expect that some portion of the network is unaware of the txn in its block so that would be another txn to include the full txns.  In the future there may be other reasons why a txn isn't well propagated.  It may become complicated if the memory pool becomes very large and different nodes retain different subsets of it to conserve resources.  Still IBLT has the ability to significantly reduce the propagation delay even if only used for a subset of the block txns.  It doesn't however allow a receiving node to know which txns it is missing and thus it can't request missing txns.

The full transactions for the block are all included in the IBLT but they are XOR'd together such that successfully decoding them becomes probabilistic. So, if there are 18 transactions overlaying each other, and 17 are known to the receiver, then 17 can be peeled off leaving the 1 unknown transaction available to use. However, if >1 in the same cell are unknown to the receiver then decode fails.
Continuing the example, there could be 18 transactions overlaying each other and 18 different receivers each missing 1 different transaction from their mempools, yet they will all be able to successfully decode the missing transaction and continue building the block from the IBLT.

Yes. If an IBLT is accepted by most nodes and being built upon, then a node which fails to read it will need to request the standard block to resync.