The optimization "problem" is a problem because it can wipe out the currency. The transition to better hardware was gradual, while a software optimization could literally make one persons CPU more efficient than the rest of the world combined.
>Protein folding / structure prediction is NP-complete, so seems unlikely.
While it may be difficult to actually fold the protein, folding the protein such that it breaks one of the assumptions I listed may be trivial.
If we could simply use NP-hard proven problems as hash functions, we would.