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
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <stanga@gmail.com>) id 1VdjwQ-0002h4-47
for bitcoin-development@lists.sourceforge.net;
Tue, 05 Nov 2013 16:57:22 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.215.43 as permitted sender)
client-ip=209.85.215.43; envelope-from=stanga@gmail.com;
helo=mail-la0-f43.google.com;
Received: from mail-la0-f43.google.com ([209.85.215.43])
by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1VdjwO-0004Nx-KT
for bitcoin-development@lists.sourceforge.net;
Tue, 05 Nov 2013 16:57:21 +0000
Received: by mail-la0-f43.google.com with SMTP id ec20so1413994lab.16
for <bitcoin-development@lists.sourceforge.net>;
Tue, 05 Nov 2013 08:57:14 -0800 (PST)
X-Received: by 10.112.168.105 with SMTP id zv9mr1924598lbb.48.1383670633889;
Tue, 05 Nov 2013 08:57:13 -0800 (PST)
MIME-Version: 1.0
Sender: stanga@gmail.com
Received: by 10.112.105.35 with HTTP; Tue, 5 Nov 2013 08:56:53 -0800 (PST)
From: Ittay <ittay.eyal@cornell.edu>
Date: Tue, 5 Nov 2013 11:56:53 -0500
X-Google-Sender-Auth: wD84oHaSoSmuaHJ-_32eGhXXw5M
Message-ID: <CABT1wWkOukEzxK5fLbnA4ZgJGN1hb_DMteCJOfA13FE_QZCi=Q@mail.gmail.com>
To: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Content-Type: multipart/alternative; boundary=001a11c259aa9e856804ea70ecfa
X-Spam-Score: -0.5 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(stanga[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked.
See
http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block
for more information. [URIs: arxiv.org]
1.0 HTML_MESSAGE BODY: HTML included in message
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1VdjwO-0004Nx-KT
Cc: Gavin Andresen <gavin@bitcoinfoundation.org>,
=?ISO-8859-1?Q?Emin_G=FCn_Sirer?= <egs@systems.cs.cornell.edu>
Subject: [Bitcoin-development] BIP proposal - patch to raise selfish mining
threshold.
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Tue, 05 Nov 2013 16:57:22 -0000
--001a11c259aa9e856804ea70ecfa
Content-Type: text/plain; charset=ISO-8859-1
Hello,
Please see below our BIP for raising the selfish mining threshold.
Looking forward to your comments.
Best,
Ittay
---
Bitcoin Improvement Proposal
Owners: Ittay Eyal and Emin Gun Sirer
We suggest a change in the propagation and mining algorithm for chains of
the same difficulty, to raise the threshold on Selfish Mining attacks.
* Current situation:
When a miner is notified of a new chain of the same difficulty as the one
it is mining on, it will ignore it.
* Background:
The selfish mining attack and its implications were described in detail in
the following research paper:
http://arxiv.org/abs/1311.0243v1
* Proposal:
To thwart selfish mining attacks launched by less than 25% of the mining
power, we propose the following change to the protocol:
When a miner learns of more than one chain of the same difficulty, it
should propagate all of them, and choose one of them to mine on uniformly
at random among all chains of the same difficulty.
When hearing of a chain of maximal difficulty that it did not know of
before:
1. Add it to a local list of maximal difficulty chains.
2. Propagate it to its neighbors.
3. Choose a branch uniformly at random from the local list, and mine on it.
* Example:
t0: learn of chain A of difficulty x.
propagate A to neighbors.
start mining on A.
t1: learn of chain B of difficulty x.
propagate B to neighbors.
toss a coin between A and B; if B wins, switch to mining on B.
t2: learn of chain C of difficulty x.
propagate C to neighbors.
toss a 3 faced coin among A, B, and C; switch to mining on the winning
chain.
* Concerns and answers:
1. No harm to miners when all are honest.
Mining blocks is a random Poisson process, which is memoryless. Having
mined on the block in the past does not provide an advantage in locating a
solution in the future. Therefore, a miner is not harmed by switching the
chain on which it mines.
2. No new vulnerabilities introduced:
Currently the choice among equal-length chains is done arbitrarily,
depending on network topology. This arbitrariness is a source of
vulnerability. We replace it with explicit randomness, which is at the
control of the protocol. The change does not introduce executions that were
not possible with the old protocol.
3. Complete backward compatibility:
Any subset of the miners can switch to the proposed protocol.
4. Progressive improvement:
Each miner that adopts the change raises the threshold a little bit. The
threshold will reach 25% with universal adoption.
--001a11c259aa9e856804ea70ecfa
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Hello,=A0</div><div><br></div><div>Please see below o=
ur BIP for raising the selfish mining threshold.=A0</div><div>Looking forwa=
rd to your comments.=A0</div><div><br></div><div>Best,=A0</div><div>Ittay=
=A0</div><div>
<br></div><div>---=A0</div><div><br></div><div>Bitcoin Improvement Proposal=
=A0</div><div><br></div><div>Owners: Ittay Eyal and Emin Gun Sirer=A0</div>=
<div><br></div><div>We suggest a change in the propagation and mining algor=
ithm for chains of the same difficulty, to raise the threshold on Selfish M=
ining attacks.=A0</div>
<div><br></div><div>* Current situation:=A0</div><div>When a miner is notif=
ied of a new chain of the same difficulty as the one it is mining on, it wi=
ll ignore it.=A0</div><div><br></div><div>* Background:=A0</div><div>The se=
lfish mining attack and its implications were described in detail in the fo=
llowing research paper:=A0</div>
<div><a href=3D"http://arxiv.org/abs/1311.0243v1" target=3D"_blank">http://=
arxiv.org/abs/1311.0243v1</a></div><div><br></div><div>* Proposal:=A0</div>=
<div>To thwart selfish mining attacks launched by less than 25% of the mini=
ng power, we propose the following change to the protocol:=A0</div>
<div>When a miner learns of more than one chain of the same difficulty, it =
should propagate all of them, and choose one of them to mine on uniformly a=
t random among all chains of the same difficulty.=A0</div><div><br></div>
<div>When hearing of a chain of maximal difficulty that it did not know of =
before:=A0</div><div>1. Add it to a local list of maximal difficulty chains=
.=A0</div><div>2. Propagate it to its neighbors.=A0</div><div>3. Choose a b=
ranch uniformly at random from the local list, and mine on it.=A0</div>
<div><br></div><div>* Example:=A0</div><div>t0: learn of chain A of difficu=
lty x.=A0</div><div>=A0 =A0 propagate A to neighbors.=A0</div><div>=A0 =A0 =
start mining on A.=A0</div><div>t1: learn of chain B of difficulty x.=A0</d=
iv><div>=A0 =A0 propagate B to neighbors.=A0</div>
<div>=A0 =A0 toss a coin between A and B; if B wins, switch to mining on B.=
=A0</div><div>t2: learn of chain C of difficulty x.=A0</div><div>=A0 =A0 pr=
opagate C to neighbors.=A0</div><div>=A0 =A0 toss a 3 faced coin among A, B=
, and C; switch to mining on the winning chain.=A0</div>
<div><br></div><div>* Concerns and answers:=A0</div><div>1. No harm to mine=
rs when all are honest.=A0</div><div>Mining blocks is a random Poisson proc=
ess, which is memoryless. Having mined on the block in the past does not pr=
ovide an advantage in locating a solution in the future. Therefore, a miner=
is not harmed by switching the chain on which it mines.=A0</div>
<div><br></div><div>2. No new vulnerabilities introduced:=A0</div><div>Curr=
ently the choice among equal-length chains is done arbitrarily, depending o=
n network topology. This arbitrariness is a source of vulnerability. We rep=
lace it with explicit randomness, which is at the control of the protocol. =
The change does not introduce executions that were not possible with the ol=
d protocol.=A0</div>
<div><br></div><div>3. Complete backward compatibility:=A0</div><div>Any su=
bset of the miners can switch to the proposed protocol.=A0</div><div><br></=
div><div>4. Progressive improvement:=A0</div><div>Each miner that adopts th=
e change raises the threshold a little bit. The threshold will reach 25% wi=
th universal adoption.=A0</div>
<div><br></div></div>
--001a11c259aa9e856804ea70ecfa--
|
