I also think "wastefull" is the wrong word. It simply has to not benefit the miner MORE than everyone else. For example, if there was a pure public good proje

I also think "wastefull" is the wrong word. It simply has to not benefit the miner MORE than everyone else. For example, if there was a pure public good project that could provide random input / output, then it would still work. Primecoin is an example of that. While finding those specific primes is of extremely minimal value, it would still work even if solving those primes had considerable value - because it would be equally valuable to all.