On Some Approaches to the Solution of the Problem «Useful Proof-of-work for Blockchains»

The blockchain technology is based on the ”Proof-of-work” principles. The essence of this principle is that some event (for example the bill-to-bill money transaction) becomes significant after the confirmation by a certain computer work. So, a demand arose for such computational problems to work on, and we will spend on it about the whole blockchain system computing capacity. Now the main kind of such a problem is a hash-puzzle – the problem to find a bit string with a hash that satisfies some conditions. The important hash-puzzle weakness is the lack of the useful application outside of the blockchain technology. In this work, we offer some approaches to ”Useful Proof-of-work for blockchains” problem, namely, consider some practical variants of the NP-complete problems that could be solved with the help of SAT or LLL-solvers as the Proof-of-Work computational problems. The use of the FPTproblems requires special study. The offered approach allows to provide the following characteristics of the proof-of-work computational problems: usefulness, problems complexity management (through the dimension change, choosing problems of certain kind, the indication of necessary solution precision), mass character. Herewith we admit that not every solved problem can be useful but we consider the opportunity to solve some practical problems with the help of the blockchain technology. Among other things it is also possible to compare the virtual crypto-currency value (through the energy costs spent) and the effective result of the practical problems solution. The most complicated points of the described approach are the realization of the events-problems (providing the computer work for these events) relations and the realization of the problems complexity analysis system. This issue should be viewed as the study program because of many technical details that must be worked out further.

1. Nakamoto S., “Bitcoin: A Peer-to-Peer Electronic Cash System”, 2009, 1–9. https://bitcoin.org/bitcoin.pdf.

2. Buterin V., “Ethereum White Paper: A next-generation smart contract and decentralized application platform”, 2014. https://github.com/ethereum/wiki/wiki/White-Paper.

3. Marques-Silva J.P., Sakallah K. ˙ A., “GRASP: A new search algorithm for satisfiability”, ˙ ICCAD ’96 Proceedings of the 1996 IEEE/ACM international conference on Computeraided design, 1996, 220—227.

4. Bayardo Jr.R., Schrag R., “Using CSP look-back techniques to solve real-world SAT ˙ instances”, AAAI’97/IAAI’97 Proceedings of the fourteenth national conference on artificial intelligence and ninth conference on Innovative applications of artificial intelligence, 1997, 203—208.

5. “International Students’ Olympiad in Cryptography NSUCRYPTO. Useful Proof-of-work for blockchains”, 2017, 12–13. https://nsucrypto.nsu.ru/archive/2017/round/2/section/0/task/11.

6. “International Students’ Olympiad in Cryptography NSUCRYPTO. Unsolved problems”, 2018. https://nsucrypto.nsu.ru/unsolved-problems/.

7. Ball M., Rosen A., Sabin M., Vasudevan P. N., Proofs of Useful Work, 2017. https://eprint.iacr.org/2017/203.pdf.

8. Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman and Co, San Francisco, Calif., 1979.

9. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to Algorithms (third ed.), MIT Press, 2009.

10. BitFury Group, “Public versus Private Blockchains. Part 1: Permissioned Blockchains. White Paper”, 2015, 1–23 (совм. с Garzik J.). https://bitfury.com/content/downloads/public-vs-private-pt1-1.pdf.

11. BitFury Group, “Public versus Private Blockchains. Part 2: Permissionless Blockchains. White Paper”, 2015, 1–20 (совм. с Garzik J.). https://bitfury.com/content/downloads/public-vs-private-pt2-1.pdf.

12. Downey R., Fellows M., Parameterized complexity, Springer Verlag, New York, 1999.

13. Flum J., Grohe M., Parameterized complexity theory, Springer Verlag, Berlin, Heidelberg, 2006.