If you find some way of hashing faster, the generating difficulty will just get higher. You might control the network's CPU power for a while, but if you can figure out a SHA-256 shortcut, everyone else will, too.

"Breaking" Bitcoin's non-standard use of SHA-256 means finding a way of creating a proof-of-work hash without doing all of the normal hashing work. But in almost all cases, you would still have to do some non-negligible amount of work. All this does is make hashing quicker for you, and this is a problem that can be solved with difficulty adjustments.

"Breaking" SHA-256 is exactly like creating a new computer chip that can do hashing 20x faster per watt than everyone else.

I will tell you one funny example from my life. Maybe you catch my worries on that.

Before many years, my friend met one well known girl from my country. She is pretty and popular, so he trotted out with it and said he get her phone number. I also liked her and was a little angry that I missed chance to meet her too. And because he didn't want to tell me her phone number .

So I told him one: "Okay, I will never know her phone number, but, please, tell me just md5 hash of it! You know that hashes are irreversible, so you do not tell me her number, but I will have a feel that I have a piece of her! He agreed, but was very 'lol' with my request - he called me a nerd .

But he was quite surprised and confused, because I told him her phone number after few minutes! I never called to this number, but it is great example that people too much rely on things they don't understand. Of cource we have only few notations of phone number in our country and approximately tens of millions unique phone numbers, so it was quite easy to break hash by bruteforce by knowing so little information.

I don't say in any way that inventors of bitcoin don't know technology they used! I just want to know *exactly* what is doing with bitcoin hashes and I'm not satisfied with 'it is well known hash function, it must be safe'! Unfortunately I did not find enough resource to know that, so I have to ask here. Please point me to some specification if exists, I will be glad to read that in detail!

Marek

I understand your worries, but your topic title is way too pretentious. You did not really find a vulnerability in the hash function.

It depends on how the the SHA-256 algorithm is broken.  If somebody creates a quantum computer with 400 qubits and is able to create any arbitrary SHA-256 hash with any other prefix or expected "proof of work" with a Big O(1) level of difficulty, Bitcoins as a program would simply be screwed and potentially attacked as if somebody just brought on a million new machines into the network.  It actually would be worse, as somebody with this kind of computing power would literally be able to create as many new blocks as fast or as slow as they cared, depending strictly on the speed of the computer to spit out new blocks.  This could conceivably happen in this situation about a thousand times per second or more, which would set up a DOS attack on the network like you've never seen before.  Difficulty could conceivably go to infinity in this situation and still not stop the flood of new blocks.  They would also all be valid new blocks, at least according to the current algorithm, and could not be rejected based upon increased difficulty.

Luckily, most current quantum computers are insanely expensive (that are genuine quantum computers) and have right now a dozen qubits as the largest register they are working with.  There is reason to believe that Moore's law applies to Quantum computing, so it is something to worry about in terms of future plans for the currency, but I put this on the order of an issue decades away, if even that.  It is also something which can be defeated at least temporarily by increasing the number of bits in the hash.

Quantum computers and in particular Shor's Algorithm (http://en.wikipedia.org/wiki/Shor%27s_algorithm) is a known weakness to encryption algorithms that depend on the public/private key method for them to work, of which the SHA-256 algorithm is certainly a member of that class of algorithms vulnerable to this kind of attack.   This algorithm isn't O(1), but it is awfully close.  What keeps it from being used is mainly a lack of hardware capable of carrying out the methodology, not a lack of ideas for it to work.

It is possible that some sort of conventional Von Neumann architecture-type computer (what most people call simply a "computer") would be able to "partially break" the algorithm where hashing would be made considerably easier than is currently the case.  In that situation, it would merely be a refinement of the algorithm and speeding up the process, in which case increasing the difficulty would protect the network at least for awhile (in terms of years of protection).  Even then, it would be wise to look at replacing the algorithm with something else.

That is ultimately the salvation for Bitcoins, and at some point in the future there will have to be a change in the basic algorithm used to creating blocks and used within Bitcoins.  We should be planning for that eventuality, even if now it is purely hypothetical.  The worst situation is an immediate and mandatory upgrade like happened to 0.3.9.

In a worst-case situation, would the whole chain have to be restarted with a new genesis block, or do you think some algorithm from some arbitrary block number, say block 200000, would require the new hashing/cryptographically securing algorithm?

Apparently the NSA is trying to work on "stronger" hash algorithms and are willing to keep the effort to upgrade the algorithm as declassified material on the presumption that American civilians also need this kind of improvement to help protect network communications in general.  Undoubtedly there will be stronger algorithms found in the future, and there may also be something which avoids the use of prime factorization and other approaches which are currently used for securing these hashes.

Yeah, it will be something that will impact far more than Bitcoins, that is for sure.

Thank you guys, it answered many my questions. Simply, when hash will be broken, we will change algorithm.

Maybe we should consider moving to something based upon http://en.wikipedia.org/wiki/Multivariate_cryptography for signing, as the hash can be changed, (made secure but making it longer).  The theft of coins is the real concern, as the network would be completely broken.