Proof of Work (PoW), which is a consensus algorithm for blockchain, entails a large number of meaningless hash calculations and wastage of electric power and computational resources. In 2021, it is estimated that the PoW of Bitcoin consumes as much electricity as Pakistan's annual power consumption (91TWh). This is a serious problem against sustainable development goals. To solve this problem, this study proposes Meaningful-PoW (mPoW), which involves a meaningful calculation, namely the application of a genetic algorithm (GA) to PoW. Specifically, by using the intermediate values that are periodically generated through GA calculations as an input to the Hashcash used in Bitcoin, it is possible to make this scheme a meaningful calculation (GA optimization problem) while maintaining the properties required for PoW. Furthermore, by applying a device-binding technology, mPoW can be ASIC resistant without the requirement of a large memory. Thus, we show that mPoW can reduce the excessive consumption of both power and computational resources.

Hashcash, which is a Proof of Work (PoW) of bitcoin, is based on a preimage problem of hash functions of SHA-2 and RIPEMD. As these hash functions employ the Merkle-Damgard (MD) construction, a preimage can be found with negligible memory. Since such calculations can be accelerated by dedicated ASICs, it has a potential risk of a so-called 51% attack. To address this issue, we propose a new PoW scheme based on the key recovery problem of cascade block ciphers. By choosing the appropriate parameters, e.g., block sizes and key sizes of underlying block ciphers, we can make this problem a memory-hard problem such that it requires a lot of memory to efficiently solve it. Besides, we can independently adjust the required time complexity and memory complexity, according to requirements by target applications and progress of computational power.