Cryptology ePrint Archive: Report 2021/1539

Route Discovery in Private Payment Channel Networks

Zeta Avarikioti and Mahsa Bastankhah and Mohammad Ali Maddah-Ali and Krzysztof Pietrzak and Jakub Svoboda and Michelle Yeo

Abstract: In this work, we are the first to explore route discovery in private channel networks. We first determine what ``ideal" privacy for a routing protocol means in this setting. We observe that protocols achieving this strong privacy definition exist by leveraging (topology hiding) Multi-Party Computation but they are (inherently) inefficient as route discovery must involve the entire network.

We then present protocols with weaker privacy guarantees but much better efficiency. In particular, route discovery typically only involves small fraction of the nodes but some information on the topology and balances -- beyond what is necessary for performing the transaction -- is leaked.

The core idea is that both sender and receiver gossip a message which then slowly propagates through the network, and the moment any node in the network receives both messages, a path is found. In our first protocol the message is always sent to all neighbouring nodes with a delay proportional to the fees of that edge. In our second protocol the message is only sent to one neighbour chosen randomly with a probability proportional to its degree. While the first instantiation always finds the cheapest path, the second might not, but it involves a smaller fraction of the network.

% We discuss some extensions like employing bilinear maps so the gossiped messages can be re-randomized, making them unlikeable and thus improving privacy. We also discuss some extensions to further improve privacy by employing bilinear maps.

Simulations of our protocols on the Lightning network topology (for random transactions and uniform fees) show that our first protocol (which finds the cheapest path) typically involves around 12\% of the 6376 nodes, while the second only touches around 18 nodes $(<0.3\%)$, and the cost of the path that is found is around twice the cost of the optimal one.

Category / Keywords: applications / Bitcoin, Route discovery, payment channel networks

Date: received 22 Nov 2021

Contact author: michellexyeo at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20211122:113625 (All versions of this report)

Short URL: ia.cr/2021/1539


[ Cryptology ePrint archive ]