Assuming this post is true, does Bitcoin have no limit on its value?

[finkleshnorts]

@jimbobway
How would that appear any different than more hashing power added to the network? I'm guessing no one will know that it's broken until someone draws up a proof.

Good point.  Depending on the strength of the cryptographic attack, let's supposed 100 blocks where solved in an hour.  It would raise a lot of suspicion since 100 is a lot.  The bitcoin client would then readjust the difficulty level and all other miners would not solve very many blocks.  Miners would complain and most likey the bitcoin dev team would change the algorithm.

But, if 10 blocks were solved in an hour and then the difficulty adjusted it could have been pure luck and there would be no sure fire way to prove it without mathematical proof.

I don't think breaking sha256 is "hacking".  It's like a gold miner finding the motherload.  However, I think breaking EC would be hacking.

I think it would take a lot more than disgruntled miners to cause an algo change

[1714124742]

1714124742

[1714124742]

1714124742

[1714124742]

1714124742

[1714124742]

1714124742

[notme]

@jimbobway
How would that appear any different than more hashing power added to the network? I'm guessing no one will know that it's broken until someone draws up a proof.

Good point.  Depending on the strength of the cryptographic attack, let's supposed 100 blocks where solved in an hour.  It would raise a lot of suspicion since 100 is a lot.  The bitcoin client would then readjust the difficulty level and all other miners would not solve very many blocks.  Miners would complain and most likey the bitcoin dev team would change the algorithm.

But, if 10 blocks were solved in an hour and then the difficulty adjusted it could have been pure luck and there would be no sure fire way to prove it without mathematical proof.

I don't think breaking sha256 is "hacking".  It's like a gold miner finding the motherload.  However, I think breaking EC would be hacking.

While this is correct, I'd like to point out that as mining moves to mostly ASIC, we will have the problem that any algorithm change will make all this custom hardware worthless.  I would think the producers of sha256 hardware would be able to quickly swap out the processors for something tuned to the new algorithm, but it still will be a higher barrier to get around.

[cypherdoc]

D&T is a respected member of the community who falls into the "brilliant" category when it comes down to mathematics and mining.  you have to at least respect his opinion.

I remember this argument he had with hashcoin on the subject of quantum computing.  I thought that D&T was wrong throughout the argument, but I'm no expert.  It just kind of ended with neither side coming around to the other's point of view.  Can you imagine??

i tried following that discussion when it happened too.  my mind almost exploded. 

[DeathAndTaxes]

The intent of the post quoted is being misunderstood.  The post simply deals with quantum computing and the very limited set of circumstances in which it could "kill" Bitcoin.  There are more likely threats to Bitcoin than Quantum computing.

From a big picture point of view there are three ways one could attack the cryptographic primatives used in Bitcoin:

• Quantum computing - very unlikely to be a threat (covered in the quoted post of OP).
• Brute force attack - there is insufficient energy remaining in our star to COUNT to 2^256 much less brute force it.
• Cryptographic flaw in one of the cryptographic primitives (ECDSA, SHA-256, RIPEMD-160) - the most plausible attack vector.

Is there a flaw?  It can't be proven.  SHA-256 has been very extensively tested by international community and so far it has remained very resistant to attack.  ECDSA is less tested although still subject to significant scrutiny.  At a minimum we can say no easily exploitable flaw has been found.  Now does a flaw mean "insta-kill bitcoin"?  No.  Most flaws tend to fall under the category of "only interesting to academics".  

SHA-256 (and SHA-512) has a cryptographic flaw.    WTF?  Yup right here:
http://eprint.iacr.org/2009/479.pdf

There is no economic value to this flaw.  However it "could" (eventually) lead to more "practical" attacks in the future.  

So what happens if SHA-256, RIPEMD-160 or ECDSA becomes "cryptographically weak"?
Well if they became weak enough one could attack private keys at a rate faster than an exhaustive brute force search.   Existing addresses would be vulnerable (at least in theory) however Bitcoin as designed to be modified.  Miners by consensus agree to a protocol enhancement which allows creation of addresses based on new cryptographic primitives (much like how Bitcoin now supports sending coins to addresses which are the hash of a script "pay to script hash"). So some future version of Bitcoin would continue to provide LEGACY support for existing addresses AND provide support for new addresses.  The timelines on cryptographic flaws tends to be measured in years so there would be extensive time to deploy a new version, and allow users to transfer coins from old "vulnerable" addresses to new "secure" addresses.  

If eventually ECDSA, SHA-256, or RIPEMD-160 becomes so degraded an attacker may be able to mine older "vulerable" addresses to steal the coins.  Users would have an incentive to upgrade their clients and move coins to newer "secure" addresses.

It is important to understand that even if we moved to a new algorithm as a precaution it might never be possible to use any flaw in practical manner.  I will give you an example.  A flaw has been discovered in SHA-1 which allows a pre-collision attack at 10,000 faster than brute force.  Sound horrible right?  Not really.  If such a flaw existing for SHA-256 it might mean you would have a 1% chance of attacking a private key in the next billion years (instead of 0.00001%).   Still as a precaution (more against future deeper flaws) it would be prudent to enhance the protocol to support newer address types.

Would a flaw in SHA-256 fatally damage the mining aspects of the network?
Under all probable scenarios no.  A round reduction attack would simply make miners more efficient (i.e.a GPU that runs at 1 GH/s might now compute at 520 TH/s).  Since difficulty is simply an arbitrary value it wouldn't really matter.  The nominal difficulty of the network would rise but miners with upgraded software/firmware would simply miner at a higher rate.  1% of network hashing power would still be 1% of network hashing power.  The one exception would be ASICs.  Since they can't be upgraded they would be a competitive disadvantage to both future ASICS (optimized to exploit any flaw) or programmable miners (CPU/GPU/FPGA).  Now granted ASICs are so much more efficient, that any disadvantage might only be academic at best.  

TL/DR version:
1) The post quoted dealt with quantum computing not SHA-256 invulnerability.
2) SHA-256 "may" be degraded someday.
3) Any attack on SHA-256 is likely to take a long time to develop and that will give the community time to upgrade.
4) The Bitcoin protocol can be enhanced to support new "strong addresses" while retaining legacy support for older "vulnerable" addresses.

[runeks]

• Cryptographic flaw in one of the cryptographic primitives (ECDSA, SHA-256, RIPEMD-160) - the most plausible attack vector.

I thought the fact that RIPEMD-160 was only used in conjunction with SHA-256 made an attack on it ineffective.
I mean, if bitcoin addresses were just RIPEMD-160 of public keys then a compromise of RIPEMD-160 would be catastrophic. But since it's RIPEMD-160(SHA-256(pub_key)) an attacker would have to break *both* SHA-256 and RIPEMD-160 in order to steal people's money, right? And at that point the protocol is broken anyway because mining relies on SHA-256.

SHA-256 (and SHA-512) has a cryptographic flaw.    WTF?  Yup right here:
http://eprint.iacr.org/2009/479.pdf

There is no economic value to this flaw.  However it "could" (eventually) lead to more "practical" attacks in the future.  

That's not an attack on SHA-256 and SHA-512. That's an attack on 41-Step SHA-256 and 46-Step SHA-512. Big difference . SHA-256 and SHA-512 are, respectively, 64 and 80 rounds, by definition. But I'm sure you knew that. Just wanted to point that out.

[Polvos]

Thank you D&T. I find all your posts extremely didactic.