Lightning Network Routing: Privacy and Efficiency In A Positive-Sum Game

The shortest distance between two points is a straight line, as everybody knows. Except it’s not true — at least not outside of a Euclidean universe of mathematical abstraction.

Everyone who’s watched lightning knows that it doesn’t travel in a straight line. Instead, lightning travels from one point in space to the next depending on the resistance it encounters, automatically finding the most efficient route, one infinitesimal segment at a time.

Payments on the Lightning Network face a similar challenge, but the network doesn’t have nature’s optimization procedures built in. Lightning (we’re talking about the network now) requires plenty of thought, code, and adaptation to be as robust and efficient as possible.

In this post, we’re going to explain how payment routing works on the Lightning Network, what aspects still need improvement, and the routing technologies of the future. Routing already works on the Lightning Network. In fact, it works very well, even on Android and the iPhone.

The Basics: Nodes, Channels, Onions

The fundamental building blocks of the Lightning Network are nodes and the payment channels (i.e. edges) that connect them. A node can be any user, merchant, or LSP. Payment channels connect (some) nodes to (some) other nodes.

Naturally, every node on the network will be connected to at least one other node.  But it is not very likely that your light client, will have a channel open with another given node, say Tschego and Lonny, whose bees make the best honey this side of Johannesburg.

Opening a payment channel is an on-chain transaction, so having to open a channel for every new counterparty would defeat the purpose of having a second-layer network. Therefore, any payment between two unconnected nodes is better off finding a route through a series of existing payment channels.

 

You’re not connected with them or their delicious honey, but somebody is. (Source:wikimedia) How Routing Currently Works

Currently, Lighting uses source routing and onion routing. With source routing, the source node is responsible for calculating the entire route, from source to destination.

To do so, a source node needs to download the entire graph of all public payment channels in order to calculate a route, considering the capacity of all the channels along the way, the cost in fees, and the number of hops required. This process involves a lot of data for a P2P transaction, and that amount will only grow with the network.

Lightning also implements onion routing, which greatly enhances privacy. It works like this: let’s say I want to send a payment to Adam, but we don’t share a payment channel. However, I share a channel with Nick, Nick shares another channel with Jameson, Jameson shares another channel with Andreas, and Andreas shares a channel with ̶V̶i̶t̶a̶l̶i̶k̶ (just kidding!) Adam.

So,

1. I lock the payment in a box, and I lock that box inside a bigger box with a key and the recipient’s address.
2. I lock the second box inside an even bigger box with a key and the previous node’s address.
3. Wash, rinse, repeat until the chain of boxes, keys, and addresses (i.e. transactions) from me to Adam is complete.

When I send the largest box to Nick, he’ll open it to find the next box and Jameson’s address. He’ll send it to Jameson, who’ll be able to open it with his key and find the next box with Andreas’s address. Andreas will open that with the next key and find the last box with Adam’s address. He forwards it to Adam, who has the final key and receives the payment.

 

Engineers look at this and see an onion. And people say they lack imagination! (Source: wikimedia)

Each node only knew the addresses of the previous node and the next node, but none could reconstitute the whole chain or identify who the final recipient was supposed to be. That’s onion routing: intermediate transfers on a need-to-know basis.

Tor further improves user privacy. With onion routing, the intermediate nodes are largely in the dark, but the sender still has access to the recipient’s IP address and rough geographical location. Tor fully obscures users’ IP addresses, so no one else on the network — not even direct channel partners — is privy to their identities or locations.

 

It’s easy to forget the value of privacy until you lose it. (Source: reddit) Greater Efficiency Thanks to PBMC

Since transactions can expire if not completed quickly enough, increasing transaction speed improves Lightning’s effectiveness and efficiency.

Initially, if a node or edge caused a routing attempt to fail, the algorithm would simply ignore it for a few seconds before losing the knowledge gained. Without some way to store and use that information, later payments and concurrent “in-flight” payments might consider defunct nodes in their routing calculations, costing time and data.

Probability-based mission control (PBMC) solves that problem by learning from past successes. Each node now starts with a default probability of success, which increases or decreases depending on its rate of actually completing transfers. The more payments the network daemon routes, the more it learns about the network’s characteristics, and the better it can route future payments.

The Route Ahead

As the Lightning Network matures, and its developers learn from existing implementations, they tend to view basic functionality, efficiency, and privacy less as three different questions. Rather, every new development takes all three aspects of routing into account and seeks an optimal balance between them.

Trampoline Payments

As mentioned above, scaling the network will increase the graph size and make source routing impractical for mobile nodes with limited bandwidth and storage. Trampoline payments are one proposed method to reduce their burdens of data and computation by outsourcing routing to “trampoline nodes.”

Trampoline nodes are simply Lightning nodes that contain the full network graph and take over the job of finding a route from payer to recipient. Instead of having to download and constantly update the graph, each light client would only need a connection to one reliable trampoline node. The payment would jump from one trampoline node to the next until it arrives at the intended recipient.

 

Trampoline payments offer the same efficiency gains as the real thing, but not quite as much fun. (Source:djromanj)

 

However, outsourcing routing to trampoline nodes presents a privacy risk: in order to route the payment, they need to know the sender and the recipient. But even before the technology goes live, there is already a promising proposal to solve the privacy problem.

The idea is to use two layers of onion wrapping: one containing the sender and the recipient, and another containing a randomly selected chain of trampoline nodes. As is generally the case with onion routing, each node along the path can only access the routing info it needs. And the random chain makes it difficult for any intermediate node to discern sensitive information. The chief drawback is that increasing the number of hops between nodes increases the transaction fee, but ten times almost nothing is still almost nothing.

Ant Routing

When returning to the nest after randomly finding food, a scout ant leaves a trail of pheromones that other ants can follow. The more the trail is used, the stronger its pull. But when the food source is exhausted, the trail will evaporate. Ants’ combination of random and orderly behavior produces optimal routes with scarce information and communication.

Wait a second!

 

If you want to find an optimal route, ***do not take the road less travelled.*** (Source: wikimedia)

The ants’ clever behavior inspired Cyril Grunspan and Ricardo Pérez-Marcoin their quest to eliminate hierarchy on the Lightning Network and let all nodes perform all functions. Their “ant routing” works like this:

1. Two nodes generate a large random number, and each generates a “pheromone seed” (i.e. a partial hash) that requires the other’s pheromone seed to reconstitute the number.
2. They broadcast their respective pheromone seeds to their neighbors.
3. When a node receives a pheromone seed, it checks to see whether that seed is present in the network’s mempool and whether its neighbors have received it.
4. If the node finds that it has received a new seed, it stores the seed in the mempool and passes it along to its neighbors.
5. When two partial seeds match somewhere in the network, they retrace their paths from neighbor to neighbor until the sender and the receiver are connected, which allows the payment to proceed.

After some period of time determined by each node, all local data about the confirmed seed is erased (just like evaporating pheromones!), and all the transaction data is deleted a short time thereafter. If no path is found in the time available, the transaction simply fails.

Since each node need only know about the immediate neighbors who transmitted the seeds, the authors claim that the algorithm preserves the sender’s and receiver’s anonymity. They also claim that their proposal eliminates the need for locally stored network graphs, which would reduce the data involved considerably and flatten the network’s structure. However, each node would have to perform some extra computation.

Ant routing could be another great way to scale the Lightning Network while improving both privacy and efficiency.

The author is the founder and CEO of Breez, a payments solution for Bitcoin’s Lightning Network. Crypto Briefing does not accept any payment or financial benefit from expert guest authors.

If you are a blockchain expert with an interest in sharing your knowledge and experience, please contact our Managing Editor, Jon Rice, via email at editor AT cryptobriefing.com

The post Lightning Network Routing: Privacy and Efficiency In A Positive-Sum Game appeared first on Crypto Briefing.