Quote from: RHorning on November 20, 2010, 05:24:06 PM

Quote from: theymos on November 20, 2010, 06:52:40 AM

"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.

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.

You can change the hash algorithm, the problem would be that the cypto that allows one to 'sign' a coin would also be broken, making bitcoin theft possible.