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 ) id 1WrqNv-0001lQ-EL for bitcoin-development@lists.sourceforge.net; Tue, 03 Jun 2014 15:12:19 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.214.169 as permitted sender) client-ip=209.85.214.169; envelope-from=dscvlt@gmail.com; helo=mail-ob0-f169.google.com; Received: from mail-ob0-f169.google.com ([209.85.214.169]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1WrqNt-0003Vd-Mp for bitcoin-development@lists.sourceforge.net; Tue, 03 Jun 2014 15:12:19 +0000 Received: by mail-ob0-f169.google.com with SMTP id vb8so6315436obc.0 for ; Tue, 03 Jun 2014 08:12:12 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.182.33.106 with SMTP id q10mr47223963obi.19.1401808332208; Tue, 03 Jun 2014 08:12:12 -0700 (PDT) Received: by 10.182.225.66 with HTTP; Tue, 3 Jun 2014 08:12:12 -0700 (PDT) In-Reply-To: References: <2341954.NpNStk60qp@1337h4x0r> <201406030452.40520.luke@dashjr.org> Date: Wed, 4 Jun 2014 00:42:12 +0930 Message-ID: From: Ashley Holman To: Ethan Heilman Content-Type: multipart/alternative; boundary=089e011614a4af436404faefefae 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 (dscvlt[at]gmail.com) -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: 1WrqNt-0003Vd-Mp Cc: Bitcoin Development 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 03 Jun 2014 15:12:19 -0000 --089e011614a4af436404faefefae Content-Type: text/plain; charset=UTF-8 There is a relevant post from Satoshi on this: https://bitcointalk.org/index.php?topic=191.msg1585#msg1585 Quote: "If SHA-256 became completely broken, I think we could come to some agreement about what the honest block chain was before the trouble started, lock that in and continue from there with a new hash function. If the hash breakdown came gradually, we could transition to a new hash in an orderly way. The software would be programmed to start using a new hash after a certain block number. Everyone would have to upgrade by that time. The software could save the new hash of all the old blocks to make sure a different block with the same old hash can't be used." On Tue, Jun 3, 2014 at 9:21 PM, Ethan Heilman wrote: > An attack on the mining difficulty algorithm does not imply violation of > the typical security properties of a cryptographic hash function*. > > Assume someone discovers a method which makes it far easier to discover > new blocks, this method: may or may not be implementable by the current > SHA256 ASIC hardware. > > 1. If it is usable by the mining hardware, then there will be brief period > of overproduction and then difficulty will adjust. If the attack is so bad > that difficulty can't scale and we run out of a leading zero's, then the > SHA256 collision resistance is broken and we have bigger problems. Under > this scenario, everyone would see the need to immediately switch to new > hardware as people could create cycles and irreconcilable forks in the > block chain > > 2. If the attack is not usable by the mining hardware, then the miners > will need to switch to new ASICs anyways and the hash function can be > changed without resistance. > > But lets ignore all that and say, for some unspecified reason, the bitcoin > community wants to switch hash functions and has some lead time to do so. > One could require that miners find two blocks, one computed using SHA256 > and one computed using the new hash function. We could then slowly shift > the difficulty from SHA256 to the new hash function. This would allow > miners a semi-predicable roadmap to switch their infrastructure away from > SHA256. > > * It would be a distinguisher which would be bad, but collision resistance > could be merely weakened. > > > On Tue, Jun 3, 2014 at 12:52 AM, Luke Dashjr wrote: > >> 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. >> >> Luke >> >> >> ------------------------------------------------------------------------------ >> 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 >> > > > > ------------------------------------------------------------------------------ > 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 > > --089e011614a4af436404faefefae Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
There is a relevant post from Satoshi on this:


Quote:

"If SHA-256 b= ecame completely broken, I think we could come to some agreement about what= the honest block chain was before the trouble started, lock that in and co= ntinue from there with a new hash function.

If the hash breakdown came gradually, we could transiti= on to a new hash in an orderly way. =C2=A0The software would be programmed = to start using a new hash after a certain block number. =C2=A0Everyone woul= d have to upgrade by that time. =C2=A0The software could save the new hash = of all the old blocks to make sure a different block with the same old hash= can't be used."


O= n Tue, Jun 3, 2014 at 9:21 PM, Ethan Heilman <eth3rs@gmail.com> wrote:
An attack on the mining dif= ficulty algorithm does not imply violation of the typical security properti= es of a cryptographic hash function*.

Assume someone discovers a method which makes it far easier to discover= new blocks, this method:=C2=A0may or may not be implementable by the curre= nt SHA256 ASIC hardware.

1. If it is usable by the mining hardware, then there will be brief per= iod of overproduction and then difficulty will adjust. If the attack is so = bad that difficulty can't scale and we run out of a leading zero's,= then the SHA256 collision resistance is broken and we have bigger problems= . Under this scenario, everyone would see the need to immediately switch to= new hardware as people could create cycles and irreconcilable forks in the= block chain

2. If the attack is not usable by the mining hardware, then = the miners will need to switch to new ASICs anyways and the hash function c= an be changed without resistance.

But lets ignore = all that and say, for some unspecified reason, the bitcoin community wants = to switch hash functions and has some lead time to do so. One could require= that miners find two blocks, one computed using SHA256 and one computed us= ing the new hash function. We could then slowly shift the difficulty from S= HA256 to the new hash function. This would allow miners a semi-predicable r= oadmap to switch their infrastructure away from SHA256.

* It would be a distinguisher which would be bad, but collision resista= nce could be merely weakened.


On Tu= e, Jun 3, 2014 at 12:52 AM, Luke Dashjr <luke@dashjr.org> wrot= e:
On Tuesday, June 03, 2014 4:29:55 AM xo= r 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 minin= g.

C) fabricate past blocks entirely.

If SHA256d is broken, Bitcoin as it is fails entirely.

Luke

---------------------------------------------------------------------------= ---
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/s= fu/NeoTech
_______________________________________________
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-de= velopment


-----------------------------------------------------------= -------------------
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/s= fu/NeoTech
_______________________________________________
Bitcoin-development mailing list
Bitcoin-develo= pment@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-de= velopment


--089e011614a4af436404faefefae--