## 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.