Optimal Fee Structure for Efficient Lightning Networks

Ren, Alvin Heng Jun; Feng, Ling; Cheong, Siew Ann; Goh, Rick Siow Mong

doi:10.1109/PADSW.2018.8644930

Public blockchains · IEEE ICPADS 2018

Optimal fee structure for efficient Lightning Networks

Alvin Heng Jun Ren, Ling Feng, Siew Ann Cheong, Rick Siow Mong Goh

Institute of High Performance Computing, A*STAR Singapore · Nanyang Technological University · National University of Singapore

The Lightning Network moves Bitcoin payments off the blockchain into two-party payment channels. The fees that routing nodes charge decide which channels a payment takes, and therefore how quickly channels run dry in one direction. Simulating real Bitcoin transaction patterns on the real 2018 network, we find that short routes and balanced channels cannot both be had, and that fees which fall with the square root of channel capacity are a good compromise.

Paper (IEEE) fengling.eth

The claim

Short payment routes and balanced channels pull against each other; a fee weight of $1/\sqrt{x}$ for channel capacity $x$ balances them.

With fees $\propto1/x^{\alpha}$ and payments routed along the cheapest path, raising $\alpha$ keeps channels balanced longer but lengthens routes. Beyond $\alpha=0.5$ the imbalance hardly improves while routes keep growing; at $\alpha=0.5$ a payment hops through 4.5 intermediate channels on average.

0 · Context

Payment channels scale Bitcoin, but each channel can run dry in one direction

Diagram. (a) A channel between A and B with 0.5 BTC on each side; after A sends 0.2 BTC to B, A has 0.3 and B 0.7. (b) A routes 0.2 BTC to C through B: first the A–B channel shifts to 0.3/0.7, then the B–C channel shifts to 0.3/0.7. — **Fig. 2.** (a) A payment in a channel between Alice (A) and Bob (B). (b) Routing 0.2 BTC from A to Charlie (C) through B, when A and C share no channel.

Every Bitcoin transaction is recorded on the public blockchain and verified by miners. As usage grew, this design could not keep up: confirmations became slow and fees high, a scaling problem shared by almost all public blockchains. The Lightning Network (LN) moves most payments off the chain. Two users lock funds into a channel; they can then pay each other almost instantly and with tiny fees, and the blockchain is only needed to open and close channels.

A channel’s capacity is the total both sides committed. If Alice and Bob each commit 0.5 BTC and Alice pays Bob 0.2 BTC, the balances become 0.3 and 0.7. Two things follow. A payment cannot exceed the sender’s side of the channel. And if payments keep flowing one way, that side empties and the channel can no longer carry payments in that direction. Users without a direct channel can still pay each other through intermediate nodes, which is called routing (Fig. 2b).

We measure how lopsided a channel is by its imbalance,

I_{cap}=\frac{|C_1-C_2|}{C_1+C_2},

where $C_1$ and $C_2$ are the balances of its two users: $I_{cap}=0$ for an even channel and 1 for one that is completely drained on one side. After Alice’s payment above, $I_{cap}=0.4$ . An imbalanced channel must be rebalanced, or closed and reopened, which costs on-chain fees. A good Lightning protocol would have low fees, short routes and balanced channels. These three interact through the fee structure: the fees decide the route, and the route decides which channels become imbalanced.

1 · Two networks

Both the Bitcoin and the Lightning network are scale-free

To simulate realistic payments, we first measured the Bitcoin network (BN) of payments and the structure of the LN itself.

814,488

Bitcoin addresses in one day of transactions (7 Feb 2018, ELTE Bitcoin project data)

2,096,150

transactions between them that day

1,355

connected Lightning nodes (13 Jun 2018 snapshot; 889 isolated nodes removed)

5,592

Lightning edges among them; each channel is modelled as two opposite edges with half its capacity each

Two log-log plots for the Bitcoin network. (a) Complementary cumulative distribution of in- and out-degree, both straight lines. (b) Probability density of transaction size in BTC, with a power-law tail above 10 to the minus 4. — **Fig. 1.** Bitcoin network, one day: (a) in- and out-degree distributions, power laws with exponents 2.8 and 2.4; (b) transaction sizes, with a power-law tail of exponent 1.6 above about $10^{-4}$ BTC.

Drawing of the Lightning Network on 13 June 2018: a dense core of blue nodes joined by black lines, a few hubs with many channels, and a ring of disconnected nodes around the periphery. — **Fig. 3.** The Lightning Network on 13 June 2018. Line width ∝ channel capacity. The disconnected nodes on the periphery cannot route payments and are removed.

Payments in the BN form a scale-free network: the number of payments a node sends or receives follows a power law, $P(k)\sim k^{-\gamma}$ with $\gamma=2.4$ (out) and $2.8$ (in), similar to the Internet. Transaction sizes are heavy-tailed too.

The LN shows visible hubs, nodes with many channels that can route many payments, and many disconnected nodes, probably users who ran nodes for testing without committing funds. Its degree distribution is also a power law, with $\gamma=2.1$ . Such a network is robust to random failures, because most nodes have few channels, but fragile to targeted attacks on its hubs.

Channel capacities in 2018 were very small, the largest about $10^{-1}$ BTC against Bitcoin transactions of up to $10^{4}$ BTC, likely because users were reluctant to commit large amounts to an experimental network. Their distribution also has a power-law tail, with exponent 1.7, so large channels are relatively common.

2 · Simulation

Real payment patterns, routed along the cheapest path on the real network

Choose sender and receiver. From the BN we measured how often a payment connects a sender of out-degree $k_{out}$ to a receiver of in-degree $k_{in}$ . Both networks’ degrees are divided by their maximum, so they lie in $[0,1]$ , and LN nodes are drawn with the BN’s probabilities.
Choose the amount. Transaction sizes, divided by the largest one, are drawn from the BN distribution; channel capacities are normalized the same way, so the two can be compared.
Route. Only total capacities are public, so every channel starts evenly balanced. Each payment takes the path with the lowest total fee among paths where every channel has enough balance in the direction of travel (Dijkstra’s algorithm). If there is none, the payment fails. Balances are updated after every payment.

Routing nodes must earn fees, or nobody will keep channels open. Large channels are harder to drain, so they should charge less, and small channels more, because the same payment unbalances them more. We give each directed edge the fee

w=\frac{1}{x^{\alpha}} ,

where $x$ is the balance available in that direction and $\alpha$ is the one tunable parameter. After Alice’s payment, sending from A to B costs $1/0.3^{\alpha}$ and from B to A $1/0.7^{\alpha}$ : whatever $\alpha$ is, the direction that rebalances the channel is cheaper. With $\alpha=1$ , the cheapest path is the weighted shortest path in the usual network-science sense. A larger $\alpha$ makes big channels relatively cheaper, which favours more hops through them; a smaller $\alpha$ favours fewer hops at higher fees. Long routes are risky, since every intermediate node can default, so we look for the $\alpha$ that best balances short routes against balanced channels. Each simulation runs 50,000 payments, one per step, averaged over 3 runs.

3 · The trade-off

Raising α keeps channels balanced but lengthens routes, and the gain stops at α = 0.5

(a) Mean channel imbalance against simulation steps for no fee and alpha 0.2, 0.5, 1 and 1.5: no fee rises fastest to 0.07, alpha 0.2 to about 0.037, and the three larger alphas nearly coincide at about 0.025. (b) Imbalance against channel betweenness centrality for the same fee structures, peaking near 10 to the minus 3; inset: average number of hops rising from 3 to about 6 as alpha goes from 0.1 to 1.5. — **Fig. 6.** (a) Mean channel imbalance $\langle I_{cap}\rangle$ over 50,000 payments, for no fee and $\alpha=0.2$ to 1.5; black lines are logarithmic fits. (b) $I_{cap}$ against channel betweenness centrality at the end of the simulation; inset: average number of hops against $\alpha$ . Tap to enlarge.

Without fees, channels become imbalanced fastest. Any fee of the form $1/x^{\alpha}$ helps noticeably, and larger $\alpha$ helps more, because it steers payments onto large channels, which resist imbalance. But beyond $\alpha=0.5$ there is no noticeable further improvement: the curves for 0.5, 1 and 1.5 almost coincide.

The imbalance grows like a logarithm of the number of payments, so it would take an exponentially long time for the network to become totally imbalanced; larger $\alpha$ pushes that further out and lets the LN run longer without new channels.

The price is route length (Fig. 6b, inset): the average number of hops rises steadily with $\alpha$ . Going below 0.5 makes the imbalance clearly worse; going above it lengthens routes for no gain. So $\alpha=0.5$ , a fee that falls with the square root of the channel’s capacity, is a good compromise. At $\alpha=0.5$ , payments hop through 4.5 intermediate channels on average.

The trade-off on a toy network

toy: 160 nodes, scale-free, not the 2018 Lightning Network

Scroll the panel sideways →

show channels for α

—

Five copies of the same toy network receive the same stream of payments; they differ only in the fee exponent $\alpha$ . Each payment takes the cheapest path with enough balance (fee $1/x^{\alpha}$ per channel; $\alpha=0$ means every channel charges the same, so payments take the fewest hops). Left: the channels of the selected copy, coloured from even (pine) to drained on one side (red), width growing with capacity. Right: mean imbalance against the number of payments, and the mean number of hops.

As in Fig. 6, larger $\alpha$ keeps channels more balanced and makes routes longer. The levels differ from the paper’s, because the toy is smaller and its payments are larger relative to the channels; the ordering is what carries over.

4 · Which channels

Channels of intermediate centrality, and those next to hubs, run dry first

(a) Channel imbalance against node-degree imbalance, flat near 0.01 then rising sharply above 0.8. (b) Imbalance against betweenness centrality with large standard-deviation bars, peaking near 10 to the minus 3. (c) The same for used channels, which peak at the same place, and unused channels, which stay near zero. — **Fig. 7.** For $\alpha=0.5$ : (a) $I_{cap}$ against the degree imbalance $I_{deg}$ of the channel’s two nodes; (b) $I_{cap}$ against betweenness centrality, with standard deviations; (c) the same for channels used and unused in the last 10,000 payments.

Which channels become imbalanced? We rank channels by betweenness centrality (BC), the share of shortest paths between all pairs of nodes that pass through a channel, a natural measure for a routing network. Imbalance rises with BC up to about $10^{-3}$ , because central channels carry more payments, then peaks and falls (Fig. 6b). With fees, every $\alpha$ shows the same peak.

The peak is unexpected. In practice it makes channels of intermediate BC the least favourable to open, which may act as a barrier against preferential attachment and keep small nodes from becoming central, possibly preventing centralization of the LN. At $\alpha=0.5$ the most central channels also have relatively high imbalance, so they offer less favourable fees than less central ones, again a possible penalty on hubs.

Illustration: a hub (yellow) with many neighbours joined by one link to a smaller node (cyan) with few neighbours; a dotted red arrow from a red node on the hub side to a green node on the other side shows payments flowing in one direction across the link. — **Fig. 8.** A link from a hub to a node with fewer neighbours has high BC and high degree imbalance; payments cross it mostly in one direction.

The general rise follows from the degree imbalance of a channel, $I_{deg}=|k_1-k_2|/(k_1+k_2)$ , where $k_1,k_2$ are the degrees of its two nodes. $I_{cap}$ increases sharply for high $I_{deg}$ (Fig. 7a): when one end has many more neighbours than the other, more payments cross in one direction. Central links often connect a hub to a node with fewer neighbours (Fig. 8), so the effect is strongest there.

At the peak, the imbalance also has the largest standard deviation (Fig. 7b), and the channels actually in use peak at the same position (Fig. 7c). This suggests that the peak is not a smooth crossover or a local maximum but possibly a critical phase transition, a question we leave for further research.

5 · Summary

Fees, imbalance and route length cannot all be optimized at once

Structure

Scale-free like its parent

The Lightning Network of 2018, like the Bitcoin payment network, has a power-law degree distribution with hubs.

Trade-off

Balanced or short

Cheapest-path routing with fees $\propto1/x^{\alpha}$ : larger $\alpha$ keeps channels balanced longer but lengthens routes.

Compromise

$\alpha\approx0.5$

Fees falling with the square root of capacity give most of the balance gain with routes of about 4.5 intermediate channels.

This was a first analysis of the network properties of the Lightning Network. It simplifies routing: real routing protocols need not find the cheapest path, though we assume they do not deviate far from it. Future work can study more realistic routing protocols, and network structures designed together with fee structures for more efficient Lightning Networks.

← fengling.eth · Public blockchains

Back to the main page