I would argue against the PoW having to be wasteful. It has to be difficult (in terms of compute power and time) but not wasteful. I'm not affiliated in any way with this, but there is one project that uses PoW to search for large primes.
The issue is economic, not technical. If I can sell the “useful” side effect of mining, then I can subsidize any attack I perform. The actual security of the network is only the work that has non-reimburseable costs.
a) it is economically rational to mine on the correct chain
b) there are substantial economic net costs to mining on a wrong fork of the chain (and these are high enough that it is prohibitively expensive to mount an attack which would fool people as to what chain is correct)
Right?
Finding primes aren't a great example. ... but unfortunately, they are the best example we have so far.
Also, I think those large primes do have economic value (https://en.wikipedia.org/wiki/Largest_known_prime_number#Pri...). I'm not sure if that's the purpose of PrimeCoin or who would get the prize, but they nonetheless have some economic value.
To see this, note that all POW and POS chains have "difficulty" functions that are actually just cost functions in external markets (hashpower or capital). What secures the difficulty of the attack in all casds is the supply curve of some block production factor in an external market.