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
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <cshrem@gmail.com>) id 1Ws09q-0001xq-MM
for bitcoin-development@lists.sourceforge.net;
Wed, 04 Jun 2014 01:38:26 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.192.42 as permitted sender)
client-ip=209.85.192.42; envelope-from=cshrem@gmail.com;
helo=mail-qg0-f42.google.com;
Received: from mail-qg0-f42.google.com ([209.85.192.42])
by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1Ws09p-0000vO-3y
for bitcoin-development@lists.sourceforge.net;
Wed, 04 Jun 2014 01:38:26 +0000
Received: by mail-qg0-f42.google.com with SMTP id q107so14847390qgd.29
for <bitcoin-development@lists.sourceforge.net>;
Tue, 03 Jun 2014 18:38:19 -0700 (PDT)
X-Received: by 10.224.4.66 with SMTP id 2mr988789qaq.58.1401845899279; Tue, 03
Jun 2014 18:38:19 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.96.52.106 with HTTP; Tue, 3 Jun 2014 18:38:04 -0700 (PDT)
In-Reply-To: <87iooi40ws.fsf@rustcorp.com.au>
References: <2341954.NpNStk60qp@1337h4x0r> <201406030452.40520.luke@dashjr.org>
<87iooi40ws.fsf@rustcorp.com.au>
From: "Charlie 'Charles' Shrem" <cshrem@gmail.com>
Date: Tue, 3 Jun 2014 21:38:04 -0400
Message-ID: <CAC787aM3bcfcw8zQQbNYXqxASFarW-z9wqiePmb6rv0RiiTdeA@mail.gmail.com>
To: Rusty Russell <rusty@rustcorp.com.au>
Content-Type: multipart/alternative; boundary=001a11c2e886db5d9c04faf8ae1d
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
(cshrem[at]gmail.com)
-0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/,
no trust [209.85.192.42 listed in list.dnswl.org]
-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: 1Ws09p-0000vO-3y
Cc: "bitcoin-development@lists.sourceforge.net"
<bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Lets discuss what to do if SHA256d is
actually broken
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, 04 Jun 2014 01:38:26 -0000
--001a11c2e886db5d9c04faf8ae1d
Content-Type: text/plain; charset=ISO-8859-1
Hey Rusty,
This is intriguing, do you have a writeup somewhere I can read more about ?
Thanks,
Charlie
CharlieShrem.com | *Please **encrypt messages with my PGP key
<http://charlieshrem.com/contact/>*
On Tue, Jun 3, 2014 at 8:45 AM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> Luke Dashjr <luke@dashjr.org> writes:
> > On Tuesday, June 03, 2014 4:29:55 AM xor wrote:
> >> Hi,
> >>
> >> I thought a lot about the worst case scenario of SHA256d being broken
> in a
> >> way which could be abused to
> >> A) reduce the work of mining a block by some significant amount
> >> B) reduce the work of mining a block to zero, i.e. allow instant mining.
> >
> > C) fabricate past blocks entirely.
> >
> > If SHA256d is broken, Bitcoin as it is fails entirely.
>
> I normally just lurk, but I looked at this issue last year, so thought
> I'd chime in. I never finished my paper though...
>
> In the event of an *anticipated* weakening of SHA256, a gradual
> transition is possible which avoids massive financial disruption.
>
> My scheme used a similar solve-SHA256-then-solve-SHA3 (requiring an
> extra nonce for the SHA3), with the difficulty of SHA256 ramping down
> and SHA3 ramping up over the transition (eg for a 1 year transition,
> start with 25/26 SHA2 and 1/26 SHA3).
>
> The hard part is to estimate what the SHA3 difficulty should be over
> time. My solution was to adjust only the SHA3 target on every *second*
> difficulty change (otherwise assume that SHA2 and SHA3 have equally
> changed rate and adjust targets on both).
>
> This works reasonably well even if the initial SHA3 difficulty is way
> off, and also if SHA2 breaks completely halfway through the transition.
>
> I can provide more details if anyone is interested.
>
> Cheers,
> Rusty.
>
>
> ------------------------------------------------------------------------------
> Learn Graph Databases - Download FREE O'Reilly Book
> "Graph Databases" is the definitive new guide to graph databases and their
> applications. Written by three acclaimed leaders in the field,
> this first edition is now available. Download your free book today!
> http://p.sf.net/sfu/NeoTech
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
--001a11c2e886db5d9c04faf8ae1d
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:arial,he=
lvetica,sans-serif;font-size:small;color:#666666">Hey Rusty,=A0</div><div c=
lass=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font=
-size:small;color:#666666">
<br></div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica=
,sans-serif;font-size:small;color:#666666">This is intriguing, do you have =
a writeup somewhere I can read more about ?=A0</div></div><div class=3D"gma=
il_extra">
<br clear=3D"all"><div><div dir=3D"ltr"><div><span style=3D"color:rgb(102,1=
02,102);font-family:arial,helvetica,sans-serif;font-size:13px;background-co=
lor:rgb(255,255,255)">Thanks,=A0</span><br></div><div><span style=3D"color:=
rgb(102,102,102);font-family:arial,helvetica,sans-serif;font-size:13px;back=
ground-color:rgb(255,255,255)"><br>
</span></div><div><span style=3D"color:rgb(102,102,102);font-family:arial,h=
elvetica,sans-serif;font-size:13px;background-color:rgb(255,255,255)">Charl=
ie</span></div><div><span style=3D"color:rgb(102,102,102);font-family:arial=
,helvetica,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br=
>
</span></div><div><span style=3D"color:rgb(102,102,102);font-family:arial,h=
elvetica,sans-serif"><a href=3D"http://CharlieShrem.com" target=3D"_blank">=
CharlieShrem.com</a> |=A0</span><font color=3D"#666666" face=3D"arial, helv=
etica, sans-serif"><i>Please=A0</i></font><i><span style=3D"color:rgb(102,1=
02,102);font-family:arial,helvetica,sans-serif">encrypt messages with=A0</s=
pan><a href=3D"http://charlieshrem.com/contact/" style=3D"font-family:arial=
,helvetica,sans-serif" target=3D"_blank">my PGP key</a></i></div>
</div></div>
<br><br><div class=3D"gmail_quote">On Tue, Jun 3, 2014 at 8:45 AM, Rusty Ru=
ssell <span dir=3D"ltr"><<a href=3D"mailto:rusty@rustcorp.com.au" target=
=3D"_blank">rusty@rustcorp.com.au</a>></span> wrote:<br><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pad=
ding-left:1ex">
Luke Dashjr <<a href=3D"mailto:luke@dashjr.org">luke@dashjr.org</a>> =
writes:<br>
> On Tuesday, June 03, 2014 4:29:55 AM xor wrote:<br>
>> Hi,<br>
>><br>
>> I thought a lot about the worst case scenario of SHA256d being bro=
ken in a<br>
>> way which could be abused to<br>
>> A) reduce the work of mining a block by some significant amount<br=
>
>> B) reduce the work of mining a block to zero, i.e. allow instant m=
ining.<br>
><br>
> C) fabricate past blocks entirely.<br>
><br>
> If SHA256d is broken, Bitcoin as it is fails entirely.<br>
<br>
I normally just lurk, but I looked at this issue last year, so thought<br>
I'd chime in. =A0I never finished my paper though...<br>
<br>
In the event of an *anticipated* weakening of SHA256, a gradual<br>
transition is possible which avoids massive financial disruption.<br>
<br>
My scheme used a similar solve-SHA256-then-solve-SHA3 (requiring an<br>
extra nonce for the SHA3), with the difficulty of SHA256 ramping down<br>
and SHA3 ramping up over the transition (eg for a 1 year transition,<br>
start with 25/26 SHA2 and 1/26 SHA3).<br>
<br>
The hard part is to estimate what the SHA3 difficulty should be over<br>
time. =A0My solution was to adjust only the SHA3 target on every *second*<b=
r>
difficulty change (otherwise assume that SHA2 and SHA3 have equally<br>
changed rate and adjust targets on both).<br>
<br>
This works reasonably well even if the initial SHA3 difficulty is way<br>
off, and also if SHA2 breaks completely halfway through the transition.<br>
<br>
I can provide more details if anyone is interested.<br>
<br>
Cheers,<br>
Rusty.<br>
<br>
---------------------------------------------------------------------------=
---<br>
Learn Graph Databases - Download FREE O'Reilly Book<br>
"Graph Databases" is the definitive new guide to graph databases =
and their<br>
applications. Written by three acclaimed leaders in the field,<br>
this first edition is now available. Download your free book today!<br>
<a href=3D"http://p.sf.net/sfu/NeoTech" target=3D"_blank">http://p.sf.net/s=
fu/NeoTech</a><br>
_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-develo=
pment@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
</blockquote></div><br></div>
--001a11c2e886db5d9c04faf8ae1d--
|