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
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <etotheipi@gmail.com>) id 1VdRxl-0006SC-04
for bitcoin-development@lists.sourceforge.net;
Mon, 04 Nov 2013 21:45:33 +0000
Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.128.50 as permitted sender)
client-ip=209.85.128.50; envelope-from=etotheipi@gmail.com;
helo=mail-qe0-f50.google.com;
Received: from mail-qe0-f50.google.com ([209.85.128.50])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1VdRxj-0008Kl-CS
for bitcoin-development@lists.sourceforge.net;
Mon, 04 Nov 2013 21:45:32 +0000
Received: by mail-qe0-f50.google.com with SMTP id 1so4435739qee.23
for <bitcoin-development@lists.sourceforge.net>;
Mon, 04 Nov 2013 13:45:25 -0800 (PST)
X-Received: by 10.224.65.199 with SMTP id k7mr25568693qai.24.1383601525759;
Mon, 04 Nov 2013 13:45:25 -0800 (PST)
Received: from [192.168.1.85] (c-76-111-96-126.hsd1.md.comcast.net.
[76.111.96.126])
by mx.google.com with ESMTPSA id k2sm59291438qan.8.2013.11.04.13.45.24
for <bitcoin-development@lists.sourceforge.net>
(version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
Mon, 04 Nov 2013 13:45:25 -0800 (PST)
Message-ID: <52781574.1000904@gmail.com>
Date: Mon, 04 Nov 2013 16:45:24 -0500
From: Alan Reiner <etotheipi@gmail.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
rv:24.0) Gecko/20100101 Thunderbird/24.0.1
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
References: <CANEZrP3iYBdg3p7Ru4O-UENY_yyQDA8=9PGn=KDKGGTrZ-xkRw@mail.gmail.com> <20131104142621.GA2190@petertodd.org> <CABT1wWm1NzKSS9H=Qh3Z6pFmNHbOFKC12WaE=b3kE0mNsRgfmw@mail.gmail.com> <20131104150406.GA2566@petertodd.org> <CABT1wWmONUeOWRg-=FKr88bgBQf0un4bvjYW2h8d-10ys-VKtA@mail.gmail.com> <CABT1wWmwb17b4ACHMmDKqd94tUSKsvwAPx344mZ0VS+47myeWg@mail.gmail.com>
<20131104210451.GA4443@petertodd.org>
In-Reply-To: <20131104210451.GA4443@petertodd.org>
X-Enigmail-Version: 1.6
Content-Type: multipart/alternative;
boundary="------------030009050004090204050809"
X-Spam-Score: -0.6 (/)
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
(etotheipi[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: doubleclick.net]
1.0 HTML_MESSAGE BODY: HTML included in message
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
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: 1VdRxj-0008Kl-CS
Subject: Re: [Bitcoin-development] Auto-generated miner backbone
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: Mon, 04 Nov 2013 21:45:33 -0000
This is a multi-part message in MIME format.
--------------030009050004090204050809
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Sorry guys, I'm a little late to the party here. I skimmed over the
paper, and appreciated Peter Todd's recap of it. My first thought was
that this seems profit-neutral at best, when you take into account all
the races you lose by trying to beat the propagation of other miners'
blocks.
So given the assumption that Alice is "well-connected" as Peter
mentioned, it seems like this is a concern. But is this a realistic
assumption? All miners have an incentive to be thoroughly connected to
one another, to make sure they minimize the amount of time they spend
mining on forks and that their blocks win with minimal chance of being
orphaned. Is it realistic that one miner can somehow monopolize the
good connections when the big miners are already trying to do the same
thing for honest reasons? If you have a network full of honest miners
and this one selfish-miner, it seems that all the honest miners need to
do is try to establish those connections to each other as well as Alice
does, and Alice will end up orphaning all her profit away.
Furthermore, you can de-incentivize it by simply randomizing the order
of broadcasts. Although you are maintaining multiple concurrent
connections, the data still exits your network card as a serial stream
of packets, and it seems that if you randomize who gets your new-block
broadcasts first, then it further reduces the Alice's advantage if she's
not guaranteed to "be first." Sure, she can do it sometimes, but it
would seem that even a couple failures to beat the rest of the network
is going to erase most/all of what she gained on the blocks/chains that
she wins.
I liked the statement by Chris WIllmer on the reddit thread: "practice
> theory". The more we can theorize our way to believing the
conclusions that this is a problem, the more incentive there is for
someone intelligent to actually try it. It's very possible that the
conditions needed to execute this "attack" just cannot be attained in
practice.
-Alan
On 11/04/2013 04:04 PM, Peter Todd wrote:
> On Mon, Nov 04, 2013 at 02:12:44PM -0500, Ittay wrote:
>> On Mon, Nov 4, 2013 at 10:25 AM, Ittay <ittay.eyal@cornell.edu> wrote:
>>
>>> As for the rational motivation of the individual miners - that's a good
>>> point!
>>> Here is a solution we did not put in the paper due to space constraints
>>> that should alleviate your concern:
>>> Instead of locally choosing a block at random, have a deterministic
>>> pseudo-random mechanism for choosing between competing chains. E.g., take
>>> the one whose last block hash is smaller. This way all miners choose the
>>> same chain, and the guarantees of our solution hold.
>>>
>> I take that back.
> Speaking of, I'm going to take back my solution as well; I misunderstood
> your paper.
>
> So here's your argument in a ELI5 nutshell:
>
> Alice is a miner with some amount of hashing power. She has the ability
> to detect new blocks on the network extremely effectively for whatever
> reason; in short she has unusually good knowledge of the state of the
> network. She is also very good at publishing her blocks and getting them
> to the majority of hashing power in very little time; she has unusually
> good connectivity to all miners. (low-latency and high bandwidth)
>
> She's so good at this that when she finds a new block, she keeps it a
> secret! She can get away with this because she knows that the moment Bob
> finds a block, she can immediately broadcast it to the rest of the
> network before the other block propagates. Instead of building on Bob's
> blocks, almost everyone builds on Alice's block, depriving Bob of the
> revenue. Gradually Alice gets more and more miners because Bob, and
> other pools, don't pay out as much.
>
> You propose a rule where essentially miners extend Bob's block 50% of
> the time, and show in your paper how that leads to a scenario where
> Alice needs to have at leastr 1/4 of the total hashing power to
> succesfully pull this attack off anyway.
>
>
> What I did succesfully show is that for a short-term rational miner
> they're still better off mining to extend the block they hear about
> first rather than using your pick-one-at-random rule, because when you
> hear about a block is important information about whether or not the
> majority is mining on it. This is true even if others are using the
> pick-one-at-random rule. (they're better defecting than doing what's
> right for the whole network) Even worse is that miners have a rational
> incentive to broadcast such near-target headers to try to encourage
> other miners to work on the same fork that they are working on. The
> near-target idea came about for a totally different reason, so it's
> something that might wind up being implemented anyway.
>
> Mike Hearn's idea of making it easy to identify nodes associated with
> hashing power is still wrong. Although again, it's something that miners
> themselves have rational incentives to do. (you always want to encourage
> others to send you their blocks, and you also want to be able to send
> your blocks to the majority of hashing power as quickly as possible)
>
> Where the idea goes wrong is it makes it easier for Alice to identify
> hashing power, specifically where she needs to send her blocks to
> distribute them to the majority as quickly as possible. The second
> problem occurs if those nodes also distribute blocks to connecting
> peers: this makes it easy for Alice to be sure she'll hear about a new
> block as soon as possible by connecting to every one of those peers with
> a high-speed, low-latency connection. Bizzarely the idea does work if
> the advertised nodes only accept blocks, and never send blocks - instead
> miners would *only* send their blocks to other miners who have proven
> their hashing power, and do so essentially largest miner to smallest.
> Now unless Alice already is a large miner, her strategy can't work. Of
> course this will strongly encourage further centralization of pools. But
> it is in the interests of rational miners sadly.
>
> That blocks take a finite amount of time to propagate makes the problem
> worse: for Alice to learn that another block has been mined only
> requires her to receive the small 80 byte header from a peer; she
> doesn't need the whole block. She thus can know the block exists well
> before it has a chance to propagate fully. Even if every miner were
> directly peered to every other as some suggest, Alice could simply make
> smaller blocks, faster propagating than everyone else and use especially
> low-latency connections to win the race.
>
> On the other hand, the Bitcoin protocol is currently designed such that
> a miner can mine a block without knowing the previous block in full.
> Given the large block reward and/or a supply of transactions they knew
> no other miner had a rational miner would start trying to extend the
> longest chain they know about prior to actually receiving and validating
> the full block. Again, when miners start doing this - perhaps out of
> desperation due to low revenue - as long as Alice has the lowest latency
> network she'll win. (she doesn't even need to have the highest bandwidth
> in this case) We can change the protocol to force miners to fully
> validate blocks prior to mining extensions, but that only forces Alice
> to get more bandwidth - she still wins.
>
> Speaking of low-latency, latency not only centralizes control in a
> single pool, it centralizes pools and even mining hardware itself in a
> single physical location. Anyone at the edges of the propagation network
> will get comparatively less revenue than those in the center, gradually
> tightening the network, even without selfish mining. Alice's strategy of
> course should be to position her nodes in the geographical center. It's
> worth noting how if Alice is the one with the lowest average latency,
> she will win against any other miner trying to persue the same selfish
> miner strategy that she is using.
>
>
> Finally nLockTime makes the selfish miner strategy even more profitable.
> You may not be aware, but it's possible to make a transaction that can't
> be mined until some time in the future, measured by either block height
> or block timestamp. I've proposed to use this mechanism in
> announce/commit sacrifices: you create a transaction that can't be mined
> until some point in the future that sacrifices a large amount to mining
> fees, and then prior to that point you include it in the blockchain as
> data, proving the whole world knew about your transaction. The idea was
> that which miner managed to include the transaction, and collect the
> reward, would be random. However whenever Alice is able to maintain a
> lead over other miners she's able to reliably mine significantly more of
> those valuable transactions, further increasing her revenue over other
> miners.
>
>
> I must say, you've really opened a can of worms...
>
>
>
> ------------------------------------------------------------------------------
> Android is increasing in popularity, but the open development platform that
> developers love is also attractive to malware creators. Download this white
> paper to learn more about secure code signing practices that can help keep
> Android apps secure.
> http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
--------------030009050004090204050809
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
Sorry guys, I'm a little late to the party here. I skimmed over the
paper, and appreciated Peter Todd's recap of it. My first thought
was that this seems profit-neutral at best, when you take into
account all the races you lose by trying to beat the propagation of
other miners' blocks. <br>
<br>
So given the assumption that Alice is "well-connected" as Peter
mentioned, it seems like this is a concern. But is this a realistic
assumption? All miners have an incentive to be thoroughly connected
to one another, to make sure they minimize the amount of time they
spend mining on forks and that their blocks win with minimal chance
of being orphaned. Is it realistic that one miner can somehow
monopolize the good connections when the big miners are already
trying to do the same thing for honest reasons? If you have a
network full of honest miners and this one selfish-miner, it seems
that all the honest miners need to do is try to establish those
connections to each other as well as Alice does, and Alice will end
up orphaning all her profit away.<br>
<br>
Furthermore, you can de-incentivize it by simply randomizing the
order of broadcasts. Although you are maintaining multiple
concurrent connections, the data still exits your network card as a
serial stream of packets, and it seems that if you randomize who
gets your new-block broadcasts first, then it further reduces the
Alice's advantage if she's not guaranteed to "be first." Sure, she
can do it sometimes, but it would seem that even a couple failures
to beat the rest of the network is going to erase most/all of what
she gained on the blocks/chains that she wins.<br>
<br>
I liked the statement by Chris WIllmer on the reddit thread:
"practice > theory". The more we can theorize our way to
believing the conclusions that this is a problem, the more incentive
there is for someone intelligent to actually try it. It's very
possible that the conditions needed to execute this "attack" just
cannot be attained in practice. <br>
<br>
-Alan<br>
<br>
<br>
<br>
<br>
<div class="moz-cite-prefix">On 11/04/2013 04:04 PM, Peter Todd
wrote:<br>
</div>
<blockquote cite="mid:20131104210451.GA4443@petertodd.org"
type="cite">
<pre wrap="">On Mon, Nov 04, 2013 at 02:12:44PM -0500, Ittay wrote:
</pre>
<blockquote type="cite">
<pre wrap="">On Mon, Nov 4, 2013 at 10:25 AM, Ittay <a class="moz-txt-link-rfc2396E" href="mailto:ittay.eyal@cornell.edu"><ittay.eyal@cornell.edu></a> wrote:
</pre>
<blockquote type="cite">
<pre wrap="">As for the rational motivation of the individual miners - that's a good
point!
Here is a solution we did not put in the paper due to space constraints
that should alleviate your concern:
Instead of locally choosing a block at random, have a deterministic
pseudo-random mechanism for choosing between competing chains. E.g., take
the one whose last block hash is smaller. This way all miners choose the
same chain, and the guarantees of our solution hold.
</pre>
</blockquote>
<pre wrap="">
I take that back.
</pre>
</blockquote>
<pre wrap="">
Speaking of, I'm going to take back my solution as well; I misunderstood
your paper.
So here's your argument in a ELI5 nutshell:
Alice is a miner with some amount of hashing power. She has the ability
to detect new blocks on the network extremely effectively for whatever
reason; in short she has unusually good knowledge of the state of the
network. She is also very good at publishing her blocks and getting them
to the majority of hashing power in very little time; she has unusually
good connectivity to all miners. (low-latency and high bandwidth)
She's so good at this that when she finds a new block, she keeps it a
secret! She can get away with this because she knows that the moment Bob
finds a block, she can immediately broadcast it to the rest of the
network before the other block propagates. Instead of building on Bob's
blocks, almost everyone builds on Alice's block, depriving Bob of the
revenue. Gradually Alice gets more and more miners because Bob, and
other pools, don't pay out as much.
You propose a rule where essentially miners extend Bob's block 50% of
the time, and show in your paper how that leads to a scenario where
Alice needs to have at leastr 1/4 of the total hashing power to
succesfully pull this attack off anyway.
What I did succesfully show is that for a short-term rational miner
they're still better off mining to extend the block they hear about
first rather than using your pick-one-at-random rule, because when you
hear about a block is important information about whether or not the
majority is mining on it. This is true even if others are using the
pick-one-at-random rule. (they're better defecting than doing what's
right for the whole network) Even worse is that miners have a rational
incentive to broadcast such near-target headers to try to encourage
other miners to work on the same fork that they are working on. The
near-target idea came about for a totally different reason, so it's
something that might wind up being implemented anyway.
Mike Hearn's idea of making it easy to identify nodes associated with
hashing power is still wrong. Although again, it's something that miners
themselves have rational incentives to do. (you always want to encourage
others to send you their blocks, and you also want to be able to send
your blocks to the majority of hashing power as quickly as possible)
Where the idea goes wrong is it makes it easier for Alice to identify
hashing power, specifically where she needs to send her blocks to
distribute them to the majority as quickly as possible. The second
problem occurs if those nodes also distribute blocks to connecting
peers: this makes it easy for Alice to be sure she'll hear about a new
block as soon as possible by connecting to every one of those peers with
a high-speed, low-latency connection. Bizzarely the idea does work if
the advertised nodes only accept blocks, and never send blocks - instead
miners would *only* send their blocks to other miners who have proven
their hashing power, and do so essentially largest miner to smallest.
Now unless Alice already is a large miner, her strategy can't work. Of
course this will strongly encourage further centralization of pools. But
it is in the interests of rational miners sadly.
That blocks take a finite amount of time to propagate makes the problem
worse: for Alice to learn that another block has been mined only
requires her to receive the small 80 byte header from a peer; she
doesn't need the whole block. She thus can know the block exists well
before it has a chance to propagate fully. Even if every miner were
directly peered to every other as some suggest, Alice could simply make
smaller blocks, faster propagating than everyone else and use especially
low-latency connections to win the race.
On the other hand, the Bitcoin protocol is currently designed such that
a miner can mine a block without knowing the previous block in full.
Given the large block reward and/or a supply of transactions they knew
no other miner had a rational miner would start trying to extend the
longest chain they know about prior to actually receiving and validating
the full block. Again, when miners start doing this - perhaps out of
desperation due to low revenue - as long as Alice has the lowest latency
network she'll win. (she doesn't even need to have the highest bandwidth
in this case) We can change the protocol to force miners to fully
validate blocks prior to mining extensions, but that only forces Alice
to get more bandwidth - she still wins.
Speaking of low-latency, latency not only centralizes control in a
single pool, it centralizes pools and even mining hardware itself in a
single physical location. Anyone at the edges of the propagation network
will get comparatively less revenue than those in the center, gradually
tightening the network, even without selfish mining. Alice's strategy of
course should be to position her nodes in the geographical center. It's
worth noting how if Alice is the one with the lowest average latency,
she will win against any other miner trying to persue the same selfish
miner strategy that she is using.
Finally nLockTime makes the selfish miner strategy even more profitable.
You may not be aware, but it's possible to make a transaction that can't
be mined until some time in the future, measured by either block height
or block timestamp. I've proposed to use this mechanism in
announce/commit sacrifices: you create a transaction that can't be mined
until some point in the future that sacrifices a large amount to mining
fees, and then prior to that point you include it in the blockchain as
data, proving the whole world knew about your transaction. The idea was
that which miner managed to include the transaction, and collect the
reward, would be random. However whenever Alice is able to maintain a
lead over other miners she's able to reliably mine significantly more of
those valuable transactions, further increasing her revenue over other
miners.
I must say, you've really opened a can of worms...
</pre>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">------------------------------------------------------------------------------
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
<a class="moz-txt-link-freetext" href="http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk">http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk</a></pre>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Bitcoin-development mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-development@lists.sourceforge.net</a>
<a class="moz-txt-link-freetext" href="https://lists.sourceforge.net/lists/listinfo/bitcoin-development">https://lists.sourceforge.net/lists/listinfo/bitcoin-development</a>
</pre>
</blockquote>
<br>
</body>
</html>
--------------030009050004090204050809--
|