Route Discovery in Private Payment Channel Networks

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

Abstract

As payment channel networks (PCNs) like Bitcoin's Lightning Network transition toward "private channels" to enhance user privacy, traditional route discovery—which relies on a global knowledge of network topology—becomes increasingly untenable. This paper investigates the challenge of finding payment routes in "dark" networks where the map is hidden from users. We propose a family of gossip-based protocols that allow users to discover efficient payment paths without a global map, offering a tunable trade-off between privacy, path optimality, and communication overhead.

Introduction

Payment Channel Networks (PCNs) provide a scalable solution for off-chain cryptocurrency transactions. Historically, routing in these networks was straightforward because the network topology was public, allowing senders to compute paths locally. However, recent protocol upgrades, such as Bitcoin’s Taproot, have enabled the proliferation of "private channels." While these channels improve individual privacy, they fragment the network map, creating a "dark" environment where no single participant knows the full topology.

The core research question addressed here is: How can a sender find a cost-effective path to a receiver when the intermediate connections are unknown? Existing alternatives, such as Multi-Party Computation (MPC), are often too computationally expensive or require the participation of the entire network, making them impractical for high-frequency payments.

Proposed Protocols

The authors introduce a "meet-in-the-middle" exploratory framework where both the sender and the receiver initiate a search simultaneously. Two primary protocols are explored:

1. Forward-to-All (FtA)

In this protocol, the sender and receiver broadcast exploratory messages to all immediate neighbors. To ensure the discovery of the most cost-effective path, nodes implement a fee-proportional delay. When a node receives a message, it waits for a duration proportional to the fee it charges before forwarding the message. The first time an intermediate node receives messages from both the sender and receiver sides, a path is established. Because of the calibrated delays, the first path discovered is mathematically guaranteed to be the cheapest.

2. Degree-Proportional Random Walk (DPRW)

To minimize the communication footprint, the authors propose a random walk variant. Instead of broadcasting to all neighbors, nodes forward the message to a single neighbor chosen with a probability proportional to that neighbor’s degree (connectivity). While this significantly reduces the number of messages in the network, it sacrifices the guarantee of finding the absolute cheapest path.

Privacy and Security Enhancements

To protect against "spy" nodes that might attempt to link exploratory messages to specific transactions, the protocols utilize bilinear maps for message unlinkability and homomorphic encryption to accumulate and hide specific fee values along the path. This ensures that intermediate nodes cannot easily deduce the total cost or the identities of the transacting parties.

Experimental Methodology

The protocols were evaluated using two distinct network models:

  • Lightning Network Snapshot: A real-world dataset from September 2021, comprising 13,780 nodes and 63,518 channels.
  • Synthetic Graphs: Barabási-Albert scale-free networks (up to 20,000 nodes) were used to test the scalability of the protocols as the network size increases.

Key Insights and Results

The Efficiency-Privacy-Optimality Trilemma

The research highlights a fundamental trade-off in private routing: users can optimize for path cost, search efficiency, or privacy, but achieving all three simultaneously is difficult. The authors introduce a parameter ($\beta$) that allows users to tune the protocol based on their specific requirements.

Performance and Scaling

  • Network Involvement: The protocols are remarkably lean. In the Lightning Network simulation, the FtA protocol involved only 3% of nodes on average. The DPRW protocol was even more efficient, involving only 0.1% of the network.
  • Path Quality: The efficiency of the Random Walk comes at a cost; the paths discovered were approximately 3.36x more expensive than the optimal paths found by FtA.
  • Sublinear Scaling: Both theoretical analysis and empirical data suggest that the random walk protocol scales sublinearly, meaning it remains viable even as the network grows significantly larger.

Privacy Vulnerabilities

The study analyzed privacy through a "First Spy Estimator" model, where an adversary controls a set of nodes and attempts to identify the sender or receiver. The probability of a successful attack (Recall) ranged from 0.129 in high-privacy configurations to 0.43 in lower-privacy settings. A critical finding was that "Well-Connected Corruption"—where an adversary targets high-degree "hubs"—is the most effective strategy for de-anonymizing users.

Limitations and Future Work

While the proposed protocols offer a significant step forward for private PCNs, several challenges remain:

  1. Adversarial Assumptions: The current model assumes "honest-but-curious" nodes. Future research must address "active" adversaries who might drop messages or provide false fee information.
  2. Network Synchronicity: The fee-proportional delay mechanism assumes a stable network. Real-world internet jitter and latency could disrupt the timing required to guarantee the cheapest path.
  3. Discovery vs. Execution: This work focuses on finding the route. The actual execution of the payment (e.g., via Hashed Time-Locked Contracts) still presents its own set of privacy leaks that need to be addressed in tandem with discovery.
  4. Dynamic State: The impact of rapidly changing channel balances and fluctuating fees was not fully captured in the static simulation environment.

Conclusion

As cryptocurrency networks move toward greater default privacy, the methods by which we navigate these networks must evolve. By using physical time as an information carrier and employing targeted gossip protocols, it is possible to find viable payment routes in "dark" networks with minimal overhead and high levels of privacy.

Summary updated

BibTeX
@inproceedings{avarikioti2024route,
  author = {Zeta Avarikioti and Mahsa Bastankhah and Mohammad Ali Maddah-Ali and Krzysztof Pietrzak and Jakub Svoboda and Michelle Yeo},
  title = {{Route Discovery in Private Payment Channel Networks}},
  booktitle = {ESORICS Workshops},
  year = {2024},
  url = {https://openreview.net/forum?id=qtaj66Csyc},
}
Figure