By Rusty Russell & Joe Netti

The Lightning Network is growing exponentially, currently at over 35,000 channels and counting. Existing implementations of the Lightning protocol are, by and large, handling this growth well. However, the burden on hardware is increasing, and if the growth of channels continues to accelerate, the network will be facing scaling issues in the not-too-distant future. Finding an efficient route through a million channels isn’t easy.

We’re very bullish on the Lightning Network at Blockstream, so some of our c-lightning team decided to head off the scaling problem before it emerges by launching the Million Channels Project.

The Million Channels Project

The Million Channels Project was proposed by Rusty Russell and implemented by Joe Netti. It approaches the Lightning scaling problem from a couple of angles:

1. Network simulation: realistic network modelling to facilitate informed optimisation of the various Lightning implementations.
2. Code optimisation: improvements to c-lightning’s gossip protocol to reduce routing overheads, based on the results from million-channel simulations.

Aside from preparing the network for future growth, the optimisations achieved by the Million Channels Project also have the upside of allowing smaller hardware to operate as a node. A Raspberry Pi for instance, should now have no trouble running a c-lightning node.

This project would not have been possible without the help of Blockstream colleagues Rusty Russell, Sebastian Geisler, Christian Decker, Lisa Neigut, and Pieter Wuille.

Generating a Realistic Network

The Million Channels Project generates a realistic network with a million channels for modelling the future Lightning Network and optimizing Lightning implementations. The software analyzes the current Lightning Network to simulate a realistic network of arbitrary size, then generates the gossip messages for all the nodes and channels, and a matching regtest bitcoin chain.

Networks generated by the project are similar in many ways to the real Lightning Network. The new networks have accurate channel capacities, distribution of channels, and node details (address types and node announcements). The real Lightning Network data that is used as a baseline for the new network is gathered from c-lightning listchannels and listnodes commands.

Steps To Generate A Network

To generate a realistic network:

1. assign channels to nodes until the channel limit is reached
2. assign each node an “allocation” of capacity
3. assign each channel a capacity
4. assign each node accurate address types and an announcement message.

To create an accurate distribution of channels in the generating network, the probability distribution of the snapshot network is mapped to a power law distribution. The power law is a common distribution observed in network theory and follows the form: y = c*((b+x)^-a. Each node is assigned a number of channels by selecting a random number in the (0-max) bounded integral of the power law with the specific parameters (a,b,c) and plugged into the power law quantile function (inverse CDF). We get this distribution on the larger network which is pretty similar to the original network:

After assigning the amount of channels to create for each node (following the power law distribution above), we still need to generate which node will be on the other side of each channel. Channels between nodes are formed randomly and incrementally so that there are no duplicate channels and there is a path between every pair of nodes (the network is not segregated).

The algorithm is as follows: we sort nodes greatest to least by how many channels they have and iterate through them. For each node with X channels left, we randomly select X unique nodes that have at least one channel left and create a channel between the two. If the node only has one channel left, we connect that channel to another node which is part of the network and has at least one channel left.

Channel Capacities

Now that each node has channels with other nodes in the network, the next step is to assign funds to each channel. The channel capacity algorithm is based on two observations of the real Lightning Network in order to make the algorithm produce a network with realistic channel capacities. First, the total capacity of channels in a node follows a power law distribution and we copy this distribution by assigning total capacity allocations to each node. The distributions of total capacity to channels is shown below:

Second, if you take the channels of a node and rank them from greatest capacity to least, they are not linear, but in a power law distribution. One possible explanation is that users tend to create a few high capacity channels and many low capacity channels. A few reasons for low capacity channels in the real network are testing, gathering information about the network, and tricking/abusing autopilots.

Third, there is a positive correlation between the capacity of a channel and total capacity of all other channels attached to the same node. This may be because people want to make high capacity channels with other nodes that have a lot of total capacity. In this new network we see around an order of magnitude larger capacity for “connected nodes” (y-axis) because the new network has around an order of magnitude higher total network capacity.

The final network has 998,005 channels, 94,501 nodes; 19383 nodes have a single channel, and the largest node has 9858 channels. The total capacity of the network is 17300.97 BTC (except scaled down); it takes 731MB of gossip traffic to describe the network.

Generating The Bitcoin Chain

The chain is generated by mining enough blocks to fund all channel funding transactions plus fees. After N + 100 empty blocks are generated, the coinbases are spent directly to the 2-of-2 segwit multisigs. Funding transactions have coinbase inputs in order to minimize the number of transactions that have to be created because cryptographic operations in the python library used are slow.

We used bitcoin’s “regtest” mode, which allows for the very simple generation of blocks. Unfortunately, regtest halving is set by default at 150 blocks in bitcoin core, which makes running out of capacity an issue. All capacities are scaled down as specified in the config, and yes, that means we change the definition of a satoshi!

Generating Gossip messages

The project implements a basic version of channel announcements, channel updates, and node announcements according to bolt #7. Unfortunately, the gossip creation program and the chain creations programs do not work as independent tools because load balancing of multiprocessing in gossip creation currently uses data generated in the build network stage–decoupling them is an area of future work.

Optimizing c-lightning

Prior to this, very little optimization work had been done on c-lightning, but one point of the Million Channels Project was to get ahead of the current network requirements and identify bottlenecks. In fact, the very first time we loaded the dataset, it took overnight to even start the node! Like many of the optimizations, the fix was simple, but showed how valuable this testing was.

In the lead-up to the 0.7.1 release, Rusty Russell created over 90 changes in 8 different pull requests, using the million channel gossip as a benchmark to optimize the memory usage and speed of the c-lightning Gossip Daemon: everything from JSON reply construction, to completely reworking the way the Gossip Daemon stores, sends, and indexes the 800MB of gossip messages, to changing the routing algorithm from Bellman-Ford-Gibson (BFG) to Dijkstra. The original choice was made to handle both negative fees and handle the 20-hop limit. Dijkstra is preferable because it is far faster, uses less memory, the 20-hop limit is rarely reached, and negative fees are not allowed in the 1.0 standard. Finally, the default compilation for non-developer builds is now done with some optimization enabled (-Og), giving a further 20% performance boost. The graph alongside shows the range of improvements.

As a stretch goal, we tried to run it on a Raspberry Pi 3B+ (32-bit ARM with 1GB of RAM). It ran out of memory and crashed, so after some more optimizations, we showed it’s possible, though certainly not fast (yet)!

Benchmarks on Raspberry Pi 3B+

Conclusion and Further Work

The Million Channels Project shows what the future Lightning Network might look like, and can be used to stress-test existing implementations. Rusty Russell used the gossip messages to optimize c-lightning for the 0.7.1 release; now commodity desktop hardware can run c-lightning on a network of 1 million channels.

However, our work continues. In particular, more optimization is needed when a node first receives gossip–either because it’s brand new, or because it has been offline for some time. And expect to see more optimizations as we get frustrated with our slow Raspberry Pi node.

Future work with the Million Channels Project includes testing how the network evolves over time, testing new routing algorithms, estimating payment success rates in some future network (number of hops and liquidity), and further optimizing other Lightning implementations.

Download the Million Channels Project yourself to try your own simulations, or just download the data to test your own node!

Note: This blog was originally posted at https://medium.com/blockstream/letting-a-million-channels-bloom-985bdb28660b