Proof-of-Work (PoW) is one of the fundamental and widely-used consensus algorithms in blockchains. In PoW, nodes compete to receive the mining reward by trying to be the first to solve a puzzle. Despite its fairness and wide-availability, traditional PoW incurs extreme computational and energy waste over the blockchain. This waste is considered to be one of the biggest problems in PoW-based blockchains and cryptocurrencies. In this work, we propose a new useful PoW called Proof-of-Useful-Randomness (PoUR) that mitigates the energy waste by incorporating pre-computed (disclosable) randomness into the PoW. The key idea is to inject special randomness into puzzles via algebraic commitments that can be stored and later disclosed. Unlike the traditional wasteful PoWs, our approach enables pre-computed commitments to be utilized by a vast array of public-key cryptography methods that require offline-online processing (e.g., digital signature, key exchange, zero-knowledge protocol). Moreover, our PoW preserves the desirable properties of the traditional PoW and therefore does not require a substantial alteration in the underlying protocol. We showed the security of our PoW, and then fully implemented it to validate its significant energy-saving capabilities.