ПОШУК ОПТИМАЛЬНОГО МАРШРУТУ ПЛАТЕЖУ У LIGHTNING NETWORK - Щербіна, Є. С.; Месюра, В. І. (Вісник Вінницького політехнічного інституту, 2020)
Розглянуто проблему масштабування біткойн блокчейну та основні методи її вирішення. Описано основні методи вирішення цієї проблеми, такі як: 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).