Ticket to Ride: Locally Steered Source Routing for the Lightning Network

Our ticket framework comprises two algorithms: Issue, executed by an originator (typically the sender), and Open, executed by each intermediate node. The framework relies on two standard primitives:

• $\mathrm{■}$

  A hash function $H:{\{0,1\}}^{\ast }\to {\{0,1\}}^{\kappa }$, modelled as a random oracle and used solely as a source of pseudorandom bits.

• $\mathrm{■}$

  An approximate-membership query structure (AMQ) that supports three polynomial time operations:

  • –

    Create$(m,\alpha )$: initializes an empty filter sized for up to $m$ insertions with false-positive probability at most $\alpha$;

  • –

    Insert$(𝖲,e)$: adds element $e$ to filter $𝖲$;

  • –

    Query$(𝖲,e)$: returns present with probability $\le \alpha$ if $e\notin 𝖲$, and never returns absent for an inserted element.

For each node $u$ controlling an authorized channel, the originator derives a unique per-hop secret using elliptic-curve Diffie–Hellman (ECDH). Specifically, the originator selects an ephemeral public key ${\mathrm{PK}}_{\mathrm{𝖾𝗉}}$, while each node $u$ has a long-term public key ${\mathrm{PK}}_u$ published through the network gossip. The shared per-hop secret is computed as:

where DH denotes an ECDH key exchange, followed by a standard key derivation function (e.g., HKDF) to yield a uniform $\kappa$-bit key. Because the sender knows the ephemeral secret and node $u$ holds the private key corresponding to ${\mathrm{PK}}_u$, only these two parties can compute the shared secret $s_u$. Consequently, any ticket entries derived from $s_u$ appear indistinguishable from random to all other nodes. This per-hop shared-secret derivation mirrors the mechanism already employed by LN’s onion-routing protocol [10].

The basic ticket of Section 3.1 stores all authorized channels in a single AMQ. Improving its accuracy normally means lowering the false-positive rate, which in turn expands the filter. TwinTicket takes an alternative path: it embeds two AMQs – one that includes authorized channels and a second that explicitly excludes those few channels misclassified by the first. In other words, TwinTicket contains

• $\mathrm{■}$

  an inclusion filter ${𝖲}^{\mathrm{𝗂𝗇𝖼}}$, which holds every authorized edge $(u,v)\in {ℒ}_{s,d}$; and

• $\mathrm{■}$

  an exclusion filter ${𝖲}^{\mathrm{𝖾𝗑𝖼}}$, which holds each false positive discovered when the sender queries ${𝖲}^{\mathrm{𝗂𝗇𝖼}}$ locally. A channel $(u,v)$ is inserted in encoded form $H\left(v\parallel s_u\right)$, identical to the inclusion encoding.

The size of a ticket – i.e., the bit length of the AMQ structure that travels with each payment – depends on three parameters:

1. (i)

   the particular AMQ design employed;

2. (ii)

   the target false-positive bound $\alpha$;

3. (iii)

   the number of elements inserted, $m$.

The literature offers a rich family of AMQ designs, each with its own space–functionality trade-off. Classic examples include the Bloom filter [4]; the counting Bloom filter, which supports deletions [7]; the Cuckoo filter [6]; and the Quotient filter [2]. Golomb–Rice coded sets (GCS) – used in Bitcoin’s compact block filters – achieve near-optimal compression for static sets by entropy-coding sorted hashes [15]. More recent proposals, such as the Learned Bloom filter [9], trade a small probability of false negatives for additional space savings. For fixed set size $m$ and target false-positive rate $\alpha$, structures like the Cuckoo filter, quotient filter, or GCS can be more compact than the original Bloom filter but may incur higher insertion cost, require sorted input, or demand more intricate parameter tuning.

For example, the classic Bloom filter – introduced by Bloom in 1970 – supports only two operations, Insert and Query, and provides no deletion primitive. With $m$ insertions and target false-positive probability $\alpha$, its information-theoretically optimal length is

obtained with $k=\lceil ({\mathrm{\ell }}_{\text{Bloom}}/m)\ln 2\rceil$ independent hash functions [4].

A second widely deployed AMQ is the Golomb–Rice Coded Set used in Bitcoin block filters (BIP 158) [15]. A GCS stores the sorted hash values and compresses their gaps with Golomb–Rice coding, again supporting Insert and Query but requiring no random oracle. Choosing the Golomb–Rice parameter $P=\lceil {\log }_2(1/\alpha )\rceil$ yields a false-positive rate at most $\alpha$ and an expected length

For the practical false–positive window $\alpha \in [2^{-7},{\mathrm{\hspace{0.17em}2}}^{-15}]$ ticket overhead remains modest. In a GCS the expected length per element is $P+1$ bits, where $P=\lceil {\log }_2(1/\alpha )\rceil$. Thus each authorized channel costs $8$ bits when $\alpha =2^{-7}$ and $16$ bits when $\alpha =2^{-15}$ – only $1$–$2$ bytes apiece. By contrast, a Bloom filter needs ${\mathrm{\ell }}_{\text{Bloom}}\approx 1.44{\log }_2(1/\alpha )$ bits per element: about $10$ bits ($\approx 1.3$ B) at $\alpha =2^{-7}$ and $22$ bits ($\approx 2.7$ B) at $\alpha =2^{-15}$. The dominant contributor to ticket length is therefore the element count $m$: in the practical range $\alpha \in [2^{-15},2^{-7}]$ each additional authorized channel adds between $c=1$ and $c=2$ bytes.

If the ticket contains only the channels of a single source-to-destination path, our framework reduces to the single-route source routing that all major Lightning implementations already employ. Adding more channels, however, gives intermediate nodes additional “steering” options and thus lowers the probability that an in-flight payment stalls on an exhausted link.

A natural choice is to populate the ticket with the union of edges that lie on any shortest path between the sender and the receiver. Although many shortest paths can coexist, the ticket remains compact: on a recent public Lightning snapshot, authorizing about $126$ channels suffices for $90\%$ of randomly chosen source–destination pairs, and $611$ channels cover $99\%$ of such pairs.

Empirical measurements show that the public Lightning graph is remarkably stable: the average channel lifetime is nearly two hundred of days [21]. Because these modest topology updates propagate through the standard gossip protocol, a well-provisioned node can maintain an up-to-date view at virtually no extra cost. Building a ticket therefore needs only this topology snapshot; rapidly fluctuating balances are irrelevant.

Ultra-constrained senders (IoT tags, single-board wallets) cannot hold the full graph. We therefore combine our ticket mechanism with trampoline payments and slice the route into three segment tickets:

1. (a)

   ${𝝉}_{𝑺\mathbf{\to }{𝑻}_{\mathrm{𝟏}}}$ (sender-issued) covers the first few hops from the sender $S$ to the entry trampoline $T_1$ and is keyed with an ephemeral ${\mathrm{PK}}_{\mathrm{𝖾𝗉}}^{(1)}$ chosen by $S$.

2. (b)

   ${𝝉}_{{𝑻}_{\mathrm{𝟏}}\mathbf{\to }{𝑻}_{𝒌}}$ (macro ticket, sender-issued) encodes the ordered list of trampoline IDs $T_2,\mathrm{\dots },T_k$, where $T_k$ is supplied by the receiver (see below). Each trampoline $T_i$ reads the next ID, computes its own micro-path to $T_{i+1}$, and attaches a fresh sub-ticket.

3. (c)

   ${𝝉}_{{𝑻}_{𝒌}\mathbf{\to }𝑹}$ (receiver-issued) steers the last one or two hops from $T_k$ to the receiver $R$, optionally biasing the route toward $R$’s best-funded inbound channel. It is keyed with a second ephemeral ${\mathrm{PK}}_{\mathrm{𝖾𝗉}}^{(2)}$ chosen by $R$.

This approach brings the following advantages:

• $\mathrm{■}$

  Compactness. The sender and receiver tickets span only a small number of hops (typically one or two) and the macro ticket is merely two or three compressed pubkeys ( B). Total header overhead, therefore, stays well under one kilobyte.

• $\mathrm{■}$

  Balanced computation. Lightweight senders route only to $T_1$; each trampoline solves a local micro-routing instance; only trampolines need the global graph.

• $\mathrm{■}$

  Privacy. Every ticket is keyed with a fresh Diffie–Hellman secret for each hop, so an intermediate node learns only whether its outgoing edges are permitted. All other tags look uniformly random, achieving the same incident-edge privacy as the original T2R.

• $\mathrm{■}$

  Fine-grained channel control. When constructing the final segment of the ticket, the receiver can privilege high-liquidity inbound channels or blacklist unreliable ones. Because this choice is encoded locally in the ticket and masked by the per-hop key, neither the sender nor any trampoline node learns which channels were favored.

• $\mathrm{■}$

  Minimal invoice overhead. When $R$ responds to an invoice_request (BOLT #12) or encodes a BOLT #11 invoice, it appends the triple $(T_k,{\mathrm{PK}}_{\mathrm{𝖾𝗉}}^{(2)},{\tau }_{T_k\to R})$. The extra payload is $\le 100$ bytes for the ticket plus 33 bytes for the key – well below the 1 kB capacity of a level-10 QR code – so invoice usability is unchanged.

With this three-ticket trampoline design, even kilobyte-scale devices can therefore utilize locally steered, privacy-preserving routing without storing the complete Lightning topology.

When an intermediate node $u$ forwards a payment over its channel to peer $v$, it engages in the standard Lightning commitment handshake. The procedure consists of two full-duplex rounds:

1. (1)

   $u$ sends an update_add_htlc (carrying the onion payload) immediately followed by commitment_signed.

2. (2)

   After validating the update, $v$ replies with commitment_signed and revoke_and_ack, completing the commit–reveal exchange.

The ticket is piggy-backed on the first update_add_htlc; no extra round trips are introduced, and only a few hundred bytes are appended to a frame that already averages $\sim$1500 bytes. Importantly, $v$ need not wait for the entire ticket to arrive before it can respond: the Lightning spec allows a node to send its commitment_signed as soon as the new Hashed Timelock Contracts (HTLC) has been parsed and validated, while the remaining payload bytes stream in.

SpeedyMurmurs can split a payment into partial payments, and send each partial payment along a different landmark–embedding tree, explicitly to hide the total value from every individual relay [17]. Achieving this goal requires the protocol to maintain several spanning trees and to send bookkeeping beacons whenever channels appear, disappear, or exhaust liquidity.

Our locally steered source routing realizes the same value privacy at virtually no extra cost. The sender simply issues as many tickets as there are partial payments – each keyed with its own per–hop secret – and launches the sub-payments concurrently. No additional control traffic is needed, and ticket construction remains fully local.

In addition, because the sender controls each ticket’s edge set, it can impose explicit path separations: for two partial payments, the sender may generate disjoint channel sets whenever the topology allows, thus guaranteeing that no single relay observes every share. SpeedyMurmurs cannot enforce such disjointness even when multiple landmark-embedding tree is used.

Our goal is to measure how effectively each algorithm discovers a route when one truly exists under the current liquidity snapshot. Accordingly, every data point in a batch of 50 000 payments is generated as follows.

1. 1.

   Endpoint sampling. Pick source $s$ and destination $d$ uniformly at random from the pruned graph ($s\ne d$).

2. 2.

   Amount selection. Draw a payment value of $A$ according to the scenario:

   • $\mathrm{■}$

     One setting of our simulation picks a uniformly random amount between intervals $\{{10}^0$–${10}^2,{10}^2$–${10}^3,{10}^3$–${10}^4,{10}^4$–${10}^5,{10}^5$–${10}^6\}$ satoshis for each payment.

   • $\mathrm{■}$

     All other settings pick a random amount $A$ between ${10}^2$–${10}^3$ satoshis. We chose this interval for the amount of the payment because both algorithms have low differences regarding success rate using this interval, which enables us to examine how other behaviors of the network affect them.

3. 3.

   Feasibility of the payment. Before routing, we verify that some optimal path can carry $(s,d,A)$ under the current liquidity and each channel’s HTLC policy:

   • $\mathrm{■}$

     Every announcement advertises htlc_minimum_msat and htlc_maximum_msat. A hop may forward only if $\text{htlc\_min}\le A\le \text{htlc\_max}$.

   • $\mathrm{■}$

     A directed edge $(u\to v)$ must also have$balance(u\to v)\ge A$ at this moment.

   • $\mathrm{■}$

     Every channel on the optimal path must be active (not flagged as disabled).

   We run a shortest-path search that enforces all of the above constraints. The source and destination for which no feasible path exists are discarded and resampled, ensuring every payment is routable in principle, so any failure reflects routing performance, not an impossible payment.

4. 4.

   Algorithm trials. Two independent copies of the network are made – one for T2R and one for SpeedyMurmurs. Each algorithm attempts to route $(s,d,A)$ once on its private copy:

   1. (a)

      If the attempt succeeds, the simulator decreases the directional balances along the path and increases the reverse directions, simulating an immediate settle.

   2. (b)

      If it fails, no balances change.

   Because the two runs start from identical liquidity and evolve independently, their success probabilities can be compared without any interference.

5. 5.

   Ticket generation. For every feasible request we enumerate all $s\to d$ paths that satisfy the public HTLC policy at every hop (${\text{htlc\_min}}_{u\to v}\le A\le {\text{htlc\_max}}_{u\to v}$), and the advertised channel capacity is at least the payment amount $A$. Every channel–direction that appears on at least one such path is inserted into the ticket. To ensure that any residual failure arises from the algorithm rather than ticket collisions, we instantiate the filter with a near-zero false-positive rate. This setting makes the probability that an unusable edge is authorized negligible. We examine the false-positive rate on success ratio later in the simulation.

6. 6.

   Forwarding behavior. Once a feasible request $(s,d,A)$ is admitted, each algorithm is invoked exactly once; a failure at any hop marks the entire payment as unsuccessful – no sender-side retry or multipath splitting is performed. Inside the network the two schemes behave differently:

   • $\mathrm{■}$

     T2R. Upon receiving the payment an intermediary node chooses one of its outgoing channels uniformly at random. If that channel both (i) meets the HTLC amount/balance constraints and (ii) appears in the ticket, the intermediary node forwards the HTLC along it. Otherwise the node samples another neighbor at random – without replacement – and repeats the test until either a suitable channel is found or all neighbors have been exhausted. If no channel passes the test the payment fails immediately.

   • $\mathrm{■}$

     SpeedyMurmurs. Each intermediary follows the greedy rule (as explained in their paper) of the landmark tree: forward to the unique neighbor whose tree distance to the destination is strictly smaller than its own.

This procedure isolates the algorithms’ ability to find a viable route, not their capacity to judge when no route exists; it also keeps the liquidity landscape dynamic, as successful payments progressively update balances – reflecting real Lightning traffic.

From each batch of $n=\mathrm{50\hspace{0.17em}000}$ payment attempts we extract two quantities to compare both algorithms.

1. 1.

   Success probability. For a batch of $n$ independent payment attempts let $𝒮\subseteq \{1,\mathrm{\dots },n\}$ be the index set of payments that are completed successfully. The empirical success rate is

   $$P_{\text{success}}=\frac{|𝒮|}{n}=\frac{\mathrm{\#}\text{successful payments}}{n}.$$

2. 2.

   Average hop count. Denote by $h_i$ the hop length of the realized path for a successful payment $i\in 𝒮$. If $m=|𝒮|$ is the number of successes, the sample mean hop count is:

   $$\overline{h}=\frac{1}{m}\sum _{i\in 𝒮}{h}_i.$$

Figures 1, 2 demonstrates the behavior of the T2R and the single-tree implementation of SpeedyMurmurs across four axes: payment amount (a), different initial balances (b), channel silent disablement (c), and random saturation (d).

T2R’s overhead is dominated by the number of encrypted items inserted into its ticket. Hence, we profile its size under two workloads.

1. 1.

   W_all: unrestricted pairs. For the same 50 000 $(s,d)$ pairs used in the main experiments, we build the candidate list for each node without capacity or HTLC limits and record $|B|$ – the element count in the resulting ticket. Also, for each node, we select all viable pairs. We ignored all these constraints to reach the absolute worst-case scenario regarding the number of elements of the ticket, enabling us to provide an upper bound for the size of the ticket.

2. 2.

   W_long: long-distance pairs. To demonstrate the worst case, we generate a separate batch of 50 000 pairs with the shortest path length of $\ge 4$ hops; the rest is identical.

Table 1 reports the key statistics (mean, median, 90^th and 99^th percentiles, and maximum) of the number of added elements in the ticket in both scenarios.

• $\mathrm{■}$

  Typical payments (W_all). The median ticket carries just 11 elements, while 90 % of payments stay below 126 elements. With a Bloom filter configured for a target error $f={10}^{-5}$ ($0.001\%$), the 90^th-percentile ticket occupies only $377$ B, whereas an equally secure GCS fits in $284$ B

• $\mathrm{■}$

  Long-distance payments (W_long). Deliberately selecting endpoints at least four hops apart roughly doubles the mean element count to 88 and the median to 34. Even so, 90 % of these worst-case payments stay under 212 elements; at the same $f={10}^{-5}$ this translates to $634$ B with a Bloom filter and $477$ B with a GCS. Even the rare cases of outlier are controllable: it vanishes once we cap the branch factor $K$ – that is, allow each node to contribute only a handful of its best channels to the ticket.

T2R’s reliability degrades only when an authorized next hop is a false positive: the intermediary node assumes an unusable edge is valid and finds no real edge left to forward the payment. To isolate this effect, we run same 50 000 payments from our main simulation under a perfect network (no disabled or saturated channels, balance split 50:50), and with balance update after each successful payment. For each payment, the sender inserts $m$ authorized channel directions and creates a ticket sized optimally for the chosen false positive rate $f$. Payment amounts are drawn uniformly at random in the 100–1000 sat interval used elsewhere in the paper; a payment is declared failed if some intermediary node has no authorized next hop. Also, we simulate both single ticket and the TwinTicket.