A of Jonald Fyookball claimed to give mathematical proof that a lightning network (LN) cannot be large and still decentralized. In light of Prof. Jorge Stolfi issued the following : recent post Murch’s response challenge There is a very simple way to shut criticisms like Jonald’s and mine. Just provide a hypothetical scenario for 10 million users with topology and numbers — how many customers, merchants, and hubs, how many channels and payments (per day or per month) per user for each pair of those user classes, and how much each user commits to his channels, etc. Then anyone who doubts the viability of the LN can simulate it with those data, and conclude for himself. Any takers for this challenge? bitcoin I decided to take up this challenge. In order to emphasize that the LN can be decentralized, the hypothetical with 10 million users is described in a way where all users are the same: all have the same number of channels initially funded with the same amount of bitcoins. There is no distinction between “customers”, “merchants” or “hubs.” In particular, each user has 14 open channels initially funded with 0.01 bitcoins. The structure of the graph is described below. network I have also written to provide a basic simulation for such a lightning network with 10 million users. There are 11 different fee policies evenly distributed among users. At each step of the simulation two users are chosen at random and one attempts to make a payment to another. The payment may either be “big” (between 0.001 and 0.009 btc, a few dollars), “midsized” (between 0.00001 and 0.001 btc, about $2 or less) or “micro” (less than 0.00001 btc, about 2 cents or less). The code searches for an inexpensive route and, if one is found, a payment is attempted. The simulator assumes that a node in the route has a 0.1% chance of becoming uncooperative, in which case a new route avoiding the node is requested (for up to 5 retries). Below we report the results of running the simulation for 400,000 payment attempts. ocaml code A network topology with 10 million users The first challenge is to imagine a graph with 10 million nodes (users), enough edges (channels) so that every node is reachable from every other node with enough redundancy that there is no centralization. We also have the constraint that each channel must be funded with a nontrivial amount of bitcoins. We consider the set of nodes to be the natural numbers from 0 to 9,999,999. A first possibility for edges is to use the binary representation of numbers from 0 to 9,999,999 (requiring 24 bits) and include an edge whenever the two bit sequences differ by exactly 1 bit (a Hamming graph). All nodes would be reachable with (many) paths of at most 24 hops, and 12 hops on average. However, there would be about 200 million channels. If both users funded each channel with 0.01 bitcoins, then 4 million bitcoins would be locked up in LN payment channels. While this is technically possible, it seems too unrealistic. Building on the idea given by a Hamming graph, we can consider the base 10 representation of nodes. First consider the possibility of only having 10 nodes in the network. In that case we could include an edge between nodes that differ by one modulo 10. This “network” is connected but has very little redundancy. Each node has two edges, and is reachable from every other node in exactly two ways. The shortest path from one node to another has at most 5 hops. Next consider having 100 nodes in the network. In this casewe could include an edge between nodes that differ by one modulo 100 or differ by 10 modulo 100. A connected network with 100 nodes and many paths Here each node has exactly 4 connections and there are many paths from one node to another, providing a great deal of redundancy. Each node is reachable within 10 hops, with 5 hops on average. Jumping to the case with 10 million nodes, we include an edge whenever nodes differ by 10 to the power of (for =0,…,6) modulo 10 million. Each node will have exactly 14 edges, corresponding to each user in the LN having 14 open channels. Since each channel involves 2 users, there are a total of 70 million open channels in the network. Suppose each user funds each channel with 0.01 bitcoins, requiring the user to lock up 0.14 bitcoins in LN channels. With 10 million users, this requires 1.4 million bitcoins to be taking part in the LN. This is still somewhat fanciful, but more realistic than the 4 million required by the Hamming graph above. (For more realistic scenarios, the number of users should probably be restricted to a million at most.) Each node is reachable from other nodes by paths of at most 35 hops, with an average of 17.5 hops. n n Simulating 400,000 payment attempts Here we describe the state of the network after simulating 400,000 attempted payments. The payments were of random values between random users, distributed between big payments (0.001 to 0.009 btc), midsized payments (0.00001 to 0.001 btc) and micropayments (less than 0.00001 btc) with roughly a third of payments falling into each category. After 400,000 attempted payments, roughly half of the users (5,049,576) had been involved in routing a payment and 10% of channels (7,091,810) had been used to route a payment. In some cases requests for a route time out (with a 1 second time limit), leading to a routing failure. This happened in 4,500 cases (just over 1% of the 400,000 attempted payments). Looking more closely routing failures occurred far more often with smaller payments. This is presumably because smaller payments were more restrictive in which routes to accept to avoid having fees too high. The maximum fee when requesting a route was always either 0.00001 btc (10 bits) or 5% of the value being transferred, whichever is higher. Here are the specific numbers for the three kinds of payments: 133,865 “big” payments (between 0.001 and 0.009) were attempted. Only 8 of these failed. The median number of hops for successful payments was 18 and the median total fees (for the entire route) were 3 bits (0.000003 btc) or 0.06% of the value transferred. 132,734 midsized payments were attempted and 1031 (0.8%) of these failed. For successful payments the median number of hops was 18 and the median total fees were 2 bits (0.000002 btc) or 0.5% of the value transferred. 133,401 micropayments were attempted and 3461 (2.6%) of these failed. For successful payments the median number of hops was 19 and the median total fees were 2 bits (0.000002 btc) or 32% of the value transferred. One possible problem pointed out by Fyookball in his is that channels will become unbalanced so that they could only be used in one direction during routing. Channels do indeed appear to start becoming unbalanced in the simulation. Among the 7 million channels used routing the almost 400,000 successful payments 294508 (4%) have 90% or more of the value on one side of the channel. This does not appear to be a problem yet, since this is still only 0.4% of the total available 70 million channels, but it might become a problem with longer runs of the simulator. If it is a problem, one would expect it to show up with increased failures to route big payments, since it would restrict the possible routes for big payments more than smaller payments. However, it is also possible that unbalanced channels will not cause a problem since there are a very high number of alternative routes (including, as Murch , routes that specifically use an unbalanced channel in the other direction). first post points out How the simulator could be improved The is relatively slow and requires more RAM the longer it runs. The simulation of these 400,000 payments took several hours and the process died before reaching 500,000 payments. The code is available in case people with access to more powerful hardware want to run the simulator for longer. simulator In addition to efficiency issues, the simulation could be improved in a number of ways to make it more realistic. For example, the simulation could be extended to model opening and closing of channels. In addition, it would be more realistic to assume that the number of channels and funding of channels varies with users. Conclusion We have given a structure for a lightning network with 10 million users which has no centralized hubs. Indeed each user has exactly the same connectivity and funding as all other users. While this is not how a lightning network would be expected to evolve in a real world scenario, it does show that it is technically possible to have such a network. In addition we have given code to simulate making payments in the network. A relatively short run (attempting 400,000 payments) shows that payments succeed 99% of the time, failing more often for micropayments than larger payments.
