summaryrefslogtreecommitdiff
path: root/a9/52a74da18cd7b916acc445b087b54bc9c221cd
blob: ca0512c68ec0175e9fdc8e478adc2d5f9f475723 (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
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 <jeremy@taplink.co>) id 1Vdlp9-0000F6-0m
	for bitcoin-development@lists.sourceforge.net;
	Tue, 05 Nov 2013 18:57:59 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of taplink.co
	designates 50.117.27.232 as permitted sender)
	client-ip=50.117.27.232; envelope-from=jeremy@taplink.co;
	helo=mail.taplink.co; 
Received: from mail.taplink.co ([50.117.27.232])
	by sog-mx-1.v43.ch3.sourceforge.com with smtp (Exim 4.76)
	id 1Vdlp7-0002Ah-Sw for bitcoin-development@lists.sourceforge.net;
	Tue, 05 Nov 2013 18:57:58 +0000
Received: from laptop-air ([192.168.168.135]) by mail.taplink.co ;
	Tue, 5 Nov 2013 10:58:04 -0800
Content-Type: multipart/alternative; boundary=----------fjmie4P42zYKJW9i6gxToi
To: "Peter Todd" <pete@petertodd.org>, Ittay <ittay.eyal@cornell.edu>
References: <CABT1wWkOukEzxK5fLbnA4ZgJGN1hb_DMteCJOfA13FE_QZCi=Q@mail.gmail.com>
	<20131105170541.GA13660@petertodd.org>
	<CABT1wWnPJOKKT5v2hGePkUT8jNau=TEK5s-n2so2kQKnv-HfqQ@mail.gmail.com>
Date: Tue, 05 Nov 2013 10:57:34 -0800
MIME-Version: 1.0
From: "Jeremy Spilman" <jeremy@taplink.co>
Organization: TapLink
Message-ID: <op.w53ax8dtyldrnw@laptop-air>
In-Reply-To: <CABT1wWnPJOKKT5v2hGePkUT8jNau=TEK5s-n2so2kQKnv-HfqQ@mail.gmail.com>
User-Agent: Opera Mail/1.0 (Win32)
oclient: 192.168.168.135#jeremy@taplink.co#465
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 SPF_PASS               SPF: sender matches SPF record
	-0.0 RP_MATCHES_RCVD Envelope sender domain matches handover relay
	domain
	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: taplink.co]
	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: 1Vdlp7-0002Ah-Sw
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>,
	Gavin Andresen <gavin@bitcoinfoundation.org>,
	=?iso-8859-15?Q?Emin_G=FCn_Sirer?= <egs@systems.cs.cornell.edu>
Subject: Re: [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 18:57:59 -0000

------------fjmie4P42zYKJW9i6gxToi
Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
Content-Transfer-Encoding: 7bit

Great paper Ittay, thanks for all your work on this.

> Today the threshold is 0% with good connectivity.

Fig. 2 captures this well, the threshold is only zero if 'y' is 1. In  
Section 6 and 6.1 you argue y -> 1 but the sybil attack you describe,  
isn't that more like how *all* sophisticated miners would want to ensure  
their blocks are widely propagated? I think you can't assume only the  
selfish miner is doing it.

Based on the current  'first seen' algorithm, as you say, competing  
longest chains happen about every 60 blocks.  The rest of the time, a  
single block propagates through the vast majority of the network  
'uncontested'.  If there are multiple valid longest blocks being  
simultaneously propagated, then  propagation pattern of the competing  
blocks will determine hash rate on each.

Selfish mining requires exploiting the race condition between learning  
about a competing block, and publishing your own. Usually we talk about  
minimizing publishing latency so that your block ends up uncontested 59/60  
times, and in the 1/60 times, even then your block has the best chance of  
winning.

Selfish mining forgoes the 59/60 chance of your block being uncontested,  
and instead chooses to 'race the network' every time. You start 'one step  
behind' the competing block (since of course you only learn about it after  
it starts propagating), so you must rely on being able to outrace  
propagation of the competing block through a private low-latency  
side-network which can inject your block at multiple points throughout the  
bitcoin p2p network to outrace the competitor.

I think it's a stretch to say 'y' is 0 with good connectivity. Even the  
best connected mining pools today are concerned with this 'y' factor.

Here's a probably very dumb idea... to throw out one possible "solution"...

You want a way to fake-out the 'selfish miner' into disclosing their  
blocks -- how can your force their hand to prevent them from accumulating  
longer private chains?

What if you propagate (and relay) an encrypted block header which honest  
miners will timestamp when they receive it, then 10 seconds later  
propagate the decryption key to unblind it. But here's the catch - maybe  
the decryption results in junk, maybe it results a new longer block. If  
it's a real block then it gets priority based on when the ciphertext was  
received instead of when the decryption key was received. Now 'selfish  
miner' can't race the network anymore, because they are always in state 0'  
and can't tell if they are up against a ghost, or a real competing block.  
If they wait for the decryption key to check, it's too late, and they are  
guaranteed to lose unless they can out-race the network, e.g. back at  
t=50%. Of course there would need to be some way to anti-DDoS this which  
allows for some amount of these fake-outs without letting them get out of  
hand.

Thanks,
Jeremy
------------fjmie4P42zYKJW9i6gxToi
Content-Type: multipart/related; boundary=----------fjmie4P42zYKJW2CmQkai6

------------fjmie4P42zYKJW2CmQkai6
Content-Type: text/html; charset=utf-8
Content-ID: <op.1383677854843.6322d4655d6b28ec@192.168.168.135>
Content-Transfer-Encoding: Quoted-Printable

<!DOCTYPE html><html><head>
<style type=3D"text/css">body { font-family:'Times New Roman'; font-size=
:13px}</style>
</head>
<body><div>
<div>Great paper Ittay, thanks for all your work on this.&nbsp;</div></d=
iv><div>
<br><blockquote style=3D"margin: 0 0 0.80ex; border-left: #0000FF 2px so=
lid; padding-left: 1ex"><div dir=3D"ltr"><div>Today the threshold is 0% =
with good connectivity.&nbsp;<br></div></div></blockquote></div><div><br=
></div><div>Fig. 2 captures this well, the threshold is only zero if 'y'=
 is 1. In Section 6 and 6.1 you argue y -&gt; 1 but the sybil attack you=
 describe, isn't that more like how *all* sophisticated miners would wan=
t to ensure their blocks are widely propagated? I think you can't assume=
 only the selfish miner is doing it.</div><div><br></div><div>Based on t=
he current&nbsp;
'first seen'
algorithm, as you say, competing longest chains happen about every 60 bl=
ocks. &nbsp;The rest of the time, a single block propagates through the =
vast majority of the network 'uncontested'. &nbsp;If there are multiple =
valid longest blocks being simultaneously propagated, then&nbsp; propaga=
tion pattern of the competing blocks will determine hash rate on each.</=
div><div><br></div><div>Selfish mining requires exploiting the race cond=
ition between learning about a competing block, and publishing your own.=
 Usually we talk about minimizing publishing latency so that your block =
ends up uncontested 59/60 times, and in the 1/60 times, even then your b=
lock has the best chance of winning.</div><div><br></div><div>Selfish mi=
ning forgoes the 59/60 chance of your block being uncontested, and inste=
ad chooses to 'race the network' every time. You start 'one step behind'=
 the competing block (since of course you only learn about it after it s=
tarts propagating), so you must rely on being able to outrace propagatio=
n of the competing block through a private low-latency side-network whic=
h can inject your block at multiple points throughout the bitcoin p2p ne=
twork to outrace the competitor.</div><div><br></div><div>I think it's a=
 stretch to say 'y' is 0 with good connectivity. Even the best connected=
 mining pools today are concerned with this 'y' factor.&nbsp;</div><div>=
<br></div><div>Here's a probably very dumb idea... to throw out one poss=
ible "solution"...</div><div><br></div><div>You want a way to fake-out t=
he 'selfish miner' into disclosing their blocks -- how can your force th=
eir hand to prevent them from accumulating longer private chains?</div><=
div><br></div><div>What if you propagate (and relay) an encrypted block =
header which honest miners will timestamp when they receive it, then 10 =
seconds later propagate the decryption key to unblind it. But here's the=
 catch - maybe the decryption results in junk, maybe it results a new lo=
nger block. If it's a real block then it gets priority based on when the=
 ciphertext was received instead of when the decryption key was received=
. Now 'selfish miner' can't race the network anymore, because they are a=
lways in state 0' and can't tell if they are up against a ghost, or a re=
al competing block. If they wait for the decryption key to check, it's t=
oo late, and they are guaranteed to lose unless they can out-race the ne=
twork, e.g. back at t=3D50%. Of course there would need to be some way t=
o anti-DDoS this which allows for some amount of these fake-outs without=
 letting them get out of hand.</div><div><br></div><div>Thanks,</div><di=
v>Jeremy</div></body></html>
------------fjmie4P42zYKJW2CmQkai6--

------------fjmie4P42zYKJW9i6gxToi--