A Novel Corona Graph Based Proof-of-Work Algorithm for Public Blockchains - Agarwal, Shalini (International Journal of Intelligent Systems and Applications in Engineering, 2024)
Various mathematical puzzle-based Proof-of-Work (PoW) algorithms have been developed to prevent adversaries from adding illegitimate nodes in public blockchains. The puzzles are devised in such a manner that they are difficult to solve by the blockchain members, hereto called ‘provers’, but easily verifiable for correctness by the blockchain administrator, hereto called as ‘verifier’. However, existing algorithms are either very computationally intensive requiring high end processing capability or consume a lot of space for storing homogeneous data tables at prover and verifier ends. In this article, we introduce a novel Corona Graph based PoW technique for distinguishing adversaries from legitimate blockchain clients and hence mitigating addition of illegitimate nodes in public blockchains. The proposed algorithm exploits the properties of modular inverses of integers in such a way so as to create a tradeoff between computational complexity and storage space required. The values of the parameters can be adjusted to set the difficulty level of corona graph according to application requirements ranging from highly critical to common client server applications. We provide formal proof of correctness of our approach and demonstrate analytically that the proposed technique is resilient and offers a practical solution for identifying adversaries.