From cjp at ultimatestunts.nl  Tue Jul  7 19:06:08 2015
From: cjp at ultimatestunts.nl (CJP)
Date: Tue, 07 Jul 2015 21:06:08 +0200
Subject: [Lightning-dev] Routing on the lightning network?
In-Reply-To: <874mlm0z5k.fsf@rustcorp.com.au>
References: <874mlm0z5k.fsf@rustcorp.com.au>
Message-ID: <1436295968.4352.49.camel@hppg6.kloosterkade>

The routing design has important implications for privacy, but also for
the enforcement of regulations on the Lightning network.

Imagine, for instance, that a couple of large nodes start requiring
their neighbors to provide identity information (KYC-style regulation),
and then require them to recursively provide identity information for
all their neighbors' neighbors, and so on. If it is visible to
intermediate nodes which other nodes participate in a transaction, this
would cause the Lightning network to split into a regulated and a
non-regulated part: nobody would dare to interface between the two,
since that would prove to the regulated side that they illegally provide
connectivity on the non-regulated side.

So, I don't want nodes to explicitly know the shape of the entire
network. Based on how Wikipedia explains source routing to me, I think
it is incompatible with what I want. Please also note that IP almost
never uses source routing.

Also, as a counter-measure against censorship (or persecution) based on
destination address, I think the function of "destination address of a
route" should be de-coupled from the function of "payer endpoint" or
"payee endpoint" of a route. In many cases, the "payer endpoint" or
especially the "payee endpoint" will also fulfill the role of
"destination address", but they may also choose a neutral "meeting
point" node in the middle, and both route towards its address. This will
allow nodes to secretly interface between regulated and non-regulated
parts of the network, for transactions going in both directions.

The time-out value is a bit of a problem in this concept, since it is an
indication of the number of hops from the payee endpoint. However, if
nodes are free to choose the time-out increment for themselves, they
could choose to make that increment smaller, to be able to route through
a node that provides an interface to the regulated part.

An additional advantage of separating destination addresses from the
payment endpoints is that routing tables can be much smaller. Most
consumers, and a lot of small shops can choose not to have their own
destination address, but instead route through the destination address
of their Lightning provider (a bit like a NAT router's IP address).

In my view, routing tables are a sort of a heuristic, that tells you how
likely a payment (of a certain amount!) to/from a certain destination
address is to succeed on one of your interfaces. It is an optimization
over the dumb algorithm of simply trying out all your interfaces one by
one(*). It is TBD how to determine these heuristics, and how to exchange
them between nodes.

This is probably quite different from how routing on the Internet works,
and I'm not sure how it will scale and how it can be defended against
DoS attacks, but it sort of follows automatically from the desire to
keep the network free.

CJP

(*) Which is currently the only routing method implemented in Amiko Pay.


Rusty Russell schreef op vr 03-07-2015 om 11:40 [+0930]:
> 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