Authors: Todorović, Milan 
Matijević, Luka 
Ramljak, Dušan
Davidović, Tatjana 
Urošević, Dragan 
Jakšić Kruger, Tatjana 
Jovanović, Đorđe 
Affiliations: Computer Science 
Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Proof-of-Useful-Work: BlockChain Mining by Solving Real-Life Optimization Problems
Journal: Symmetry
Volume: 14
Issue: 9
First page: 1831
Issue Date: 2022
Rank: ~M22
ISSN: 2073-8994
DOI: 10.3390/sym14091831
Abstract: 
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.
Keywords: consensus protocols | energy efficiency | combinatorial optimization | heuristic methods | distributed computing
Publisher: MDPI

Show full item record

SCOPUSTM   
Citations

1
checked on Feb 6, 2023

Page view(s)

12
checked on Feb 5, 2023

Google ScholarTM

Check

Altmetric

Altmetric


This item is licensed under a Creative Commons License Creative Commons