An Analysis of the Correctness and Computational Complexity of Path Planning in Payment Channel Networks
2025
Read An Analysis of the Correctness and Computational Complexity of Path Planning in Payment Channel Networks (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-11419.txt.
Introduction
Corcoran and Lewis analyse path planning in payment channel networks in twenty twenty-five. These networks speed up cryptocurrency payments and cut their delay. A payment needs a cheap, feasible path through the network between two peers. Many planning tools use a variant of a classic shortest path algorithm.
The authors prove when that algorithm is correct and how costly it is. If channel fees meet a consistency property, the algorithm is correct and runs in polynomial time. In the general case, the algorithm can fail, and the planning problem is NP-hard. They show the Lightning Network, built on Bitcoin, currently meets the needed property. A two way search variant keeps the same theory bounds but runs faster in tests on that network.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-11419
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Analysis of the Correctness and Computational Complexity of Path Planning in Payment Channel Networks Abstract Payment Channel Networks (PCNs) are a method for improving the scaling and latency of cryptocurrency transactions. For a payment to be made between two peers in a PCN, a feasible low-fee path in the network must be planned. Many PCN path planning algorithms use a search algorithm that is a variant of Dijkstra’s algorithm. In this article, we prove the correctness and computational complexity of this algorithm. Specifically, we show that, if the PCN satisfies a consistency property relating to the fees charged by payment channels, the algorithm is correct and has polynomial computational complexity. However, in the general case, the algorithm is not correct and the path planning problem is NP-hard. These newly developed results can be used to inform the development of new or existing PCNs amenable to path planning. For example, we show that the Lightning Network, which is the most widely used PCN and is built on the Bitcoin cryptocurrency, currently satisfies the above consistency property. As a second contribution, we demonstrate that a small modification to the above path planning algorithm which, although having the same asymptotic computational complexity, empirically shows better performance. This modification involves the use of a bidirectional search and is empirically evaluated by simulating transactions on the Lightning Network. \addauthor [[email protected]] Padraig Corcoran School of Computer Science & Informatics, Cardiff University, Cardiff, Wales, UK. \addauthor [[email protected]] Rhyd Lewis School of Mathematics, Cardiff University, Cardiff, Wales, UK. \titlethanks Keywords. payment channel networks; path planning; lightning network. 1 Introduction A cryptocurrency is a digital currency that is decentralised in nature and not issued or controlled by a central authority. The most famous and successful example of a cryptocurrency is Bitcoin, invented by Satoshi Nakamoto [ 1 ] . Cryptocurrencies are enabled by the use of blockchain systems, which are a type of distributed system that maintains a ledger or database of digital currency transactions. A necessary component of any blockchain system is a consensus algorithm . This is an algorithm that allows all peers in the system to achieve agreement regarding the state of the ledger [ 2 ] . As a consequence of the need to ensure decentralisation and security, many consensus algorithms exhibit scalability issues relating to low transaction throughput (the number of transactions per second) and transaction confirmation latency (the time until a transaction can be considered settled). The former property can, in turn, lead to high transaction fees when large sets of transactions are competing to get into the blockchain. For example, Bitcoin can currently only process seven transactions per second and has a transaction confirmation latency of approximately ten minutes. This is assuming that the transaction is actually included in the very next block and is considered confirmed immediately when this happens. In contrast, the VISA payment system can process 65,000 transactions per second and has a transaction confirmation latency of just a few seconds. The low transaction throughput of Bitcoin means that, in times of high demand, transaction fees can be expensive and greatly exceed the cost of many everyday purchases. To overcome the above scaling challenge, several potential solutions have been proposed [ 3 ] . One promising direction of research is payment channel networks (PCNs) that allow the consolidation of a larger set of transactions into a smaller set, where individual transactions can be confirmed almost instantly. The Lightning Network (LN) is the most widely used PCN and is designed to work with Bitcoin [ 4 ] . To illustrate the potential benefits of PCNs, consider the case where Alice is a merchant and Bob is a customer. Alice makes regular small payments to Bob, and sometimes Bob makes refunds to Alice. Instead of submitting each transaction to be processed immediately by the consensus algorithm, Alice and Bob can establish a payment channel between them that maintains a balance that is updated after each transaction. When Alice and Bob have completed their transactions, they submit the final balance to be processed by the consensus algorithm. Since only a single transaction is processed by the consensus algorithm, this can increase transaction throughput significantly. Furthermore, since each transaction is only processed locally, the transaction latency is reduced to the time required to send a small number of network messages between Alice and Bob. By establishing a network of payment channels, individuals can also make payments to others who they do not share a direct payment channel with. For example, consider the case where Alice wants to make a payment to Charlie but has not established a corresponding payment channel. If Alice has an existing payment channel to Bob, and Bob has an existing payment channel to Charlie, then Alice can make the payment to Bob and Bob can, in turn, forward the payment to Charlie. PCNs are typically implemented using smart contracts, which are pieces of code executed on a blockchain that ensure the security of the payments. Despite the potential of PCNs, the technology still faces several challenges. This work focuses on path planning which concerns finding a useful path in the network of payment channels for making a given payment. There exists no universal method for performing path planning in most PCNs including the LN. Instead, different implementations use different methods for solving this problem [ 5 ] . Given that the size of PCNs can be very large, it is important that path planning is performed in a correct and computationally efficient manner. Most current path planning algorithms use a variant of Dijkstra’s algorithm. Dijkstra’s algorithm assumes that the network in question contains arcs with constant and non-negative weights. This assumption does not hold in the LN where arc weights correspond to fees charged for forwarding payments and vary as a function of the payment amount. Hence, existing correctness and computational complexity results for Dijkstra’s algorithm do not generalise to this variant. In fact, to the authors’ knowledge, there exists no analysis of this algorithm’s correctness and computational complexity in this setting. In this work, we address this research gap. These new results tell us that, if the PCN in question satisfies a consistency property relating to the fee charged for forwarding payments, the algorithm is correct and has polynomial computational complexity. Otherwise, in the general case, the algorithm is not correct and the path planning problem is NP-hard. In turn, we show that the LN satisfies this property. A second contribution made in this article is the proposal of a small modification to the above path planning algorithm which, though having the same asymptotic computational complexity, empirically shows better performance. This modification involves the use of a bidirectional search. The remainder of this paper is structured as follows. In Section 2 we review related works on path planning in PCNs. In Section 3 we formally define the problem of path planning in the LN. This section also identifies a connection between LN path planning and a specific recurrence relation , which we solve. In Sections 4 and 5 we formally describe the variant of Dijkstra’s algorithm mentioned above and provide an analysis of its correctness and computational complexity. In Section 6 we then describe the proposed modification