Anything that operates on proof-of-work like Bitcoin does will need a valuable operation that 1) can have its difficulty tuned up or down, 2) has a result that'

Anything that operates on proof-of-work like Bitcoin does will need a valuable operation that 1) can have its difficulty tuned up or down, 2) has a result that's quick to precisely verify, and (I suppose) 3) the result of which is less valuable than the coins it will yield. Oh and you'd want it to be basically the same operation at least for long periods of time, if not indefinitely. That narrows down what you can do with it quite a bit. [EDIT] oh AND it has to prove you were performing the operation with the current block in hand. No running ahead with the calculations then hashing it with the block when you get it, or anything like that. You mustn't be able to even start until you have the block.