[Lightning-dev] Ionization Protocol: Flood Routing

Rusty Russell rusty at rustcorp.com.au
Wed Sep 23 02:42:57 UTC 2015


Anthony Towns <aj at erisian.com.au> writes:
> On Mon, Sep 21, 2015 at 11:46:13AM +0930, Rusty Russell wrote:
>> We regularly choose a dozen "beacon" nodes at random (using proximity to
>> the SHA of latest block hash or something).  Everyone propagates the
>> cheapest route to & from those nodes (which is pretty efficient, similar
>> to your scheme).
>
> I think what you're implicitly assuming here is:
>
>  a) global p2p network of lightning nodes; at a minimum each node has
>     a connection to every node it has a channel open with
>
>  b) consensus protocol for choosing an ordering of potential beacons
>
>  c) potential beacons have to have committed to a beacon id prior to
>     ordering being chosen (with spam/flooding protection)
>
>  d) gossip protocol to announce potential beacons and compare against
>     ordering, keeping the top few in memory.
>
>  e) sharing routes to beacons with direct neighbours
>
>  f) distributed hash to store/lookup route recommendations, keyed by
>     beacon/endpoint
>
>  g) distributed hash to lookup fees for hops keyed by hop ends
>
>
> I think (a) is trivial; and you already called out (b).
>
> For (c), not having a commitment means that people could generate a new
> node id that does well in the ordering algorithm after the fact; if it's
> SHA comparisons, that means miners would likely monopolise being a beacon.
>
>> 4) How to avoid fake beacons?
>>    Require a signature attached to an unspent bitcoin TX from before
>>    beacon selection?  That TXID is actually what competes to be close
>>    to the beacon selector.
>
> This might as well be the (an) anchor transaction. It's already in the
> blockchain, it's already associated with a channel. You couldn't just
> use the txid directly, because that wouldn't differentiate between
> endpoints though. This would give an advantage to nodes with lots of
> channels open; not sure whether that's desirable? Probably it is?
>
> For (d), once you've got the ordering, nodes tell each other about their
> 12 favourite beacons, and if they hear about better ones, they pass those
> on too. That needs to be global knowledge, but it doesn't matter too much
> if we have slightly different sets of 12 beacons at any point.  12 beacon
> ids is a fine amount of information to pass around globally, too.
>
> For (e), I don't think you want to gossip globally about routes --
> that's too much information to pass around if it's not necessary; but
> you still have to share your routes to beacons with your neighbours in
> order to figure anything out. Nodes announcing their best routes to their
> neighbours is basically just Dijkstra's algorithm in parallel I think.

Indeed, it's trivial (and I've already implemented a simple simulator to
do it).  The initial spamminess can be mitigated by waiting before
broadcasting depending on how likely you are a beacon.

> But just knowing your neighbours' routes isn't enough; you need to be
> able to lookup a route for anyone, and that (by definition I think)
> means you need (f) a DHT of routes-to-beacons. Note that looking up a
> route has privacy implications, in that it implies you're probably going
> to make a payment along that route!

That's why the recipient provides a set of routes from (some subset of)
beacons to them.  You know routes to all beacons, so pathfinding solved.

>> To receive a payment, B picks a few beacon nodes at random and sends
>> those routes (beacons -> B) to A.  Presumably A knows its route to all
>> the beacon nodes and thus can choose the best.
>
> A trivial DHT would be to have each node store its routes locally,
> and just make a TCP/IP connection to the node directly to ask for its
> routes. That seems like it'd be pretty bad for privacy though. I'm a
> fan of being able to route to/through nodes you can't reach via IP, and
> this would prevent that too.

Yes, that's a bad idea.  And I'm not sure why you need this?

> Finally for (g), I don't think you want to store fees in the routes
> directly, since updating fees would require updating an unknown number
> of routes; but fees have to be queryable, so that's a separate DHT. This
> one doesn't need to be updated when new beacons are elected though. This
> DHT would want to be fairly high performance, because you're doing 2*B*L
> lookups everytime you want to find a route, and it has to accept and
> propogate updates fairly quickly if fees change.

Well, propagating fee updates for (say) 1200 routes isn't too bad,
as long as they're not changing too fast.

>> There are some twisty details here:
>> 1) How many beacon nodes?
>>    12, and increase on a log scale with network size.  That size can
>>    be derived from previous beacons.
>
> I think it's also something you could set per-node, like the
> minrelaytxfee.

That doesn't make sense, since we need to agree on who is a beacon.

>> 2) How long between selection and a beacon becoming active?
>>    10 blocks.  That gives time for others to connect to beacon node.
>
> Beacons can be "active" as soon as you can route through them, and that's
> just a DHT lookup to determine, and then a matter of comparing fees to
> what the old beacons give you. So I think no artificial delay is needed,
> and the real question is just when you expire your routes to/from the
> old beacons?

No.  Beacons will get saturated fast unless they have a chance to
prepare.  In particular, the network will want to establish channels
with new beacons, and beacons may well want to bring offline funds
online to handle the anticipated capacity.

>> 3) How long before a beacon node is invalid?
>>    No idea.  Let's keep a day's worth for the moment?
>
> Sounds fine; also mostly a client side parameter. (Though if the routing
> DHT is non-trivial, old beacons should expire from there after some
> interval too to deal with nodes that disappear)
>
>> 5) How to update beacon routing?
>>    Particularly for fee changes, this is important.  Best effort,
>>    with ratelimiting.  I hope eventually we'll have reasonable traffic
>>    models so a node can say "I'm going to ramp up/down my fees for
>>    this long at this rate" and have a reasonable chance that it's true.
>
> I think this is reinventing DHTs, though maybe none of the existing ones
> work well enough for this use case?

What's the fascination with DHTs?

> I think rate limiting decreases in fees is always safe (it won't prevent
> any transactions going through, it will only prevent them being started).
>
> (I'm not sure a programmed ramp-up/down of fees makes sense; though
> maybe it would be a good way to perform price discovery)
>
>> PS.  For the immediate term, we'll use a global comms mechanism like
>>      IRC, but that's just a prototype hack.
>
> Hmm. Counterproposal: no beacons or routing DHT, just fees by gossip
> protocol (or IRC channel as prototype hack). Everyone has a complete
> (but possibly slightly out of date) database of node-node (but not
> node-wallet) channel fees, and changes are propogated by gossip. Back
> of the envelope maths:
>
>   everyone uses lightning ==> 8B wallets (5B teens/adults, 3B businesses)
>   every wallet has ~4 channels ==> 32B node-wallet channels
>   100k wallet channels per node on average ==> 320k nodes

Um, so each wallet isn't a node?  That's a very different architecture,
which uses hosted wallets or something?  I don't think that's very
interesting.

Cheers,
Rusty.


More information about the Lightning-dev mailing list