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; 
MIME-Version: 1.0
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
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
Precedence: list

--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">&lt;<a href=3D"mailto:rusty@rustcorp.com.au" target=
=3D"_blank">rusty@rustcorp.com.au</a>&gt;</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 &lt;<a href=3D"mailto:luke@dashjr.org">luke@dashjr.org</a>&gt; =
writes:<br>
&gt; On Tuesday, June 03, 2014 4:29:55 AM xor wrote:<br>
&gt;&gt; Hi,<br>
&gt;&gt;<br>
&gt;&gt; I thought a lot about the worst case scenario of SHA256d being bro=
ken in a<br>
&gt;&gt; way which could be abused to<br>
&gt;&gt; A) reduce the work of mining a block by some significant amount<br=
>
&gt;&gt; B) reduce the work of mining a block to zero, i.e. allow instant m=
ining.<br>
&gt;<br>
&gt; C) fabricate past blocks entirely.<br>
&gt;<br>
&gt; 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&#39;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&#39;Reilly Book<br>
&quot;Graph Databases&quot; 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--