ПОШУК ОПТИМАЛЬНОГО МАРШРУТУ ПЛАТЕЖУ У LIGHTNING NETWORK

Автор(и)

  • Є. С. Щербіна Вінницький національний технічний університет
  • В. І. Месюра Вінницький національний технічний університет

DOI:

https://doi.org/10.31649/1997-9266-2020-153-6-93-99

Ключові слова:

криптовалюта, біткоїн, блокчейн, лайтнінг, теорія графів, алгоритми на графах, пошук найкоротшого шляху

Анотація

Розглянуто проблему масштабування біткойн блокчейну та основні методи її вирішення. Описано основні методи вирішення цієї проблеми, такі як: SPV-вузли (Simplified Payment Verification), SegWit, допоміжні блокчейни (sidechains) та Лайтнінг мережа (Lightning Network). Наведено переваги та недоліки вищезгаданих підходів.

У статті наведені деталі технічного влаштування мережі Lighting Network, механізм якої дозволяє уникати запису кожної транзакції на блокчейн. Описані такі ключові концепції як непідтверджені транзакції, механізм захисту від подвійної витрати (double spend), мультипідпис, тимчасові блокування, хеші і секрети. Розглянуто процес відкриття каналу та здійснення лайтнінг транзакції. Надано та проаналізовано вихідний код програм на стековій мові програмування Bitcoin Scrypt, що використовуються під час здійснення лайтнінг (lightning) транзакцій.

В рамках статті запропоновано моделі, зручні для опису мережі лайтнінг (lightning), а саме графова та мережева модель. Графова модель має на увазі проведення платежу вздовж одного шляху, в свою чергу мережева модель має на увазі розбиття платежу на декілька платежів меншого розміру (можливо з використанням алгоритму AMP (Atomic Multipath Payment).

У статті розглянуто задачі, з якими стикаються розробники гаманців для Lightning Network, а саме знаходження розміру максимального платежу, який може бути проведений за певних умов (з довільною або фіксованою кількістю посередників) та проведення платежу фіксованого розміру з мінімально можливою комісією. Здійснено їх формалізацію в термінах теорії графів за допомогою розроблених моделей. Запропоновано детальний алгоритм розв’язання формалізованих задач, з використанням алгоритмів бінарного пошуку, алгоритму пошуку у ширину та алгоритму пошуку потоку мінімальної вартості (min-cost-max-flow).

Біографії авторів

Є. С. Щербіна, Вінницький національний технічний університет

аспірант кафедри комп’ютерних наук

В. І. Месюра, Вінницький національний технічний університет

канд. техн. наук, доцент, професор кафедри комп’ютерних наук

Посилання

«Пошук у ширину,» Електронний журнал MAXimal, 2008. [Електронний ресурс]. Режим доступу: https://e-maxx.ru/algo/bfs.

«Потік мінімальної вартості,» Електронний журнал MAXimal, 2008. [Електронний ресурс]. Режим доступу: https://e-maxx.ru/algo/min_cost_flow .

Btc Drak, Mark Friedenbach, and Eric Lombrozo, “CHECKSEQUENCEVERIFY,” 2015. [Electronic resource]. Available: https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki .

Eric Lombrozo, Johnson Lau, and Pieter Wuille, “Segregated Witness (Consensus layer) ,” 2015. [Electronic resource]. Available: https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki .

Johnson Lau, and Pieter Wuille, “Transaction Signature Verification for Version 0 Witness Program,” 2016. [Electronic resource]. Available: https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki .

Eric Lombrozo, and Pieter Wuille, “Segregated Witness (Peer Services),” 2016. [Electronic resource]. Available: https://github.com/bitcoin/bips/blob/master/bip-0144.mediawiki .

Peter Todd, “OP_CHECKLOCKTIMEVERIFY,” 2014. [Electronic resource]. Available: https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki .

Sean Bowe, and Daira Hopwood, “Hashed Time-Locked Contract transaction,” 2017. [Electronic resource]. Available: https://github.com/bitcoin/bips/blob/master/bip-0199.mediawiki .

##submission.downloads##

Переглядів анотації: 166

Опубліковано

2020-12-25

Як цитувати

[1]
Є. С. . Щербіна і В. І. . Месюра, «ПОШУК ОПТИМАЛЬНОГО МАРШРУТУ ПЛАТЕЖУ У LIGHTNING NETWORK», Вісник ВПІ, вип. 6, с. 93–99, Груд. 2020.

Номер

Розділ

Інформаційні технології та комп'ютерна техніка

Метрики

Завантаження

Дані завантаження ще не доступні.

Статті цього автора (авторів), які найбільше читають

1 2 > >>