Difficulty Scaling in Proof of Work for Decentralized Problem Solving

Authors

  • Pericles Philippopoulos Ozeki Inc.
  • Alessandro Ricottone McGill University
  • Carlos G. Oliver Ozeki Inc.

DOI:

https://doi.org/10.5195/ledger.2020.194

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.

Cover of Ledger volume 5 2020

Downloads

Additional Files

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

Issue

Vol. 5 (2020)

Section

Research Articles

License

Authors who publish with this journal agree to the following terms:

  1. The Author retains copyright in the Work, where the term “Work” shall include all digital objects that may result in subsequent electronic publication or distribution.
  2. Upon acceptance of the Work, the author shall grant to the Publisher the right of first publication of the Work.
  3. The Author shall grant to the Publisher and its agents the nonexclusive perpetual right and license to publish, archive, and make accessible the Work in whole or in part in all forms of media now or hereafter known under a Creative Commons Attribution 4.0 International License or its equivalent, which, for the avoidance of doubt, allows others to copy, distribute, and transmit the Work under the following conditions:
    1. Attribution—other users must attribute the Work in the manner specified by the author as indicated on the journal Web site;
    with the understanding that the above condition can be waived with permission from the Author and that where the Work or any of its elements is in the public domain under applicable law, that status is in no way affected by the license.
  4. The Author is able to enter into separate, additional contractual arrangements for the nonexclusive distribution of the journal's published version of the Work (e.g., post it to an institutional repository or publish it in a book), as long as there is provided in the document an acknowledgement of its initial publication in this journal.
  5. Authors are permitted and encouraged to post online a prepublication manuscript (but not the Publisher’s final formatted PDF version of the Work) in institutional repositories or on their Websites prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work. Any such posting made before acceptance and publication of the Work shall be updated upon publication to include a reference to the Publisher-assigned DOI (Digital Object Identifier) and a link to the online abstract for the final published Work in the Journal.
  6. Upon Publisher’s request, the Author agrees to furnish promptly to Publisher, at the Author’s own expense, written evidence of the permissions, licenses, and consents for use of third-party material included within the Work, except as determined by Publisher to be covered by the principles of Fair Use.
  7. The Author represents and warrants that:
    1. the Work is the Author’s original work;
    2. the Author has not transferred, and will not transfer, exclusive rights in the Work to any third party;
    3. the Work is not pending review or under consideration by another publisher;
    4. the Work has not previously been published;
    5. the Work contains no misrepresentation or infringement of the Work or property of other authors or third parties; and
    6. the Work contains no libel, invasion of privacy, or other unlawful matter.
  8. The Author agrees to indemnify and hold Publisher harmless from Author’s breach of the representations and warranties contained in Paragraph 6 above, as well as any claim or proceeding relating to Publisher’s use and publication of any content contained in the Work, including third-party content.
  9. The Author agrees to digitally sign the Publisher’s final formatted PDF version of the Work.

Revised 7/16/2018. Revision Description: Removed outdated link.