О некоторых подходах к решению задачи «Useful Proof-of-work for blockchains»

Технология блокчейн основана на принципе доказательства работой «Proof-ofwork». Суть данного принципа состоит в том, что некоторое событие (например, перевод денежных средств с одного счета на другой) становится значимым только после того, как оно подтверждено определенным объемом вычислительной работы. Соответственно возникает потребность в вычислительных задачах, над которыми такую работу можно производить, причем на решение этих задач будет тратиться практически вся вычислительная мощность блокчейн-сети. На сегодня в качестве таких задач получили распространение «хэш-головоломки» – задачи поиска битовой строки с хэшем, удовлетворяющим определенным условиям. Существенным недостатком хэш-головоломок является отсутствие у них какого-либо полезного применения за пределами технологии блокчейн. В работе описываются подходы к решению задачи «Useful Proof-of-work for blockchains», а именно предлагается рассматривать в качестве вычислительных задач для доказательства работой возникающие на практике индивидуальные представители NP-полных задач, которые могут решаться, например, SAT- или LLL-решателями. Отдельной проработки требует вопрос об использовании FPT-задач. Предлагаемый подход позволяет обеспечить следующие свойства вычислительных задач для доказательства работой: полезность, управляемость сложностью задач (через изменение размерности, выбор задач определенного вида, указание точности необходимого решения), массовость. При этом допускается, что не каждая решенная задача может оказаться полезной, однако предоставляется возможность решать с помощью технологии блокчейн задачи, возникающие на практике. Кроме прочего, таким образом становится возможным сопоставить стоимость виртуальной криптовалюты через затраты электроэнергии при ее генерации с практическим результатом от решения вычислительных задач. Наиболее трудными вопросами в контексте рассматриваемого подхода являются реализация связи событий и задач, обеспечивающих эти события вычислительной работой, и реализация системы анализа сложности задач. Статью следует воспринимать как программу исследований, поскольку многие технические детали требуют отдельной проработки.

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.