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 Date: Sun, Aug 30, 2015 at 1:11 PM Subject: Another issue with the Fee Demand curve To: Peter R 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 Date: Sat, Aug 29, 2015 at 10:21 PM Subject: Re: [bitcoin-dev] Unlimited Max Blocksize (reprise) To: Daniele Pinna 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 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" 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 > >