[bitcoin-dev] Unlimited Max Blocksize (reprise)

[bitcoin-dev] Unlimited Max Blocksize (reprise)

[Peter R]

[-- Attachment #1: Type: text/plain, Size: 1129 bytes --]

Hello Tom, Daniele --

Thank you Tom for pointing out the knapsack problem to all of us.  I will include a note about it when I make the other corrections to the Fee Market paper.

I agree with what Daniele said previously.  The other "non-greedy" solutions to the knapsack problem are most relevant when one is choosing from a smaller number of items where certain items have a size similar to the size of the knapsack itself.  For example, these other solutions would be useful if transactions were often 50 kB, 100 kB, 400 kB in size, and we were trying to find the optimal TX set to fit into a 1 MB block.  

However, since the average transaction size is ~500 bytes, even with a block size limit of 1 MB, we are looking at up to 2000 transactions.  The quantization effects become small.  Rather than 22 triangles as shown in Fig. 3 (http://imgur.com/rWxZddg), there are hundreds or a few thousands, and we can reasonably approximate the discrete set of points as a continuous curve.  Like Daniele pointed out, the greedy algorithm assumed in the paper is asymptotically optimal in such a case.

Best regards,
Peter

[-- Attachment #2: Type: text/html, Size: 1505 bytes --]

Re: [bitcoin-dev] Unlimited Max Blocksize (reprise)

[Tom Harding]

[-- Attachment #1: Type: text/plain, Size: 168 bytes --]

On 8/30/2015 9:54 AM, Peter R wrote:
> Like Daniele pointed out, the greedy algorithm assumed in the paper is
> asymptotically optimal in such a case.

I'm convinced.


[-- Attachment #2: Type: text/html, Size: 553 bytes --]

Re: [bitcoin-dev] Unlimited Max Blocksize (reprise)

[Daniele Pinna]

[-- Attachment #1: Type: text/plain, Size: 6849 bytes --]

I think that the argument for Peter's optimal block construction algorithm
(leading to the definition of the Fee Demand Curve) is that in the limit of
a mempool with a very large number of transactions, you should be able to
assume that for any given transaction [image: i] of size [image: s_i] and
fee density [image: \phi_i], many transactions [image: j] will exist such
that [image: s_j<s_i] and [image: \phi_j=\phi_i]. This means that, in
solving the knapsack problem, one has the choice of including what
effectively amounts to fractions of transactions. This in turn results in
an unbounded knapsack problem for which Peter's greedy algorithm is an
asymptotically optimal solution.

Obviously this breaks down in small mempool scenarios where the
discreteness of transactions can not be washed away (such as the current
state of the network).

I hope this clarifies your point.

Daniele

---------- Forwarded message ----------
From: Daniele Pinna <daniele.pinna@gmail.com>
Date: Sun, Aug 30, 2015 at 1:11 PM
Subject: Another issue with the Fee Demand curve
To: Peter R <peter_r@gmx.com>


This was pointed out to me by Tom Harding.

Choosing what the optimal way of choosing transactions to be included in a
block is a knapsack problem (an NP-complete problem!):

https://en.wikipedia.org/wiki/Knapsack_problem

For which your suggested solution, which is by no means exact, is known as
the "Greedy Approximation Algorithm". This algorithm in turn works best
only when a very large quantity of high density transactions is available
in the mempool.

This wouldn't invalidate your proof but it may significantly alter the
optimal block size value.

Just thought I would throw this your way.

Daniele

---------- Forwarded message ----------
From: Tom Harding <tomh@thinlink.com>
Date: Sat, Aug 29, 2015 at 10:21 PM
Subject: Re: [bitcoin-dev] Unlimited Max Blocksize (reprise)
To: Daniele Pinna <daniele.pinna@gmail.com>


Daniele --

Thanks!  I printed it and read the whole thing.  It's really a great step
forward building on the Peter R paper. The conclusions are enticing.  I'm
looking forward to understanding it in more detail and participating in the
discussion.

I find your work to be rational and scholarly without being obscure,
pedantic, or getting caught up in unimportant details.  It has a long-term
focus.


"The optimal strategy, first analyzed in [3]"  I don't recall whether Peter
R considered constrained block space or not, but if it is considered,
simple fee-density prioritization is not necessarily optimal (it is a
knapsack problem).




On 8/29/2015 10:16 AM, Daniele Pinna wrote:

Here you go Tom!

https://www.scribd.com/doc/276849939/On-the-Nature-of-Miner-Advantages-in-Uncapped-Block-Size-Fee-Markets

Daniele Pinna, Ph.D

On Thu, Aug 27, 2015 at 12:59 AM, Tom Harding <tomh@thinlink.com> wrote:

>
> Thanks for posting this.  I'm very interested to read your paper when it
> is available.
>
>
>
> On 8/26/2015 3:22 PM, Daniele Pinna via bitcoin-dev wrote:
>
> I don't get how it's very risky to have the Mike and Gavin redirect the
> course of the bitcoin protocol but it's totally fine to consider complex
> miner voting protocols as a hard fork option.
>
> I believe that this community has not given due weight to the analysis
> proposed by Peter__R on the existence of fee markets with  uncapped max
> blocksizes. The critiques made toward his work were in no way definitive
> and discussion just stopped. Is it the math that bothers people?
>
> If his work stands the test of scrutiny, then a controlled raising of the
> max blocksize in the interim to ease into the fee market dynamic described
> is the best option. Possibly a stepwise BIP101 where the community
> hardforks every two years until we all trust the fee market dynamics.
>
> The main critique to uncapped max blocksizes which I've heard stems from
> our incapacity to quantify the advantages that large miners have over
> smaller ones. As I will show in an upcoming paper, these advantages do not
> stem from the act of propagating large blocks but rather from the block
> subsidies which allow miners to mine unnecessary large blocks irregardless
> of the fees contained therein. One typical example is Peter Todd's
> suggested attack whereby a miner creates a massive block filled with spam
> transactions that pay himself solely to slow down the rest of the network
> and gain an advantage. Putting aside the increased orphan risk arising from
> the propagation of such a large block, this attack would never be viable if
> it weren't for the existence of current block subsidies.
>
> As such, exponential increases to the max blocksize make perfect sense
> since the block reward decreases exponentially also. All arguments invoking
> rates of technological advances (see Gavin's original posts) don't mean
> anything. Rational miners will NOT be incentivized to mine gargantuan spam
> filled blocks in the presence of a vanishing block reward.
>
> I truly hope this matter gets the consideration it deserves. Particularly
> with the upcoming scaling workshops.
>
> Dpinna
> On Aug 21, 2015 11:35 PM, "Daniele Pinna" <daniele.pinna@gmail.com> wrote:
>
> "I ran some simulations, and if blocks take 20 seconds to propagate, a
> network with a miner that has 30% of the hashing power will get 30.3% of
> the blocks."
>
> Peter_R's analysis of fee markets in the absence of blocksize limits [1]
> shows that the hashrate advantage of a large miner is a side-effect of
> coinbase subsidization. As the block rewards get smaller, so will large
> miner advantages. An easy way to think about this is as follows:
>
> Currently, the main critique of larger blocksizes is that we'll connected
> miners can cut out smaller miners by gratuitously filling up blocks with
> self-paying transactions. This only works because block subsidies exist.
> The moment block rewards become comparable to block TX fees, this exploit
> ceases to be functional.
>
> Basically, large miners will still be forced to move full blocks, but it
> will go against their interest to fill them with spam since their main
> source of income is the fees themselves. As a result, large miners (unlike
> smaller ones) will lose the incentive to mine an un full block this evening
> the playing                           field.
>
> In this context, large blocksizes as proposed by BIP100-101 hope to
> stimulate the increase of TX fees by augmenting the network's capacity. The
> sooner block rewards become comparable to block fees, the sooner we will
> get rid of mine centralization.
>
> Dpinna
>
> [1]
> http://www.scribd.com/mobile/doc/273443462/A-Transaction-Fee-Market-Exists-Without-a-Block-Size-Limit
>
>

[-- Attachment #2: Type: text/html, Size: 10661 bytes --]

Re: [bitcoin-dev] Unlimited Max Blocksize (reprise)

[Jorge Timón]

On Thu, Aug 27, 2015 at 12:22 AM, Daniele Pinna via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> I don't get how it's very risky to have the Mike and Gavin redirect the
> course of the bitcoin protocol but it's totally fine to consider complex
> miner voting protocols as a hard fork option.

Maybe this helps undesrtanding the risks of a contentious/schism
hardfork: https://github.com/bitcoin/bips/pull/181/files#diff-e331b8631759a4ed6a4cfb4d10f473caR137
That section can be greatly improved though.

> I believe that this community has not given due weight to the analysis
> proposed by Peter__R on the existence of fee markets with  uncapped max
> blocksizes. The critiques made toward his work were in no way definitive and
> discussion just stopped. Is it the math that bothers people?

I have only skimmed the document, but I believe its conclusions (or
some of them) are right for the current propagation code.
The assumption may not stand if we move to something like IBLT though.
I believe that document also proves that it is
irrational/noncompetitive for miners to include ANY free transactions
at all (like they currently do).
But the analysis is about the effect of the maximum block size on
fees: there's more effects of that consensus rule.
The most important one being that it limits mining centralization (and
centralization in general).
This is true for at least 2 reasons: one is related to block
propagation and it is what is usually described.
At a bigger scale (even with crazy assumptions like constant time
infinite bandwidth, instant [superluminal] communication, zkSNARKS
block validity proofs ) minimum CPU costs will be something to limit
through the maximum block size consensus rule. There's a scale at
which the minimum CPU costs for a miner to be competitive may be so
high that some small miners without the resources to meet that minimum
will become unprofitable.
Admittedly we're not near that scale yet, but if something to take into account.

> The main critique to uncapped max blocksizes which I've heard stems from our
> incapacity to quantify the advantages that large miners have over smaller
> ones.

There are some simulations. See:
http://gavinandresen.ninja/are-bigger-blocks-better-for-bigger-miners

The goal of https://github.com/bitcoin/bitcoin/pull/6382 is to allow
people to do more realistic simulations (by using real full nodes).
That doesn't mean that more simplified simulations are worthless, but
I didn't want people to have to create their own testchain every time
they want to simulate a different size, like rusty had to do for:

http://rusty.ozlabs.org/?p=509

So the "incapacity to quantify the advantages that large miners have
over smaller ones" doesn't really exist.
It would be nice to have more data about this (more sizes, more
network topologies, etc) though.

> As I will show in an upcoming paper, these advantages do not stem from
> the act of propagating large blocks but rather from the block subsidies
> which allow miners to mine unnecessary large blocks irregardless of the fees
> contained therein. One typical example is Peter Todd's suggested attack
> whereby a miner creates a massive block filled with spam transactions that
> pay himself solely to slow down the rest of the network and gain an
> advantage. Putting aside the increased orphan risk arising from the
> propagation of such a large block, this attack would never be viable if it
> weren't for the existence of current block subsidies.

Although smaller subsidies will remove some problems we currently
have, for example, SPV mining (there's no incentive to SPV mine
worthless empty blocks), I don't understand your claim that they will
also solve mining centralization problems related to block
propagation.

> As such, exponential increases to the max blocksize make perfect sense since
> the block reward decreases exponentially also. All arguments invoking rates
> of technological advances (see Gavin's original posts) don't mean anything.

I really dislike basing the consensus rules on predictions about
future technology. For all I know, a terrible war could destroy half
of the global internet infrastructure in the next 5 years.
I prefer simpler increments like in bip102 (although I don't have the
data to know if 2MB is safe mining-centralization-wise at this point
[when mining centralization is pretty bad]).
Arguments against that kind of change are usually along the lines
"then we will have to repeat this same discussion in 1 or 2 years".
I believe that with the proper simulation tools being deployed and a
better general understanding of what the concerns are, the
conversation should be much simpler the next time.

> Rational miners will NOT be incentivized to mine gargantuan spam filled
> blocks in the presence of a vanishing block reward.

Actually some simulations show they in fact have incentive to do just
that in some cases.
But more importantly, we shouldn't assume that all attackers are
rational miners. Maybe a potential attacker is a secret service or a
financial cartel attempting to destroy Bitcoin for whatever reason.

> I truly hope this matter gets the consideration it deserves. Particularly
> with the upcoming scaling workshops.

I truly hope that the discussion can move forward into more productive
territories after the workshop, and I'm particularly interested in
Peter R's presentation, even if I haven't found the time to read his
paper yet. Even if fees are not the main reason why we want to have a
block size maximum, fees are certainly very relevant and anything that
he has mathematically proven in that regard will be useful to this
discussion.

> On Aug 21, 2015 11:35 PM, "Daniele Pinna" <daniele.pinna@gmail.com> wrote:
>
> "I ran some simulations, and if blocks take 20 seconds to propagate, a
> network with a miner that has 30% of the hashing power will get 30.3% of the
> blocks."
>
> Peter_R's analysis of fee markets in the absence of blocksize limits [1]
> shows that the hashrate advantage of a large miner is a side-effect of
> coinbase subsidization. As the block rewards get smaller, so will large
> miner advantages. An easy way to think about this is as follows:
>
> Currently, the main critique of larger blocksizes is that we'll connected
> miners can cut out smaller miners by gratuitously filling up blocks with
> self-paying transactions. This only works because block subsidies exist. The
> moment block rewards become comparable to block TX fees, this exploit ceases
> to be functional.
>
> Basically, large miners will still be forced to move full blocks, but it
> will go against their interest to fill them with spam since their main
> source of income is the fees themselves. As a result, large miners (unlike
> smaller ones) will lose the incentive to mine an un full block this evening
> the playing field.
>
> In this context, large blocksizes as proposed by BIP100-101 hope to
> stimulate the increase of TX fees by augmenting the network's capacity. The
> sooner block rewards become comparable to block fees, the sooner we will get
> rid of mine centralization.
>
> Dpinna
>
> [1]
> http://www.scribd.com/mobile/doc/273443462/A-Transaction-Fee-Market-Exists-Without-a-Block-Size-Limit
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[bitcoin-dev] Unlimited Max Blocksize (reprise)

[Daniele Pinna]

[-- Attachment #1: Type: text/plain, Size: 3539 bytes --]

I don't get how it's very risky to have the Mike and Gavin redirect the
course of the bitcoin protocol but it's totally fine to consider complex
miner voting protocols as a hard fork option.

I believe that this community has not given due weight to the analysis
proposed by Peter__R on the existence of fee markets with  uncapped max
blocksizes. The critiques made toward his work were in no way definitive
and discussion just stopped. Is it the math that bothers people?

If his work stands the test of scrutiny, then a controlled raising of the
max blocksize in the interim to ease into the fee market dynamic described
is the best option. Possibly a stepwise BIP101 where the community
hardforks every two years until we all trust the fee market dynamics.

The main critique to uncapped max blocksizes which I've heard stems from
our incapacity to quantify the advantages that large miners have over
smaller ones. As I will show in an upcoming paper, these advantages do not
stem from the act of propagating large blocks but rather from the block
subsidies which allow miners to mine unnecessary large blocks irregardless
of the fees contained therein. One typical example is Peter Todd's
suggested attack whereby a miner creates a massive block filled with spam
transactions that pay himself solely to slow down the rest of the network
and gain an advantage. Putting aside the increased orphan risk arising from
the propagation of such a large block, this attack would never be viable if
it weren't for the existence of current block subsidies.

As such, exponential increases to the max blocksize make perfect sense
since the block reward decreases exponentially also. All arguments invoking
rates of technological advances (see Gavin's original posts) don't mean
anything. Rational miners will NOT be incentivized to mine gargantuan spam
filled blocks in the presence of a vanishing block reward.

I truly hope this matter gets the consideration it deserves. Particularly
with the upcoming scaling workshops.

Dpinna
On Aug 21, 2015 11:35 PM, "Daniele Pinna" <daniele.pinna@gmail.com> wrote:

"I ran some simulations, and if blocks take 20 seconds to propagate, a
network with a miner that has 30% of the hashing power will get 30.3% of
the blocks."

Peter_R's analysis of fee markets in the absence of blocksize limits [1]
shows that the hashrate advantage of a large miner is a side-effect of
coinbase subsidization. As the block rewards get smaller, so will large
miner advantages. An easy way to think about this is as follows:

Currently, the main critique of larger blocksizes is that we'll connected
miners can cut out smaller miners by gratuitously filling up blocks with
self-paying transactions. This only works because block subsidies exist.
The moment block rewards become comparable to block TX fees, this exploit
ceases to be functional.

Basically, large miners will still be forced to move full blocks, but it
will go against their interest to fill them with spam since their main
source of income is the fees themselves. As a result, large miners (unlike
smaller ones) will lose the incentive to mine an un full block this evening
the playing field.

In this context, large blocksizes as proposed by BIP100-101 hope to
stimulate the increase of TX fees by augmenting the network's capacity. The
sooner block rewards become comparable to block fees, the sooner we will
get rid of mine centralization.

Dpinna

[1]
http://www.scribd.com/mobile/doc/273443462/A-Transaction-Fee-Market-Exists-Without-a-Block-Size-Limit

[-- Attachment #2: Type: text/html, Size: 4204 bytes --]