path: root/7c/58b1ac6135551465a101c008f897f605733c4d

Return-Path: <daniele.pinna@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 32F8AD03
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 30 Aug 2015 11:49:26 +0000 (UTC)
Received: by lbbsx3 with SMTP id sx3so48025602lbb.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <daniele.pinna@gmail.com>
Date: Sun, 30 Aug 2015 13:49:05 +0200
Message-ID: <CAEgR2PGsOgdTKMXAabeRZfREciTntj9uaBDLPuFz84rUoSVSLw@mail.gmail.com>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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<s_i] and [image: \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 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, =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 <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 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" <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 (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

<div dir=3D"ltr"><div class=3D"gmail_quote"><div dir=3D"ltr"><br clear=3D"a=
ll"><div><div><div>I think that the argument for Peter&#39;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 <img alt=3D"i"=
 title=3D"i" src=3D"http://latex.codecogs.com/gif.latex?%5Cdpi%7B300%7D%5Ci=
nline%09i" height=3D"11" width=3D"4" style=3D"display:inline"> of size <img=
 alt=3D"s_i" title=3D"s_i" src=3D"http://latex.codecogs.com/gif.latex?%5Cdp=
i%7B300%7D%5Cinline%09s%5Fi" style=3D"display:inline;vertical-align:-2.2px"=
 height=3D"9" width=3D"11">=C2=A0and fee density=C2=A0<img alt=3D"\phi_i" t=
itle=3D"\phi_i" src=3D"http://latex.codecogs.com/gif.latex?%5Cdpi%7B300%7D%=
5Cinline%09%5Cphi%5Fi" height=3D"15" width=3D"13" style=3D"display:inline;v=
ertical-align:-3.3px">, many transactions <img alt=3D"j" title=3D"j" src=3D=
"http://latex.codecogs.com/gif.latex?%5Cdpi%7B300%7D%5Cinline%09j" style=3D=
"display:inline;vertical-align:-3.3px" height=3D"14" width=3D"6">=C2=A0will=
 exist such that <img alt=3D"s_j&lt;s_i" title=3D"s_j&lt;s_i" src=3D"http:/=
/latex.codecogs.com/gif.latex?%5Cdpi%7B300%7D%5Cinline%09s%5Fj%3Cs%5Fi" sty=
le=3D"display:inline;vertical-align:-4.767px" height=3D"14" width=3D"47">=
=C2=A0and <img alt=3D"\phi_j=3D\phi_i" title=3D"\phi_j=3D\phi_i" src=3D"htt=
p://latex.codecogs.com/gif.latex?%5Cdpi%7B300%7D%5Cinline%09%5Cphi%5Fj=3D%5=
Cphi%5Fi" height=3D"16" width=3D"52" style=3D"display:inline;vertical-align=
:-4.767px">. 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&#39;s=
 greedy algorithm is an asymptotically optimal solution.<br><br>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).<b=
r><br>I hope this clarifies your point.</div><div><br></div><div>Daniele</d=
iv></div></div>
<br><div class=3D"gmail_quote"><div><div class=3D"h5">---------- Forwarded =
message ----------<br>From: <b class=3D"gmail_sendername">Daniele Pinna</b>=
 <span dir=3D"ltr">&lt;<a href=3D"mailto:daniele.pinna@gmail.com" target=3D=
"_blank">daniele.pinna@gmail.com</a>&gt;</span><br>Date: Sun, Aug 30, 2015 =
at 1:11 PM<br>Subject: Another issue with the Fee Demand curve<br>To: Peter=
 R &lt;<a href=3D"mailto:peter_r@gmx.com" target=3D"_blank">peter_r@gmx.com=
</a>&gt;<br><br><br></div></div><div dir=3D"ltr"><div><div class=3D"h5">Thi=
s was pointed out to me by Tom Harding.<div><br></div><div>Choosing what th=
e optimal way of choosing transactions to be included in a block is a knaps=
ack problem (an NP-complete problem!):<br><br><a href=3D"https://en.wikiped=
ia.org/wiki/Knapsack_problem" target=3D"_blank">https://en.wikipedia.org/wi=
ki/Knapsack_problem</a></div><div><br></div><div>For which your suggested s=
olution, which is by no means exact, is known as the &quot;Greedy Approxima=
tion Algorithm&quot;. This algorithm in turn works best only when a very la=
rge quantity of high density transactions is available in the mempool.</div=
><div><br></div><div>This wouldn&#39;t invalidate your proof but it may sig=
nificantly alter the optimal block size value.</div><div><br></div><div>Jus=
t thought I would throw this your way.</div></div></div><span><font color=
=3D"#888888"><div><br></div><div>Daniele<br><br><span style=3D"color:rgb(34=
,34,34)">---------- Forwarded message ----------</span><br style=3D"color:r=
gb(34,34,34)"><span style=3D"color:rgb(34,34,34)">From:=C2=A0</span><b clas=
s=3D"gmail_sendername" style=3D"color:rgb(34,34,34)">Tom Harding</b><span s=
tyle=3D"color:rgb(34,34,34)">=C2=A0</span><span dir=3D"ltr" style=3D"color:=
rgb(34,34,34)">&lt;<a href=3D"mailto:tomh@thinlink.com" target=3D"_blank">t=
omh@thinlink.com</a>&gt;</span><br style=3D"color:rgb(34,34,34)"><span styl=
e=3D"color:rgb(34,34,34)">Date: Sat, Aug 29, 2015 at 10:21 PM</span><br sty=
le=3D"color:rgb(34,34,34)"><span style=3D"color:rgb(34,34,34)">Subject: Re:=
 [bitcoin-dev] Unlimited Max Blocksize (reprise)</span><br style=3D"color:r=
gb(34,34,34)"><span style=3D"color:rgb(34,34,34)">To: Daniele Pinna &lt;<a =
href=3D"mailto:daniele.pinna@gmail.com" target=3D"_blank">daniele.pinna@gma=
il.com</a>&gt;</span><br style=3D"color:rgb(34,34,34)"><br style=3D"color:r=
gb(34,34,34)"><br style=3D"color:rgb(34,34,34)"><div bgcolor=3D"#FFFFFF" te=
xt=3D"#000000" style=3D"color:rgb(34,34,34)">Daniele --<br><br>Thanks!=C2=
=A0 I printed it and read the whole thing.=C2=A0 It&#39;s really a great st=
ep forward building on the Peter R paper. The conclusions are enticing.=C2=
=A0 I&#39;m looking forward to understanding it in more detail and particip=
ating in the discussion.<br><br>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<br><br><br>&quot;<span style=3D=
"word-spacing:4px;letter-spacing:1px"><span style=3D"width:14px"></span>The=
 optimal strategy,=C2=A0=EF=AC=81rst analyzed=C2=A0in [3]&quot;</span>=C2=
=A0 I don&#39;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).<div><div><br><br><br><br><div=
>On 8/29/2015 10:16 AM, Daniele Pinna wrote:<br></div><blockquote type=3D"c=
ite"><div dir=3D"ltr">Here you go Tom!<br><br><a href=3D"https://www.scribd=
.com/doc/276849939/On-the-Nature-of-Miner-Advantages-in-Uncapped-Block-Size=
-Fee-Markets" target=3D"_blank">https://www.scribd.com/doc/276849939/On-the=
-Nature-of-Miner-Advantages-in-Uncapped-Block-Size-Fee-Markets</a><br></div=
><div class=3D"gmail_extra"><br clear=3D"all"><div><div dir=3D"ltr">Daniele=
 Pinna, Ph.D</div></div><br><div class=3D"gmail_quote">On Thu, Aug 27, 2015=
 at 12:59 AM, Tom Harding=C2=A0<span dir=3D"ltr">&lt;<a href=3D"mailto:tomh=
@thinlink.com" target=3D"_blank">tomh@thinlink.com</a>&gt;</span>=C2=A0wrot=
e:<br><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;b=
order-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:s=
olid;padding-left:1ex"><div bgcolor=3D"#FFFFFF" text=3D"#000000"><br>Thanks=
 for posting this.=C2=A0 I&#39;m very interested to read your paper when it=
 is available.<div><br><br><br><div>On 8/26/2015 3:22 PM, Daniele Pinna via=
 bitcoin-dev wrote:<br></div></div><blockquote type=3D"cite"><p dir=3D"ltr"=
>I don&#39;t get how it&#39;s very risky to have the Mike and Gavin redirec=
t the course of the bitcoin protocol but it&#39;s totally fine to consider =
complex miner voting protocols as a hard fork option.</p><p dir=3D"ltr">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?</p><p dir=3D"ltr"=
>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.</p><p dir=3D"=
ltr">The main critique to uncapped max blocksizes which I&#39;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&#39;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&#39;t for the existence of current block subsidies.=C2=A0</p><p dir=3D"=
ltr">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&#39;s original posts) don&#39;=
t mean anything. Rational miners will NOT be incentivized to mine gargantua=
n spam filled blocks in the presence of a vanishing block reward.</p><p dir=
=3D"ltr">I truly hope this matter gets the consideration it deserves. Parti=
cularly with the upcoming scaling workshops.</p><p dir=3D"ltr">Dpinna</p><d=
iv class=3D"gmail_quote">On Aug 21, 2015 11:35 PM, &quot;Daniele Pinna&quot=
; &lt;<a href=3D"mailto:daniele.pinna@gmail.com" target=3D"_blank">daniele.=
pinna@gmail.com</a>&gt; wrote:<br type=3D"attribution"><blockquote style=3D=
"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,2=
04,204);border-left-style:solid;padding-left:1ex"><p dir=3D"ltr">&quot;I ra=
n some simulations, and if blocks take 20 seconds to propagate, a<br>networ=
k with a miner that has 30% of the hashing power will get 30.3% of the bloc=
ks.&quot;</p><p dir=3D"ltr">Peter_R&#39;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:</p><p dir=3D"ltr">Currently, the main critique of larger block=
sizes is that we&#39;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.</p><p dir=3D"ltr">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.</p><p dir=3D"ltr">In th=
is context, large blocksizes as proposed by BIP100-101 hope to stimulate th=
e increase of TX fees by augmenting the network&#39;s capacity. The sooner =
block rewards become comparable to block fees, the sooner we will get rid o=
f mine centralization.</p><p dir=3D"ltr">Dpinna</p><p dir=3D"ltr">[1]=C2=A0=
<a href=3D"http://www.scribd.com/mobile/doc/273443462/A-Transaction-Fee-Mar=
ket-Exists-Without-a-Block-Size-Limit" target=3D"_blank">http://www.scribd.=
com/mobile/doc/273443462/A-Transaction-Fee-Market-Exists-Without-a-Block-Si=
ze-Limit</a></p></blockquote></div></blockquote></div></blockquote></div></=
div></blockquote></div></div></div></div></font></span></div>
</div><br></div>
</div><br></div>

--089e0158b60e8f864d051e85e823--