  Many blockchain systems today, including Bitcoin, rely on Proof of Work
(PoW). Proof of work is crucial to the liveness and security of
cryptocurrencies. The assumption when using PoW is that a lot of trial and
error is required on average before a valid block is generated. One of the main
concerns raised with regard to this kind of system is the inherent need to
"waste" energy on "meaningless" problems. In fact, the Bitcoin system is
believed to consume more electricity than several small countries.
  In this work we formally define three properties that are necessary for
wasteless PoW systems: (1) solve "meaningful" problems (2) solve them
efficiently and (3) be secure against double-spend attacks. These properties
aim to create an open market for problem-solving, in which miners produce
solutions to problems in the most efficient way (wasteless). The security of
the system stems from the economical incentive created by the demand for
solutions to these problems.
  We analyze these properties, and deduce constraints that must apply to such
PoW systems. In our main result, we conclude that under realistic assumptions,
the set of allowed problems must be preimage resistant functions in order to
keep the system secure and efficient.
