Preview

Моделирование и анализ информационных систем

Расширенный поиск

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

https://doi.org/10.18255/1818-1015-2018-4-402-410

Аннотация

Технология блокчейн основана на принципе доказательства работой «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.


Рецензия

Для цитирования:


Дурнев В.Г., Мурин Д.М., Соколов В.А., Чалый Д.Ю. О некоторых подходах к решению задачи «Useful Proof-of-work for blockchains». Моделирование и анализ информационных систем. 2018;25(4):402-410. https://doi.org/10.18255/1818-1015-2018-4-402-410

For citation:


Durnev V.G., Murin D.M., Sokolov V.A., Chalyy D.J. On Some Approaches to the Solution of the Problem «Useful Proof-of-work for Blockchains». Modeling and Analysis of Information Systems. 2018;25(4):402-410. (In Russ.) https://doi.org/10.18255/1818-1015-2018-4-402-410

Просмотров: 1393


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)