ScaloWork: Useful Proof-of-Work with Distributed Pool Mining

Bitcoin blockchain uses hash-based Proof-of-Work (PoW) that prevents unwanted participants from hogging the network resources. Anyone entering the mining game has to prove that they have expended a specific amount of computational power. However, the most popular Bitcoin blockchain consumes 175.87 TWh of electrical energy annually, and most of this energy is wasted on hash calculations, which serve no additional purpose. Several studies have explored re-purposing the wasted energy by replacing the hash function with meaningful computational problems that have practical applications. Minimum Dominating Set (MDS) in networks has numerous real-life applications. Building on this concept, Chrisimos [TrustCom '23] was proposed to replace hash-based PoW with the computation of a dominating set on real-life graph instances. However, Chrisimos has several drawbacks regarding efficiency and solution quality. This work presents a new framework for Useful PoW, ScaloWork, that decides the block proposer for the Bitcoin blockchain based on the solution for the dominating set problem. ScaloWork relies on the property of graph isomorphism and guarantees solution extractability. We also propose a distributed approach for calculating the dominating set, allowing miners to collaborate in a pool. This enables ScaloWork to handle larger graphs relevant to real-life applications, thereby enhancing scalability. Our framework also eliminates the problem of free-riders, ensuring fairness in the distribution of block rewards. We perform a detailed security analysis of our framework and prove our scheme as secure as hash-based PoW. We implement a prototype of our framework, and the results show that our system outperforms Chrisimos in all aspects.