Skip to main content

Maypoles: Lightning Striking Twice

Published onApr 22, 2024
Maypoles: Lightning Striking Twice


The Lightning Network (LN) is a second layer solution built on top of Bitcoin, aimed to solve Bitcoin’s long transaction waiting times and high transaction fees. Empirical and theoretical studies show that the LN is tending towards the hub and spoke network topology. In this topology most of the nodes, the spokes, open a single channel to one of the few well-connected nodes, the hubs. This topology is known to be prone to failures, attacks, and privacy issues. In this work we introduce the Maypoles protocol in which most nodes open two channels instead of one. We show that this protocol benefits the network significantly by enhancing its stability, privacy, and resilience to attacks. We also examine the economic incentives of nodes to take part in Maypoles.


The limited throughput is a challenge shared by all Proof of Work (PoW) blockchains, such as Bitcoin. By design, these blockchains limit the expected number of transaction per second, as making this number larger comes at the expense of security.

A direct consequence of this is an auction-like dynamic for the limited space available, driving the transaction fees up. High fees limit the usability of the blockchain, and narrow its adoption.

Another limit of PoW blockchains is the long waiting time needed for a transaction to be considered secure. In PoW blockchains, the longer one waits, the more secure the transaction is. The expected time a transaction waits until it is approved varies between blockchains, usually being somewhere between a few minutes to an hour. Even a minute is an unacceptable waiting time for retail transactions and other use-cases. Similar to the throughput problem, this cannot be changed without serious security risks.

Second layer protocols are solutions to the above challenges. Generally speaking, these protocols aggregate transactions and send a summary to the blockchain as seldom as possible. By doing this, these protocols reduce congestion on the blockchains and offer cheaper and quicker transactions.

In this paper, we focus on Bitcoin’s most predominant second layer solution, the Lightning Network (LN) introduced in [1]. The results presented here are relevant in the wider context of payment channel networks that work on the same principles. See [2] for an overview.

The basic building block of the LN is a channel. Alice and Bob open a channel by sending a Bitcoin transaction. This transaction locks a given amount of bitcoin inside the channel. Once the channel is open, Alice and Bob can freely transact with each other by shifting the amount of funds owned by each party in the channel. These transactions happen immediately, and do not entail any fees. At any point, Alice and Bob can close the channel by sending another Bitcoin transaction and get their respective funds back on the blockchain.

Furthermore, if Bob also has a channel with Carol, Alice can transact with Carol through Bob, if Bob allows this. There is no theoretical limit1 on the length of the chain of payments. So, Alice can pay Zoey through Bob, Charlie, Donna, and so on, as long as all the parties on the way from Alice to Zoey agree to this. Parties along the route may charge a fee. We give further details on payments over the LN in Appendix 6.

Several studies have shown the tendency of the LN towards the hub and spoke topology. This topology can be described as follows. There is a small number of nodes with many channels, these nodes are called hubs. The rest of the nodes are connected to a single hub. A node connected with a single channel to a hub is called the hub’s spoke. See Figure 1 for an illustration.

Figure 1: Hub and spoke topology. Each hub, a blue circle, has many spokes. Each spoke, a green squares, is connected to a single hub.

Hub and spoke networks suffer from stability, security, and privacy issues. These issues arise both from the lack of guarantees provided by the connections between the hubs and from the fact that the spokes have only a single channel.

In this paper, we propose a solution called Maypoles. This solution builds on top of the hub and spoke topology. In Maypoles, each spoke opens two channels instead of one. The first channel to a hub of its choice, called the main hub, through which it plans to move most of its transactions. The second channel to a hub chosen by the spoke’s main hub, this hub is called the secondary hub. The main hub selects the secondary hub randomly. The full details of the protocol are given in Section 2.2.

We show that by adding channels as prescribed by Maypoles, we are able to make the network exhibit a healthy topology that is less prone to attacks and breakdowns due to malfunction, and to enhances privacy. We also show that it is in the best interest of the spokes to open these two channels, as this allows them to send payments over the LN without down-times and save on channel rebalancing fees.

Our Contribution

Topological improvements

In this paper we make the first attempt, to the best of our knowledge, to push back against the tendency of the LN to collapse to a centralized structure such as the hub and spoke topology. While understanding that currently most nodes open a single channel to a well-connected hub, we offer to build on top of this to improve the network’s structure.

We prove theoretical results, with no assumptions on the structure of the underlying LN, and then show the results of simulations on top of current LN data. The simulations show that the average case over the current LN is even better than the guarantees given by the theoretical results.

Local change for global impact

In Maypoles the benefits to the network do not rely on a coordinated effort of all nodes. Each hub chooses its own random subset of secondary hubs, and each node chooses its main hub independently of other nodes in the network. We show that local independent decisions can improve global properties of the network.

Economic incentives

To motivate improvements to the LN, we use recent results on the economy of transactions fees in Bitcoin and of LN channels. By examining economic incentives, we create a win-win situation where both the network and the spokes benefit from the protocol. The economic assumption made in proving the incentive compatibility are modest and backed by data.


The Model

The starting point we wish to improve is the hub and spoke topology. We assume that the set of nodes is V=HSV=H\cup S, where HH is the set of hubs and SS is the set of spokes. Each spoke sSs\in S is connected to a single hub by exactly one channel. We assume that each hub hHh\in H has at least 4 spokes. We also assume that there is some global parameter kk all the hubs use for the protocol2.

We assume that we are in the steady state of the hub and spoke model, that is, each spoke ss chose the hub hsh_s, as it wishes to send and receive all of its transactions through hsh_s. When the channel between ss and hsh_s becomes unbalanced, that is, it cannot support any more transactions that the spoke wishes to send or receive, the spoke will rebalance the channel. For example, if all of the balance of ss in the LN is 0 and ss wishes to keep sending transactions, ss will move funds from the blockchain to the LN. We give further details on rebalancing strategies in Section 4.1.

We also assume that the fee of a Bitcoin transaction is correlated to the urgency of the transaction, that is, at any moment in time there is a fixed fee that will guarantee with high probability that the transaction appears in the next block. A smaller fee will guarantee that the transaction will appear in the next 6 block, and so on. We also assume that the cost of keeping a channel that is always available for sending or receiving, is a monotone decreasing function of the cost of rebalancing the channel.

The Protocol

Maypoles is built on top of a network with a hub and spoke topology. In Maypoles, each spoke opens two channels instead of one. From the spoke’s viewpoint, it opens a main channel to a hub of their choice. The hub then recommends a hub for the spoke to open their secondary channel to.

To recommend a secondary channel to each spoke, every hub does the following protocol (independently of the other hubs)

  1. Initiate LL as an empty list, and let ll denote the size of LL throughout the protocol.

  2. Choose kk hubs uniformly at random. Add them to LL.

  3. Notify the hubs that they are chosen, and add any hub that chose you to the list LL.

  4. Break the spokes into l(=L)l(=|L|) sets of size as even as possible.

  5. Instruct the spokes in set ii to open their secondary channels to the ii’th hub in LL.

Notice that there is a symmetry between choosing a hub in step (2) and being chosen by a hub in step (3), that is, there are secondary channels between the spokes of hubs h0h_0 and h1h_1 if either h0h_0 chose h1h_1 or h1h_1 chose h0h_0.

Overview of the Benefits

If the hub h0h_0 chose the hub h1h_1 (or vise versa) then the result will be spokes that are connected to both of them (see Figure 2). This means that transactions can go between h0h_0 and h1h_1, creating a new connection. This connection can be used if need be.

Figure 2: Hubs and spokes in Maypoles. The red thick edges represent the spokes' main channels, and the blue thin edges represent the secondary channels

For example, in cases of failure in the network, different nodes can use this connection to route their transactions. Spokes can also choose to use this connection to enhance their privacy by occasionally using the secondary channel to transact. The main theorem concerning the network topology shows that Maypoles guarantees various network properties. Simulations based on the current LN show that these improvements out perform the theoretical guarantees in the average case. Further details are given in Section 3.

We also make sure that the spokes do not lose money when opening the secondary channel. As the cost of the LN channel strongly depends on the cost of on-chain transactions, we can use the fact that delayed on-chain transaction have lower fees for the benefit of the spokes. Further details are given in Section 4.

Maypoles and Network Topology

Network Topology

The topology of channels in the LN has a crucial effect on the stability, security, and privacy of the network. There are several graph theoretical properties that are of interest when we are considering the topology of the LN. We start by giving an overview of these properties in the context of the LN.


We say that a network is connected if for every pair of nodes there is a path of edges between them. We say that a network is mm-edge (node) connected, if one needs to remove at least mm-edge (node) to make it disconnected. A network’s edge connectivity is equivalent to the minimum-cut of the network. In the context of the LN, the edges are LN channels, and the nodes are LN nodes that take part in these channels.

Figure 3: Let p be the probability of an edge failing due to an attack or a malfunction. The above figure shows the probability of the network staying connected as a function of its edge connectivity for different values of p .

Node and edge connectivity are a way to measure the network’s stability. High connectivity in the LN ensures that even if several nodes or channels malfunction, the other nodes can continue to transact with each other. See Figure 1 for an example.

Furthermore, high connectivity ensures the existence of many disjoint paths going between different nodes in the network. This helps both stability and privacy. For example, if Alice and Zoe don’t have a channel between them, and occasionally transact, the nodes along the path that they use can gain information about their transaction habits (see [3] for further details). Having many disjoint paths to choose from helps secure the privacy of both Alice and Zoe by making it significantly more difficult to collect information.


The distance between two nodes is the length of the shortest path connecting them in the network. The diameter of a graph is the maximum distance between two nodes in the graph. The diameter gives us an upper bound on the distance between nodes, which guarantees the existence of a short path between any pair.

Long paths are a problem in the LN for two reasons. First, any node along the path charges a fee, making the use of long routs expensive. Second, as channels might malfunction or fail to accommodate transactions, each extra channel in the path adds a non-negligible probability of failure.

Currently, the fees in the LN are rather small, but the failure rates are high. Routes mostly fail due to insufficient funds in one of the channels, although nodes going offline and other problems are also an issue. For the payment to go through, we cannot allow even a single failure along the route. This means that the probability of failure grows exponentially with the length of the route. Figure 4 shows how the route successes probability diminishes as the length of the route grows.

Figure 4: Probability of a route succeeding as a function of the length of the route, assuming the probability of a single channel to fail is p.

A short diameter offers an upper bound on the failure probability for a transaction sent between any pair of nodes. This probability is an important parameter for the usability of the LN.


A network having high expansion means that any set of nodes has many edges connecting it to the rest of the network. In the LN, having good expansion will ensure that any set of nodes has many channels connecting the set to the other nodes in the network. Having high expansion guarantees many helpful properties. For example, high expansion guarantees that breaking the network into two large components that cannot transact with each other requires removing a very large number of edges (see [4]). This makes a large scale attack extremely difficult to accomplish.

High expansion also guarantees that the network is not centralized around a small set of nodes. This is of particular importance in the LN, as the decentralization helps privacy, censorship resistance and stability.

Betweenness Centrality

The betweenness centrality of a node vv in a network is the proportion of the shortest paths, between any pair of nodes, that goes through vv. Most nodes in the LN choose to route using the shortest path3 in the network. In light of this, if there is a small set of nodes with a betweenness centrality that is significantly greater than the average, this means that most nodes route through that set. This allows the nodes, especially if they are working together, to learn a vast amount of information about flows in the network. As any form of centralization, it also opens up the network to failures and various attacks.

To make sure that nodes do not that take up a disproportional part of the flow in the network, we look at the values of the betweenness centrality of all the nodes in the network, and take the standard deviation of these values. The smaller the standard deviation is, the better, as this points to the decentralization of the network. As this is a difficult parameter to study formally, we will focus on it only in the simulation part.

The hub and spoke topology cannot guarantee good network parameters. By adding channels as prescribed in Maypoles, we can ensure the network’s health. In the next section, we give formal definitions of the above properties, state and prove the main theorem that shows Maypoles indeed improves the topology without making any assumption on the underlying LN. Then we present the results of several simulations where we study the Maypoles protocol over a snapshot of the LN and consider several variations to the protocol.

The Main Theorem

The theorem we state and prove in this section shows the benefits of Maypoles to the network structure. Before stating and proving our theorem, we need to give formal definitions for the LN under Maypoles and for the desired network properties.

In Maypoles, if a hub, say h0h_0, has chosen another hub, say h1h_1, then h0h_0 and h1h_1 are connected to each other via a subset of their spokes. This means that h0h_0 and h1h_1 can transact with each other, routing through the spokes they share. To study this relation, we define the secondary network.

Definition 3.1 (Secondary Network). The Maypoles protocol with a fixed constant kk creates the secondary network Lk\mathcal{L}_k. The nodes of Lk\mathcal{L}_k are all the hubs in the LN. There is an edge between hub h0h_0 and hub h1h_1 in Lk\mathcal{L}_k if one of the hubs chose the other in stage (2) of the Maypoles protocol, that is, if there are spokes connected simultaneously to h0h_0 and h1h_1.

When considering the influence of Maypoles on the LN, we think of a new network created by adding the edges of Lk\mathcal{L}_k to the existing LN. The LN together with Lk\mathcal{L}_k will have edge and node connectivity greater or equal to the connectivity of Lk\mathcal{L}_k. The same holds for expansion. As for the diameter, the distance between nodes in Lk\mathcal{L}_k is an upper bound on the distance in the LN together with Lk\mathcal{L}_k, and so the diameter can only become smaller.

To understand how the addition of Lk\mathcal{L}_k improves the topology we first give the formal definitions of the network properties, then we state the theorem, and finally prove it.

Definition 3.2. Let G=(V,E)G=(V,E) be a connected network, where VV is the set of nodes, and EE is the set of edges.

  • Connectivity GG is connected if there is a path between any two node. GG is mm edge (node) connected if it stays connected if we remove any set of <m< m edges (nodes).

  • Diameter For u,vVu,v \in V, let d(u,v)d(u,v) be the distance between uu and vv, defined as the length of the shortest path from uu to vv. The diameter of GG is maxu,vVd(u,v)\max_{u,v\in V}d(u,v), that is, the greatest distance between two nodes in GG.

  • Expansion For a set of nodes SVS\subseteq V define its outer boundary to be the set of edges that have one end in SS and one end outside SS, that is, (S)={(u,v)E s.t. uS and vS}\partial(S)=\{(u,v)\in E \text{ }s.t. \text{ }u\in S \text{ }and \text{ } v\notin S\}.

    The edge expansion of GG is the smallest ratio between the size of the boundary of a set and the size of the set itself, that is, minSV,0<SV2(S)S\min_{S\subseteq V, 0<|S|\leq \frac{|V|}{2}} \frac{|\partial(S)|}{|S|}.

Theorem 3.3. Let Lk\mathcal{L}_k be Maypoles’ secondary network with k2k\geq 2. Then w.h.p.4

  1. Lk\mathcal{L}_k is kk edge connected

  2. Lk\mathcal{L}_k is kk node connected

  3. Lk\mathcal{L}_k has an edge expansion of at least (1+o(1))k(1+o(1))k

  4. Lk\mathcal{L}_k has a diameter of at most (1+o(1))lognk+1(1+o(1))\frac{\log n}{k+1}, where nn is the number of nodes.

Note that the theorem does not assume anything about the underlying LN graph, and only shows properties of Lk\mathcal{L}_k. When adding Lk\mathcal{L}_k to the LN, it could happen that the connectivity and expansion would be even better, and the diameter even smaller. When we simulate Maypoles with a snapshot of the LN, we indeed see that the improvement in the average case is even better than is guaranteed by the theorem. Further details on the simulations are given in Section 3.3. The proof of the theorem can be found in Appendix 7.

Simulations and Variations

In the previous section, we have focused on theoretical results that allowed us to give bounds on properties guaranteed by the Maypoles protocol, regardless of the structure of the underlying LN. In this section, we simulate the effect of Maypoles on the current topology of the LN. We also discuss and simulate some variations of the Maypoles protocol and their effect on network properties. To simulate Maypoles and its variation, we have used the LN snapshot from [5]. The code of the simulation can be found in [6].

In addition to studying the regular Maypoles protocol, we have also considered the following variations. In the first one, when a hub chooses kk hubs to connect to, there is a subset of hubs it prefers over the others. It is natural to assume that some hubs would prefer to connect to hubs that are similar to them. The similarity could be in relation to geography, the demography of customers, or other parameters that will make the link between the hubs more advantageous. As we do not have any meta-data on the hubs in the LN snapshot, we chose a random-like heuristic where hubs prefer other hubs if the last digits of their IDs are the same.

In the second variation, some hubs do not cooperate, that is, these hubs do not instruct their spokes to open secondary channels. It could easily happen that a hub would signal that it is interested in taking part in Maypoles, and then fail to perform the protocol. In many cases, hubs are interested in a change, yet will take a very long time before adopting it in practice. To simulate this, each hub chooses whether to cooperate or not by flipping a coin with some fixed success probability. Hubs do not know which hubs cooperate and which don’t, and so a cooperating hub might instruct its spokes to connect to a non-cooperating hub. This will help the non-cooperating hubs, but not as much as performing the protocol.

We examine Maypoles and the above variations through two parameters. The first is the edge connectivity of the network. This will tell us both how resilient is the network to failures and attacks, and will show us the number of different routes available between pairs of nodes. If hubs deviate from the uniform choice by preferring some hubs, we expect to see similar results to the uniform case, as there is a variety of edges added for every hub. Because connectivity is very sensitive to local changes, we expect a significant change if a large proportion of hubs do not cooperate.

The second parameter we want to examine is the betweenness centrality in the network. Most nodes in the LN will choose to route through the shortest path available. In any connected network, for any pair of nodes {s,t}\{s,t\}, there is at least one path of minimal length. For a hub hh, the betweenness centrality is the proportion of these paths that go through hh. Intuitively, if the betweenness centrality of a hub is significantly larger than the average, this means that the network is centralized around this hub. In the context of the LN, this will mean that a larger proportion of the payments routed in the network will go through a specific hub. Looking through this lens, we will say the network is decentralized if the betweenness centrality of the hubs is similar. To measure this, we look at the standard deviation of the values of the betweenness centrality. The smaller the standard deviation, the better the decentralization of the network.

To be more precise, the cases we have simulated are the following. For each hub in the Network:

  1. Uniform The hub chooses kk hubs uniformly at random (as prescribed by Maypoles)

  2. Preferred Hubs Let dd be the last digit of the hub’s ID. The hub chooses kk other hubs, where the probability of a hub with a last digit dd to be chosen is 10 times greater than that of a hub with the last digit different from dd

  3. 10%10\% Hub Failure With probability 90%90\% the hub chooses kk hubs uniformly at random, with probability 10%10\% the hub does not add any new connections

  4. 50%50\% Hub Failure With probability 50%50\% the hub chooses kk hubs uniformly at random, with probability 50%50\% the hub does not add any new connections

For all of the above we have simulated values of kk between 0 and 1212. Note that k=0k=0 is just the snapshot of the LN without any changes. The simulation repeated 50 times, and the average of the results was taken.

Figure 3 shows the edge connectivity of the LN as a function of kk for the various cases stated above. The LN snapshot has connectivity 88, as is shown in the k=0k=0 column. As kk grows, so does the edge connectivity of the network. Notice that, for example, for k=12k=12 in the Uniform case, Theorem 3.3 guarantees edge connectivity of 1212. As the base graph has connectivity 88 and we are adding to it a graph with connectivity 12, we could have expected a connectivity of 12+8=2012+8=20. The simulation shows that the average case out performs the theoretical bounds significantly, as the average connectivity is above 2727. In Theorem 3.3, we have shown that various properties will hold w.h.p., yet it seems that the average case will be even better than what is stated in the theorem.

Figure 5: Edge connectivity as a function of the parameter k, for the different variations. The greater the edge connectivity, the better is the topology of the graph.

When comparing Uniform to the other variations in Figure 5, we see that, as expected, nodes that do not cooperate bring the connectivity down. This is particularly significant when the failure probability is 50%50\%. Preferred Hubs on the other hand will not bring connectivity as sharply down, because many edges are added. Other properties studied in Theorem 3.3 exhibit similar improvement dynamics, yet due to the currently small size of the LN, they are less interesting. With the growth of the network, the diameter and the expansion are expected to become more significant.

Figure 6 shows the standard deviation of the betweenness centrality as a function of kk, for the different variation of hub choices. The smaller the standard deviation, the better. A small standard deviation points to a uniform distribution of paths between the hubs. As kk grows, we see that the standard deviation becomes smaller. The fact that the routing paths are distributed more evenly between hubs, means that no hub controls a disproportional part of the flow in the network.

Figure 6: The standard deviation of the betweenness centrality values of hubs in the network as a function of k. The smaller the standard deviation, the better, as it shows the network is more decentralized.

Similarly to the previous figure, the Uniform choice gives the best results, Preferred Hubs and 10%10\% Hub Failure have only slightly larger standard deviations. 50%50\% Hub Failure does not perform as well as the other cases. The hubs that do not cooperate stay behind and do not take part in many paths in the graph, which keeps the standard deviation rather high. For example, 50%50\% Hub Failure for k=12k=12 performs similarly to Uniform with kk as small as 55. This points to the fact that hubs that do cooperate get more routes going through them, and this could incentives hubs to join Maypoles.

Spokes in Maypoles

In Maypoles, spoke open two channels instead of one. Even if it benefits the network, we cannot expect the spokes to do this without proper economic incentive. In this section, we show that by opening channels as prescribed in Maypoles, the spokes save on the costs of continuously transacting over the LN. The savings are due to the dynamics of fees in Bitcoin.

A basic demand from any type of payment system is that it will be always available, that is, at any moment in time the user can send funds that they own and receive funds from other users. Looking at the LN as a mean of payment for spokes, we assume that a spoke in LN needs to always be able to send or receive transactions

In this section we examine the cost of having a channel that is always balanced, that is, always available for sending or receiving transactions. We call such a channel a high availability channel (HAC). We show that following Maypoles allows spokes to have an HAC for a lower cost than trying to have an HAC without Maypoles. The reason that Maypoles is cheaper is that a large part of the cost of an HAC is the on-chain rebalancing fees. When maintaining and using a channel over long periods of time, one must occasionally rebalance by moving funds on the blockchain. Maypoles allows paying smaller fees every time we need to perform such a rebalance, without suffering any downtime.

To gain some intuition, we start with an example. Assume that Alice sells T-shirts online and accepts payments over the LN. Any downtime in which the channel cannot receive payments can result in loss of revenue. Thus, Alice wants a HAC. If Alice has a single channel, when her channel gets depleted, that is, she cannot receive payments, she needs to rebalance. As she has a single channel, any rebalancing option includes an on-chain transaction, and so the main cost will be the transaction fee.

One option is sending the rebalancing transaction with a fee that guarantees it will go through as quickly as possible. This will be expensive, as the waiting time for the transaction to be included strongly depends on the fee. Another option is trying to rebalance in advance, yet this is not cheap either, as it entails locking in the LN large sums (either Alice’s or the hub’s) and often opening parallel channels to the same hub. Both of these are expensive and in some cases hubs will not allow5 the spoke to do so.

On the other hand, if Alice’s node is a spoke in Maypoles she has two channels, main and secondary. The main channel is the one that she mostly uses to receive payments, and so it is an HAC. Alice’s secondary channel is used to rebalance the main channel, that is, when the main channel is depleted Alice uses the secondary channel to rebalance it (see Figure 7 for an illustration). As this rebalance happens on the LN, it is immediate, and the fees are negligible. When the secondary channel needs to be rebalanced, this entails an on-chain transaction. When rebalancing the secondary channel, Alice can wait for a long time for the rebalancing transaction to go through, as her main channel is still open. By allowing longer waiting times when rebalancing, Alice pays a smaller fee. Because of the difference in the rebalancing fees, the cost of maintaining an HAC over Maypoles is smaller than the cost of a single channel as an HAC.

Figure 7: Spoke a is rebalancing the main channel it has with h0h_0 using the cycle a \rightarrow h1h_1 \rightarrow b \rightarrow h0h_0 \rightarrow a. This also benefits spoke b, as it rebalances its main channel with h1h_1.

In the next sections we define a general setting for channel costs, prove the benefits for the spokes, and finally give some numeric examples.

The Cost of a Lightning Channel

The cost of maintaining an HAC has two main parts. The first part is the fees paid each time the channel needs to be rebalanced. The second part is the opportunity loss of the bitcoin locked in the channel. On the one hand, if there is a large amount of bitcoin locked in the channel, we will rarely need to rebalance it, but the opportunity loss is significant. On the other hand, if the amount locked in the channel is a small, so is the opportunity loss, but we need to rebalance the channel often. As the amount of bitcoin locked in the channel can be chosen by the nodes opening it, they can optimize the amount to get a minimal channel cost. As for the rebalancing fee, the smaller it is, the smaller the cost of the channel.

Formally, denote by BB the cost of rebalancing a LN channel once, and by F(B)F(B) the minimum possible cost of an HAC as a function of BB. We assume that the transaction flow rate and the interest rate, that is the rate of opportunity loss, are constant. A natural assumption is that F(B)F(B) decreases as BB decreases. We use this for the benefit of spokes in Maypoles.

In the LN, and similar solutions, there are two main ways to rebalance the channel. The first one is moving funds from a different channel owned by the same node (see [7] for further details), the second one is performing an on-chain transaction. The LN fees are negligible in comparison to the on-chain fees, and so we may focus on the cost arising from the need to move funds on-chain.

If a node mostly pays on the LN, it will need to move funds from the blockchain to the network regularly, as the funds in all of its channels will run out. Similarly, if a node mostly gets paid, it will need to move funds back to the blockchain to allow for incoming transactions. It is rare that a node sends and receives at exactly the same rate, yet even in this case from time to time the node’s funds will be depleted and there will be need for an on-chain transaction to rebalance. See [8] for further details.

Rebalancing through the blockchain entails transaction fees. As there is an ongoing auction for space on the blockchain, a high fee will get the transaction into the blockchain quickly, while a transaction with a lower fee might wait for hours or days. If a node is not in hurry, it can take advantage of this fact, and send transactions with a lower fee (see [9] for further details). In Figure 8 we show the ratio between the estimated fee for a transaction to be included in 6 blocks versus the next block, between April 2021 and April 2022 as presented in [10]. Waiting 6 blocks cuts the transaction fee by half in most cases. We believe that waiting even longer would allow for even lower fees.

Figure 8: A moving weekly average of the ratio between the estimated fee for a transaction to appear in 6 blocks and the estimated fee for a transaction to appear in the next block

Benefits of Maypoles for a Spoke

To show that there is a financial motivation for spokes that wish to have an HAC, we need to show that by choosing correctly the sizes of the main and secondary channels in Maypoles, the cost of having an HAC with Maypoles is cheaper in expectation than the cost of a single channel HAC. With a single channel, if one wishes it to have high availability, one needs to either open a new channel before the old one is depleted, thus forgoing interest for large sums in the LN, or to pay high transaction fees. Maypoles avoids this problem and saves on rebalancing costs.

A spoke in Maypoles will hold in its main channel an amount which allows for a few days worth of transactions. The secondary channel would be of size optimized for a minimal cost. The spoke can make sure that the main channel always has liquidity, by moving liquidity from the secondary channel. The move of liquidity from the secondary channel to the main channel is done through a short cycle in the LN, as shown in Figure 7, and so has a negligible cost.

The spoke can wait a long time before rebalancing the secondary channel, as it is only used to rebalance the main channel. Thus, even if this is done by an on-chain transaction, this can be done at a significantly lower cost.

In the following theorem, we show that a spoke’s HAC will be cheaper in Maypoles than in the single channel case, if the spoke chooses the sizes of the main and secondary channels correctly. The savings are due to the difference in the on-chain transaction fees. We define an immediate transaction to be a transaction offering a fee high enough for it to be in the next block, and a delayed transaction to be a transaction offering a fee high enough for it to appear in the next 6 blocks. The choice of 6 blocks is rather arbitrary and can be a few days worth of waiting, as shown in examples in Section 4.3.

Theorem 4.1. Let F(B)F(B) be the channel cost function, let BiB_{i} be the cost of immediate rebalancing and let BdB_{d} be the cost of delayed rebalancing. For Bi>BdB_i>B_d, there is a choice of sizes for the channels in Maypoles that make an HAC cheaper in Maypoles than a single channel HAC.

Proof. Let Fi=F(Bi)F_i = F(B_i) be the cost of a single channel HAC, and let us compare it to the cost of the Maypoles channels. In Maypoles, we can guarantee that the cost of the secondary channel is Fd=F(Bd)F_d = F(B_d). As for the main channel, assume that it is has KK bitcoin in it. The size of the main channel, that is, the amount locked inside it, is an upper bound on its cost, as it is never rebalanced on-chain. Thus, the cost of the two Maypoles channels is at most Fd+KF_d+K.

Choose K<FiFdK<F_i-F_d, and as F(B)F(B) is monotone in BB, we know that we can choose K>0K>0. Then we get that


that is, the cost of the two Maypoles channels is smaller than the cost of a single regular channel.

An important observation is that the benefits for a spoke do not depend on the hubs’ cooperation. Although rebalancing the spoke’s main channel is easier and cheaper if there is a short cycle for the spoke to use, the spoke can make do by finding a path between the two hubs it is connected to. Another solution for the spoke is opening both channels to the same hub, yet this forgoes any privacy benefit and not all hubs allow it.

We finish this section by giving some numeric examples based on the cost functions derived in [8], to show that this indeed works with real world numbers.

Numeric Examples

Assume that nodes n0n_0 and n1n_1 open a channel where funds flow at rate λ0\lambda_0 from n0n_0 to n1n_1 and at rate λ1\lambda_1 in the opposite direction, and assume that rr is the market interest rate. As before, BB is the cost of rebalancing the channel once. Consider the cost function whose asymptotic around r=0r=0 are given in [8].

Theorem 4.2 ([8]). In the limit of rr near zero, the first order approximation of the minimum cost of a channel is

  1. If λ0>λ1\lambda_0 >\lambda_1 then

    2(B(λ0λ1)r)1/2 2 \left(\frac{B (\lambda_0-\lambda_1)}{r}\right)^{1/2}

  2. If λ0=λ1=λ\lambda_0=\lambda_1=\lambda then

    3(2Bλr)1/3 3 \left(\frac{2 B \lambda}{r}\right)^{1/3}

Example 1

Assume that a spoke spends λ0=10,000$\lambda_0=10,000\$ annually over the LN and does not receive funds over the LN, that is λ1=0\lambda_1=0. Furthermore, assume that the fee for rebalancing the channel in the next block is Bi=1$B_i=1\$ and the fee for a delayed rebalancing (say, going into a block in the next 24 hours) is Bd=0.25$B_d=0.25\$ and let the interest rate be r=0.05r=0.05. Then the expected cost of a single channel is approximately 2(1100000.05)1/2$894$.2\left(\frac{1\cdot 10000}{0.05}\right)^{1/2}\$\approx 894\$.

As for the two channel case, assume that in the main channel we deposit 50$50\$, the amount expected to be used in two days, and in the secondary channel the optimal amount for the minimal cost indicated by Theorem 4.2. Then, in total, the cost is expected to be at most 50$+2(0.25100000.05)1/2$274$.50\$+2\left(\frac{0.25\cdot 10000}{0.05}\right)^{1/2}\$\approx274\$.

From this, we see that the user is expected to save 620$\approx620\$ each year, which is almost 70%70\%.

Figure 9: In this graph, we compare the savings in Maypoles for different transaction rates λ, assuming various ratios C between immediate and delayed refunding of a channel.

Example 2

In Figure 9 we examine the amount saved by opening two Maypoles channels instead of one regular channel for various transaction rates and ratios between transaction fees. Define C=BdBiC =\frac{B_d}{B_i}, that is, the ratio between a delayed transaction fee and an immediate transaction fee. In this example, we assume that the main channel has a week’s worth of funds locked in it. We see that the savings grow as the transaction rate grows and as the ratio CC gets smaller.

Previous Works

This work builds upon previous research on network theory, random graphs, and the economy of the LN. This is the first protocol that offers to use the economic incentives in the LN to improve its topology. We give a short overview of results used in this paper, directly or indirectly.

The starting point of this paper is the fact that the LN has a hub and spoke topology, and that it is not expected to change. This has been shown in several studies, both empirical (e.g., [11], [12], [13], [14], [15], [16], [17]) and theoretical (e.g., [18], [19], [20]).

It is particularly important to note the studies that point to weaknesses of the network due to its tendency towards the hub and spoke model. See for example [21], [22], [23] and to some extent also [24]. Although some of this works offer local remedies for specific attacks, the hub and spoke topology is fragile by nature, and so in Maypoles we aim to change the topology itself and thus resolve many of the potential problems shown in these papers.

The health of networks is a well studied subject, and there are many works from which we can draw properties we want our network to exhibit. These works can be both theoretical (e.g., [25], [26], [27]), and as practical as network manuals (e.g., [28]). As the LN is decentralized and arises from economic needs, we cannot expect the healthy topologies described in the aforementioned works to appear on their own. To guarantee a good network topology, we need to push the network towards it.

To prove the compatibility with node’s economic incentives, we use the results in [9] that show the correlation between waiting times and transaction fees. When going into concrete examples, we use [8] where the authors study closely the cost of lightning channels, together with other questions. This work has only considered the LN on the scope of a channel, we use it to examine how local economic incentives can be used to better the network in general.

Conclusion and Discussion

In this work, we have introduced and studied the Maypoles protocol, which improves payment channel networks that have a hub and spoke topology, such as the Lightning Network. We have shown that Maypoles increases the network stability, privacy, and resilience to attacks. Going over several parameters that measure the health of a network, we have shown that both in theory and in practice, Maypoles improves them significantly.

We have also shown that by correctly choosing the channel sizes, the spokes can save on costs of maintaining a channel that is always available for sending and receiving transactions The savings are due to the correlation between transaction fee over Bitcoin and the urgency of the transaction. This can motivate spokes to participate in the Maypoles protocol. By taking into account the economic incentives, we made sure to create a win-win situation between individual nodes and the network as a whole.

The framework created here can be used to examine other variation of decentralized changes to the topology. In Section 3.3 we have discussed a few variations on the Maypoles protocol and simulated their performance. In the future, it could be interesting to examine other variations tailored to the specific challenges of different networks.

It could also be interesting to examine the addition of channels to other topologies, such as scale-free graphs (see, e.g, [29]). In such networks, there won’t be a clear-cut difference between "large" nodes, like hubs, and "small" ones, like spokes. This might prove to be more useful for the study of some payment channel networks, especially as they grow.

Another interesting direction to look into is encouraging nodes to open more than one channel. In Maypoles, we give economic incentive for opening two channels. It would be better if the number of channels would be even greater. Opening more than two channels as described in Maypoles will not offer significant savings. It could be that there is another scheme which can motivate spokes to have many channels.

The LN is a very young project with many changes and upgrades happening. For example, Multi-Path Payment is a solution that allows splitting a single payment into several smaller payments and sending the smaller payments along different routes. The ability to do so can motivate nodes to open several channels for better privacy and liquidity management. Studying how to better utilize this and other developments for the health of the network would be of great importance to the development of the LN.


A. The Lightning Network

A channel in the LN is opened between two parties. Both parties lock a sum in the channel by signing an on-chain Bitcoin transaction. Once the channel is open, they can transact between themselves by changing the ownership over parts of the locked funds.

For example, assume that Alice regularly buys coffee from Bob. They open a channel where Alice locks 5 bitcoin that she is planning to pay Bob with. Bob is not locking any funds, as he does not expect to pay Alice.

The first time Alice buys coffee, she wants to transfer 1 bitcoin to Bob, and so they change the state of the channel to Alice having 4 bitcoin and Bob having 1 (see Figure 10). They can continue transacting if the channel’s funds allow it, and Bob can also send bitcoin to Alice if needed.

Figure 10: An example of Alice paying Bob 1 bitcoin over their channel

If there is also a channel between Bob and Carol, Alice can transact with Carol without opening a new channel to her. She can pay Carol through Bob, if Bob agrees to cooperate. Bob can charge a fee for the service he is providing to Alice and Carol. To pay Carol 1 bitcoin, Alice sends 1 bitcoin to Bob, who then sends 1 Bitcoin to Carol. See Figure 11 for this example.

Figure 11: An example of Alice sending Carol 1 bitcoin through Bob

The last example we want to consider is when Alice has channels both to Bob and to Carol, and Bob and Carol have their own channel. Assume Alice and Bob’s channel is depleted, that is, Bob owns all the bitcoin, and assume that Alice still has funds in her channel with Carol. Then Alice can refund her channel with Bob by moving some funds from the Alice and Carol channel to the Alice and Bob channel. Bob and Carol must agree to this, and the channel their channel must have sufficient funds.

For example, if Alice wants to send 1 bitcoin from her channel with Carol to her channel with Bob, she will do this by using Carol and Bob’s channel. To be more precise, Alice sends herself 1 Bitcoin through Carol and Bob. In the channel of Alice and Carol, Alice sends 1 Bitcoin to Carol. In the channel of Carol and Bob, Carol sends 1 bitcoin to Bob. In the Channel of Bob and Alice, Bob sends 1 bitcoin to Alice. Each one has the same amount in the beginning and the end, only the distribution between the channels changed. See Figure 12 for an illustration.

Figure 12: An example of Alice rebalancing her channel with Bob, by using the funds she has in the channel with Carol

Note that this is cryptographically guaranteed to ensure that no harm can come to any party. If Alice pays Bob, she cannot later claim that the transaction did not happen, and if Bob and Carol agree to facilitate the transaction, they cannot disappear with the funds and not commit their part of the deal. The full details can be found in [1] and in several blog posts, such as [30].

B. Proof of The Main Theorem

A key part of the proof of Theorem 3.3 is the observation that the Maypoles protocol gives raise to a kk-out graph, as introduced in [31].

Definition B.1 (kk-out graph). Starting from an empty graph G=(V,)G=(V, \emptyset) we do the following steps

  1. For each vV(G)v\in V(G) create a set A(v)A(v) by choosing kk nodes from V(G)V(G) uniformly, independently, and allowing repetitions

  2. For each vV(G)v\in V(G) add an edge between vv and each node in A(v)A(v)

  3. Remove double edges and self-loops

The resulting graph is called a kk-out graph.

The proof of the main theorem builds upon the observation that Lk\mathcal{L}_k is a kk-out graph. To prove the claimed graph properties, we need the following two lemmas. The first lemma is in the heart of the theorem, and shows that a kk-out graph has good expansion. The second lemma shows that graphs with good expansion have a low diameter. We start by stating and proving the lemmas, and then we proceed to the proof of the theorem.

Lemma B.2. Let G=(V,E)G=(V,E) be a random kk-out graph, for some constant kk. Then for every SVS\subset V, such that SV/2|S|\leq |V|/2, we have that (S)(1+o(1))kS\partial(S)\geq (1+o(1))k|S| w.h.p.

Proof. We split the proof into two cases. We first focus on the more complicated case where S>n1/4|S|>n^{1/4}. After proving that the lemma holds for such SS, we finish the proof by showing the simpler case where Sn1/4|S|\leq n^{1/4}.

Let S=s|S|=s and V=n|V|=n. Define (S)\overline{\partial}(S) to be the random variable counting the number of edges between SS and VSV\setminus S prior to the removal of double edges in the kk-out processes, that is, prior to step 6 of the processes. We will show that w.h.p. (S)=(1+o(1))(S)\partial(S)=(1+o(1))\overline{\partial}(S) and (S)(1+o(1))ks\overline{\partial}(S)\geq (1+o(1))ks.

To show that w.h.p. (S)(1+o(1))ks\overline{\partial}(S)\geq (1+o(1))ks, we calculate the expectation of (S)\overline{\partial}(S) and then show that (S)\overline{\partial}(S) is concentration around its expectation. Edges in (S)\overline{\partial}(S) appear if either a node in SS chooses a node in VSV\setminus S or if a node in VSV\setminus S chooses a node in SS, call the former type 1 and the latter type 2.

For each vSv \in S the expected number of nodes it chooses outside SS is

kVSVk\cdot \frac{|V\setminus S|}{|V|}

Thus the expected number of edges of type 1 is

SkVSV=ks(ns)n.|S|\cdot k\cdot \frac{|V\setminus S|}{|V|}=k \frac{s(n-s)}{n}.

Similarly, the expected number of edges of type 2 is

VSkSV=ks(ns)n.|V\setminus S| \cdot k \cdot \frac{|S|}{|V|}= k \frac{s(n-s)}{n}.

Thus, the expected number of edges with one node in SS and one node in VSV\setminus S is

E[(S)]=2ks(ns)n\mathbb{E}[\overline{\partial}(S)] =2k \frac{s(n-s)}{n}

To show that (S)\overline{\partial}(S) is concentrated around its expectation we use Chebyshev’s inequality

Theorem (Chebyshev’s inequality) For any random variable XX and positive aa


The variance of the random variable (S)\overline{\partial}(S) can be calculated as follows. For vSv\in S let XvX_v be the number of nodes in VSV\setminus S chosen by vv, and for uVSu\in V\setminus S let YuY_u be the number of nodes in SS chosen by uu. Note that the above variables are all independent of each other, and that (S)=vSXv+uVSYu\overline{\partial}(S)= \sum_{v\in S} X_v + \sum_{u\in V\setminus S} Y_u. Using these two facts we get that

Var[(S)]=vSVar[Xv]+uVSVar[Yu].Var[\overline{\partial}(S)]=\sum_{v\in S}Var[X_v]+\sum_{u\in V\setminus S}Var[Y_u].

As XvX_v behaves as the Binomial random variable Bin(k,nsn)Bin(k, \frac{n-s}{n}), and YuY_u behaves as Bin(k,sn)Bin(k, \frac{s}{n}), we get

Var[(S)]=vSknsn(1nsn)+uVSksn(1sn)=sknsnsn+(ns)ksnnsn=nksn(ns)n=ks(ns)n.\begin{aligned} Var[\overline{\partial}(S)] &= \sum_{v\in S}k \frac{n-s}{n} (1- \frac{n-s}{n})+\sum_{u\in V\setminus S}k \frac{s}{n}(1- \frac{s}{n})\\ &=sk \frac{n-s}{n}\cdot \frac{s}{n}+(n-s)k \frac{s}{n}\cdot \frac{n-s}{n} \\ &=n\cdot k \frac{s}{n}\frac{(n-s)}{n}=k\frac{s(n-s)}{n}. \end{aligned}

Notice that Var[(S)]=12E[(S)]Var[\overline{\partial}(S)]=\frac{1}{2}\mathbb{E}[\overline{\partial}(S)], and so by choosing a=E((S))2/3a=\mathbb{E}(\overline{\partial}(S))^{2/3} and plugging it into Chebyshev’s inequality we get


It is left to show that 12E[(S)]1/3n0\frac{1}{2\mathbb{E}[\overline{\partial}(S)]^{1/3}} \underset{n\to \infty}{\longrightarrow} 0. As n2sn1/4\frac{n}{2}\geq s\geq n^{1/4}, and as f(s)=s(ns)f(s)=s(n-s) is a monotone increasing function in this range, we have that

(2E[(S)])1/3=(4ks(ns)n)1/3(4kn1/4(nn1/4)n)1/3n1/120.\begin{aligned} (2\mathbb{E}[\overline{\partial}(S)])^{-1/3}=&(4k\frac{s(n-s)}{n})^{-1/3}\\ \leq&(4k \frac{n^{1/4}\cdot(n-n^{1/4})}{n})^{-1/3}\leq n^{-1/12}\to 0. \end{aligned}

Thus we have that w.h.p. 

(S)=(1+o(1))E[(S)]=(1+o(1))2ks(ns)n(1+o(1))2ks(nn/2)n=(1+o(1))ks    (1) \begin{aligned} \overline{\partial}(S)&=(1+o(1))\mathbb{E}[\overline{\partial}(S)]=(1+o(1))2k\frac{s(n-s)}{n}\\ &\geq(1+o(1)) 2k\frac{s(n-n/2)}{n}=(1+o(1))ks \text{ } \text{ } \text{ } \text{ (1) } \end{aligned}

where Inequality (1) holds as sn2s\leq \frac{n}{2}.

As for the case where sn1/4s\leq n^{1/4}, the probability that a node in SS chooses a node in VSV\setminus S is

VSV=nsnnn1/4n=11n3/4.\frac{|V\setminus S|}{|V|}=\frac{n-s}{n}\geq \frac{n-n^{1/4}}{n}=1-\frac{1}{n^{3/4}}.

The probability that all the nodes in SS choose nodes in VSV \setminus S is at least

(11n3/4)ks(11n3/4)kn1/4n1.(1-\frac{1}{n^{3/4}})^{ks}\geq (1-\frac{1}{n^{3/4}})^{kn^{1/4}}\underset{n\to \infty}{\longrightarrow} 1.

From the above, if sn1/4s\leq n^{1/4} we have that w.h.p. all the edges that nodes in SS chose are to VSV\setminus S. This means that w.h.p. (S)ks\overline{\partial}(S)\geq ks.

It is left to show that (S)=(1+o(1))(S)\partial(S)=(1+o(1))\overline{\partial}(S). The difference between (S)\overline{\partial}(S) and (S)\partial{(S)} is the number of double edges between SS and VSV\setminus S. Denote the random variable counting these double edges by D(S)D(S), and note that

(S)(S)D(S).   (2)  \partial(S)\geq \overline{\partial}(S)- D(S). \text{ } \text{ } \text{ (2) }

Let vSv\in S and uVSu \in V\setminus S. The probability of more than one edge between them is at least the probability of exactly 2 edges. The nodes vv and uu make together 2k2k choices. The probability that uu chooses vv or vice versa is 1n\frac{1}{n}. Thus, the number of edges between them follows the binomial distribution Bin(2k,1n)Bin(2k,\frac{1}{n}) and so

P(exactly 2 edges between u and v)=(2k2)1n2(11n)2k24k2n2.\mathbb{P}(exactly \text{ } 2 \text{ } edges \text{ } between \text{ } u \text{ } and \text{ } v)=\binom{2k}{2}\frac{1}{n^2}(1-\frac{1}{n})^{2k-2}\leq \frac{4k^2}{n^{2}}.

From this, we get that the expected number of double edges is at most

E(D(S))s(ns)4k2n2=2knE[(S)].\mathbb{E}(D(S))\leq s(n-s)4\frac{k^2}{n^{2}}=\frac{2k}{n}\mathbb{E}[\overline{\partial}(S)].

By Markov’s inequality we have that

P(D(S)>n1/2E(D(S)))E(D(S))n1/2E(D(S))=1n1/20\mathbb{P}\left(D(S)>n^{1/2}\mathbb{E}(D(S))\right)\leq \frac{\mathbb{E}(D(S))}{n^{1/2}\mathbb{E}(D(S))}=\frac{1}{n^{1/2}}\to 0

and so w.h.p. we have that D(S)n1/2E[D(S)]n1/22knE[(S)]=o(E[(S)])D(S)\leq n^{1/2}\mathbb{E}[D(S)] \leq n^{1/2}\frac{2k}{n}\mathbb{E}[\overline{\partial}(S)]=o(\mathbb{E}[\overline{\partial}(S)]).

Plugging the above into Equation (2), we get that w.h.p. 

(S)(1+o(1))(S)(1+o(1))ks\partial(S)\geq(1+o(1))\overline{\partial}(S)\geq (1+o(1))ks

and this completes the proof. ◻

Lemma 8. Let GG be a graph on nn nodes. If GG is a kk-expander, then the diameter of GG is at most logn/(k+1)\log n/(k+1)

Proof. For any vV(g)v\in V(g), let Si(v)S_i(v) be the set of nodes of distance at most ii. S0(v)={v}=1S_0(v)=|\{v\}|=1. As GG is a kk-expander, the number of nodes in S1(v)S_1(v), including vv itself, is at least S0(v)+kS0(v)=k+1S_0(v)+k\cdot S_0(v)=k+1. If Sm1(v)<n2S_{m-1}(v)<\frac{n}{2} then the number of nodes in Sm(v)S_m(v) is at least Sm1+kSm1(k+1)mS_{m-1}+k\cdot S_{m-1}\geq (k+1)^m. Choosing m0=12logn/log(k+1)m_0=\frac{1}{2}\log n/\log(k+1), we get that there are at least n/2n/2 nodes of distance at most m0m_0 from vv.

Let uu and vv be a pair of nodes in GG. From the above, there are at least n/2n/2 nodes of distance at most m0m_0 from uu and the same holds for vv. Thus, there must be a node in both Sm0(v)S_{m_0}(v) and Sm0(u)S_{m_0}(u), and so there is a path of length at most 2m0=logn/log(k+1)2m_0 = \log n/\log(k+1) from uu to vv. ◻

We are now ready to prove Theorem 3.3.

Proof of Theorem 3.3. The key observation we need is that Lk\mathcal{L}_k is equivalent to a kk-out graph. Indeed, as a hub instructs its spokes to connect to kk different hubs that are chosen uniformly at random, it creates kk random edges in Lk\mathcal{L}_k. This is exactly step 2 of the kk-out creation processes. If two hubs choose each other, or a hub chooses another hub twice, we still think about the connection between them as a single edge in Lk\mathcal{L}_k, and this is step 6 of the kk-out processes. This shows that the resulting graph Lk\mathcal{L}_k is a kk-out graph.

Items 1 and 2 are obtained by the above observation and the following result of Frieze.

Theorem[[32], Theorem 17.2] Let k2k\geq 2 be a fixed integer. Then a kk-out graph has w.h.p. edge connectivity and node connectivity kk.

Item 3 is a direct consequence of the above observation and of Lemma 7 that shows that kk-out graphs are(1+o(1))k(1+o(1))k expanders. Item (3) is obtained by the observation, Lemma 7, and Lemma 8 that shows that expanders have the needed diameter. ◻

No comments here
Why not start the discussion?