Optimizing Off-Chain Payment Networks in Cryptocurrencies

Yotam Sali and Aviv Zohar Affiliation: The Hebrew University of Jerusalem, The School of Computer Science Affiliation: {yotam.sali,avivz}@cs.huji.ac.il

Abstract

Off-chain transaction channels represent one of the leading techniques to scale the transaction throughput in cryptocurrencies such as Bitcoin. They allow multiple agents to route payments through one another. So far, the topology and construction of payment networks has not been explored much. Participants are expected to minimize costs that are due to the allocation of liquidity as well as blockchain record fees. In this paper we study the optimization of maintenance costs of such networks. We present for the first time, a closed model for symmetric off-chain channels, and provide efficient algorithms for constructing minimal cost spanning-tree networks under this model. We prove that for any network demands, a simple hub topology provides a 2-approximation to the minimal maintenance cost showing that spanning trees in general are efficient. We also show an unbounded price of anarchy in a greedy game between the transactors, when each player wishes to minimize his costs by changing the network’s structure. Finally, we simulate and compare the costs of payment networks with scale free demand topologies.

1 Introduction

A main approach to solve the scalability problem in Bitcoin is to use off-chain transaction channels that allow parties to transfer funds while communicating directly, and only occasionally to settle the accumulated transfers that they have done on the blockchain [25]. In this manner, space on the blockchain (which is highly constrained) will be used to aggregate the result of multiple transactions that occurred over channels.

Transaction channels are created between a pair of participants by locking money into a “joint account”. The money is transfered between the participants by exchanging signed transaction messages that change the way funds in this account are allocated. The channel is closed by the participants when sending the latest transaction to the blockchain, which finalizes this allocation. Channels can be chained together securely to allow users to transfer funds to others that they are not directly connected to, and thus form fast payment networks that provide near instant payments that require few interactions with the blockchain.

The implication of this construction is that transaction channels necessitate locking liquidity for extended periods of time. These liquidity costs are balanced against the costs of fees that must be paid whenever channels are opened or closed—an operation that requires transactions on the blockchain. Intuitively, increasing liquidity costs by locking more funds into the channel lowers the fees that will be paid, as channels will need to be reset less often.

In this paper we take the first steps to study and optimize the costs of payment networks. We study both game-theoretic formation of channels, and globally optimal solutions.

Our Contributions:

•

We show that hub topologies can be highly efficient in terms of costs minimization, which increases the concern that large monopolistic players will arise and out-perform decentralized networks. We show this by exploring cost-optimal topologies and liquidity allocations, and by proving that a hub topology provides a 2-approximation to the optimal maintenance cost of any topology. We further show that this approximation is tight.
•

Using a model for the expected lifetime of symmetric channels (when both parties transfer coins in the same rate in both directions) from [9] we derive the optimal liquidity allocation for any topology and routing algorithm.
•

We solve the problem of building cost-optimal spanning tree networks for symmetric demands.
•

Finally, we explore a game theoretic model for the network formation of payment channels by defining a game in which participants connect to the network and seek to minimize their costs. We study the equilibrium points in the restricted setting of trees for this game, and prove an unbounded price of anarchy for this setting.

Our results open the field for further explorations of the costs of payment networks, and highlight the need for further study of more general cases (such as non-symmetric demands).

1.1 Payment Networks Basics

Payment channels are based on exchanging signed messages that describe how to allocate funds between pair of agents. For example, let us assume that Alice and Bob opened a payment channel by locking 0.5 BTC each. When Alice wants to transfer 0.1 BTC to Bob, she signs a message containing the new channel balance (of 0.4 BTC for Alice, 0.6 BTC coins for Bob, as described in figure 1, transaction 1). She sends the message to Bob, that transmits the message to the blockchain at will. Bob will usually not do so immediately, but rather hold on to this message and replace it with newer allocations after more transfers are made.

While transaction channels themselves are limited to exchanges between pairs of individuals, further developments like the Lightning network[25] allow users to securely route payments over longer paths and thus can allow the construction of a well connected network that can be used to transfer money quickly and with relatively little interaction with the blockchain. For example, let us assume that Alice wants to transfer money to Charlie. Instead of opening a shared payment channel or transacting directly via the blockchain, she can first transfer money to Bob via their shared payment channel, and ask Bob to send money to Charlie via another payment channel (as described in figure 1, transaction 2). In order to avoid the risk of having an intermediate node accept money without forwarding the payment, paths are composed using HTLCs (Hash time lock contracts) that release funds only if a secret—initially known only to the sender—is released. More details can be found in [25].

Refer to caption — Figure 1: Draw of payment network usage

When the most recent state of a channel allocates all funds in the joint account to one of the agents, it is no longer possible to transfer money to that agent using the channel. Further transfers must either use the blockchain directly, or the channel must go through a “reset”; recording the channel balance on the blockchain, and opening a new channel (alternatively funds can be added to the channel by the participant that lacks liquidity, but this too requires a blockchain transaction). As we have already mentioned, blockchain records incur a constant fee.

1.2 Related work

The original Lightning Network paper [25] suggests a BGP-like routing method. The implementation of the Lightning network (off-chain network over the Bitcoin blockchain), uses source routing, based on channel usage fees. The Raiden network [1], like other P2P networks, implements a Kademila-based routing system, in order to minimize the number of hops. Another idea for scaling transactions over Ethereum, is the Perun payment hub [11]. The idea is based on a network in the structure of a hub, that will be efficient in the number of routing hops per transaction. The paper implements a secured method for shortcutting several hops, based on smart contracts.

Several recent papers [5] [6] [13] discuss the same question of payment channels creation game as we did. However, while those papers choose a transaction-series/single-channel based model, we differ with a network traffic rates model. A recent paper [4] discussed the same question of global fees optimization in payment channels network design, but again it uses the same transaction-series model.

Two recent papers [8] [28] present a real data-driven analysis of lightning routing, fees and topology. We differ from them by presenting a theoretical model to this problem, rather than analyzing real-world data.

Some recent works [15, 26, 17] refer to other side-effects of routing (such as privacy and memory demands), and present efficient algorithms for the routing problem. The Fulgor and Rayo paper [22], that describes two of the major methods for the remaining privacy and concurrency in off-chain networks, assumes that routing path is being chosen by the transactor, in order to minimize the fee per transaction.

The topology of off-chain networks, has been studied in [2]. Measures such as the connectivity of the network and routing availability are the main focus. Algorithms for balancing edges (using “smart routing” of transactions) have been presented and simulated in [29]. Some mathematical analysis of the expected channel lifetime over off-chain channels, has been conducted [9]. We build upon and extend their model.

An economic model of the routing problem in Lightning, has been studied in [12], but we differ from this research in the basic model: The authors assume the cost of transmitting transactions is linearly related to the volume of payments and therefore the payoff can be formulated as a linear optimization problem. As far as we are aware, we are the first to explore cost minimization in this setting.

A recent paper [19] presents an instance local solution to the channel resets problem, which is re-balancing a group of channels by transacting in cycles. We differ from this paper, by our approach of optimizing topology and liquidities, rather than re-balancing a liquidities in some specific channels.

The Plasma paper [24] presents a generalization of payment channels to general state that is managed by local consensus protocols.

A few papers [21] [10] [23] discuss the problem of optimizing communication networks from the perspective of cut-capacities, Gomory-Hu trees and submodular optimization. We use a similar approach in our paper.

2 The Model

We now present our model of off-chain payment networks. We first define the state of a channel, and how transactions affect it, then define a payment network and a routing policy, and finally, a probabilistic model for transaction demand.

The State of a Channel

Let $e$ be a payment channel between two participants: Alice and Bob. The payment channel state is a pair $(\omega_{A},\omega_{B})$ , denoting the internal allocation of funds between the participants (Alice holds $\omega_{A}$ coins, and Bob holds $\omega_{B}$ coins). The sum $\omega=\omega_{A}+\omega_{B}$ is called the liquidity of the channel, and the amounts $\omega_{A},\omega_{B}$ must be non-negative.

Feasible Transactions

The liquidity of the channel, remains constant during its lifetime. Transactions, however, change the internal balance. Given a channel between Alice and Bob, with state $(\omega_{A},\omega_{B})$ , a transaction of $x$ coins from Alice to Bob changes the state to $(\omega_{A}-x,\omega_{B}+x)$ . The transaction is feasible if and only if $0\leq x<\omega_{A}$ , i.e., it cannot reach or exceed the liquidity boundaries.

Although transfers in one direction are still possible when liquidity is fully shifted to one of the channel’s sides, we assume the channel has to always be ready for transfers in both directions (otherwise we may be forced to use a blockchain transaction which takes very long). Therefore, we assume channels are reset whenever liquidity has fully shifted.

The Cost of Payment Channels

We model the cost of locking liquidity $\omega$ in the channel as $\alpha\cdot\omega$ coins per second, where $\alpha$ reflects the interest rate in the economy. We further denote the blockchain fee required to write a record by $\phi$ . This fee is paid whenever a channel reset occurs. ¹¹ 1 There may in fact be added costs for writing more-complex transactions to the blockchain that both transfer and reset the channel.

We denote by $RPS$ the rate of blockchain records per second that are used to maintain channels. The cost of a channel (per time unit) is then $\alpha\cdot\omega+\phi\cdot RPS$ .

We are now ready for definitions pertaining to more complex networks:

Definition 1 (Payment Network).

A payment network is described by a graph $G=(V,E)$ , and a liquidity allocation $\omega:E\rightarrow R^{+}$ . $V$ denotes the set of transactors, $E$ is the set of payment channels, and $\omega(e)$ is the liquidity of channel $e$ . We denote the sum of all channels’ liquidities as $W$ . Transactions are transfered over paths in the graph. A transaction of $x$ coins via the path $(e_{1},...,e_{n})$ , changes the state $(\omega_{i_{1}},\omega_{i_{2}})$ of channel $e_{i}$ (for every $i$ ), to be $(\omega_{i_{1}}-x,\omega_{i_{2}}+x)$ . Transactions must be feasible for all channels along the path.

Given a payment network, it is important how payments are routed (as this may in turn affect the volume of payments going through individual channels).

Definition 2 (Routing Policy).

A routing policy $\pi$ over a graph $G=(V,E)$ is a function $\pi$ such that $\pi(i,j)$ is a legal path in $G$ between $i$ and $j$ with no cycles. For every $i,j\in V$ there holds $\pi(i,j)$ is the reverse of $\pi(j,i)$ .

This definition refers to a state-independent symmetric routing protocol. We restrict our attention to protocols that do not depend on direction or state, since this is the current way payment networks are implemented in Bitcoin (routing is independent of channel state as state changes too quickly to allow for global routing adjustments to occur).

Finally, we will define the demand matrix, which defines a probabilistic model for transaction requests:

Definition 3 (The Demand Matrix).

Let $G=(V,E)$ be a payment channel network, $V={v_{1},\ldots,v_{n}}$ and let $(\lambda_{i,j})$ denote the Demand Matrix for transactions. Every second, $v_{i}$ transfers to $v_{j}$ an amount of coins, from a Poisson process with mean $\lambda_{i,j}$ .

The demand matrix along with the topology and routing protocol effectively set the number of transfers on each channel and will later allow us to derive the maintenance costs of the network.

2.1 Symmetric Networks

We are particularly interested in symmetric-demand networks, in which each pair of participants transact at the same expected rate in both directions, since such payments often cancel out and represent an optimistic case for transaction channels’ lifetimes.

We thus assume that transaction amounts are all identical (for convenience, we assume all transfers are for 1 unit of money), and that furthermore, transaction rates are symmetric: $\lambda_{ij}=\lambda_{ji},\ \ \forall\ 1\leq i,j\leq n$ .

The symmetric demands assumption, creates only balanced channels for every routing policy. That is because the traffic components over a channel, are identical in both directions. Under this model, each channel is simulating a random walk process. Every time a transaction through the channel is infeasible (due to liquidity constraints), we reset the channel, and pay a constant blockchain fee.

Definition 4.

Let $e$ be an off-chain transaction channel. Let $T_{i}$ [seconds] be the random variable of the channel lifetime after $i-1$ resets of the channel. Let $\phi$ [coins] be the constant fee for blockchain record. We define $RPS_{e}$ [ $\frac{records}{seconds}$ ], the average rate of records per second, to be:

RPS_{e}=\lim_{k\to\infty}\mathrm{E}\left[\frac{k}{T_{1}+...+T_{k}}\right]

The blockchain cost per second is then $\phi\cdot RPS_{e}$ .

Lemma 1.

Let $T_{i}$ [seconds] be the random variable of channel $e$ ’s lifetime after $i-1$ blockchain records. For every $i$ , Let $\mu_{e}=E[T_{i}]$ . Therefore:

\lim_{k\to\infty}\mathrm{E}\left[\frac{k}{T_{1}+...+T_{k}}\right]=\frac{1}{\mu_{e}}

Proof.

From the Strong law of large numbers [16], since $T_{1},\ldots,T_{k}$ are identically distributed, independent and have finite expected value, the series of arithmetic means $\frac{T_{1}+...+T_{k}}{k}$ is converging almost surely to $\mu_{e}$ . We will prove that $\frac{1}{\frac{T_{1}+...+T_{k}}{k}}$ converges almost surely to $\frac{1}{\mu_{e}}$ . Let us denote:

\begin{split}X_{k}=\frac{T_{1}+...+T_{k}}{k},\ \ X=\mu_{e},\ \ \\ A=\{\omega:\lim_{k\to\infty}X_{k}(\omega)=X(\omega)\}\end{split}

(1)

From convergence almost surely $P(A)=1$ . From the basic laws of calculus, we know that on $A\cap\{\omega:X(\omega)\neq 0\}$ there holds

\lim_{k\to\infty}\frac{1}{X_{k}(\omega)}=\frac{1}{X(\omega)}

(2)

Since $X$ is a positive constant random variable, $\{\omega:X(\omega)\neq 0\}=\Omega$ . Therefore:

\begin{split}1\geq Pr\left(\lim_{k\to\infty}\frac{1}{X_{k}(\omega)}=\frac{1}{X(\omega)}\right)\\ \geq Pr(A\cap\{\omega:X(\omega)\neq 0\})=1\end{split}

(3)

From that we deduce $Pr(\lim_{k\to\infty}\frac{1}{X_{k}(\omega)}=\frac{1}{X(\omega)})=1$ . Meaning that $\frac{1}{\frac{T_{1}+...+T_{k}}{k}}$ is converging almost surely to $\frac{1}{\mu_{e}}$ . We know that $T_{1},...,T_{k}\geq 1$ because a channel reset requires at least one transaction. Therefore: $\frac{T_{1}+...+T_{k}}{k}\geq 1$ which implies $0<\frac{1}{\frac{T_{1}+...+T_{k}}{k}}\leq 1$ for all $k$ .

Let us denote a constant random variable $Y=1$ . We know $Y$ has finite expected value, and that $|\frac{1}{X_{k}}|\leq Y$ for all $k$ . According to the Lebesgue dominated convergence theorem [16], Since $\frac{1}{X_{k}}$ converges almost surely to $\frac{1}{\mu_{e}}$ , we deduce:

\lim_{k\to\infty}\mathrm{E}\left[\frac{k}{T_{1}+...+T_{k}}\right]=\mathrm{E}\left[\frac{1}{\mu_{e}}\right]=\frac{1}{\mu_{e}}

(4)

∎

The next corollary follows immediately:

Corollary 1.

$\displaystyle\sum_{e\in E}{RPS_{e}}=\sum_{e\in E}\frac{1}{\mu_{e}}$

From this formula we will be able to compute the blockchain records cost for every network and routing policy.

The Expected Lifetime Of Balanced Channels

We recall a derivation from [9] that finds the optimal liquidity allocation and expected channel lifetime, in a balanced channel:

Lemma 2 (From [9]).

Let us have a channel between Alice and Bob, with transfers of one coin occurring at a Poisson rate of $\lambda$ from Alice to Bob in each time slot, from Bob to Alice (a symmetric channel). The liquidity of the channel is $\omega$ . The allocation that maximizes the expected time for the next reset is an equal allocation, and the expected value of channel life time is: $\mathrm{E}[T]=\frac{\omega^{2}}{8\lambda}$ .

The Rate of Transfer Through a Channel

In off-chain networks, every channel services multiple source-target transfers based on the routing policy. We define the rate over an edge (this rate is the same in both directions since our networks are symmetric):

Definition 5.

Let $\pi$ be a routing policy over a network $G=(V,E)$ , with a symmetric demands matrix $(\lambda_{ij})$ . We denote for a channel $e\in E$ , the balanced channel Poisson rate of $e$ as the following: $\displaystyle\lambda_{e}=\sum_{\{i,j\}\ s.t\ e\in\pi(i,j)}{\lambda_{ij}}$

This is essentially the total single-directional traffic over an edge, as derived from the routing policy. We rely here on the fact that the sum of Poisson random variables is a Poisson variable with rate equal to the sum of their rates.

3 Hub Is 2-Approximation for Cost Optimal Network

Theorem 1.

Let $G=(V,E)$ be an off-chain network, with a routing policy $\pi$ , and liquidity allocation $\omega:E\rightarrow R^{+}$ . Let $H=(V,E_{H})$ be a hub topology centered at an arbitrary vertex of $G$ , $v_{0}\in V$ . There exists a routing policy $\pi_{H}$ and liquidity allocation $\omega_{H}:E_{H}\rightarrow R^{+}$ for $H$ , such that for every series of transactions, the number of channel resets is at most twice the number of channel resets in $G$ , and the required liquidity is at most doubled: $\sum_{e^{\prime}\in E_{H}}\omega_{H}(e^{\prime})\leq 2\cdot\sum_{e\in E}\omega(e)$ .

Proof.

The proof is based on duplicating original channel traffic in $G$ into two channels in $H$ , by transferring the transaction throughout $v_{0}$ hub. For every node $x\in V$ , let us denote $E_{x}=\{e\in E\ s.t\ x\in e\}$ all the channels in $G$ that $x$ is connected to. We define $\omega_{H}$ to be:

\omega_{H}(\{x,v_{o}\})=\sum_{e\in E_{x}}\omega(e)

(5)

We can now calculate the total amount of liquidity in $H$ :

\begin{split}\sum_{e^{\prime}\in E_{H}}\omega^{\prime}(e^{\prime})=\sum_{x\in V\setminus\{v_{0}\}}\sum_{e\in E_{x}}\omega(e)\\ \leq\sum_{x\in V}\sum_{\{x,y\}\in E}\omega(\{x,y\})=2\sum_{e\in E}\omega(e)\end{split}

(6)

Any channel’s liquidity in the original graph, is added at most twice. Now we will define the hub routing policy $\pi_{H}$ . Let $(v_{1},v_{2})\in V^{2}$ to be a pair of nodes. Let $P=(\{v_{1},x_{1}\},\{x_{1},x_{2}\},...,\{x_{k},v_{2}\})=\pi(v_{1},v_{2})$ be the path in the original routing policy in $G$ (between $v_{1}$ and $v_{2}$ ). The path $P_{H}=\pi_{H}(v_{1},v_{2})$ in the new routing policy over $H$ is:

P_{H}=(\{v_{1},v_{0}\},\{v_{0},v_{2}\})

(7)

We remove all routing hops of the form $\{v_{0},v_{0}\}$ from the new path $P_{H}$ . This is simply an elimination of the loop hops (trips back and forth to the hub). We will show that the number of channel resets is at most twice the original number of resets. We can look at each hub channel $\{x,v_{0}\}$ as a “superposition” of all the original channels in $G$ that $x$ was connected to, $E_{x}$ . This is also a superposition in the liquidity, since new liquidity is the sum of all $E_{x}$ -channels liquidities. Therefore, we can split the original hub channel $\{x,v_{0}\}$ , into imaginary channels that represent the original channels of $E_{x}$ . We split the total liquidity $\sum_{e\in E_{x}}\omega(e)$ into the liquidities of imaginary channels of $E_{x}$ . We simulate the action of each transaction over the imaginary channels in $E_{x}$ , by changing their balances.

Each channel that was originally between $x$ and $y$ now has a share of the liquidity in $\{x,v_{0}\}$ and in $\{v_{0},y\}$ . Every time that an imaginary channel has to be reset (in the simulation), we will perform a reset over that channel only in this both edges. It means that the hub’s channel balance, summing the balances of all imaginary channels, will reset only the imaginary channel’s balance component. This simulation fully implements a hub payment channel. In that way, for every series of transactions, the number of resets is the sum of all original $E_{x}$ channels reset numbers or less (due to the loops we’ve removed).

When applying these partial resets, we can calculate the number of reset events over all the hub channels. It is bounded by the sum of imaginary $E_{x}$ channels reset events, for every $x$ in $V\setminus\{v_{0}\}$ . As a result, since every original $G$ channel can be summed at most twice (in two hub channels that connects to it’s endpoints), the total number of resets in $H$ is at most twice the total number of resets in $G$ . This result holds for every set of transactions, and therefore for all transaction demands.

∎

Corollary 2.

For any transaction demands, a hub over an arbitrary node is a 2-approximation for the optimal maintenance cost network.

This corollary raises the concern that centralized topologies (such as a hub) will be used widely in off-chain networks due to their maintenance-cost efficiency, although they go against the decentralized nature of blockchain technologies.

4 Optimizing Networks’ Maintenance Costs

In this section we will tackle the optimization problem seeking to minimize the rate of blockchain record fees per second (for a given amount of total liquidity).

4.1 Optimizing Liquidities Over a Network

Here we derive the optimal allocation of the liquidity between the channels in any network, that minimizes the network’s maintenance cost.

Lemma 3.

Let $G=(V,E)$ be a symmetric payment network, with a set of vertices $V$ , and $n$ edges. Network channels have a $\lambda_{e}$ transaction rate in both directions for every edge $e$ . The optimal liquidity allocation for $G$ (with total liquidity $W$ ) is: $\omega(e)=W\frac{\lambda_{e}^{\frac{1}{3}}}{\sum_{\bar{e}\in E}\lambda_{\bar{e}}^{\frac{1}{3}}}$ .

Proof.

Let $x_{e}=\frac{\omega_{e}}{W}$ . The chain record fees we wish to minimize are:

\frac{8\phi}{W^{2}}\sum_{e\in E}\frac{\lambda_{e}}{x_{e}^{2}}

(8)

with a condition of $\sum_{e\in E}x_{e}=1$ .
We use Lagrange multipliers to optimize. Let us define $g$ by the condition $\sum_{e\in E}x_{e}=1$ :

g(x_{1},...,x_{n},k)=\frac{8\phi}{W^{2}}\sum_{e\in E}\frac{\lambda_{e}}{x_{e}^{2}}-k\sum_{1\leq i\leq n}x_{i}

(9)

If we differentiate $g$ and equate the derivatives to zero, we get

\frac{2\lambda_{1}}{x_{1}^{3}}=...=\frac{2\lambda_{n}}{x_{n}^{3}},\sum_{1\leq i\leq n}x_{i}-1=0

(10)

By that we get ${x_{i}^{3}\propto\lambda_{i}}$ (for every $i$ ).
Since $x_{i},\lambda_{i}>0$ we conclude $x_{i}\propto\lambda_{i}^{\frac{1}{3}}$ (for every $i$ ).

We know $\sum_{1\leq i\leq n}x_{i}=1$ , which means we have to normalize the $x_{i}$ ’s. We have:

\omega(e)=Wx_{e}=W\frac{\lambda_{e}^{\frac{1}{3}}}{\sum_{\bar{e}\in E}\lambda_{\bar{e}}^{\frac{1}{3}}}

(11)

∎

Corollary 3.

The optimal blockchain record fees per second for the network, with liquidity sum of $W$ is: $\frac{8\phi}{W^{2}}\left(\sum_{e\in E}{\lambda_{e}^{\frac{1}{3}}}\right)^{3}$ .

4.2 Cost Minimizing Spanning Trees

Given a demand matrix for transactions, we wish to understand what the minimal cost payment network topology is. While solving this problem for general topologies is left open in this work, we are able to solve a more restricted case of tree topologies. The routing policy in a spanning tree is unique, because there is a unique path between every pair of vertices. This will allow us to more easily derive the best tree topology.

First, we will calculate channels transaction rates, for a certain demand matrix and spanning tree. In order to do that, we reiterate the definition of cut-capacities from [18]:

Definition 6.

Let $G=(V,E)$ be a network, $(\lambda_{i,j})$ a capacity matrix, and $(X,V\setminus X)$ a graph cut. We define the cut’s $\lambda$ -capacity to be: $\displaystyle\sum_{\{i,j\}\in E\ s.t\ i\in X,\ j\in V\setminus X}{\lambda_{i,j}}$

Now we can calculate the transactions rate over a spanning tree channel:

Lemma 4.

The Poisson rate of a channel $e$ , in a spanning tree network $T$ and demands matrix $(\lambda_{i,j})$ , equals the $\lambda$ -capacity of the cut between the two connectivity components of $T-e$ .

Once we can calculate the transaction rates in spanning trees, we adapt our setting to one that was defined originally by T.C Hu in 1974 [18]. In Hu’s problem, we are given a demands matrix $(\lambda_{ij})$ , denoting the communication requirements between pairs of nodes. Hu finds a spanning tree $T=(V,E_{T})$ , that minimizes $\sum_{e\in E_{T}}\lambda_{e}$ where $\lambda_{e}$ is the communication traffic over the tree’s edge $e$ . The communication rate over a tree channel, is similarly calculated according to lemma 4.

The Gomory-Hu tree (cut-tree) [14], can be calculated in polynomial time, and in addition to other properties, the tree is assured to minimize the sum of the tree’s channels traffic, $\sum_{e\in E_{T}}\lambda_{e}$ .

Unlike Hu’s problem, we are interested in minimizing $\sum_{e\in E_{T}}(\lambda_{e})^{\frac{1}{3}}$ . In this section, we will prove that the Gomory-Hu tree is also an optimal spanning tree for our problem. We will dive into the theory of submodular functions, in order to understand the properties of the Gomory-Hu tree.

4.3 Submodular Optimization of Induced Record Fees

It is known [27] that the cut capacity function $c_{\lambda}(X,V\setminus X)$ for non-negative capacity function over the edges $\lambda:E\rightarrow R^{+}$ , is a symmetric submodular function. The Gomory-Hu tree exists for every symmetric submodular function [27], when the definition is being adapted to a general function:

Theorem 2 (Queyranne, Maurice [27]).

Let $V$ be a ground set, and let $f:2^{V}\rightarrow\mathbf{R}^{+}$ be a symmetric submodular function. Given $s,t$ in $V$ define the minimum cut between $s$ and $t$ as $\displaystyle\alpha_{f}(s,t)=\min_{W\subset V,|W\cap\{s,t\}|=1}f(W)$ . Then, there is a Gomory-Hu tree that represents $\alpha_{f}$ . That is, there is a tree $T=(V,E_{t})$ and a liquidity function $c:E\rightarrow\mathbf{R}^{+}$ such that $\alpha_{f}(s,t)=\alpha_{T}(s,t)$ for all $s,t\in V$ . Moreover, a minimum cut in T induces a minimum cut according to $f$ for every $s,t$ .

Since the cut capacity function $c_{\lambda}(X,V\setminus X)$ is submodular and symmetric, the Gomory-Hu tree that minimizes the sum of $n-1$ cut-capacities (created between the connectivity components of $T-e$ for every channel $e$ ), is assured to exist. However, we wish to optimize $\sum_{e\in E}\lambda_{e}^{\frac{1}{3}}$ , and unlike the regular $\lambda$ -cut capacity function, we cannot claim that $c_{\lambda}(X,V\setminus X)^{\frac{1}{3}}$ is submodular (although it is symmetric). ²² 2 In fact, a counter example to the submodularity of $c_{\lambda}(X,V\setminus X)^{\frac{1}{3}}$ exists and is provided in the full version. Quite surprisingly, we show that the Gomory-Hu tree $T$ for the regular cut function minimizes $\sum_{e\in T}c_{\lambda}(C_{e},V\setminus C_{e})^{\frac{1}{3}}$ .

Lemma 5.

Let $g:\mathbf{R}\rightarrow\mathbf{R}$ be a non-decreasing function. Let $T$ be a Gomory Hu tree for a submodular symmetric non-negative function $f$ and a vertices set $V$ . Then $T$ minimizes the value of $\sum_{e\in T}g(f(C_{e}))$ when $C_{e}$ is one connectivity component of $T-e$ (which creates a cut).

Proof.

We will use a property according to Adolphson and Hu [3].

For two spanning trees $T_{1}=(V,E_{1}),T_{2}=(V,E_{2})$ , there is a one-to-one mapping $\psi$ between $E_{1}$ and $E_{2}$ , which satisfies the following condition: For every $e=\{v_{1},v_{2}\}\in E_{1}$ , $\psi(e)$ is in the path between $v_{1},v_{2}$ in $T_{2}$ . Let $T_{1}$ be a Gomory-Hu tree. For every edge $\{v_{1},v_{2}\}=e_{1}\in E_{1}$ there is a unique edge $e_{2}\in E_{2}$ that represents a cut separating $v_{1},v_{2}$ (since it is on the unique path between them in $T_{2}$ ). From the property of Gomory-Hu tree,

\min_{W\subset V,|W\cap\{v_{1},v_{2}\}|=1}f(W)=f(C_{e_{1}})

(12)

Thus, $f(C_{e_{1}})\leq f(C_{e_{2}})$ . Since $\psi$ is a one-to-one mapping

\sum_{e\in E_{1}}f(C_{e})\leq\sum_{e\in E_{1}}f(C_{\psi(e)})=\sum_{e\in E_{2}}f(C_{e})

(13)

Since $g$ is non decreasing, we can apply $g$ over this equation:

\sum_{e\in E_{1}}g(f(C_{e}))\leq\sum_{e\in E_{1}}g(f(C_{\psi(e)}))=\sum_{e\in E_{2}}g(f(C_{e}))

(14)

Having that, every spanning Tree $T$ will have greater or equal value of $\sum_{e\in T}g(f(C_{e}))$ , compared to the Gomory-Hu Tree. ∎

The main corollary (Gomory-Hu tree is optimal spanning tree network), is derived from the lemma with $f(X)=c_{\lambda}(X,V\setminus X),g(x)=x^{\frac{1}{3}}$ :

Corollary 4.

Let $G=(V,E)$ be a complete graph with non-negative transaction Poisson rate over the edges $\lambda:E\rightarrow\mathbf{R}^{+}$ . Let $T=(V,E_{T})$ be a regular Gomory-Hu tree over the weight function $\lambda$ . Then $T$ is the optimal spanning tree over the value of blockchain record fees per second, and it can be calculated in polynomial time.

5 Towards Global Optimization

5.1 The Cost of a Symmetric Network

The first step in exploring the global optimization of the maintenance cost, is to explore the connection between the different ingredients of that cost.

We showed in corollary 3, that the $RPS$ of a payment network is linear in $W^{-2}$ , for every topology including the optimal. Therefore, we can denote the network’s optimal $RPS$ , as follows: $RPS=\frac{RPS_{0}}{W^{2}}$ , Where $RPS_{0}$ is the optimal RPS rate with $W=1$ sum of liquidity.

Now, we can calculate the liquidity $W$ that minimizes the network’s maintenance cost.

Lemma 6.

Let $G=(V,E)$ be a payment network, with $W$ liquidity sum. Let us denote $\alpha$ as the liquidity interest rate per second, $\phi$ as a single blockchain record fee, and $RPS_{0}$ as the optimal blockchain records per second rate (when $W=1$ ). When optimizing the value of $W$ , the optimal maintenance cost of the network is proportional to:

M.C_{opt}\propto RPS_{0}^{\frac{1}{3}}\cdot\phi^{\frac{1}{3}}\cdot\alpha^{\frac{2}{3}}

Proof.

According to our definition of channel costs, when summing the liquidity and blockchain records over all the channels in $E$ , the full maintenance cost is:

M.C(W)=\phi\cdot\frac{RPS_{0}}{W^{2}}+\alpha\cdot W

(15)

We can derive this equation, and find the minimum point (via the sign of the second derivative):

\frac{d}{dW}M.C=\alpha-\frac{2\cdot\phi\cdot RPS_{0}}{W^{3}},\\ W_{opt}=\left(\frac{2\cdot\phi\cdot RPS_{0}}{\alpha}\right)^{\frac{1}{3}}

(16)

By placing $W_{opt}$ into $M.C(W)$ , we get the following relation:

M.C(W_{opt})\propto RPS_{0}^{\frac{1}{3}}\cdot\phi^{\frac{1}{3}}\cdot\alpha^{\frac{2}{3}}

(17)

∎

5.2 Tightness of Hub 2-Approximation

The results of the previous section allow us to prove the tightness of the hub 2-approximation, that we showed in section 3.

Theorem 3.

For every $\epsilon>0$ , there exists a set of transaction demands $(\lambda_{ij})$ , in which the optimal maintenance cost per second, is at least $(2-\epsilon)$ times lower than in every hub.

The full proof appears in the full version. The example that achieves a factor of 2- $\epsilon$ is based on a setting in which agents are paired together transacting only with each other. In a minimal cost network each such pair would form a channel between them, but in a hub, users are forced to route through two hops, incurring twice the cost.

6 Greedy Games for Payment Networks

In this section we explore a ”network formation” model that considers that players wish to minimize their individual costs. We begin by showing that the results of a greedy liquidity allocation, are about the same.

6.1 Greedy Liquidity Allocation

We analyze how individual channels optimize liquidity:

Lemma 7.

The minimal maintenance cost per second for a balanced channel with $\lambda$ transactions Poisson rate, $\alpha$ interest rate for locked coins, and $\phi$ cost for a single Blockchain record, is: $M.C_{e}=3\sqrt[3]{2}\lambda^{\frac{1}{3}}\phi^{\frac{1}{3}}\alpha^{\frac{2}{3}}$ .

6.2 Tree Topology Greedy Game

In contrast to the liquidity allocation process, the greedy development of the network topology, is much more interesting. Each one of the players has an effect over the routing of other players. We will study a game, in which each player (node) wished to optimize his own costs, with restriction to the spanning tree topology. First, we define a player’s share in channel fees:

Definition 7.

Let $G=(V,E)$ be a payment network. $e\in E$ is a channel with $M.C_{e}$ maintenance cost per second, and $\lambda_{e}$ balanced transaction Poisson rate. Let us assume that player $v\in V$ is transferring in $\lambda_{e}(v)$ rate over the channel $e$ . Therefore, the share of player $v$ in the maintenance cost of $e$ is:

M.C_{e}(v)=\frac{\lambda_{e}(v)}{\lambda_{e}}\cdot M.C_{e}

The player’s fees are proportional to their relative part in the transaction rate. The motivation for this definition is that fees are charged as a fixed amount per transfer, that needs to cover the total cost of the channel. We can now derive the total maintenance cost per second for a single player:

Corollary 5.

Let $\lambda_{e}(v)$ denote the transaction rate of player $v$ over channel $e$ . The maintenance cost per second for player $v$ is then: $\displaystyle M.C(v)=3\sqrt[3]{2}\phi^{\frac{1}{3}}\alpha^{\frac{2}{3}}\sum_{e\in E}{\frac{\lambda_{e}(v)}{\lambda_{e}}\lambda_{e}^{\frac{1}{3}}}$

It is clear from the formula, that a player’s costs depend on the routing policy. However, over a spanning tree topology, the routing is unique.

Definition 8.

The Tree Topology Greedy Game, is a game between the agents in $V$ , assuming a certain demands matrix $(\lambda_{i,j})$ . The goal of every player $v\in V$ , is to minimize his maintenance costs per second, $M.C(v)$ .

The game starts with an initial spanning tree $T_{0}$ . In every turn, each player can reconnect a single edge that is incident on its vertex. Such re-connections are restricted to maintain the spanning tree topology.

Definition 9.

An equilibrium point in the spanning tree greedy game, is a spanning tree $T^{*}$ , in which every player $v\in V$ cannot reduce his maintenance costs $M.C(v)$ by a legal move (of reconnecting a channel in the tree).

6.3 The Unbounded Price of Anarchy

Lemma 8.

The spanning tree topology game has unbounded price of anarchy. In other words, for every $K>0$ there exists an equilibrium point in the spanning tree greedy game, $T^{*}$ , in which there holds $M.C(T^{*})>K\cdot M.C(T_{G})$ where $T_{G}$ is the optimal maintenance cost spanning tree.

Proof.

Let us build a series of equilibrium trees, $T_{k}$ , with $k$ vertices, for every integer $k\geq 4$ . The demands matrix is the following: $\lambda_{1,k}=1$ , $\lambda_{1,2}=1$ , and $\lambda_{k-1,k}=1$ . All the other transaction requirements equal zero. For every $k$ , we can build a chain spanning tree - a cyclic ring along the nodes index, with removing the edge between $v_{k-2}$ and $v_{k-1}$ . It creates 3 channels with $\lambda=1$ transactions rate, and zero transactions rate for all the other $k-3$ channels. Now, let us describe the equilibrium spanning tree of $T_{k}$ by the set of edges $E_{k}$ :

E_{k}=\{\{v_{1},v_{2}\}\{v_{2},v_{3}\},...,\{v_{k-2},v_{k-1}\},\{v_{k-1},v_{k}\}\}

(18)

This is a simple chain from $v_{1}$ to $v_{k}$ . By a quick calculation, we can see that using this spanning tree network, 2 channels will have $\lambda=2$ transactions rate ( $\{v_{1},v_{2}\}$ and $\{v_{k-1},v_{v_{k}}\}$ ). All the other $k-3$ channels will have a transaction rate of $\lambda=1$ . Therefore, the ratio of maintenance cost per second, between $T_{k}$ and the optimal spanning tree, according to corollary 7, is at least:

\frac{(k-3)+2^{\frac{4}{3}}}{3}

(19)

Since this expression is converging to infinity, for every value of $K$ there exists $k$ , such that $M.C(T_{k})>K\cdot M.C(T_{G})$ . We will complete the proof by showing that $T_{k}$ is an equilibrium for every $k\geq 4$ .

It is clear that the nodes from the series $v_{3},...,v_{k-2}$ has no interest to reconnect a channel connected with them, since their costs are fully payed by the remained nodes. $v_{1}$ and $v_{k}$ are symmetric, as well as $v_{2}$ and $v_{k-1}$ . It is clear these two pairs don’t benefit from reconnecting, with both external nodes or with each other.

A precise examination shows that all the agents have no interest for structure change. Therefore, $T_{k}$ is an equilibrium for every $k\geq 4$ . ∎

7 Simulation Results

In this section we provide simulation results of more complex payment networks. Real-world transaction networks exhibit scale-free structure, and behave according to power-laws, e.g., in the distribution of degrees of vertices, and in transaction rates and amounts [7]. One interesting question is whether in such cases, hubs perform better than a 2-approximation to optimal networks.

We compare three network structures in our simulations: the optimal maintenance cost spanning tree (Gomory-Hu tree) derived with our algorithms, hub topologies (around an optimal node), and a complete graph topology. The latter two lie on two extremes: a centralized hub around a major transactor, or a channel between every pair of agents.

We simulated a network with 100 agents. We created the demand matrix in a scale-free graph model: generating a random scale-free graph [20] between the agents (with a certain power-law coefficient), and setting a non-zero transaction rate for every pair of connected nodes. The non-zero transaction Poisson rates, were also generated from a power-law distribution for different power-law exponents.

We checked the ratio of expected blockchain records per second (RPS) between agents in each of the three scenarios (a complete graph, a hub, and an optimal spanning tree).

As we can see in figure 3, a complete graph topology is becoming more efficient as the transaction demands’ centrality grows. This is because with a more centralized transaction demand graph, routing over a complete graph is closer to hub-routing. Moreover, it seems that in the majority of cases, a hub network achieves better results than the tight 8 RPS approximation (2-approximation in the total maintenance cost). Further simulations show that transaction-rates’ power-law coefficient has no affect over efficiency.

In the full version, we present additional simulation results in the same scale-free model, including simulations of the greedy game, and the price of anarchy. We show that power-law coefficients of the degree and transaction rates have no major affect on the probability of stability of optimal spanning trees, or on the price of anarchy.

8 Discussion and Future Work

In this paper we defined a model for the maintenance cost of payment networks, and provided results on liquidity allocation when transaction demands are symmetric, and for optimal spanning trees. We further showed that spanning trees (and in particular hubs) provide a constant approximation for any optimal graph and routing system. One of the weaknesses of our model is in the assumption of balanced channels. Some channels in payment networks might be unbalanced, and therefore their lifetime may be closer to a linear factor of the liquidity they hold, which will imply blockchain costs will be higher. Similarly, the question of different routing algorithms for asymmetric demands matrices, remains open and should be the focus of future work.

Another aspect that is still open, is the theory of online algorithms for balancing channels. Although some articles presented algorithms for this problem [29], they have not proposed a closed model for effectiveness estimation. These balancing algorithms can reduce the channels lifetime significantly, and the analytical estimation question still remains open.

References

[1] Raiden network, 2017.
[2] Adkin, ‘On the inefficacy of a distributed lightning network’, (2018).
[3] D Adolphson and T Ch Hu, ‘Optimal linear ordering’, SIAM Journal on Applied Mathematics, 25(3), 403–423, (1973).
[4] Georgia Avarikioti, Gerrit Janssen, Yuyi Wang, and Roger Wattenhofer, ‘Payment network design with fees’, in Data Privacy Management, Cryptocurrencies and Blockchain Technology, 76–84, Springer, (2018).
[5] Georgia Avarikioti, Rolf Scheuner, and Roger Wattenhofer, ‘Payment networks as creation games’, in Data Privacy Management, Cryptocurrencies and Blockchain Technology, 195–210, Springer, (2019).
[6] Zeta Avarikioti, Lioba Heimbach, Yuyi Wang, and Roger Wattenhofer, ‘Ride the lightning: The game theory of payment channels’, arXiv preprint arXiv:1912.04797, (2019).
[7] Stjepan Begušić, Zvonko Kostanjčar, H Eugene Stanley, and Boris Podobnik, ‘Scaling properties of extreme price fluctuations in bitcoin markets’, arXiv preprint arXiv:1803.08405, (2018).
[8] Ferenc Béres, Istvan Andras Seres, and András A Benczúr, ‘A cryptoeconomic traffic analysis of bitcoins lightning network’, arXiv preprint arXiv:1911.09432, (2019).
[9] Simina Brânzei, Erel Segal-Halevi, and Aviv Zohar, ‘How to charge lightning’, CoRR, abs/1712.10222, (2017).
[10] Josep Díaz, Jordi Petit, and Maria Serna, ‘A survey of graph layout problems’, ACM Computing Surveys (CSUR), 34(3), 313–356, (2002).
[11] Stefan Dziembowski, Lisa Eckey, Sebastian Faust, and Daniel Malinowski, ‘Perun: Virtual payment hubs over cryptocurrencies’, in Perun: Virtual Payment Hubs over Cryptocurrencies, p. 0. IEEE, (2019).
[12] Felix Engelmann, Henning Kopp, Frank Kargl, Florian Glaser, and Christof Weinhardt, ‘Towards an economic analysis of routing in payment channel networks’, 2, (2017).
[13] Oguzhan Ersoy, Stefanie Ross, and Zekeriya Erkin, ‘How to profit from payments channels’, arXiv preprint arXiv:1911.08803, (2019).
[14] Ralph E Gomory and Tien Chung Hu, ‘Multi-terminal network flows’, Journal of the Society for Industrial and Applied Mathematics, 9(4), 551–570, (1961).
[15] CYRIL Grunspan and RICARDO Pérez-Marco, ‘Ant routing algorithm for the lightning network’, arXiv preprint arXiv:1807.00151, (2018).
[16] Allan Gut, Probability: a graduate course, volume 75, Springer Science & Business Media, 2013.
[17] Jordi Herrera-Joancomarti, Guillermo Navarro-Arribas, Alejandro Ranchal Pedrosa, Perez-Sola Cristina, and Joaquin Garcia-Alfaro, On the difficulty of hiding the balance of lightning network channels, Ph.D. dissertation, Dépt. Réseaux et Service de Télécom (Institut Mines-Télécom-Télécom SudParis, 2019.
[18] Te C Hu, ‘Optimum communication spanning trees’, SIAM Journal on Computing, 3(3), 188–195, (1974).
[19] Rami Khalil and Arthur Gervais, ‘Revive: Rebalancing off-blockchain payment networks’, in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 439–453. ACM, (2017).
[20] Lun Li, David Alderson, John C Doyle, and Walter Willinger, ‘Towards a theory of scale-free graphs: Definition, properties, and implications’, Internet Mathematics, 2(4), 431–523, (2005).
[21] Thomas L Magnanti and Richard T Wong, ‘Network design and transportation planning: Models and algorithms’, Transportation science, 18(1), 1–55, (1984).
[22] Giulio Malavolta, Pedro Moreno-Sanchez, Aniket Kate, Matteo Maffei, and Srivatsan Ravi, ‘Concurrency and privacy with payment-channel networks’, in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 455–471. ACM, (2017).
[23] Michel Minoux, ‘Networks synthesis and optimum network design problems: Models, solution methods and applications’, Networks, 19(3), 313–360, (1989).
[24] Joseph Poon and Vitalik Buterin, ‘Plasma: Scalable autonomous smart contracts’, White paper, 1–47, (2017).
[25] Joseph Poon and Thaddeus Dryja, ‘The bitcoin lightning network: Scalable off-chain instant payments’, draft version 0.5, 9, 14, (2016).
[26] Pavel Prihodko, Slava Zhigulin, Mykola Sahno, Aleksei Ostrovskiy, and Olaoluwa Osuntokun, ‘Flare: An approach to routing in lightning network’, White Paper (bitfury. com/content/5-white-papers-research/whitepaper_flare_an_approach_to_routing_in_lightning_n etwork_7_7_2016. pdf), (2016).
[27] Maurice Queyranne, ‘Minimizing symmetric submodular functions’, Mathematical Programming, 82(1-2), 3–12, (1998).
[28] Daniel Rincon, Eva Yiwei Wu, Sofia Dewar, and Daniel Zhu, ‘Identifying beneficial connection types in payment channel networks: The case of lightning’, University of California Berkeley, (2020).
[29] Sascha Schmid, ‘Balanced routing in micropayment channel networks’, (2017).