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
|
Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193]
helo=mx.sourceforge.net)
by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <btcdev@quinnharris.me>) id 1Vdqxj-0005Fk-S0
for bitcoin-development@lists.sourceforge.net;
Wed, 06 Nov 2013 00:27:11 +0000
Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of quinnharris.me
designates 67.223.164.214 as permitted sender)
client-ip=67.223.164.214; envelope-from=btcdev@quinnharris.me;
helo=fza.durangomail.com;
Received: from fza.durangomail.com ([67.223.164.214])
by sog-mx-3.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
id 1Vdqxi-0001Fz-IR for bitcoin-development@lists.sourceforge.net;
Wed, 06 Nov 2013 00:27:11 +0000
Received: from localhost (localhost [127.0.0.1])
by fza.durangomail.com (Postfix) with ESMTP id 7D5311E03F5
for <bitcoin-development@lists.sourceforge.net>;
Tue, 5 Nov 2013 17:27:04 -0700 (MST)
X-Virus-Scanned: amavisd-new at fza.durangomail.com
Received: from fza.durangomail.com ([127.0.0.1])
by localhost (fza.durangomail.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id pzPxLgfUQ_E8
for <bitcoin-development@lists.sourceforge.net>;
Tue, 5 Nov 2013 17:27:03 -0700 (MST)
Received: from localhost (localhost [127.0.0.1])
by fza.durangomail.com (Postfix) with ESMTP id DC1A21E0403
for <bitcoin-development@lists.sourceforge.net>;
Tue, 5 Nov 2013 17:27:02 -0700 (MST)
DKIM-Filter: OpenDKIM Filter v2.7.1 fza.durangomail.com DC1A21E0403
X-Virus-Scanned: amavisd-new at fza.durangomail.com
Received: from fza.durangomail.com ([127.0.0.1])
by localhost (fza.durangomail.com [127.0.0.1]) (amavisd-new, port 10026)
with ESMTP id yYcE9Lb_JiSb
for <bitcoin-development@lists.sourceforge.net>;
Tue, 5 Nov 2013 17:27:02 -0700 (MST)
Received: from [192.168.0.109] (pc-149-184-100-190.cm.vtr.net
[190.100.184.149])
by fza.durangomail.com (Postfix) with ESMTPSA id 0E8FA1E03F5
for <bitcoin-development@lists.sourceforge.net>;
Tue, 5 Nov 2013 17:27:01 -0700 (MST)
Message-ID: <52798CD3.3060806@quinnharris.me>
Date: Tue, 05 Nov 2013 21:26:59 -0300
From: Quinn Harris <btcdev@quinnharris.me>
User-Agent: Mozilla/5.0 (X11; Linux i686;
rv:24.0) Gecko/20100101 Thunderbird/24.1.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
References: <N1-9eAtMHauq2@Safe-mail.net> <52796C14.5070300@quinnharris.me>
<CANAnSg19N6Ri9vVkKqP2VB14KgLN6=whAbtzV9EBcLUfDs_dJQ@mail.gmail.com>
In-Reply-To: <CANAnSg19N6Ri9vVkKqP2VB14KgLN6=whAbtzV9EBcLUfDs_dJQ@mail.gmail.com>
Content-Type: multipart/alternative;
boundary="------------000601080001070909040108"
X-Spam-Score: -0.6 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
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.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
-0.0 SPF_PASS SPF: sender matches SPF record
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: 1Vdqxi-0001Fz-IR
Subject: Re: [Bitcoin-development] Possible Solution To SM Attack
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: Wed, 06 Nov 2013 00:27:12 -0000
This is a multi-part message in MIME format.
--------------000601080001070909040108
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
On 11/05/2013 08:03 PM, Drak wrote:
> On 5 November 2013 22:07, Quinn Harris <btcdev@quinnharris.me
> <mailto:btcdev@quinnharris.me>> wrote:
>
> I don't think choosing the block with the lowest hash is the best
> option. The good and bad miners have an equal probability of
> finding a
> lower hash. But after Alice finds a block she can easily
> determine the
> probability that someone else will find a lower hash value that meets
> the difficulty requirement. This can be used to judge if its best to
> start working on the next block or work on finding a lower value
> hash to
> increase the chance her block is used.
>
>
> Well in that case, you could make it unpredictable by choosing based
> on a hash of the blockhash and chose the lowest from two. There is no
> way for Alice to know if Bob's resulting hash will be higher or lower
> than hers since she does not know Bob's blockhash in advance and
> therefore she would be better broadcasting her block immediately.
>
I don't think that will work but the bit test I suggested won't work either.
Alice can calculate the hash of her blockhash and if the block to mine
is chosen based on the lowest result she will know the probability Bobs
block will be used. This complexity doesn't change anything. If hers
is more than 50% likely to be used she should mine the next block
otherwise its best to work to find a better current block.
But if the block determination takes into account the current difficulty
we can prevent Alice from knowing if Bobs or any block she mines is more
likely to win.
Assuming
a = hash of block A
b = hash of block B
difficulty = current difficulty such that A < difficulty and b < difficulty
The following code could be used to determine if the higher or lower
block should be chosen
uint256 choose_block(uint256 a, uint256 b, uint256 difficulty)
{
bool choice = false; // false for lower hash, true for greater hash
uint256 am = (a + d/4) % difficulty;
uint256 bm = (b + d/4) % difficulty
if (a + d/4 >= d)
choice = b > a || b < am || bm > a || bm < am;
else
choice = (b > a && b < am) || (bm > a && bm < am);
return choice ? (a > b ? a : b) : (a > b ? b : a);
}
The basic idea is to find a range over 0 to difficulty starting at A and
B that is 1/4 of the range of the difficulty. If the two ranges overlap
which should be 1/2 of the time pick the greater hash is used otherwise
the lower hash.
There is likely a cleaner solution but this demonstrates the basic idea.
You could use the hash of the blockhash and just set the difficulty to
the maximum hash value which would really just end up removing all the
modulus stuff and make the code simpler. But that code requires much
less computation that any cryptographic hash.
I think this is preferable to each node randomly picking a block to mine
on as the paper suggests. This should be completely unpredictable but
deterministic so all the miners should end up working on the same block.
> You could even add another unpredictable factor: deciding the rules of
> whether higher or lower wins by hashing both competing blockhashes. If
> the leading two hex digits are below 128 lower wins, and if above,
> higher wins.
>
> Drak
>
>
> ------------------------------------------------------------------------------
> November Webinars for C, C++, Fortran Developers
> Accelerate application performance with scalable programming models. Explore
> techniques for threading, error checking, porting, and tuning. Get the most
> from the latest Intel processors and coprocessors. See abstracts and register
> http://pubads.g.doubleclick.net/gampad/clk?id=60136231&iu=/4140/ostg.clktrk
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
--------------000601080001070909040108
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 bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 11/05/2013 08:03 PM, Drak wrote:<br>
</div>
<blockquote
cite="mid:CANAnSg19N6Ri9vVkKqP2VB14KgLN6=whAbtzV9EBcLUfDs_dJQ@mail.gmail.com"
type="cite">
<div dir="ltr">On 5 November 2013 22:07, Quinn Harris <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:btcdev@quinnharris.me" target="_blank">btcdev@quinnharris.me</a>></span>
wrote:<br>
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">I don't
think choosing the block with the lowest hash is the best<br>
option. The good and bad miners have an equal probability
of finding a<br>
lower hash. But after Alice finds a block she can easily
determine the<br>
probability that someone else will find a lower hash value
that meets<br>
the difficulty requirement. This can be used to judge if
its best to<br>
start working on the next block or work on finding a lower
value hash to<br>
increase the chance her block is used.</blockquote>
<div><br>
</div>
<div>Well in that case, you could make it unpredictable by
choosing based on a hash of the blockhash and chose the
lowest from two. There is no way for Alice to know if
Bob's resulting hash will be higher or lower than hers
since she does not know Bob's blockhash in advance and
therefore she would be better broadcasting her block
immediately.</div>
<div><br>
</div>
</div>
</div>
</div>
</blockquote>
I don't think that will work but the bit test I suggested won't work
either.<br>
<br>
Alice can calculate the hash of her blockhash and if the block to
mine is chosen based on the lowest result she will know the
probability Bobs block will be used. This complexity doesn't change
anything. If hers is more than 50% likely to be used she should
mine the next block otherwise its best to work to find a better
current block.<br>
<br>
But if the block determination takes into account the current
difficulty we can prevent Alice from knowing if Bobs or any block
she mines is more likely to win.<br>
<br>
Assuming<br>
a = hash of block A<br>
b = hash of block B<br>
difficulty = current difficulty such that A < difficulty and b
< difficulty<br>
<br>
The following code could be used to determine if the higher or lower
block should be chosen<br>
<br>
uint256 choose_block(uint256 a, uint256 b, uint256 difficulty)<br>
{<br>
bool choice = false; // false for lower hash, true for greater
hash<br>
uint256 am = (a + d/4) % difficulty;<br>
uint256 bm = (b + d/4) % difficulty<br>
if (a + d/4 >= d)<br>
choice = b > a || b < am || bm > a || bm < am;<br>
else<br>
choice = (b > a && b < am) || (bm > a
&& bm < am);<br>
return choice ? (a > b ? a : b) : (a > b ? b : a);<br>
}<br>
<br>
The basic idea is to find a range over 0 to difficulty starting at A
and B that is 1/4 of the range of the difficulty. If the two ranges
overlap which should be 1/2 of the time pick the greater hash is
used otherwise the lower hash. <br>
<br>
There is likely a cleaner solution but this demonstrates the basic
idea.<br>
<br>
You could use the hash of the blockhash and just set the difficulty
to the maximum hash value which would really just end up removing
all the modulus stuff and make the code simpler. But that code
requires much less computation that any cryptographic hash.<br>
<br>
I think this is preferable to each node randomly picking a block to
mine on as the paper suggests. This should be completely
unpredictable but deterministic so all the miners should end up
working on the same block.<br>
<br>
<blockquote
cite="mid:CANAnSg19N6Ri9vVkKqP2VB14KgLN6=whAbtzV9EBcLUfDs_dJQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div>You could even add another unpredictable factor:
deciding the rules of whether higher or lower wins by
hashing both competing blockhashes. If the leading two hex
digits are below 128 lower wins, and if above, higher
wins.</div>
<div><br>
</div>
<div>Drak</div>
</div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">------------------------------------------------------------------------------
November Webinars for C, C++, Fortran Developers
Accelerate application performance with scalable programming models. Explore
techniques for threading, error checking, porting, and tuning. Get the most
from the latest Intel processors and coprocessors. See abstracts and register
<a class="moz-txt-link-freetext" href="http://pubads.g.doubleclick.net/gampad/clk?id=60136231&iu=/4140/ostg.clktrk">http://pubads.g.doubleclick.net/gampad/clk?id=60136231&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>
--------------000601080001070909040108--
|
