Rusty Russell [ARCHIVE] on Nostr: 📅 Original date posted:2015-09-22 📝 Original message: Anthony Towns <aj at ...

📅 Original date posted:2015-09-22
📝 Original message:
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.