Blockchains (BCs) are distributed database systems, popular for their innovative, unsupervised maintenance process. They use a so-called consensus protocol to prevent inference by any third party of absolute trust. Security, privacy, consistency, and energy consumption have been identified as the main issues involved in BC maintenance. According to the recent literature, some of these issues can be formulated as combinatorial optimization (CO) problems, and this fact motivated us to consider incorporating CO approaches into a BC. In this paper, we propose the new combinatorial optimization consensus protocol (COCP) based on the proof-of-useful-work (PoUW) concept that assumes solving instances of real-life CO problems. Due to the complexity of the underlying CO problems, we have developed various types of heuristic methods, which are utilized in the COCP. Most of these methods are problem-dependent stochastic heuristic or metaheuristic methods. As is the case with the majority of consensus protocols, PoUW exhibits the property of asymmetry. It is difficult to find a solution for the considered CO problem; however, once a solution is found, its verification is straightforward. We present here a BC framework combining the two above-mentioned fields of research: BC and CO. This framework consists of improvements aiming towards developing the COCP of the PoUW type. The main advantage of this consensus protocol is the efficient utilization of computing resources (by exploring them for finding solutions of real-life CO problem instances), and the provision of a broad range of incentives for the various BC participants. We enumerate the potential benefits of the COCP with respect to its practical impacts and savings in power consumption, describing in detail an illustrative example based on part of the real-life BC network. In addition, we identify several challenges that should be resolved in order to implement a useful, secure, and efficient PoUW consensus protocol.

This paper proposes a variant of the recently reported pool mining approach and provides a reduction in the energy that is consumed by the blockchain consensus protocol. The novelty of the proposed architecture lies in the employment of an innovative cryptographic puzzle that is based on stream ciphering. This enables flexibility in setting the difficulty parameter of the protocol, and allows for the separation of the energy and memory resources that are required for the puzzle solving. The proposed approach provides high resistance against the following malicious activities of miners in public blockchain systems: (i) the submission of fake work and fictitious computation results; and (ii) some well-known attacks that target the blockchain incentive mechanism. We experimentally evaluate the power consumption of the proposed consensus protocol and compare it with the traditional proof-of-work protocol based on hashing. The obtained results point out the gain that the proposed pool mining provides compared with the traditional types.