Finding the Optimal Payment Route in the Lightning Network

Abstract

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 min-cost-max-flow algorithms.