Пошук оптимального маршруту платежу у Lightning Network

Abstract

Розглянуто проблему масштабування біткойн блокчейну та основні методи її вирішення. Описано основні методи вирішення цієї проблеми, такі як: 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).

The article is devoted to the problem of scaling the bitcoin blockchain and the main methods of its solution. The main methods of solving this problem are described, such as SPV (simplified payment verification) — nodes, SegWit, auxiliary blockchains (sidechains) and Lightning Network (Lightning Network). The advantages and disadvantages of the above approaches are presented. The article provides details of the technical structure of the Lighting Network, the mechanism of which allows you to avoid writing each transaction on the blockchain. Key concepts such as unconfirmed transactions, double spend protection, multi-signature, temporary locks, hashes and secrets are described. The process of channel opening and lightning transaction are considered. The source code of Bitcoin Scrypt stack programming programs used during lightning transactions is provided and analyzed. The article proposes models that are convenient for describing lightning network, namely graph and network model. The graph model involves making a payment along one path, in turn, the network model involves splitting the payment into several smaller payments (possibly using the algorithm AMP — atomic multipath payment). The article describes the tasks faced by developers of wallets for Lightning Network, namely finding the size of the maximum payment that can be made under given conditions (with an arbitrary or fixed number of intermediaries) and making a fixed size payment with the minimum possible fee. Algorithms were formalized in terms of graph theory by the help of developed models. A detailed algorithm for solving formalized problems is proposed, using binary search, width search and mincostmax-flow algorithms.

Рассмотрена проблема масштабирования биткойн блокчейна и основные методы ее решения. Описаны основные методы решения этой проблемы такие как 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).