Why do you say the proof of work needs to be "wasteful". The way I see it there are three major things:
1) It's hard to compute an answer (in bitcoin a low hash)
2) It's easy to verify an answer
3) The starting parameters can not be dictated by previous winners (the hash of the block in bitcoin)
This does not dictate that it can not be useful, in fact prime coin (http://primecoin.io/) could be used as an example of a cryptocurrency that has a moderately useful proof of work.
One proof of work could be based off of protein folding, however the parameters need to be chosen pesudo randomly or an attacker could store up a chain of multiple valid proofs of work then unlease a long chain all at once. So we can not direct the work, but the work can be done in a larger fertile space.
1) It's hard to compute an answer (in bitcoin a low hash)
2) It's easy to verify an answer
3) The starting parameters can not be dictated by previous winners (the hash of the block in bitcoin)
This does not dictate that it can not be useful, in fact prime coin (http://primecoin.io/) could be used as an example of a cryptocurrency that has a moderately useful proof of work.
One proof of work could be based off of protein folding, however the parameters need to be chosen pesudo randomly or an attacker could store up a chain of multiple valid proofs of work then unlease a long chain all at once. So we can not direct the work, but the work can be done in a larger fertile space.