Routing with Selfish Information Sharing
In our latest paper, we discuss the tradeoff triangle: Confidentiality-Efficiency-Effectiveness of the route discovery process.
Route discovery methodologies gaining increasing attention as a scalability requirement on the Lightning Network, and Trampoline Nodes are currently the most accepted solution. The following will discuss the implications of selfish incentives on these nodes.
Offchains & Route Discovery
Offchain networks provide a promising solution to overcome the scalability challenges of cryptocurrencies. They are built from “nodes” (i.e. users) and “channels” (i.e. links) with unstructured formation. Node A that wants to send a transaction to node B, has to establish a “good” route of interconnected nodes to B. In our paper, we focus on the simple question:
What are the possible routes?
Learning about possible routes is challenging: Currently, every node needs to know (and maintain) all the channels between all the nodes in the network.
Obviously, it doesn’t scale.
Trampoline nodes are one suggestion to solve this problem, in which the process of route discovery will be out-sourced to a new type of node. Thus, nodes that wish to be “light” (less memory, lower bandwidth usage and can be offline) may query these nodes and retrieve information in exchange for fees.
For the sake of our discussion, we evaluate two properties for the routes: (1) Nodes require a fee in order to participate in a transaction’s route, therefore cheaper routes are preferred, and (2) not all the nodes are available for every transaction (due to lack of resources or because they’re offline), therefore available routes are preferred.
Incentives
When a node building its own route, it can choose the “best” route. When a node uses Trampoline nodes (TN), it is vulnerable to both a confidentiality problem (another node is now aware of its transactions) and performance — how can it ensure that the resulting route is indeed “best”?
We assume that TNs get their fees by routing the “customers” through links that they own (and earn the participation fee). Therefore, a TN is actually incentivized to not share the “best” route, but only to maximize its earnings.
Search Friction & Digital Goods
From an economic perspective, these are well-researched fields:
In Search Friction, the buyer wants a product that many sellers offer, each with possibly different quality/price. The buyer needs to “pay” in order to query each seller (intuitively, he pays with his time).
So, how should the buyer maximize his profit?
In our case, the routes are the products, and the search cost is privacy loss and time.
In Digital Goods, the sellers have an “unlimited” amount of products, and sells a piece of information (or access to it). How should the sellers price this sell? How does the price change when there is a competition?
In our case, the sellers are the TNs, and they sell their knowledge about good routes in the topology.
In traditional markets, there is no merit to combine these approaches into single research, because digital goods are considered to be easily found, and thus with negligible search friction.
Our case falls in these two topics, thus it is interesting from an economic perspective as well.
Confidentiality-Efficiency-Effectiveness Tradeoff
Our main interest is to qualify the tradeoff between these properties.
The theoretical part of the paper shows that route-discovery algorithms, in fact, can not promise any bounds to these properties. In particular, we showed that for every algorithm, there exists a topology in which the loss of every property is unbounded. In practice, this is not the case.
We used the (publicly known) topology of the Lightning Network in order to evaluate the tradeoffs in a real-life scenario. Moreover, we examine another sparse topology in order to conclude broader insights.
Efficiency-Confidentiality Tradeoff
Empirically, close neighborhoods in the Lightning Network topology are crowded, therefore the TNs that the nodes find and query are not on always on the optimal route. On the other hand, in the sparse topology there are fewer edges, therefore if there is a TN in a close neighborhood, then the optimal route goes through it with a higher probability.
We can see that nodes in the Lightning topology find more TNs in their close neighborhoods, but the weights are far from optimal.
Effectiveness-Confidentiality Tradeoff
On the sparse topology we see that when we query bigger neighborhoods, the number of queries increases due to longer routes (which decreases the availability), but also more routes are found because there are more TN to query (and thus more disjoint routes, i.e. different channels).
Note that in both topologies, larger neighborhoods will result in more available routes, but at the cost of more queries.
On the Lightning topology, the curvature of the graph shows that the number of queries does not increase as fast when there are more TNs. We consider this as a result of the higher degree in the Lightning Network; the 3-neighborhood contains almost the entire graph, thus the TNs will yield disjoint routes which increases the probability of availability.
Effectiveness-Efficiency Tradeoff
The last tradeoff discusses the average route weight when assuming that the routes could be unavailable. In this experiment, we tried to route through the 10 shortest paths and checked the average weight and the number of pairs that did not find any route.
Note the interesting phenomenon in the sparse topology, in which the fee decreases when the availability decreases. This happens because the available routes become shorter, and thus the average fee decreases.
On the other hand, in the Lightning topology, the fee increases due to the larger number of pairs that succeed to transact. This might suggest that either there is a single route and if it is not available, then the transaction cannot be executed; or there are many different routes with approximately the same weight, which makes the unavailability of some routes have a smaller effect on the route efficiency.
Conclusions
We see trampoline nodes as an interesting player with different economical incentives compared to the other nodes in the network. While the wallet has search friction that is based on the number of queries that it needs to perform and the resulting privacy loss, the TNs may offer different prices that may be changed according to the wallet’s strategy.
This post discussed these ideas briefly, and more ideas, analyses, and formal proofs can be found in the full paper: https://arxiv.org/pdf/2005.14676.pdf
We welcome any questions, constructive feedback, and future cooperation:
Saar Tochner, saart@cs.huji.ac.il
Stefan Schmid, schmiste@gmail.com
