From rusty at rustcorp.com.au  Fri Jul  3 02:10:15 2015
From: rusty at rustcorp.com.au (Rusty Russell)
Date: Fri, 03 Jul 2015 11:40:15 +0930
Subject: [Lightning-dev] Routing on the lightning network?
Message-ID: <874mlm0z5k.fsf@rustcorp.com.au>

Hi all,

        One of the fun open questions for LN is how routing will work.
I'd like to kick off that discussion now, to see if we can create a
strawman which doesn't immediately collapse.

Assumptions:
1. I'm assuming each node is known by its pubkey.

2. Source routing seems the easiest route; best for privacy, best for
   any tradeoffs between reliability/price etc.

3. We should do onion routing: each node knows the source and next step.
   This is not perfect: R values trivially identifies connections (if
   you own two nodes on the path, you can connect them), and the timeout
   implies a minimum TTL.

4. A recipient gives the payer 100 routes from some nodes to them.  The
   payer hopefully can route to one of the mentioned nodes (probably the
   cheapest).  This also means that if the payer has to do some route
   query it doesn't trivially reveal who the recipient is.

Route broadcast is more fun.  It's not like BGP where you have useful
subnets; even if you did, you need the pubkey of every node.

My original idea was a subset of hubs (a few thousand?) to which you
would connect: that makes full discovery routing fairly easy within that
network, and you report your address as "client XXXXX via hub <pubkey>".
Your hub(s) keep the routing tables, you just query them mostly.

A more ambitious idea would be to select N "beacons" based on the block
hash which every node figures out their best routes to/from.  That's
actually really efficient for broadcasting: you can guess whether a node
is a likely beacon based on previous results, and only broadcast likely
winners.  It also means each node only has to remember N * 144 routes
each way if we want beacons to expire after a day.

But could also result in the beacons (and their neighbors) getting
slammed.  Maybe beacons only become usable after 10 blocks, so they have
a chance to boost their connections in preparation?  I'd have to
simulate it...

Joseph also pointed out that the anchor transactions in the blockchain
imply the network topology.  That's kind of cool, but I'll let him
explore that.

Cheers,
Rusty