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.