11institutetext: Distributed Security Infrastructures
Technical University of Berlin
11email<EMAIL_ADDRESS>22institutetext: Distributed Security
Infrastructures
Technical University of Berlin
22email: {elias.rohrer<EMAIL_ADDRESS>
# On the Routing Convergence Delay in the Lightning Network

Niklas Gögge 11 Elias Rohrer 22 Florian Tschorsch 22

###### Abstract

Nodes in the Lightning Network synchronise routing information through a
gossip protocol that makes use of a staggered broadcast mechanism. In this
work, we show that the convergence delay in the network is larger than what
would be expected from the protocol’s specification and that payment attempt
failures caused by the delay are more frequent, the larger the delay is. To
this end, we measure the convergence delay incurred in the network and analyse
what its primary causes are. Moreover, we further investigate and confirm our
findings through a time-discrete simulation of the Lightning Network gossip
protocol. We explore the use of alternative gossip protocols as well as
parameter variations of the current protocol and evaluate them by the
resulting bandwidth usage and convergence delay. Our research shows that there
are multiple ways of lowering the convergence delay, ranging from simple
parameter changes to overhauling the entire protocol.

###### Keywords:

Bitcoin Lightning Network Gossip Convergence Delay.

##  1 Introduction

Since its inception in 2008, the Bitcoin [8] network showed an inability to
scale to a high volume of transactions [13]. The Bitcoin Lightning Network
[11] is a second-layer payment channel network (PCN) that enables a high
volume of low-cost off-chain Bitcoin transactions.

In the Lightning Network, nodes route payments by finding a path to the
destination based on a local copy of the public channel graph that each node
maintains. In order to keep their channel graph views in sync, nodes propagate
update messages via a peer-to-peer gossip protocol that utilizes a so-called
_staggered broadcast_ mechanism. As a result of the gossip protocol, it can—in
the worst case—take more than $10$ minutes for a message to reach all nodes in
the network.

To avoid issues caused by stale routing information, a convergence delay of
this magnitude goes against the common goal of routing protocols to reach
convergence quickly and reliably. The larger the convergence delay is, the
more likely it is for payment attempts to fail since a source node might be
computing a route based on stale information. Payment attempt failures
stemming from the convergence delay currently account for roughly $1.24\%$ of
all failures according to [14]. These failures can not be eliminated
completely given that message propagation cannot be instant. Moreover,
improved routing algorithms such as multi-part payments (MPPs) do not improve
the rate at which these failures occur. In fact, they may even increase their
occurrences as the probability of such failures only increases with the number
of channels involved in a payment.

In this work, we investigate the convergence delay of routing information and
its effects on payments in the Lightning Network. Our main goal is to present
the state of the convergence delay in the Lightning Network, the issues it
causes, and to layout potential improvement ideas. Our contributions can be
summarized as follows:

  * •

We analyze the Lightning Network’s gossip protocol in its current state by
looking at and comparing c-lightning and LND, the two most popular node
implementations. We measure the delay seen in the real network through a
passive experiment and catalog the seen gossip messages (specifically all
channel updates) to understand why and when gossip messages are broadcast by
nodes. The catalog is also useful to understand which types of channel updates
are potentially disruptive to payment routing. (Section 3)

  * •

We implemented a simulator capable of simulating the Lightning Network’s
gossip protocol as well as payments in the Lightning Network. We can bootstrap
our simulation from historical topology data and replay recorded gossip
messages. We use the simulation to gain further inside into how the gossip
protocol operates and where its inefficiencies lie. (Section 4)

  * •

We evaluate the use of alternative message propagation mechanisms in the
Lightning Network. Through simulation, we compare flooding, a structured
broadcast utilizing the channel graph topology, inventory based gossip, as
well as efficient set reconciliation using Minisketch [4]. (Section 4)

To our knowledge, there exists no prior related work on the convergence delay
in the Lightning Network. However, there is a long history of convergence
delay research in internet routing through the Border Gateway Protocol (BGP),
which we use to draw inspiration for potential improvement ideas [7, 2, 1]. We
discuss these and other related works in Section 6. In the following, we give
a primer on information propagation and the convergence delay in the Lightning
Network.

##  2 Information Propagation in the Lightning Network

The Bitcoin Lightning Network [11] is a second-layer payment channel network
(PCN) that enables a high volume of low-cost off-chain Bitcoin transactions. A
payment channel describes a type of smart contract that enables two parties to
transact off-chain, with the only bottleneck being the network latency between
the two parties. A PCN enables payments between nodes that do not have direct
channels with each other by routing payments over intermediary nodes to reach
the destination. In order to ensure that payment forwarding requires no trust
towards these intermediaries, such multi-hop payments are secured through so-
called Hash Time Locked Contracts (HTLCs). Candidate routes are discovered by
the originators through a source-routing algorithm operating on a local copy
of the network graph, i.e., the routing information base (RIB). These local
information are regularly kept in sync by gossiping update messages in the
network.

The channel_announcement, node_announcement and channel_update messages are
the three main messages of the Lightning Network’s gossip protocol. Channel
announcements are used by two nodes to prove that there is a channel between
them. The proof comes in the form of four signatures tying the nodes to the
keys used in the funding transaction. Node announcements are used to provide
additional information about a node such as reachable network addresses.
Channel updates provide routing information for a channel edge, such as
routing fees and lock times. Each channel counterparty is able to broadcast a
channel update for its outgoing channel edge. In order for a channel to be
operational the network has to see three messages, one channel announcement
and two channel updates (one for each edge of the channel).

###  2.1 Influences on the Convergence Delay

While the details of the information dissemination protocols are left to the
implementations, the most common implementations, such as
c-lightning111https://github.com/ElementsProject/lightning and
LND222https://github.com/lightningnetwork/lnd, generally follow the same
concepts. As we show later, the concepts presented in the following and their
concrete parameterizations can have a significant impact on the convergence
delay.

#### Staggered Broadcast.

The gossip protocol of the Lightning Network uses a staggered broadcast that
acts as a natural rate limiting mechanism to ensure that the network is
resistant to certain types of denial-of-service (DoS) attacks. In a staggered
broadcast, each node listens for gossip messages for a specified interval
(stagger interval) before broadcasting all messages to a subset of peers.
While listening, messages concerning the same channels are deduplicated by the
timestamp field provided in the messages. If two channel updates for the same
channel edge are seen, only the most recent update is kept in the broadcast
queue. The value chosen for the stagger interval has a big impact on the
convergence delay, since the higher it is the longer messages take to reach a
majority of nodes. The specification333https://github.com/lightning/bolts
recommends a $60$ second stagger interval.

#### Gossip Syncers.

The gossip_timestamp_filter message allows nodes to manage from which peers
they want to receive new gossip. Not sending the filter message is equivalent
to not requesting any gossip. By default, nodes only send filters to a subset
of their peers, which are called active gossip syncers, while all other peers
are passive gossip syncers. The number of active syncer connections each node
maintains has an impact on the convergence delay since it determines how well
nodes are connected. The more active syncer nodes choose the faster messages
will propagate.

#### Rate Limiting.

While the staggered broadcast already offers a form of rate limiting, nodes in
addition apply a second rate limit on a per-edge basis. Only a certain number
of updates from the same edge are allowed for each rate limiting interval.
Such policies exist to prevent nodes from spamming the network with channel
updates, but also to prevent I/O DoS attacks, since nodes write new channel
updates to disk. A third rate limiting applies to redundant channel updates
(only differing in the timestamp of the message), which are also considered as
keep alive updates. A node will broadcast keep alive updates to indicate that
its channels are still active and should not be pruned from other nodes’ views
of the network. To rate limit keep alive updates, nodes usually only allow
them in a defined frequency, but the details differ from implementation to
implementation.

#### Comparing Node Implementations

While the Lightning implementations generally follow the concepts just
discussed, the specific parameters used by these implementations can differ
quite a bit. In the following, we therefore discuss the relevant details of
the two most popular implementations of the Lightning Network protocol,
c-lightning and LND.

|  c-lightning |  LND
---|---|---
Staggered Broadcast |  60 second stagger interval. |  90 second stagger interval, batches are broadcast in 5 second intervals.
Gossip Syncers |  Five syncers, individual rotations every hour. |  Three syncers, one being rotated every 20 minutes.
Rate Limiting |  One channel update per day, burst up to 4. |  One channel update per minute, burst of up to 10.
Table 1: Comparison of c-lightning and LND with regard to the most influential
concepts on the convergence delay.

As also shown in Table 1, the behavior of c-lightning generally sticks to the
specification’s guidance, while LND differs from it significantly with a
stagger interval of $90$ seconds. When the timer expires, all seen messages
are split up into batches and broadcast to all relevant peers in $5$ second
intervals. The function for calculating the batch size from the total number
of messages $n$ to broadcast is the following:

$sb(n)=min\left(10,\frac{n\cdot 5s+90s-1}{90s}\right)$

The number of broadcast batches increases with the number of messages, but is
capped at $18$ in order to prevent the overlapping of stagger intervals. With
$5$ seconds between batches and a maximum of $18$ batches, the last message
may potentially be broadcast $17\cdot 5=85$ seconds after the stagger timer
expires. A plot of $sb(n)$ can be seen in Figure 1. Only if there are more
than $162$ messages seen per $90$-second stagger interval, all $18$ batches
will be filled. If the general rate of messages in the network is lower than
that, less batches will be used lowering the convergence delay.444The stagger
interval was increased in January 2019 from $30$ to $90$ seconds with the
reasoning to lower bandwidth usage by slowing the propagation of messages
[10]. In April 2019, the sub-batch broadcast was introduced with the reasoning
to eliminate bursty resource usage after the stagger timer expires [6]. We
could not find records of detailed discussion on how the exact parameter
values for these changes were chosen.

The rate limiting policies of these two node implementations do not play
together without friction. If a channel is updated once per minute, a
c-lightning node would disregard all updates after the fourth for up to one
hour, while a LND node would happily accept all updates. The c-lightning node
will not relay disregarded updates, which can cause the convergence delay for
these updates to increase. However, this is not an observable issue, since the
majority of nodes are running LND.

##  3 Gossip Traffic Analysis

In the following, we describe our methodology for measuring and analysing
gossip traffic in the Lightning Network.

###  3.1 Measuring the Convergence Delay

$0$$100$$200$$300$$400$$500$$600$$700$$800$$900$$1{,}000$$0$$10$$20$$30$$40$$50$$60$$70$Number
of messages to be broadcastNo. msgs/batchNo. batches Figure 1: LND batch
sizes.

050010001500Time in seconds0.000.250.500.751.00Share of converged nodes

Figure 2: Measured convergence delay.

Figure 3: LND’s broadcast batching and measured convergence delay.

In order to measure the convergence delay in the Lightning Network, we used
the python pyln-
proto555https://github.com/ElementsProject/lightning/tree/master/contrib/pyln-
proto package to connect to and communicate with nodes on the network. The
node addresses were extracted from a topology snapshot collected from an LND
node right before the start of the experiment (Oct. 30, 2021). We connected to
as many nodes as possible and chose all of them as our active gossip syncers.
We recorded all received messages including at which times
$\\{t_{1},\ldots,t_{n}\\}$ and from which node we got the message. The
recorded timestamps can then be used to estimate the convergence delay in the
network by looking at the difference between the first and last timestamp.
This estimation method assumes that the first timestamps in these lists
correspond to the time of initial broadcast and that all nodes have seen the
message after the last timestamp.

In total, we received $69,942$ unique gossip messages from $1,046$ nodes over
a time span of close to $10$ hours. To estimate the convergence delay, we used
all messages that were received at least from $500$ different nodes.

Figure 2 shows the share of nodes that have seen a message in relation to the
time since initial broadcast: the average time it takes for a node to see a
message is $359.9$ seconds, with $95\%$ of nodes seeing messages after $753$
seconds and $100\%$ of nodes seeing messages after $2,500$ seconds.

###  3.2 Dissecting Recorded Gossip

We then categorized the collected data and examined which share of gossip
messages are node announcements, channel announcements or channel updates. We
also analyzed the contents of all channel updates to understand when nodes
send updates and how they typically update channel policies.

0100002000030000Time in seconds0.000.250.500.751.00Share of all
messageschannel updatesnode announcementschannel announcements

Figure 4: Observed shares of update messages.

0100002000030000Time in seconds0.000.250.500.751.00Share of all updateskeep
aliveclosuresreopensdisruptivenon disruptivemisc

Figure 5: Channel updates cataloged by type.

Figure 6: Categorization of observed gossip messages.

As seen in Figure 4, the rate at which new messages arrive is more or less
constant. Of all messages we recorded, $5.13\%$ were node announcements,
$0.34\%$ were channel announcements and $94.53\%$ were channel updates. This
distribution matches our expectations, as channel announcements are directly
rate limited by the blockchain, node announcements only need to be broadcast
infrequently to modify network addresses or add new feature announcements, and
channel updates change channel policies, which happens regularly over the
course of a channel’s lifespan.

We categorized channel updates into six different categories:

  * •

_Keep-alive_ updates only differ in the timestamp field. These updates are
meant to tell the network that a channel is still active. They made up
$45.32\%$ of all recorded messages.

  * •

_Channel closure_ updates close a channel temporarily or permanently.
Temporary channel closures can happen if a peer goes offline due to network
issues, in which case the other peer will broadcast such an update to inform
the network not to route over the offline peer. These updates made up
$19.29\%$ of all recorded messages.

  * •

_Channel re-open_ updates open a channel that was previously closed. These
updates made up $18.66\%$ of all recorded messages.

  * •

_Disruptive_ updates change the channel policy in a way that could cause
payment failures, if the payment source does not know of the update. Channel
closures are excluded because we categorize them separately. Disruptive
updates made up $8.57\%$ of all recorded messages.

  * •

_Non-disruptive_ updates change the channel policy in a way that could cause a
payment source to over-pay on fees or use a higher lock time than needed.
These updates made up $7.22\%$ of all recorded messages.

  * •

_Misc._ updates are all other updates that we saw. For example, updates that
change the htlc_minimum_msat field fall into this category. These updates made
up $0.99\%$ of all recorded messages.

The observed amount of keep-alive updates is slightly concerning, as they make
up roughly $50\%$ of all seen updates. This amount of keep-alive updates
cannot be explained by nodes broadcasting them at a reasonable rate. In
theory, a keep-alive only has to be sent for channels that did not have an
update within $14$ days. Therefore, transmitting a keep-alive update every
$13$ days should be sufficient to prevent other nodes from pruning the
channel. Figure 7 shows the difference in the timestamp field between the
keep-alive and the previous update: we observe that for almost all of the
keep-alive updates the differences lie between $86,400$ and $88,200$ seconds,
which corresponds to exactly $1$ day and $1$ day plus $30$ minutes. We found
that LND nodes are responsible for these updates, because they check every
$30$ minutes if any of their channels had an update within the last day, and
will broadcast a keep-alive update otherwise. However, we were not able to
explain the large peaks seen in Figure 7 at the interval boundaries. Moreover,
we did not observe any keep-alive updates with a smaller difference, because
LND nodes do not relay such updates and therefore they do not propagate
through the network.

Looking at the timestamp differences for all updates in our channel re-open
category (cf. Figure 8), we see that most channels edges that get re-opened
were disabled for short periods of time. For example, $60\%$ of edges were
closed for less than $22$ minutes. This is likely caused by network issues
that lead nodes to temporarily disable edges.

860008700088000Timestamp
delta$\displaystyle{10^{1}}$$\displaystyle{10^{3}}$No. keep-alives

Figure 7: Time since last keep-alive.

025005000750010000Timestamp delta0.000.250.500.751.00Share of temporary
closures

Figure 8: Cumulative channel closure durations.

Figure 9: Timestamp differences of keep-alive and channel closure updates.

##  4 Simulation Study

In the following, we discuss the conducted model-based simulation study on the
routing convergence delay in the Lightning Network.

###  4.1 Simulation Model

The behavior of real-world peer-to-peer networks is influenced by many
different variables. Nodes participating in such networks can be diverse in
geographical location, bandwidth restrictions, software implementation,
software version or configuration, and simulating all different permutations
is simply not feasible. In the context of investigating the gossip protocol of
the Lightning Network, we restrict the scope of our simulation by making the
following assumptions: if two nodes are connected through a channel, they have
a constant TCP connection. The snapshot we use to bootstrap our simulation
contains all nodes and all channels that exist in the network. We ignore any
non-listening nodes that were not announced to the network, as well as private
channels. Our simulation propagates node and channel announcements, but does
not actually add them to the simulated topology. Only channel updates are
applied to the simulated topology. The gossip algorithm is the main influence
on the convergence delay, and we do not simulate other potential influences
such as an overhead caused by cryptographic functions. Payments are atomic and
instant. All nodes in each simulation follow the same gossip protocol. All
nodes have the same bandwidth of $1\,MB/s$ in up- and download.

We chose to implement our discrete-event
simulator666https://github.com/dergoegge/lnconv-paper-sim in the Go
programming language and bootstrap the simulation from historical topology
snapshots that were extracted from an LND node with a fully synced network
graph. These snapshots contain a list of nodes and channels which we use to
build our simulation network. The snapshot we use for all simulations contains
$17,332$ nodes, $77,921$ channels and was taken on Oct. 30, 2021. In order to
simulate a realistic amount of traffic, we replay gossip messages that we
recorded in the real network. This works well as most gossip messages can be
traced back to an origin node in the network as long the snapshot we use to
bootstrap the simulation is not much older than the start of the recorded
period. For messages for which we could not find an origin in our snapshot we
choose a random origin. Bandwidth is modeled by each node having an incoming
byte counter that gets incremented with every message that is being downloaded
and decremented with every message that is fully received. The arrival time of
a new message is calculated based on a fixed bandwidth, the number of incoming
bytes and a fixed latency overhead of $100\,ms$.

###  4.2 Simulation Results

In this section, we present the data collected on an LND simulation scenario
in which we replayed the first hour of the gossip we recorded in Section 3,
consisting of $7,217$ network messages. We simulate $100,000$ payment attempts
which were uniformly distributed over the hour. Payment sources and
destinations are chosen randomly and the payment amount is set to $1\,sat$ in
order to reduce interference by failures originating from anything else than
outdated routing information.

#### Bandwidth.

The simulated network transferred a total of $40.77\,GB$ to deliver the
$7,217$ messages to all nodes. The theoretical lower bound for bandwidth usage
$B_{min}$ is the product of the number of all nodes, the total number of
messages and the average message size, i.e.,

$B_{min}=num\\_nodes\cdot num\\_messages\cdot avg\\_message\\_size$

Assuming all messages are channel updates with a size of $128\,bytes$,
$B_{min}=16.01\,GB$. We therefore found that the network uses $2.55$ times the
theoretically needed bandwidth $B_{min}$.

#### Redundancy.

$6.29\%$ of messages will be seen only once, $33.28\%$ will be seen twice,
$59.93\%$ will be seen three, and $0.5\%$ will be seen four times. All nodes
have $3$ active gossip syncers which explains why most messages are seen three
times or less. A message is only seen $4$ times if it is received as part of
the initial broadcast, which goes out to all connected peers. On average each
message is seen $2.55$ times. Note that this is the same factor as the one
from our bandwidth calculations: every message that is received more than once
is exactly the overhead to a perfect broadcast in which every message is
received only once by each node.

#### Convergence Delay.

We measure the convergence delay by recording how long it takes a message to
be seen for the first time by every node. This is very similar to the
measurements conducted in Section 3, but within a simulation we get much more
accurate data since we have an omniscient view. Figure 10 compares the
convergence delay we recorded in the real network to the one we observed in
the simulation. In our simulation, the average time it took for a node to see
a message is $291.21$ seconds, with $95\%$ of nodes seeing messages after
$510$ seconds and $100\%$ of nodes seeing messages after $1,075$ seconds. The
convergence delay seen in the simulation slightly differs from the delay
measured in the real network with messages in the simulation propagating
faster after initially being broadcast and messages taking longer to reach all
nodes in the real network. From $20\%$ to $80\%$ of nodes having seen the
messages it takes $240$ seconds in the simulation while in took $265$ seconds
in the real network.

As mentioned previously, roughly $50\%$ of the messages that we recorded are
keep-alive updates. We ran a simulation without the keep-alive updates (lnd-
no-keepalives) and found that the convergence delay was significantly reduced,
with $95\%$ of nodes converging after $374.19$ instead of $510$ seconds.

010002000Time in seconds0.000.250.500.751.00Share of converged nodeslndlnd-no-
keepalivesreal

Figure 10: Measured vs. simulated conv. delay.

050100150Wait time in seconds0.000.250.500.751.00Share of messageslndlnd-no-
keepalives

Figure 11: Queue waiting times.

Figure 12: Convergence delay and broadcast queue waiting times in a simulated
network consisting only of LND nodes.

#### Waiting Times.

Looking at the broadcast queue waiting times of messages we observed that
waiting times and hence the convergence delay become larger the more messages
are propagating through the network. This is explained by the sub-batch
trickling approach that LND has chosen which makes waiting times dynamic to a
certain degree. The growth of waiting times is bounded by the maximum number
of sub-batches that LND will send. A plot of the waiting times can be seen in
Figure 11. The minimum waiting time is $0$ seconds and the maximum is $175$
seconds. A message will wait $175$ seconds, if it arrives at the beginning of
the $90$ second stagger interval and gets broadcast in the last sub-batch,
$85$ seconds after the stagger timer ticks.

#### Failed Payment Attempts.

Out of the $100,000$ tried payment attempts, $42\%$ were successful and $58\%$
failed. $0.114\%$ of attempts failed because the payment source did not have a
recent update for one of the channel edges in the payment route.

As we have seen, the staggered broadcast is quite inefficient in its bandwidth
usage with messages being seen $2.55$ times on average by the same node and
$95\%$ of nodes converging after $510$ seconds. The share of unconverged
payment attempts ($0.114\%$) does not seem that problematic but it could be
argued that in absolute numbers the total number of unconverged payment
attempts can still be large. The research by [14] suggests that this rate is
actually higher at around $1.2\%$ [14]. Exploring alternative gossip
algorithms seems worthwhile based on these results.

###  4.3 Evaluating Alternative Gossip Strategies

In this section, we layout ideas for potential alternative gossip algorithms
that the Lightning Network could employ. We use our simulator to compare the
different algorithms and evaluate the feasibility of these alternatives being
used in the real network based on bandwidth usage, convergence delays, and
their impact on payment attempts. We compare the following alternative
strategies: flooding, a structured broadcast using a global spanning tree,
inventory based gossip, parameter variations of the current protocol, as well
as set reconciliation using Minisketch [4].

We compare all alternative strategies to each other and the simulation data
from Section 4.2. We specifically compare bandwidth usage, convergence times
and the number of unconverged payment attempts and simulate each algorithm
using the same snapshot and replaying the same messages as before ($17,332$
nodes, $77,921$ channels, $7,217$ messages over $1$ hour, $100,000$ payment
attempts). The convergence delays and bandwidth usage for all the different
algorithms are listed in Table 2.

Algorithm | Conv. Delay | Bandwidth Usage | Payment attempts
---|---|---|---
lnd | 509.75s | 40.47 GB | 602
lnd-t1s | 312.65s | 39.36 GB | 349
lnd-sb100 | 266.54s | 38.9 GB | 316
lnd-inv | 509.46s | 19.26 GB | 592
lnd-inv-t1s | 313.45s | 19.41 GB | 394
lnd-inv-sb100 | 267.93s | 20.23 GB | 274
c-lightning | 101.29s | 59.52 GB | 171
c-lightning-inv | 103.2s | 26.36 GB | 161
spanning (BFS) | 1.11s | 15.7 GB | 5
flooding-4 | 2.72s | 50.7 GB | 3
flooding-8 | 1.72s | 94.7 GB | 1
flooding-16 | 1.16s | 180.92 GB | 2
flooding-32 | 0.82s | 353.21 GB | 4
minisketch-4 | 19.25s | 19.15 GB | 33
minisketch-8 | 20.24s | 19.84 GB | 43
minisketch-16 | 20.7s | 21.45 GB | 43
minisketch-32 | 20.54s | 21.46 GB | 30
Table 2: Convergence Delays (95%), bandwidth usage, and unconverged payment
attempts.

As expected, flooding has the highest bandwidth usage with low convergence
delays and the spanning tree algorithm (global tree constructed using breadth-
first search) has the lowest bandwidth usage and the lowest convergence delay.
With flooding, we see the bandwidth consumption scaling proportionally with
increased connectivity (number of active syncer connections). The convergence
delay is naturally smaller with increased connectivity.

LND’s choice of staggered broadcast parameters results in a roughly five times
increase in the convergence delay compared to c-lightning. While LND’s
approach leads to a larger convergence delay it also reduces bandwidth usage
by about $33\%$. We simulated two variations of LND’s algorithm, one with a
minimum sub-batch size of $100$ instead of $10$ messages (lnd-sb100), and one
with a sub-batch delay of one instead of five seconds (lnd-t1s). Both of these
parameter changes lead to faster messages broadcast after the stagger timer
expires leading to an decrease in convergence delay of $39\%$ for lnd-t1s and
$48\%$ for lnd-sb100.

Inventory-based protocols announce a shortened version of the full message to
give the receiver the chance to only request the full message once. For gossip
messages in the lightning network, the size of an inventory message can be
$64$ bits [12]. We see that inventory based protocols reduce bandwidth usage
significantly when compared to their regular variants. With lnd-inv requiring
$52.4\%$ less bandwidth than lnd and c-lightning-inv requiring $55.7\%$ less
bandwidth than c-lightning. The convergence delays however are unaffected by
the decrease in bandwidth usage. Usually it would be expected that latency
increases with an inventory-based gossip protocol but the extra round trip has
no impact here, given that the stagger interval is multiples larger than the
round trip time.

In Figure 13(a), we compare the bandwidth usage of flooding and set
reconciliation, in relation to the connections made by each node. Our set
reconciliation algorithm is based on the Erlay protocol that was proposed for
the transaction relay in the Bitcoin network [9]. In our protocol, we
implemented no fan-out flooding and hence all messages are exchanged via set
reconciliation. We observe that bandwidth usage does not increase
proportionally with the number of connections made for the set reconciliation
protocol. Instead, the bandwidth usage scales with the rate of messages in the
network, just like the Erlay protocol.

481632Number of active gossip connections0100200300Bandwidth in
GBfloodingminisketch

(a) Bandwidth usage vs. increased connectivity.

0200400Convergence delay in seconds0200400600Payment attempts

(b) Unconverged payment attempts vs. convergence delay.

Figure 13: Simulated parameter interdependencies.

We observe that the number of unconverged payment attempts is highly
correlated with the convergence delay. We do not distinguish between failed
payment attempts and attempts that arise due to opportunity costs, as the
combined number of these attempts is sufficient in evaluating different
protocols. As seen in Figure 13(b), based on our limited data set of the
different algorithms, the relationship between the convergence delay and the
number of unconverged payment attempts is linear. The lower the convergence
delay, the fewer unconverged payment attempts can be observed.

##  5 Discussion

The staggered broadcast protocols rate-limit the propagation of channel
updates by de-duplicating updates for the same channel with in the stagger
interval. This means that a node will only forward one channel update for the
same channel edge in every stagger interval. No potentially important updates
are discarded, since the newest update that was seen will always be forwarded.
This form of rate limiting prevents the network from witnessing rapid changes
in channel policies, while still propagating the newest updates. The
propagation of the newest updates is significantly delayed as we have shown
through the simulations and measured in Section 3. We argue that this form of
rate limiting implicitly discourages frequent channel updates at the cost of
delivering the newest updates with large delays. Explicitly discouraging
frequent updates through strict per-channel rate limiting as discussed in
Section 3 could be well suited for some of our alternative protocols that aim
to deliver messages faster. A strict rate limit would discard newer updates
that violate the rate limit, so honest nodes should never broadcast messages
for the same channel in violation of the limit.

LND’s choice of parameters for its staggered broadcast is a bit of a mystery,
since there is no public record on how the exact values were chosen. However,
broadcasting messages in sub-batches instead of one large batch after the
stagger timer expires is a good choice to reduce bursty resource usage. We
would however recommend that the LND developers revisit their choice of
parameters for the staggered broadcast, because reducing bandwidth usage by
$33\%$ while increasing the convergence delay by a factor of five does not
seem like a reasonable trade-off (compared to parameters mentioned in the
specification). As we have shown through the simulations, adjusting the
parameters can have a big impact on the convergence delay. Adjusting these
parameters would be the least complex software change to address the large
convergence delay, while maintaining the rate limiting properties of the
staggered broadcast.

Introducing an inventory-based gossip protocol reduces the bandwidth usage
without changing the convergence delay at all. In combination with adjusting
the parameters of the staggered broadcast the convergence delay could also be
lowered. An inventory-based gossip protocol could remain a staggered broadcast
and thereby maintain its rate limiting effect without introducing strict rate
limiting. The added software complexity of an inventory-based gossip is fairly
low and there already exists a proposal on the specification [5].

Increasing the number of connections that nodes make to gossip (connectivity)
can lead to better reliability in adversarial environments. With low
connectivity an attacker has to control less connections to be able to censor
information from reaching a victim. For some protocols an increase in
connectivity can also lead to a reduction in convergence times because the
spread factor is higher.

Even though the spanning tree protocol seems great based on the results, it is
not a great fit for the real network. As mentioned earlier, the protocol makes
the assumption that all nodes agree on the exact same static spanning tree,
which would not trivially work in the real network. A single tree is also not
going work for security and reliability reasons. If one node in the tree goes
offline, none of the nodes in its sub-tree would receive new messages.
Introducing multiple trees to gain redundancy would increase the bandwidth
usage which makes using a spanning tree less desirable in the first place. A
spanning tree protocol with multiple trees would probably turnout to be
similar in efficiency to a flooding protocol.

A flooding protocol comes with a small convergence delay of one to two seconds
but increases bandwidth usage above that of the current algorithm (lnd).
Bandwidth usage increases linearly with increased connectivity. If an increase
in connectivity is wanted then flooding would not be suitable. In fact all
protocols besides set reconciliation lead to a proportional increase in
bandwidth with increased connectivity.

Compared to the other protocols, set reconciliation has a small convergence
delay and low bandwidth usage. Increasing connectivity is also possible
without increasing bandwidth usage, as the bandwidth usage scales with the
rate of messages seen in the network. Introducing set reconciliation comes
with much greater software complexity than any of the other protocols.
Multiple new message types would need to be introduced and the Minisketch
library adds a dependency.

Decreasing the number of unconverged payment attempts can also be done without
changing the gossip protocol. Nodes could temporarily allow payments that use
old channel policies, after broadcasting a new policy. This would work well
for fee or lock time adjustments. In the end this depends on the channel
owners preferences on whether or not they want updates to immediately take
effect.

##  6 Related Work

The explosive growth of the internet in its topological complexity as well as
user count has led to a lot of research on the convergence delay for routing
protocols, such as the Border Gateway Protocol (BGP). Large convergence delays
in BGP can cause routing failures similar to how large convergence delays in
the Lightning Network can cause payment failures. [7] showed through a
$2$-year study that the convergence delay of BGP was much higher than
previously expected. By injecting routing events to simulate failures and
collecting data on these events, the authors were able to figure out the
convergence delay for different types of events. Convergence delays were
primarily caused by different router vendor’s implementations of the BGP
specification with regard to the choice of timer values [7]. [2] suggested
ways on how to lower the BGP convergence delay which included adjusting timer
values of implementations and centralizing control of networks [2]. [1]
investigated slow BGP table transfers which increase the convergence delay.
They found that gaps, in which both sender and receiver are idle, during table
transfers are a common occurrence caused by timer driven implementations, with
different vendors choosing different timer values [1]. Similar to this BGP
research, we found that a big part of the convergence delay in the Lightning
Network is driven by the parameter choices for the staggered broadcast of
different implementations.

[3] measured block propagation times in the Bitcoin network and verified that
the propagation time is the primary cause for forks in the blockchain. They
measured the propagation times by connecting to a large number of nodes and
listening for block announcements. With this setup they recorded when blocks
where seen and from which nodes. From this data they are able to estimate how
long it takes blocks to traverse the network after the initial broadcast [3].
Our work is methodically similar, since we also measure the convergence delay
in the Lightning Network by connecting to many nodes in the network and record
arrival times of messages.

[9] proposed Erlay, a protocol for transaction relay in the Bitcoin network
that makes use of efficient set reconciliation in combination with flooding.
It aims to lower the bandwidth requirements needed for transaction relay with
the trade-off of higher latency. The authors evaluated the bandwidth and
latency trade-off of Erlay and compared it to the current flood-only protocol
[9]. We used the Erlay protocol as inspiration for simulating a similar
protocol in the Lightning Network and specifically used their prior research
when choosing the parameters for our protocol.

[14] studied availability and reliability properties of the Lightning Network.
They tested the network’s ability to route payments of different amounts and
created a taxonomy of permanent and temporary failures that occurred. They
looked at the availability of nodes in the network and measured how much churn
(nodes joining and leaving the network) exists [14]. This work listed payment
attempt failure types that were caused by outdated routing information, by
probing the network with real payments. We only simulated payments to
investigate these failure types.

##  7 Conclusion

In this work, we analyzed the convergence delay in the Lightning Network,
described the effect it can have on payments, and evaluated alternative gossip
protocols that could reduce the delay. We found the network to have a
significant convergence delay, with $95\%$ of nodes only having converged
after roughly $10$ minutes. A majority of the gossip traffic consists of
redundant channel updates (keep-alive messages), which further increase the
delay given the parameter choices of the LND implementation. Our simulations
show that payment attempt failures due to unconverged routing information are
rare (occuring in $\ll 1\%$ of payment attempts). However, the convergence
delay may still be lowered while also reducing the bandwidth usage, either by
switching to alternative gossip algorithms or adjusting the parameters of the
current protocol. By switching to a set reconciliation based protocol, the
connectivity of the network could be increased with nodes receiving gossip
updates from more peers without suffering from significant increases in
bandwidth.

## References

  * [1] Zied Ben Houidi, Mickael Meulle and Renata Teixeira  “Understanding Slow BGP Routing Table Transfers”  In _Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement_ , IMC ’09  Chicago, Illinois, USA: Association for Computing Machinery, 2009, pp. 350–355  DOI: 10.1145/1644893.1644935
  * [2] R.. da Silva and E. Souza Mota  “A Survey on Approaches to Reduce BGP Interdomain Routing Convergence Delay on the Internet”  In _IEEE Communications Surveys Tutorials_ 19.4, 2017, pp. 2949–2984  DOI: 10.1109/COMST.2017.2722380
  * [3] Christian Decker and Roger Wattenhofer  “Information propagation in the bitcoin network”  In _P2P ’13: Proceedings of the 13th IEEE International Conference on Peer-to-Peer Computing_ , 2013, pp. 1–10
  * [4] Minisketch Developers  “Minisketch: a library for BCH-based set reconciliation” [accessed on 2021-12-5]  URL: https://github.com/sipa/minisketch/blob/89629eb2c7e262b39ba489b93b111760baded4b3/README.md
  * [5] Fabrice Drouin  “[WIP] BOLT 7: Inventory-based gossip” [accessed on 2021-12-5]  URL: https://github.com/lightning/bolts/pull/584
  * [6] johng  “Broadcast gossip announcements in sub batches” [accessed on 2021-12-5]  URL: https://github.com/lightningnetwork/lnd/pull/2985
  * [7] Craig Labovitz et al.  “Delayed Internet Routing Convergence”  In _SIGCOMM Comput. Commun. Rev._ 30.4 New York, NY, USA: Association for Computing Machinery, 2000, pp. 175–187  DOI: 10.1145/347057.347428
  * [8] Satoshi Nakamoto  “Bitcoin: A peer-to-peer electronic cash system”, 2008
  * [9] Gleb Naumenko et al.  “Erlay: Efficient Transaction Relay for Bitcoin”  In _CCS ’19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ , 2019, pp. 817–831
  * [10] Olaoluwa Osuntokun  “config: increase default trickle delay from 30s to 1m30s” [accessed on 2021-12-5]  URL: https://github.com/lightningnetwork/lnd/pull/2538
  * [11] Joseph Poon and Thaddeus Dryja  “The bitcoin lightning network: Scalable off-chain instant payments”, 2016
  * [12] Rusty Russell  “[Lightning-dev] Minisketch and lightning gossip” [accessed on 2021-12-5]  URL: https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-December/001741.html
  * [13] Yonatan Sompolinsky and Aviv Zohar  “Accelerating Bitcoin’s Transaction Processing. Fast Money Grows on Trees, Not Chains”  In _Cryptology ePrint Archive, Report 2013/881_ , 2013
  * [14] Finnegan Waugh and Ralph Holz  “An empirical study of availability and reliability properties of the Bitcoin Lightning Network”  In _CoRR_ abs/2006.14358, 2020  arXiv: https://arxiv.org/abs/2006.14358