summaryrefslogtreecommitdiff
path: root/b6/14b9fca49851873b9d959ff1423b1133ad9bb4
blob: e7ebd98c20823dd896db4a9e986feeb68325b712 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
Return-Path: <anthony.j.towns@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id AFCD0259
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  7 Aug 2015 02:16:53 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wi0-f174.google.com (mail-wi0-f174.google.com
	[209.85.212.174])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3363EE8
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  7 Aug 2015 02:16:52 +0000 (UTC)
Received: by wicgj17 with SMTP id gj17so44052513wic.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 06 Aug 2015 19:16:50 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:sender:in-reply-to:references:date:message-id:subject
	:from:to:cc:content-type;
	bh=RHwgHVZ0cL0xmbaOAICwDeVpKLly43AkxFICRiH0vQU=;
	b=mThoGg+pC8nzVxV2b5lU1M0Zjf7+2Ov+nQOPFJTSmK7Mq9NoKsaffSdUXvfDGPbzcb
	se8pVwCoMNaoeOPWKEqrHT88nyzOKnH+difpulZKVBF25MuGFOjl8RXdsa5zfN6qngFU
	pHDkhzUcUkaQ1M/rk/r/0GWNxNujOnlhN33GzwOy5xMpCPQVqwz6JmDA3/9wkbCRg1jg
	d3CoMjith8yRmWRMY6LwthzvyfwqEooPMBuqYvP6kg/UCf6vKe+vajSpuS8m+5Z4Vsfn
	0gFWxtTxTFmPdVekOmEpYD01UxQK576j4POgTCjobm/eF+DMCYMkLknK2vXyCXgTm8fh
	FyWA==
MIME-Version: 1.0
X-Received: by 10.194.158.34 with SMTP id wr2mr9484883wjb.23.1438913810674;
	Thu, 06 Aug 2015 19:16:50 -0700 (PDT)
Sender: anthony.j.towns@gmail.com
Received: by 10.28.176.69 with HTTP; Thu, 6 Aug 2015 19:16:50 -0700 (PDT)
In-Reply-To: <CAOvA3_hhzWqX0k7xbua=qFptb90fkbCU-WDMih4=mX+kRrWG1g@mail.gmail.com>
References: <CAOvA3_hhzWqX0k7xbua=qFptb90fkbCU-WDMih4=mX+kRrWG1g@mail.gmail.com>
Date: Fri, 7 Aug 2015 12:16:50 +1000
X-Google-Sender-Auth: w5MeYVo7VcLi7B-euohQhpkfr3c
Message-ID: <CAJS_LCWznwYy_mOHRf9ykyWAQEzO2u79EO2GGo5ex=sgCubofQ@mail.gmail.com>
From: Anthony Towns <aj@erisian.com.au>
To: Wes Green <maveric100@gmail.com>
Content-Type: multipart/alternative; boundary=089e013c669e8c3b71051caf3ade
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,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
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Block size implementation using Game Theory
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: Fri, 07 Aug 2015 02:16:53 -0000

--089e013c669e8c3b71051caf3ade
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On 7 August 2015 at 09:52, Wes Green via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:=E2=80=8B

> Bitcoin is built on game theory. Somehow we seem to have forgotten that
> and are trying to fix our "block size issue" with magic numbers, projecte=
d
> percentage growth of bandwidth speeds, time limits, etc... There are
> instances where these types of solutions make sense, but this doesn't
> appear to be one of them. Lets return to game theory.
>
> Proposal: Allow any miner to, up to, double the block size at any given
> time - but penalize them. Using the normal block reward, whatev
> =E2=80=8BH=E2=80=8B
> er percentage increase the miner makes over the previous limit is taken
> from both the normal reward and fees. The left over is rewarded to the ne=
xt
> miner that finds a block.
> =E2=80=8B=E2=80=8B
>
> What this would look like: The miners start seeing what looks like natura=
l
> network growth, and make the decision (or program an algorithm, the beaut=
y
> is it leaves the "how" up to the miners) to increase the blocksize. They
> think that, in the long run, having larger blocks will increase their
> revenue and its worth taking the hit now for more fees later. They increa=
se
> the size to 1.25 MB. As a result, they reward would be 18.75 (75%). The
> miner fees were .5BTC. The miner fees are also reduced to .375BTC.
>

The equilibrium for that game is just keeping the same block size, isn't
it? Assume there's a huge backlog of fee-paying transactions, such that you
can trivially fill 1MB, and easily fill 1.25MB for the forseeable future;
fee per MB is roughly stable at "f". Then at any point in time, a miner has
the choice between receiving 25 + f btc, or increasing the blocksize to 1+p
MB and earning (25+f+pf) * (1-p) =3D f-ppf =3D 25(1-p) + f(1-pp) < 25+f. Ev=
en
if you think bigger blocks are good long term, wouldn't you reason that
other people will think so too, so why pay the price for it yourself,
instead of waiting for someone else to pay it and just reaping the benefit?


An idea I've been pondering is having the block size adjustable in
proportion to fees being paid. Something like "a block is invalid if
a(B-c)*B > F" where B is the block's size, F is the total fees for the
block, and a and c are scaling parameters -- either hardcoded in bitcoin,
or dynamically adjusted by miner votes. ATM, bitcoin's behavour is
effectively the same as setting c=3D1MB, a>=3D21M BTC/byte.

Having a more reasonable value for a would make it much easier to produce a
fee market for bitcoin transactions -- if the blocksize is currently around
some specific "B", then the average cost per byte of a transaction is just
"a(B-c)". If you pay more than that, then a miner will include your txn
sooner, increasing the blocksize beyond average if necessary; if you pay
less, you may have to wait for a lull in transactions so that the blocksize
ends up being smaller than average and miners can afford to include your
transaction (or someone might send an unnecessarily high fee paying txn
through, and yours might get swept along with it).

To provide some real numbers, you need to make some assumptions on fee
levels. If you're happy with:

 - 1 MB blocks are fine, even if no one's paying any fees
 - if people are paying 0.1 mBTC / kB (=3D0.1 BTC/MB) in fees on average th=
en
8MB is okay

then a(1-c)=3D0, so c=3D1MB, and a(8-1)=3D0.1, so a=3D0.0143 and the scalin=
g works
out like:

 - 1MB blocks: free transactions, no fees
 - 2MB blocks: 0.0143 mBTC/kB, 0.02 btc in fees/block
 - 4MB blocks: 0.043 mBTC/kB, 0.17 btc in fees/block
 - 8MB blocks: 0.1 mBTC/kB, 0.8 btc in fees/block
 - 20MB blocks: 0.27 mBTC/kB, 5.4 btc in fees/block
 - 40MB blocks: 0.56 mBTC/kB, 22 btc in fees/block

In the short term, miners can just maximise fees for a block -- ie, add the
highest fee/byte txns in order until adding the next one would invalidate
the block.

Over the long term, you'd still want to be able to adjust a and c -- as the
price of bitcoin in USD/real terms goes up, a should decrease
proportionally; as hardware/software improve, a should decrease and/or c
should increase.  Essentially miners would want to choose a,c such that the
market for block space clears at a price of some $x/byte, where $x is
determined by their costs -- ie, hardware/software constraints. If they set
a too high, or c too low, then they'll be unable to accept some
transactions offering $x/byte, and thus lose out. If they set a too low or
c too high, they'll be mining bigger blocks for less reward, and lose out
that way too. At the moment, I think it's a bit of both problems -- c is
too low (meaning some transactions get dropped), but a is too high (meaning
fees are too low to pay for the effort of bigger blocks).

Note that, as described, miners could try cheating this plan by making a
high fee transaction to themselves but not publishing it -- they'll collect
the fee anyway, and now they can mine arbitrarily large blocks. You could
mitigate this by having a(B-c) set the /minimum/ fee/byte of every
transaction in a block, or alternatively by enforcing each miner pay a
significant %ge of collected fees to the miner of the next block(s).

=E2=80=8BCheers,
aj=E2=80=8B

--=20
Anthony Towns <aj@erisian.com.au>

--089e013c669e8c3b71051caf3ade
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:monospac=
e"><span style=3D"font-family:arial,sans-serif">On 7 August 2015 at 09:52, =
Wes Green via bitcoin-dev </span><span dir=3D"ltr" style=3D"font-family:ari=
al,sans-serif">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org"=
 target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span><spa=
n style=3D"font-family:arial,sans-serif"> wrote:</span>=E2=80=8B</div><div =
class=3D"gmail_extra"><div class=3D"gmail_quote"><blockquote class=3D"gmail=
_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:=
1ex"><div dir=3D"ltr"><p style=3D"margin:0px 0px 0.357142857142857em;paddin=
g:1px 0px;font-size:14px;line-height:1.3em;font-family:Verdana,arial,sans-s=
erif;color:rgb(34,34,34)">Bitcoin is built on game theory. Somehow we seem =
to have forgotten that and are trying to fix our &quot;block size issue&quo=
t; with magic numbers, projected percentage growth of bandwidth speeds, tim=
e limits, etc... There are instances where these types of solutions make se=
nse, but this doesn&#39;t appear to be one of them. Lets return to game the=
ory.</p><p style=3D"margin:0.357142857142857em 0px;padding:1px 0px;font-siz=
e:14px;line-height:1.3em;font-family:Verdana,arial,sans-serif;color:rgb(34,=
34,34)">Proposal: Allow any miner to, up to, double the block size at any g=
iven time - but penalize them. Using the normal block reward, whatev</p><di=
v class=3D"gmail_default" style=3D"font-family:monospace;display:inline">=
=E2=80=8BH=E2=80=8B</div>er percentage increase the miner makes over the pr=
evious limit is taken from both the normal reward and fees. The left over i=
s rewarded to the next miner that finds a block.<div class=3D"gmail_default=
" style=3D"font-family:monospace;display:inline">=E2=80=8B=E2=80=8B</div><p=
></p></div></blockquote><blockquote class=3D"gmail_quote" style=3D"margin:0=
 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><p =
style=3D"margin:0.357142857142857em 0px;padding:1px 0px;font-size:14px;line=
-height:1.3em;font-family:Verdana,arial,sans-serif;color:rgb(34,34,34)">Wha=
t this would look like: The miners start seeing what looks like natural net=
work growth, and make the decision (or program an algorithm, the beauty is =
it leaves the &quot;how&quot; up to the miners) to increase the blocksize. =
They think that, in the long run, having larger blocks will increase their =
revenue and its worth taking the hit now for more fees later. They increase=
 the size to 1.25 MB. As a result, they reward would be 18.75 (75%). The mi=
ner fees were .5BTC. The miner fees are also reduced to .375BTC.</p></div><=
/blockquote><div><br></div><div><div class=3D"gmail_default" style=3D"font-=
family:monospace">The equilibrium for that game is just keeping the same bl=
ock size, isn&#39;t it? Assume there&#39;s a huge backlog of fee-paying tra=
nsactions, such that you can trivially fill 1MB, and easily fill 1.25MB for=
 the forseeable future; fee per MB is roughly stable at &quot;f&quot;. Then=
 at any point in time, a miner has the choice between receiving 25 + f btc,=
 or increasing the blocksize to 1+p MB and earning (25+f+pf) * (1-p) =3D f-=
ppf =3D 25(1-p) + f(1-pp) &lt; 25+f. Even if you think bigger blocks are go=
od long term, wouldn&#39;t you reason that other people will think so too, =
so why pay the price for it yourself, instead of waiting for someone else t=
o pay it and just reaping the benefit?</div><div class=3D"gmail_default" st=
yle=3D"font-family:monospace"><br></div><div class=3D"gmail_default" style=
=3D"font-family:monospace"><br></div><div class=3D"gmail_default" style=3D"=
font-family:monospace">An idea I&#39;ve been pondering is having the block =
size adjustable in proportion to fees being paid. Something like &quot;a bl=
ock is invalid if a(B-c)*B &gt; F&quot; where B is the block&#39;s size, F =
is the total fees for the block, and a and c are scaling parameters -- eith=
er hardcoded in bitcoin, or dynamically adjusted by miner votes. ATM, bitco=
in&#39;s behavour is effectively the same as setting c=3D1MB, a&gt;=3D21M B=
TC/byte.</div><div class=3D"gmail_default" style=3D"font-family:monospace">=
<br></div><div class=3D"gmail_default" style=3D"font-family:monospace">Havi=
ng a more reasonable value for a would make it much easier to produce a fee=
 market for bitcoin transactions -- if the blocksize is currently around so=
me specific &quot;B&quot;, then the average cost per byte of a transaction =
is just &quot;a(B-c)&quot;. If you pay more than that, then a miner will in=
clude your txn sooner, increasing the blocksize beyond average if necessary=
; if you pay less, you may have to wait for a lull in transactions so that =
the blocksize ends up being smaller than average and miners can afford to i=
nclude your transaction (or someone might send an unnecessarily high fee pa=
ying txn through, and yours might get swept along with it).</div><div class=
=3D"gmail_default" style=3D"font-family:monospace"><br></div><div class=3D"=
gmail_default" style=3D"font-family:monospace">To provide some real numbers=
, you need to make some assumptions on fee levels. If you&#39;re happy with=
:</div></div><div class=3D"gmail_default" style=3D"font-family:monospace"><=
br></div><div class=3D"gmail_default" style=3D"font-family:monospace">=C2=
=A0- 1 MB blocks are fine, even if no one&#39;s paying any fees</div><div c=
lass=3D"gmail_default" style=3D"font-family:monospace">=C2=A0- if people ar=
e paying 0.1 mBTC / kB (=3D0.1 BTC/MB) in fees on average then 8MB is okay<=
/div><div class=3D"gmail_default" style=3D"font-family:monospace"><br></div=
><div class=3D"gmail_default" style=3D"font-family:monospace">then a(1-c)=
=3D0, so c=3D1MB, and a(8-1)=3D0.1, so a=3D0.0143 and the scaling works out=
 like:</div><div class=3D"gmail_default" style=3D"font-family:monospace"><b=
r></div><div class=3D"gmail_default" style=3D"font-family:monospace">=C2=A0=
- 1MB blocks: free transactions, no fees</div><div class=3D"gmail_default" =
style=3D"font-family:monospace">=C2=A0- 2MB blocks: 0.0143 mBTC/kB, 0.02 bt=
c in fees/block</div><div class=3D"gmail_default" style=3D"font-family:mono=
space">=C2=A0- 4MB blocks: 0.043 mBTC/kB, 0.17 btc in fees/block<br></div><=
div class=3D"gmail_default" style=3D"font-family:monospace">=C2=A0- 8MB blo=
cks: 0.1 mBTC/kB, 0.8 btc in fees/block</div><div class=3D"gmail_default" s=
tyle=3D"font-family:monospace">=C2=A0- 20MB blocks: 0.27 mBTC/kB, 5.4 btc i=
n fees/block</div><div class=3D"gmail_default" style=3D"font-family:monospa=
ce">=C2=A0- 40MB blocks: 0.56 mBTC/kB, 22 btc in fees/block</div><div class=
=3D"gmail_default" style=3D"font-family:monospace"><br></div><div class=3D"=
gmail_default" style=3D"font-family:monospace">In the short term, miners ca=
n just maximise fees for a block -- ie, add the highest fee/byte txns in or=
der until adding the next one would invalidate the block.</div><div class=
=3D"gmail_default" style=3D"font-family:monospace"><br></div><div class=3D"=
gmail_default" style=3D"font-family:monospace">Over the long term, you&#39;=
d still want to be able to adjust a and c -- as the price of bitcoin in USD=
/real terms goes up, a should decrease proportionally; as hardware/software=
 improve, a should decrease and/or c should increase.=C2=A0 Essentially min=
ers would want to choose a,c such that the market for block space clears at=
 a price of some $x/byte, where $x is determined by their costs -- ie, hard=
ware/software constraints. If they set a too high, or c too low, then they&=
#39;ll be unable to accept some transactions offering $x/byte, and thus los=
e out. If they set a too low or c too high, they&#39;ll be mining bigger bl=
ocks for less reward, and lose out that way too. At the moment, I think it&=
#39;s a bit of both problems -- c is too low (meaning some transactions get=
 dropped), but a is too high (meaning fees are too low to pay for the effor=
t of bigger blocks).</div><div class=3D"gmail_default" style=3D"font-family=
:monospace"><br></div><div class=3D"gmail_default" style=3D"font-family:mon=
ospace">Note that, as described, miners could try cheating this plan by mak=
ing a high fee transaction to themselves but not publishing it -- they&#39;=
ll collect the fee anyway, and now they can mine arbitrarily large blocks. =
You could mitigate this by having a(B-c) set the /minimum/ fee/byte of ever=
y transaction in a block, or alternatively by enforcing each miner pay a si=
gnificant %ge of collected fees to the miner of the next block(s).<br></div=
><div class=3D"gmail_default" style=3D"font-family:monospace"><br></div><di=
v><div class=3D"gmail_default" style=3D"font-family:monospace">=E2=80=8BChe=
ers,</div><div class=3D"gmail_default" style=3D"font-family:monospace">aj=
=E2=80=8B</div></div></div><div><br></div>-- <br><div class=3D"gmail_signat=
ure">Anthony Towns &lt;<a href=3D"mailto:aj@erisian.com.au" target=3D"_blan=
k">aj@erisian.com.au</a>&gt;</div>
</div></div>

--089e013c669e8c3b71051caf3ade--