[Lightning-dev] network topology and routing

[Anthony Towns]

On Tue, Sep 15, 2015 at 02:10:18PM +0200, Pierre wrote:
> Now that I made a fool of myself, please correct me :-)

None of what you said seems foolish to me; routing's an open problem...

> I know there hasn't been much work on routing yet (not that I am aware of
> at least), but it seems there is a consensus around the fact that the
> target network topology would look like this :
> [a] https://s3-eu-west-1.amazonaws.com/acinq/public/lightning_network_1.svg
> [b] https://s3-eu-west-1.amazonaws.com/acinq/public/lightning_network_2.svg

Both these indicate each wallet (end-user) is connected to just one node;
I'd expect the usual case to be two or three so you can more easily deal
with downtime by a node.

> [a] implying that :
> - there would exist multiple paths to a target user
> - reaching a target user would require several hops
> - some nodes might even be connected only to nodes
> 
> This puzzles me because the network topology I expected would look more
> like [b]:
> I am not saying each node should be aware of every other node, but that :
> - nodes connected only to nodes shouldn't exist

If I'm an end-user with a wallet with two channels; and I switch my
software to being a full lightning node with the same two channels, I'd
end up in this state. Likewise if I was a new node trying to establish
myself on the network.

Also, if there's a lot of traffic from node A to node B, their channel
will become lopsided (B will own all the coins), if it turns out that
C has channels with both A and B, a circular transaction A -> C -> B ->
A would allow those channels to rebalance (and x->A->C->B->y would allow
x and y to continue to transact despite A->B being full). If that happens
a lot, it might be profitable for everyone concerned if "C" sets up a
node that only does that, and doesn't deal with end-users directly.

> - when user A sends a payment to user B, it goes through at most 2 nodes,
> or just 1 if A and B are connected to the same node

That's optimal for efficiency, but probably pessimal for privacy. If
lightning is fast and cheap enough, delaying things slightly for a
significant increase in privacy would be worthwhile.

> The reason for that is there is an incentive for reducing the number of
> hops right ? Because it is faster (each hop adds latency) and cheaper (each
> hop adds a fee).
> With that in mind, why would routing be more complicated than just
> <user-id>@<node> ?

Setting up channels isn't free, though -- it costs a blockchain
transaction, and locks up bitcoins for no value if the channel's idle --
so you also want to minimise the number of channels, not just the number
of hops for a transaction.

I think this means you actually want to optimise a formula more like

   ALPHA * (d/2 * N^2) + BETA * log_d( N )

where N is number of nodes, and d is the average number of channels a
node has open, and ALPHA and BETA are (roughly) the costs of having a
channel, and adding a hop to the average transaction respectively.

> Then we just agree on a standard port and that's it !
> Isn't it how the internet works already ? Why do we need an
> application-level routing on top of the IP routing ?

1) It'd be expensive to join the lightning network (if I wanted to be
able to send up to $5 to anyone, and there were 100 nodes on the
network, I'd need to commit $500 to lightning channels up front).

2) It'd be easy to block payments (USA bans anyone from setting up
channels with anyone in Cuba; Cubans can't run nodes)

3) If there's a communications blockage, there's no ability to route
around it.

That said, no routing might still result in a functional system when
we're just trying things out and there's only a handful of people
running nodes?

Cheers,
aj