It doesn't have to be wasteful but the computation must be asymmetric. That is it must be much more difficult to compute than to verify. The SHA-256 nonce disco

It doesn't have to be wasteful but the computation must be asymmetric. That is it must be much more difficult to compute than to verify. The SHA-256 nonce discovery computation used by Bitcoin has this property, but is not really useful. Others have given the example of PrimeCoin which is asymmetric, but somewhat useful as it discovers prime numbers. A great metaphor for this is a Sudoku puzzle. It is much harder to solve than it is to check the solution.