Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 32F8AD03 for ; Sun, 30 Aug 2015 11:49:28 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-lb0-f170.google.com (mail-lb0-f170.google.com [209.85.217.170]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6F0C019D for ; Sun, 30 Aug 2015 11:49:26 +0000 (UTC) Received: by lbbsx3 with SMTP id sx3so48025602lbb.0 for ; Sun, 30 Aug 2015 04:49:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:from:date:message-id:subject:to:content-type; bh=F/BTDM9df5XsPcReUgrmmrICj4gTJyeoEzw2WJJJAEA=; b=P4aECnrh3H/7f9HViKm5CBgIHvpxVCWHlg7/LvTGF+bmQSpDkmB0yuCn3SMnFpouKa ziOIhLuJrslFmDn+Ids7t4odaf7YnFW/+I6CQCkWJQzs7JcnoVY5sFQIln36Ese1r/Ln p9Z0+TTiH+9ZCjnbzDXPDRqNW4HQKo7Jmvad+SQu8dg1oHOUZ0Dbz5X4FvV+poA3Ha8J j4tNzHemaNynM07s42KLEG8lpAVf0vExu2OFCnh8hMERoKmHmYNVI6FH+NwIImeBpUYO YXtiC/8qDRVI8qhPcq51ug75KI1xxFjWypFLsVE4Sh9EXWfITlU0qisEW5Z80mJ5JQxa AXYQ== X-Received: by 10.152.36.103 with SMTP id p7mr444941laj.90.1440935364755; Sun, 30 Aug 2015 04:49:24 -0700 (PDT) MIME-Version: 1.0 Received: by 10.112.143.229 with HTTP; Sun, 30 Aug 2015 04:49:05 -0700 (PDT) From: Daniele Pinna Date: Sun, 30 Aug 2015 13:49:05 +0200 Message-ID: To: bitcoin-dev@lists.linuxfoundation.org Content-Type: multipart/alternative; boundary=089e0158b60e8f864d051e85e823 X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_20,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] Unlimited Max Blocksize (reprise) X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 30 Aug 2015 11:49:28 -0000 --089e0158b60e8f864d051e85e823 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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, =EF=AC=81rst analyzed in [3]" I don't recall whethe= r 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-U= ncapped-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 describe= d > 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 no= t > stem from the act of propagating large blocks but rather from the block > subsidies which allow miners to mine unnecessary large blocks irregardles= s > 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 fr= om > 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 invoki= ng > rates of technological advances (see Gavin's original posts) don't mean > anything. Rational miners will NOT be incentivized to mine gargantuan spa= m > 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 (unlik= e > smaller ones) will lose the incentive to mine an un full block this eveni= ng > 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. T= he > 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-Exist= s-Without-a-Block-Size-Limit > > --089e0158b60e8f864d051e85e823 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

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 3D"i"= of size =C2=A0and fee density=C2=A03D"\phi_i", many transactions 3D"j"=C2=A0will= exist such that 3D"s_j<s_i"= =C2=A0and 3D"\phi_j=3D\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 t= his breaks down in small mempool scenarios where the discreteness of transa= ctions 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= >


Thi= s was pointed out to me by Tom Harding.

Choosing what th= e optimal way of choosing transactions to be included in a block is a knaps= ack problem (an NP-complete problem!):

https://en.wikipedia.org/wi= ki/Knapsack_problem

For which your suggested s= olution, which is by no means exact, is known as the "Greedy Approxima= tion Algorithm". This algorithm in turn works best only when a very la= rge quantity of high density transactions is available in the mempool.

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

Jus= t thought I would throw this your way.

Daniele

---------- Forwarded message ----------
From:=C2=A0Tom Harding=C2=A0<t= omh@thinlink.com>
Date: Sat, Aug 29, 2015 at 10:21 PM
Subject: Re:= [bitcoin-dev] Unlimited Max Blocksize (reprise)
To: Daniele Pinna <daniele.pinna@gma= il.com>


Daniele --

Thanks!=C2= =A0 I printed it and read the whole thing.=C2=A0 It's really a great st= ep forward building on the Peter R paper. The conclusions are enticing.=C2= =A0 I'm looking forward to understanding it in more detail and particip= ating in the discussion.

I find your work to be rational and scholar= ly without being obscure, pedantic, or getting caught up in unimportant det= ails.=C2=A0 It has a long-term focus.=C2=A0


"The= optimal strategy,=C2=A0=EF=AC=81rst analyzed=C2=A0in [3]"=C2= =A0 I don't recall whether Peter R considered constrained block space o= r not, but if it is considered, simple fee-density prioritization is not ne= cessarily 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=C2=A0<tomh@thinlink.com>=C2=A0wrot= e:

Thanks= for posting this.=C2=A0 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 redirec= t the course of the bitcoin protocol but it's totally fine to consider = complex miner voting protocols as a hard fork option.

I b= elieve that this community has not given due weight to the analysis propose= d by Peter__R on the existence of fee markets with=C2=A0 uncapped max block= sizes. The critiques made toward his work were in no way definitive and dis= cussion 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 hardfork= s every two years until we all trust the fee market dynamics.

The main critique to uncapped max blocksizes which I've heard stem= s from our incapacity to quantify the advantages that large miners have ove= r smaller ones. As I will show in an upcoming paper, these advantages do no= t stem from the act of propagating large blocks but rather from the block s= ubsidies which allow miners to mine unnecessary large blocks irregardless o= f the fees contained therein. One typical example is Peter Todd's sugge= sted attack whereby a miner creates a massive block filled with spam transa= ctions that pay himself solely to slow down the rest of the network and gai= n an advantage. Putting aside the increased orphan risk arising from the pr= opagation of such a large block, this attack would never be viable if it we= ren't for the existence of current block subsidies.=C2=A0

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

I truly hope this matter gets the consideration it deserves. Parti= cularly with the upcoming scaling workshops.

Dpinna

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

"I ra= n some simulations, and if blocks take 20 seconds to propagate, a
networ= k with a miner that has 30% of the hashing power will get 30.3% of the bloc= ks."

Peter_R's analysis of fee markets in the ab= sence 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 block= sizes is that we'll connected miners can cut out smaller miners by grat= uitously filling up blocks with self-paying transactions. This only works b= ecause block subsidies exist. The moment block rewards become comparable to= block TX fees, this exploit ceases to be functional.

Bas= ically, 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 o= nes) will lose the incentive to mine an un full block this evening the play= ing=C2=A0 =C2=A0=C2=A0 =C2=A0=C2=A0 =C2=A0=C2=A0 =C2=A0=C2=A0 =C2=A0=C2=A0 = =C2=A0=C2=A0 =C2=A0=C2=A0 =C2=A0=C2=A0 =C2=A0field.

In th= is context, large blocksizes as proposed by BIP100-101 hope to stimulate th= e 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 o= f mine centralization.

Dpinna

[1]=C2=A0= http://www.scribd.= com/mobile/doc/273443462/A-Transaction-Fee-Market-Exists-Without-a-Block-Si= ze-Limit



--089e0158b60e8f864d051e85e823--