Difficulty Scaling in Proof of Work for Decentralized Problem Solving

  • Pericles Philippopoulos Ozeki Inc.
  • Alessandro Ricottone McGill University
  • Carlos G. Oliver Ozeki Inc.
Keywords: Proof of work, optimization, blockchain

Abstract

We propose DIPS (Difficulty-based Incentives for Problem Solving), a simple modification of the Bitcoin proof-of-work algorithm that rewards blockchain miners for solving optimization problems of scientific interest. The result is a blockchain which redirects some of the computational resources invested in hash-based mining towards scientific computation, effectively reducing the amount of energy ‘wasted’ on mining. DIPS builds the solving incentive directly in the proof-of-work by providing a reduction in block hashing difficulty when optimization improvements are found. A key advantage of this scheme is that decentralization is not greatly compromised while maintaining a simple blockchain design. We study two incentivization schemes and provide simulation results showing that DIPS is able to reduce the amount of hash-power used in the network while generating solutions to optimization problems.

Author Biographies

Pericles Philippopoulos, Ozeki Inc.

PhD Candidate, Department of Physics, McGill University

Co-founder Ozeki Inc. Blockchain Research & Consulting

Alessandro Ricottone, McGill University
PhD Candidate, Department of Physics, McGill University
Carlos G. Oliver, Ozeki Inc.

PhD Candidate, Computer Science

McGill University & Montreal Institute for Learning Algorithms

Co-founder Ozeki Inc. Blockchain Research & Consulting

References

Amar, D., Zilpa, L. “Incentive-Based Integration of UsefulWork into Blockchains.” arXiv (2019) (accessed 18 July 2020) https://arxiv:org/abs/1901:03375.

Andersen, J. V., Bogusz, C. I. “Patterns of Self-Organising in the Bitcoin Online Community: Code Forking as Organising in Digital Infrastructure.” In Thirty Eighth International Conference on Information Systems, Seoul 2017 (2017) https://aisel:aisnet:org/icis2017/DigitalPlatforms/Presentations/4/.

Anderson, D. P., Cobb, J., Korpela, E., Lebofsky, M., Werthimer, D. “SETI@home: An Experiment in Public-Resource Computing.” Communications of the ACM 45.11 56–61 (2002) https://doi:org/10:1145/581571:581573.

Ball, M., Rosen, A., Sabin, M., Vasudevan, P. N. “Proofs of UsefulWork.” IACR Cryptology ePrint Archive 2017 203 (2017) https://eprint:iacr:org/2017/203:pdf.

Bron, C., Kerbosch, J. “Algorithm 457: Finding All Cliques of an Undirected Graph.” Communications of the ACM 16.9 575–577 (1973) https://doi:org/10:1145/362342:362367.

Chatterjee, K., Goharshady, A. K., Pourdamghani, A. “Hybrid Mining: Exploiting Blockchain’s Computational Power for Distributed Problem Solving.” In Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing ACM 374–381 (2019) https://doi:org/10:1145/3297280:3297319.

Huang, C.-W., Lee, W.-S., Hsieh, S.-Y. “An Improved Heuristic Algorithm for Finding Motif Signals in DNA Sequences.” IEEE/ACM Transactions on Computational Biology and Bioinformatics 8.4 959–975 (2010) https://doi:org/10:1109/TCBB:2010:92.

Ileri, A. M., Ozercan, H. I., Gundogdu, A., Senol, A. K., Ozkaya, M. Y., Alkan, C. “Coinami: A Cryptocurrency with DNA Sequence Alignment as Proof-of-work.” arXiv (2016) (accessed 18 July 2020) https://arxiv:org/abs/1602:03031.

Karp, R. M. “Reducibility Among Combinatorial Problems.” In R. E. Miller, J.W. Thatcher, J. D. Bohlinger (Eds.), Complexity of Computer Computations Springer 85–103 (1972)https://doi:org/10:1007/978-1-4684-2001-2 9.

Kawrykow, A., et al. “Phylo: A Citizen Science Approach for Improving Multiple Sequence Alignment.” PloS one 7.3 e31362 (2012) https://doi:org/10:1371/journal:pone:0031362.

King, S. “Primecoin: Cryptocurrency with prime number proof-of-work.” primecoin.io (accessed 18 July 2020) https://primecoin:io/bin/primecoin-paper:pdf.

Larson, S. M., Snow, C. D., Shirts, M., Pande, V. S. “Folding@Home and Genome@Home: Using Distributed Computing to Tackle Previously Intractable Problems in Computational Biology.” arXiv (2009) (18 July 2020) https://arxiv:org/abs/0901:0866.

Li, J., Zimmerman, L. J., Park, B.-H., Tabb, D. L., Liebler, D. C., Zhang, B. “Network-Assisted Protein Identification and Data Interpretation in Shotgun Proteomics.” Molecular Systems Biology 5.1 https://doi:org/10:1038/msb:2009:54.

Loe, A. F., Quaglia, E. A. “Conquering Generals: an NP-Hard Proof of Useful Work.” In Proceedings of the 1st Workshop on Cryptocurrencies and Blockchains for Distributed Systems ACM 54–59 (2018) https://doi:org/10:1145/3211933:3211943.

Nakamoto, S. “Bitcoin: A Peer-to-Peer Electronic Cash System.” (2008) (accessed 18 July 2020) https://bitcoin:org/bitcoin:pdf.

No Author. “Bitcoin Energy Consumption Index.” Digiconomist (accessed 18 July 2020) https://digiconomist:net/bitcoin-energy-consumption.

No Author. “CureCoin Whitepaper.” FoldingCoin (2015) (accessed 18 July 2020) http://foldingcoin:net/the-coin/white-paper/.

No Author. “Total Hashrate.” Blockchain.com (accessed 18 July 2020) https://www:blockchain:com/charts/hash-rate.

Oliver, C. G., Ricottone, A., Philippopoulos, P. “Proposal for a Fully Decentralized Blockchain and Proof-of-Work Algorithm for Solving NP-Complete Problems.” arXiv (2017) (accessed 18 July 2020) https://arxiv:org/abs/1708:09419.

Tomita, E., Tanaka, A., Takahashi, H. “The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments.” Theoretical Computer Science 363.1 28–42 (2006) https://doi:org/10:1016/j:tcs:2006:06:015.

Xu, L., et al. “Enabling the Sharing Economy: Privacy Respecting Contract Based on Public Blockchain.” In S. Lokam, S. Ruj, K. Sakurai (Eds.), Proceedings of the ACM Workshop on Blockchain, Cryptocurrencies and Contracts 15–21 (2017) https://doi:org/10:1145/3055518:3055527.

Published
2020-08-20
How to Cite
Philippopoulos, P., Ricottone, A., & G. Oliver, C. (2020). Difficulty Scaling in Proof of Work for Decentralized Problem Solving. Ledger, 5. https://doi.org/10.5195/ledger.2020.194
Section
Research Articles