TLDR
- Payment Channel Network (PCN) is a scaling solution for Cryptocurrency networks.
- We advance the PCN multi-path routing by better modeling the system and
incorporating the cost of the routing fee and the privacy requirement of the channel
balance.- We design our Auto-Tune routing algorithm to optimize the routing concerning the
success rate and the routing fee and utilize the limited channel capacity
information.- To analyze the cost from the system requirement of the channel balance privacy, we compare Auto-Tune against the state-of-the-art Flash algorithm assuming the
availability of the channel balance information. The results show that the success rate
and fee obtained by Auto-Tune are close to that obtained by Flash.
Core Research Question
How to design a routing algorithm to optimize the routing concerning both success rate and routing fees while utilizing the limited channel capacity information (due to the privacy concern, the exact channel balance information is withheld under current implementations)?
Citation
H. -J. Hong, S. -Y. Chang and X. Zhou, "Auto-Tune: Efficient Autonomous Routing for Payment Channel Networks," 2022 IEEE 47th Conference on Local Computer Networks (LCN), 2022, pp. 347-350, doi: 10.1109/LCN53696.2022.9843633.
Background
- Payment Channel Network (PCN): A second layer network operating on top of the
cryptocurrency network to deal with the scalability issue. Specifically, PCN uses bidirectional payment channels to send off-chain transactions efficiently without
broadcasting to the public blockchain. All payment channels comprise a PCN. - Channel Establishment: Two parties establish a payment channel by depositing
funds on a 2-of-2 multi-signature wallet. The corresponding balances keep changing
as the two parties exchange mutually signed commitment transactions. - Channel Capacity & Balances: In current PCN implementations, the channel
balances are only known to the two parties due to privacy concerns. Other nodes in
PCN only know the channel capacity (the sum of channel balances). - Payment Routing: Payment routing in PCN is originally based on single path
routing. With limited channel capacity information, the routing has a poor success
rate. In view of this, both the academy and industry started working on multi-path
payment routing to improve performance. - Routing Fee: To give incentives to intermediate nodes in helping payment routing,
the sender should pay the routing fee to the intermediate node. Such cost is
significantly lower than the cost of building a direct channel between sender and
receiver.
Summary
- Payment reliability (success rate) is a concern in PCN due to two key factors. First,
the sender only has the channel capacity information for helping with the routing
decision due to the privacy concern. Second, the routing is originally based on
single-path routing while using a trial-and-error approach. - To improve reliability, the R&D community of PCN works on supporting multi-path
payments. However, how to cleverly split a payment while considering both the
success rate and routing fee is still a challenging problem. - We propose a multi-path routing algorithm called Auto-Tune to autonomously split a
payment based on the dynamic network view with channel capacities and optimally
tune the payment splitting amounts to maximize the success probability while
considering the routing fee. - The state-of-the art Flash algorithm assumes that the exact channel balance can be
probed and thus violates the current PCN implementation. Moreover, Flash classifies
the transaction into elephant and mice transactions and process them differently.
However, inferring the payment amounts and using it for setting up the elephant-
mice threshold is hard in PCN. - Simulation result shows that Auto-Tune achieves the routing fee close to the optimal
fee obtained by Flash (having the channel balance and violating the current design),
and the success rate is also close to the success rate achieved by Flash.
Method
- For the candidate path selection, we use Yen’s algorithm to obtain k shortest paths where k is decided by the preliminary analyses.
- We design a path score for evaluating different candidate paths for sending a split
payment a^x_{ij} where x is given by a candidate path p_x, i and j are the corresponding sender and receiver. The initial path score is designed as the success probability using the channel capacity information in PCN. - We observe that we should further use the first hop channel balance to further
optimize the design of path score. Therefore, we incorporate such information as
weights into the path score. The finalized weighted path score is computed as {\displaystyle \prod_{s=1}^{s=n} min(m(p_x), a^x_{ij}) \cdot P(b^s_x \geq a^x_{ij})} where m(p_x) represents the upper-bound amount that can support by the candidate path p_x, n is number of hops of p_x. Note that P(b^s_x \geq a^x_{ij}) represents the success probability when payment a^x_{ij} goes
through the s-th hop on path p_x. Since the corresponding balance information b^s_x is unknown, we utilize the capacity information c^s_x to compute the probability. In this work, we assume uniform channel balance distribution, so P(b^s_x \geq a^x_{ij}) is computed as \frac{c^s_x - a^x_{ij} + 1}{c^s_x}. - Auto-Tune finds the smallest number of paths to minimize routing fee while ensuring
the feasibility of selected path. There are different path selections that can have the
same number of paths, we select the one with the highest sum of path scores denoted
as \tilde{P_f}. Since the split payment amounts have not been assigned yet, we use equal splitting for compute the path score. After getting \tilde{P_f}, we use brute-force search to find the best split amounts that can maximize the path scores. - After sending the corresponding split payments, Auto-Tune utilizes success and
failure results as feedback to help make a better routing decision for the next round
and improve the success rate.
Results
- We generate two synthetic network topologies (scale-free Barabasi-Albert (BA)
graph and Watts-Strogatz (WS) small-world graph) for our simulation. We also use a
snapshot of real-work PCN topology as empirical data for comparison. - We compare our Auto-Tune algorithm with the shortest path approach and the state-
of-the-art Flash algorithm. The result shows that among those successful payments
achieved by Flash, 96.45%, 97.25%, and 97.77% of the payments can also succeed
using Auto-Tune for BA, WS, and empirical topology. - For fee comparison, we use the fee ratio as a metric. The fee ratios are 1.1141,
1.1472, and 1.123 on BA, WS, and empirical topology, respectively. The result
shows that Auto-Tune achieves the routing fee close to the optimal fee obtained by
Flash. (*Note that Flash uses the exact balance information so it can achieve optimal
solution. However, it violates the current PCN implementations.)
Discussion and Key Takeaways
- Multi-path routing can undoubtedly improve the success rate. However, how to
design a good routing algorithm while considering the trade-off between the success
rate and the routing fee is extremely important and worth some more discussion. - In academia, the state-of-art Flash routing algorithm (which is also based on multi-
path routing) unfortunately did not consider the current implementations that channel
balances should remain secret - In industry, different PCN implementations started supporting multi-path routing;
however, not so much effort is spent on optimally splitting a payment but blindly
splitting it (such as equal splitting). - Our work thus strives to fill the gap for both academia and industry.
Implications and Follow-Ups
- Future research directs to improve the success rate by getting more information, such as sharing the last-hop balance, because the sender knows the receiver and may request the receiver to share such information to increase the success rate.
- Another follow-up research could be designing a multi-path routing algorithm under
the scenario that the sender has a budget concern on the routing fee. Similarly, in a
more practical case, the sender might have an efficiency concern in sending a
payment. Therefore, designing a multi-path routing algorithm considering the
Hashed Timelock Contracts (HTLCs) is also an interesting and challenging topic.
Applicability
- Our Auto-Tune algorithm can undoubtedly benefit the industry working on multi-
path routing implementations on PCN. It brings a potential routing solution by
cleverly splitting a payment. - Since the path score design behind the Auto-Tune algorithm is based on success
probability, the solution can still work if the channel balance distribution changes.