  Bitcoin is the first of its kind, a truly decentralized and anonymous
cryptocurrency. To realize it, it has developed blockchain technology using the
concept of `Proof of Work' (PoW). The miners, nodes responsible for writing
transaction databases, solve a cryptographic puzzle to claim the right to write
to the database. Though bitcoin and many other relevant cryptocurrencies, such
as ether use revolutionary ideas, the main criticism involves computing
resources and energy consumption to solve puzzles that have otherwise no use.
There are attempts to use the PoW to do something useful, commonly referred to
as Proof-of-Useful-Work (PoUW). In this paper, we attempt to (i) make PoUW more
usable -- describe how a central problem setter can crowdsource their work as
PoUW and (ii) in the true spirit of blockchains, decentralize the role of
problem setter, whom we call puzzlers. We propose a formal framework to do so,
namely PUPoW. PUPoW has an inbuilt provision of payments from the puzzler to
the miner who solves its puzzle. Additionally, miners have the option to not
rely on a continuous feed of the puzzles and instead use original PoW puzzles.
  We also propose a way to use PUPOW for solving TOR vanity URL generation and
bitcoin vanity address generation problems. We call this PUPoW blockchain
solving vanity address generation problems as VanityCoin. Both problems require
generating public keys from private keys such that resultant addresses are of
interest. Such key pairs are found only by a brute-force search. However, there
are privacy concerns that miners would know the private keys of the puzzlers.
We resolve this by splitting the private keys, and the miners would know only
one part of it. In summary, we are proposing how PoW can be made practically
helpful, and we believe such an approach is needed for PoW blockchains to
survive.
