One candidate for useful work is TOR-supernode work. If the internet were to become distributed and fully encrypted you'd need a lot of bogus traffic and rerouting so the real traffic becomes invisible. There are many obvious problems with this, but in theory the more computational resources you put into a TOR-like network the more resilient and the more anonymous it becomes.

The morning paper had a post about it the other day[1], but I'm not sure if the solution is acceptable to the usual cryptocurrency crowd because it depends on running the useful code on a secure enclave (like Intel's SGX) to ensure single-threading and correct count of useful instructions that were executed. The miners are then rewarded according to number of useful instructions they executed. (The correctness of the instruction count and the work done can be validated cryptographically with SGX). I thought it was an interesting concept nonetheless.

[1]https://blog.acolyer.org/2017/09/06/rem-resource-efficient-m...

Absolutely! And even ‘proof of stake’ alternatives tend to degrade into ‘proof of work’ (citation required: unfortunately I’m on mobile and don’t have the link to the relevant papers to hand!)

Note: Even basic forms of proof of ‘useful’ work, like using the heat from the miners’ CPUs, just act like a subsidy and push the cost of competitive mining further away, rather than making the blockchain more efficient...

Securing a public ledger is useful.

The only kinds of problems that are suitable for PoW are those with predictable computational cost. The only thing that even approaches this and is also extrinsically useful is maybe math problems like finding prime numbers, but we don’t actually know what complexity class that falls under.

The problem with useful proof of work, is that the emission rate becomes very hard to control. In most PoW consensus algorithms, a difficulty parameter is constantly updated to keep the average block-time around 10 minutes. To do useful PoW consensus, you'd need to find a useful problem, where the difficulty of solving the different problems is easily solved, while the solution to the next block, is still dependent on the solution from the last block.