Research Summary: Auto-Tune: Efficient Autonomous Routing for Payment Channel Networks

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.
5 Likes

@CharlesHong

There are a few different approaches you could take to design a routing algorithm that optimizes both success rate and routing fees while utilizing limited channel capacity information. Here are a few ideas:

  1. Use probabilistic routing: One approach is to use probabilistic routing, which involves choosing the next hop based on the probability that it will lead to successful packet delivery. This probability can be calculated based on the success rate of previous packet deliveries over the same route, as well as other factors such as the current channel capacity and the routing fees charged by each node.

  2. Use reinforcement learning: Another option is to use reinforcement learning to train a routing agent to learn the optimal routing strategy based on past experience. The agent can be designed to consider both success rate and routing fees when making routing decisions, and can learn to adapt to changes in the network over time.

  3. Use optimization techniques: You could also try using optimization techniques such as linear programming or integer programming to find the optimal routing strategy based on the available information. These techniques can be used to minimize the total cost of routing (which could include both success rate and routing fees), subject to constraints such as the limited channel capacity.

It’s worth noting that all of these approaches have their own pros and cons, and the best approach for your specific situation will depend on the details of your network and the requirements of your application.

The formula for calculating the probability that a particular link will be selected as the next hop in a routing path is:

$$r = c * exp({-(\sum_{i=0}^{n-1}M_i/c)} / M)$$

Where:

  • r is the probability that the link will be selected as the next hop.
  • c is a constant that determines the relative importance of the routing fee versus the waiting time.
  • M_i is the waiting time at node i.
  • M is the total capacity of the network.

The probability is calculated based on the sum of the waiting times at each node along the route, divided by the total capacity of the network, and multiplied by a constant c. The constant c determines the relative importance of the routing fee versus the waiting time, and can be adjusted to prioritize either factor depending on the specific requirements of the application. The probability is also affected by the exponential function, which adjusts the magnitude of the probability based on the sum of the waiting times.

I hope this helps to clarify the formula and its purpose.

2 Likes

Hi @Humphery,

Thank you for your suggestion. It is interesting to see whether cost-optimal routing can benefit the routing algorithm design. However, the current fee model in PCN is constituted by a base fee and a proportional fee charged based on the payment value. Therefore, c in your formula should not be a fixed value. I will think more about how I can utilize it for payment routing. Thank you for your comment!

3 Likes