A Novel Corona Graph Based Proof-of-Work Algorithm for Public Blockchains
Keywords:
Blockchain, Consensus, Corona Graphs, Cryptographic Puzzles, Proof-of-WorkAbstract
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.
Downloads
References
Nakamoto, S. (2008). "Bitcoin: A Peer-to-Peer Electronic Cash System." Available at: https://bitcoin.org/bitcoin.pdf
Mehmud Abliz, Taieb Znati and Adam J. Lee, “Mitigating Distributed Service Flooding Attacks with Guided Tour Puzzles, International Journal on Advances in Security’, vol 5 no 3 & 4, year 2012, http://www.iariajournals.org/security/
Dwork, C., & Naor, M. (1993). Pricing via Processing or Combatting Junk Mail. Advances in Cryptology - CRYPTO’92: Lecture Notes in Computer Science, 740, 139-147.
Gervais, A., Ritzdorf, H., Karame, G. O., & Capkun, S. (2015). Tampering with the Delivery of Blocks and Transactions in Bitcoin. CCS ’15 Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (pp. 692-705). Denver, Colorado, USA: ACM.
Meshkov, D., Chepurnoy, A., & Jansen, M. (2017). Short Paper: Revisiting Difficulty Control for Blockchain Systems. In Data Privacy Management, Cryptocurrencies and Blockchain Technology (pp. 429-436). Oslo, Norway
W. Mahmoud and A. Etaiwi, “Encryption algorithm using graph theory,” Journal of Scientific Research and Reports, vol. 3, no. 19, pp. 2519–2527, 2014.
Werner, F. Graph-Theoretic Problems and Their New Applications. Mathematics 2020, 8, 445. https://doi.org/10.3390/math8030445
A. Juels and J. Brainard, “Client puzzles: A cryptographic countermeasure against connection depletion attacks,” in NDSS ’99, San Diego, CA, 1999, pp. 151–165
X. Wang and M. K. Reiter, “Defending against denial-of service attacks with puzzle auctions,” in IEEE Symposium on Security and Privacy, Oakland, 2003, pp. 78–92
Luu, L., Narayanan, V., Zheng, C., Baweja, K., Gilbert, S., & Saxena, P. (2016). "A Secure Sharding Protocol for Open Blockchains." arXiv preprint arXiv:1704.08502.
B. Parno, D. Wendlandt, E. Shi, A. Perrig, B. Maggs, and Y. Hu, “Portcullis: Protecting connection setup from denial-of-capability attacks,” in ACM SIGCOMM, 2007, pp. 289– 300
G. A. Selim, “How to encrypt a graph,” International Journal of Parallel, Emergent and Distributed Systems, vol. 35, no. 6, pp. 668–681, 2020.
P. Kedia and S. Agrawal, “Encryption using Venn-diagrams and graph,” International Journal of Advanced Computer Technology, vol. 4, no. 01, pp. 94–99, 2015
M. Yamuna and K. Karthika, “Data transfer using bipartite graphs,” International Journal of Advance Research in Science and Engineering, vol. 4, no. 02, pp. 128–131, 2015.
B. R. Arunkumar, “Applications of Bipartite Graph in diverse fields including cloud computing,” International Journal of Modern Engineering Research, vol. 5, no. 7, p. 7, 2015
A. Razaq, H. Alolaiyan, M. Ahmad et al., “A novel method for generation of strong substitution-boxes based on coset graphs and symmetric groups,” IEEE Access, vol. 8, pp. 75473–75490, 2020.
R. Frucht and F. Harary, “On the corona of two graphs,” Aequationes Math, vol. 4, pp. 322–325, 1970.Garay, J. A., Kiayias, A., & Leonardos, N. (2015). "The Bitcoin Backbone Protocol: Analysis and Applications."
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.
