  Proof-of-Work (PoW) blockchains have emerged as a robust and effective
consensus mechanism in open environments, leading to widespread deployment with
numerous cryptocurrency platforms and substantial investments. However, the
commonly deployed PoW implementations are all based on solving cryptographic
puzzles. Researchers have been pursuing the compelling idea of replacing
cryptopuzzles with useful computing tasks for over a decade, in face of the
substantial computational capacity of blockchain networks and the global
pursuit of a more sustainable IT infrastructure. In this study, we conduct a
comprehensive analysis of the prerequisites for alternative classes of tasks.
We provide insight into the effect of introducing "usefulness" and of
transitioning to task classes other than cryptopuzzles. Having distilled the
prerequisites, we use them to examine proposed designs from existing
literature. Finally, we discuss pertinent techniques and present research gaps
in the current state-of-the-art.
