Geodesic
On some approaches to the solution of the problem for blockchains>>
Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 4, pp. 402-410.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : FPT, FPT
Keywords: proof-of-work, blockchain, satisfiability, SAT-solver, NP-complete, algorithm. 
@article{MAIS_2018_25_4_a4,
     author = {V. G. Durnev and D. M. Murin and V. A. Sokolov and D. Ju. Chalyy},
     title = {On some approaches to the solution of the problem {<<Useful} {Proof-of-work} for blockchains>>},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {402--410},
     publisher = {mathdoc},
     volume = {25},
     number = {4},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2018_25_4_a4/}
}
TY  - JOUR
AU  - V. G. Durnev
AU  - D. M. Murin
AU  - V. A. Sokolov
AU  - D. Ju. Chalyy
TI  - On some approaches to the solution of the problem <>
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2018
SP  - 402
EP  - 410
VL  - 25
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2018_25_4_a4/
LA  - ru
ID  - MAIS_2018_25_4_a4
ER  - 
%0 Journal Article
%A V. G. Durnev
%A D. M. Murin
%A V. A. Sokolov
%A D. Ju. Chalyy
%T On some approaches to the solution of the problem <>
%J Modelirovanie i analiz informacionnyh sistem
%D 2018
%P 402-410
%V 25
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2018_25_4_a4/
%G ru
%F MAIS_2018_25_4_a4
V. G. Durnev; D. M. Murin; V. A. Sokolov; D. Ju. Chalyy. On some approaches to the solution of the problem <>. Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 4, pp. 402-410. http://geodesic.mathdoc.fr/item/MAIS_2018_25_4_a4/

[1] Nakamoto S., Bitcoin: A Peer-to-Peer Electronic Cash System, , 2009, 9 pp. 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.Ṗ., Sakallah K.Ȧ., “GRASP: A new search algorithm for satisfiability”, ICCAD '96 Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, 1996, 220—227 | MR

[4] Bayardo Jr.Ṙ., 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] “Useful Proof-of-work for blockchains”, International Students' Olympiad in Cryptography NSUCRYPTO, 2017, 12–13 https://nsucrypto.nsu.ru/archive/2017/round/2/section/0/task/11

[6] 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 NP-Completeness, W. H. Freeman and Co, San Francisco, Calif., 1979 | MR | Zbl

[9] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to Algorithms, third ed., MIT Press, 2009 | MR | Zbl

[10] BitFury Group, Garzik J., Public versus Private Blockchains. Part 1: Permissioned Blockchains. White Paper, , 2015, 23 pp. https://bitfury.com/content/downloads/public-vs-private-pt1-1.pdf

[11] BitFury Group, Garzik J., Public versus Private Blockchains. Part 2: Permissionless Blockchains. White Paper, , 2015, 20 pp. https://bitfury.com/content/downloads/public-vs-private-pt2-1.pdf

[12] Downey R., Fellows M., Parameterized complexity, Springer Verlag, New York, 1999 | MR | Zbl

[13] Flum J., Grohe M., Parameterized complexity theory, Springer Verlag, Berlin–Heidelberg, 2006 | MR