Beginner's question: Why must proof-of-work be useless?

I wonder why the proof-of-work under no circumstances may be usable.

Proof of work is useful: it allows a network of untrusted participants to reach consensus without the need for a trusted party.

As others have mentioned, making the work useful in other ways actually reduces this network security, as the cost of attack is subsidized by the external usefulness of the work.

Is a crypto currency system unconceivable where the user must pass the results of the proof-of-work to a central instance which can use them?

If the user would need the approval of the centralized party in order to add the next block, then this would be a huge security risk to the network: the centralized party would have the ability to arbitrarily censor users and transactions from participating. This is very unattractive, nobody should want to participate in a system that they might be unfairly censored from.

If the user would not need approval from the central party to add the next block, then how is the validity of their solution determined?

---

A good PoW algo will be hard to compute but easy to verify, and it should include a method to adjust the network difficulty.

In addition to this, the proof-of-work must somehow be tied to the specific block and transactions that are being mined. A good proof-of-work cannot just be some useful-equation-solution that has been arbitrarily attached to a block, that wouldn't provide much security at all!

As example: you wouldn't want a user to be able to take the solutions to past problems, build new blocks to attach them to, and then start broadcasting a conflicting history to network peers. By what method would a new network peer be able to decide which blockchain history is the correct one? It wouldn't be possible, since the work would not be inherently tied to any block.

On the other hand, energy spent on Bitcoin's proof-of-work inspires trust in the security of the network history, and in doing so it irrevocably attaches specific transactions to specific blocks.

In addition to the technical factors mentioned by MCCCS, it's important to consider economical factors as well.

If the problem being solved has value outside of the Bitcoin network, it allows miners to essentially "double dip" on the rewards - they earn both from the Bitcoin received as block rewards, as well as the incentive structure off chain.

For example, if the problem being solved is character recognition, it would enable a number of companies who seek good character parsing systems, such as Google, self driving car companies, etc, to double dip. These companies are then incentivized to build a a mining farm to not only train their programs, but also use that training to earn Bitcoin, subsidizing the operation they're already doing.

Being such large companies, their primary goal is likely to have a good text recognition system - the value of Bitcoin earned is secondary. This allows them to invest much more into their mining farms, potentially outstripping other miners who do not have a dual incentive. Moreover, as they get paid twice, it is in their favour to attempt to resolve minor reorgs to build on top of their blocks - they are already subsidized via the off chain incentive, so the cost of losing a block proportional to their operating cost is much lower, allowing them to take riskier routes to resolving minor forks.

This also reduces the cost of mounting attacks - if the mining power required to launch an attack is subsidized by external incentives, it is easier to pay for and acquire.

This also changes the reward structure overall - if the majority of the earnings for a miner are from an outside source, they are less concerned with the effects of bad blocks, 51% attacks, or other bitcoin issues that drop the value of bitcoin. The risk:reward calculation for attacking the chain becomes skewed, allowing for high reward attacks to have a lower cost than in a single use system.

The problem is that one can find a proof of work algorithm that gives a useful output. However, it may not stay useful forever. When the research is done, it will have to be replaced. When proof of work is replaced, years of research about ASIC designing for a specific algorithm is waster. The CPU => GPU => ASIC cycle starts again. In the first two stages of cycle, the coin is vulnerable to botnets. Since we're in the ASIC stage in Bitcoin, botnets would be relatively significantly inefficient, and there's no fear of a new miner coming in and killing the coin.

It is also unadvisable for a coin to have the same PoW algorithm as a coins with a larger hashrate, in which case the difficulty adjusting algorithm is abused and blocks are only feasible when the difficulty value drops.

But why not use ideas from captchas of which the usage can be monetarized (e.g. by improving character recognition systems)?

Because the most of proof of works aren't reusable. I can request a proof-of-work for a math problem but once you're done, there's no trustless way of generating original problems.