Microeconomics of a dynamic size limit

[snakecharmr1024]

What if there was a merkle tree of subblocks in the blockchain, and you could verify that X BTC had moved "into" (i.e. all transactions containing these TxOuts occur in the subblock) a subblock, Y BTC had been moved "out" of the subblock, and X >=Y. If none of your transactions occurred in a subblock, you would not need to get access it or the transaction history inside it, but you could still see that it is impossible for it to have diluted your holdings.

I'm glad you bring this up, it's related to something I've been mulling over for a while. The blockchain is essentially one of many topological sorts of the transaction set, which can be thought of as a partially ordered set.

Along one axis, two opposite extreme alternatives would be
1 - have a different block for each transaction (essentially make txs == blocks)
2 - have a block propagate every 10 years instead of 10 minutes

Neither of these are desirable, clearly, but this illustrates how the blocksize limit is closely related with block propagation time. In other words, if we changed the 10 minutes to 1 minute, we'd effectively be able to process 10 times as many transactions with the same blocksize limit...

Another nearby idea (sorry for the nonlinear ramble): Since we really just want a topological sort or partial ordering of transactions, we don't actually need the blockchain to be linear. It could be a poset that preserves the ordering of transactions. Blocks could have multiple parent and child blocks. Block A would have a secure reference (hash in the header) back to blocks B_i for each block that had a transaction that was a parent to a transaction in Block A (excluding A itself). So this blockswarm, if you will, would facilitate downloading only relevant transactions. Also, this abstraction recurses nicely, so we could have blocks of blocks and so forth, making a tree of nested relevant contexts that all respect the ordering of transactions, with the depth parametrizing the tradeoff between resources and security.

This idea is incomplete, I'm not sure how consensus would be reached on which swarm is best (sum of work over whole swarm? sum only on relevant branches?). I'm also not sure if it introduces new difficulties in detecting double spends. Some miners would still need to see all transactions, and it might introduce a lot more orphaning. Anyways, it's a thought. Hope this didn't stray too far off topic...

 

[freetrader]

What do you think about making the "dynamic size limit" proposed by @Gavin Andresen (or something similar) not a limit but an
"advice"?
[...]

The block closer to the advised size wins.

I think a rational miner would no longer choose to deviate from the last advice in order to increase the block size cap, if they can be swiftly defeated by just one other miner sticking to it.

This might well lead to practically no-one increasing the size of their blocks, because the incentive of higher fees through larger block size has been effectively neutered -- unintentionally rendering the dynamic algorithm useless.

 

[HostFat]

@freetrader
Hmm, I agree.
I think that the easier solution is making the past-advise the minimum advice and the new-advice ("Maximum = some multiple of those percentages") the new maximum.
So there will be a free space of competition (between the minimum and the maximum) where the rule is the first block noticed by the nodes with higher work (as it is now)

Anyway, I hope that this idea can bring better ones than mine ;D

@snakecharmr1024
I'm not sure, but maybe this can be interesting to you.
https://docs.google.com/document/d/13s6BKzRq9oD5Me55JBRzR7BdvjJ44QKqPu2lf-JsAlU/edit

 

[Peter R]

I think the ideal solution would be along the lines of what @HostFat suggested. The key concept being that the block size is unlimited by the protocol (it's not part of the consensus layer) but there is "guidance" that is somehow offered and loosely enforced that results in a high likelihood of orphaning excessive blocks.

Already, excessive blocks have a high probability of being orphaned simply due to their increased propagation time. But if this effect could be reliably amplified, then perhaps the "TB spam block fear" goes away completely.

One idea came to me after reading “The Bitcoin Mining Game," by Dr. Nicolas Houy. He analyzes the transaction fee market from a game theory perspective. While I analyzed in detail the case of many small miners (such that the “self-propagation” advantage was negligible), Houy considers in detail the case of two miners, each with different hash powers where the self-propagation advantage is significant.

In the two-miner case, there appears to exist a “game theoretic” limit to the maximum size of a block that a rational miner will produce regardless of the fees paid. In other words, even if the fees per byte become arbitrarily high, a miner controlling a fraction of the network hash power will not produce an arbitrarily large block.

The lower-bound for the size of this "infinitely expensive" block is Q_c = z*T, where z is the network propagation impedance (seconds / MB) and T is the block time (10 min). I refer to Q_c as the "network block size capacity"--it's equal to the size of the block that would be take 10 minutes to propagate. [Hat tip to @theZerg for this idea].

Perhaps reasonable guidance would be for miners to agree to orphan blocks greater than Q_c. When new research regarding Q_c is published--and if there's demand for more capacity--miners could issue new guidance in some sort of decentralized way. [Right now Q_c is probably about 35 MB].

Nodes would use Bitcoin Unlimited's "meta-cog" logic so that excessive blocks could be accepted when necessary to track consensus, even if the operator forgot to increase his block size limit.

 

[awemany]

@Peter R.:

Another thing worth mentioning (again) in the debate is that I think that the 1MB is effectively forcing the fee market already. I think any blocksize limit is theoretically forcing the fee market. (And before any small blocker comes out of the woodwork now: I think only recently is this effect becoming non-negligible).

If you look more closely, your described possible dead-weight loss is just part of the picture.

I remember that Gavin had a blog post describing the observed fee market vs. transaction confirmation time.
Basically, miners apparently have a preference to cast high-paying transactions into blocks first.

Of course, orphan cost is already an incentive for miners to include high-fee TXN first.

But also, due to the Poisson nature of the mining process, there are dry spells in generated blocks. Even if mean transaction rate is only 500kB, this will mean that some 1MB blocks will be full and transactions have to spill over into later blocks. This artificially increases transaction delays and skews the fee market - even though the mean blocksize is well below max.

This should be an effect forcing the fee market (vs. transaction time) that might be observable right now.

Has this been further investigated?

 

[awemany]

To extend on my post, I (probably re-)did a very simple simulation today, basically of the 'capacity cliff effect' (to use Mike Hearn's words). Preliminary data!

Transactions are trickling in Poisson distributed into an unlimited mempool, with varying rate. With an average rate of once per 600s, transactions are put into blocks, always taking the oldest transactions first (too see how the network operates when under load and but assuming most/all transactions are valid and assuming miners are nice in a 'no transaction left behind' sense). The 1MB limit is simulated by assuming all transactions are 300 bytes of size and so at most 3333 transactions are put into a single block. The idea is to look at the effect of transactions piling up and thus causing longer delays.

I averaged 8 simulations with 1e7 transactions per rate bin (takes a while, is slow, in python...) and in the picture below, I am plotting the mean confirmation time of a transaction. Error bars are 1-sigma of the standard-deviation for each rate bin.

The effect is rare but if a pile up occurs, it is strongly affecting the confirmation time.

As you can see, we're in the forced transaction market already. When we're closer to 4txn/s, we'd have about double the usual confirmation time (~1280s @ 4.1 txn/s). Purely from a gut feeling, I'd guess that at this point, people who are not aware of the whole blocksize issue will complain. From this, I gather that some of the annoyances that we have seen so far are probably not due to stress tests but simply one of those rare but existing long-tail events annoying users.

Note also that this is the mean time. The tail of the longest-confirming txn might be a lot worse. Unfortunately, I didn't save the intermediate data yet, so I have to rerun this to get some more ideas on that.

 

[Peter R]

Nice work, @awemany!

Did you happen to compare your results to this?:

http://hashingit.com/analysis/34-bitcoin-traffic-bulletin

It seems the previous investigators made an error regarding the probability distributions. But I'm not sure if that was just an error in their presentation, or also in their simulations [or maybe I'm still not understanding something].

Also, can we solve this problem analytically?

 

[awemany]

@Peter R.

So he's aiming at essentially the same thing as I did. He also has a corrected page up now. I have to admit I didn't look very carefully at his code yet.

That said, our results agree pretty well, up to (but excluding) the 100% saturation case.

In this graph,

he's doing a simulation for up to 100% load. I think there must be a problem here, as at 100% load the mean confirmation time graph (as I have plotted in my post above) clearly becomes singular. With anything just barely above 100% of load, the network will simply not catch up anymore and the backlog and mean confirmation time will go to infinity. The capacity cliff.

In my simulation, the problem becomes that statistics becomes bad and the cumulative confirmation time distribution shifts towards infinity. But this is much closer to what I would expect for this case.

Here is my result:

Here's an overlay of my plot onto his plot:

So both sims do quite agree well for anything that is not closely approaching the singularity. As I said above, I believe he must be wrong in the extreme case.

I am, too (too optimistic - I am biased towards earlier confirmation as I assume an empty mempool at the beginning of the simulation). That's also why I excluded 100% loading in my other plot in the post above.

However, my simulation at least shows this effect of divergence at 100%, whereas his doesn't do that at all and shows this funny smooth curve. (I also probably the worse statistics as I have unoptimized python code...)

My plot here is for 10^8 transactions for each curve, starting with an empty mempool.

I use linearly spaced bins of 100 seconds each for my above plots and just plot logarithmically. I expect hashingit.com is doing the same.

/u/jstolfi made a fine comment on reddit saying that a purely Poisson transaction arrival process is optimistic, and I agree. It would be interesting to see whether some kind of timing distribution could be extracted from real Bitcoin transaction data. Sadly, I don't have the data from a properly instrumented full node that would also track the initial arrival time of transactions. Is such a data set available?

If anything has a good idea/pointer, I'd like to hear about that.

That said, I am also wondering whether there is an analytical way to describe this. It looks easy, though entangling the first (transactions) with the second (blocks) Poisson process does make this hard to approach for me.

Assuming a constant transaction rate as a simplification would probably go a
long way in getting closer to an analytical solution. (In this context, the large blocks assumption...)

If there is interest, I can put my code onto github. It is really just ~60 lines of code for the sim, excluding my ad-hoc plotting of the data.

 

[Peter R]

@awemany

I agree with the note about the expected divergence for the 100% saturation case.

For all other cases, the system enters "statistical equilibrium" where transactions are posted at the same rate--on average--that they're being committed into blocks. However, for the 100% case, statistical equilibrium is never reached; instead the backlog continually grows. So both your curve and his curve are incorrect for the 100% case. Instead, I think you'd want to show a curve at 95%, 98%, 99%, 99.5%, etc, showing the pattern that happens at saturation. The difficulty is that the simulations would need to run for a lot longer as it will take a very long time to reach statistical equilibrium.

I also agree that the best approach to solving this analytically would be to assume a constant transaction rate and take it from there.

 

[Gavin Andresen]

A constant transaction rate is a good place to start. Then I think adding in the time-of-day variability in transaction submission rate would be the second-most important effect.

I doubt the poisson distribution of individual transaction submissions has much of an effect on anything besides theoretical peak network bandwidth usage (and only at some point in the future when the network is not so stupid about how new blocks are announced....).