An analysis of the correctness and computational complexity of path planning in Payment Channel Networks

Corcoran, Padraig ORCID: https://orcid.org/0000-0001-9731-3385 and Lewis, Rhydian ORCID: https://orcid.org/0000-0003-1046-811X 2025. An analysis of the correctness and computational complexity of path planning in Payment Channel Networks. The Journal of Financial Technology

Preview

PDF - Accepted Post-Print Version Download (450kB) | Preview

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.

Item Type:	Article
Status:	In Press
Schools:	Computer Science & Informatics Mathematics
ISSN:	2516-3639
Date of First Compliant Deposit:	15 January 2025
Date of Acceptance:	13 January 2025
Last Modified:	29 Jan 2025 10:45
URI:	https://orca.cardiff.ac.uk/id/eprint/175234

Actions (repository staff only)

Edit Item