From rusty at rustcorp.com.au Tue Apr 26 00:43:41 2016 From: rusty at rustcorp.com.au (Rusty Russell) Date: Tue, 26 Apr 2016 10:13:41 +0930 Subject: [Lightning-dev] Fwd: Re: Routing & Beacons In-Reply-To: <5710DC8F.70902@gmail.com> References: <570E333F.8030401@gmail.com> <5710DC8F.70902@gmail.com> Message-ID: <87oa8x5hdu.fsf@rustcorp.com.au> laurentmt writes: > Hi Rusty, > > If I'm correct, it means that on a given period all payments go through > the selected beacons nodes ? To a first approximation, yes (obviously, if the route would go in and out the same channel, it can be eliminated, but that's statistically unlikely for a well-connected beacon). BTW, the literature seems to use the term "landmarks", so I'm trying to stop saying "beacons" :) > I ask this because some protocols like the pulse protocol are also based > on beacons to update the routing tables but they don't require that all > "messages" go through the beacons. "Messages" go through the first > common ancestor of source and target in the spanning tree associated to > the selected beacon. > > The main drawback with this approach is that the source doesn't know the > route beforehand... The main advantage is that it puts less "pressure" > on the beacons. Yes, I'd really like something better, but the beacon/landmark idea is simple, enables a one-pass communication for the route (here's a QR code on how to reach me from N landmarks), and doesn't require the receiver to know the buyer's location. > Another question: have you already decided on an update strategy for the > routing tables? No, I haven't. Thoughts welcome :) > As I understand the problem, there's 2 variables which determine the > best route: > > - capacity of channels at time t (max number of bitcoins I can transfer > through a given channel). It determines if a route can be used to > transfer the amount. > > - fees charged by nodes. It determines the best route. > > Capacity is likely the most dynamic of the two variables. Do you > consider capacity as an information stored in the routing tables (but it > may be very challenging to keep tables up to date) or is it checked "in > live" when the payment is propagated ? My base assumption is that payments are generally smaller than channel capacity, i.e. micropayments. Also, the route map itself is fairly static, and in fact could be fully known to a node: the pricing information is dynamic and needs careful thought. You want a payment to Just Work most of the time; getting routefails and forcing retries should be unusual. My current idea (beyond a prototype where every node chats on IRC indicating their current routes and prices) is that: 1) Prices are indicated as base + per-satoshi cost. 2) Nodes are ratelimited on their pricing updates (say, once every 30 seconds, perhaps with some burst capacity). I'm also considering that price changes phase in over time, indicating how they change over time from some base (eg. "increase by .01 satoshi every second from X until Y"). My concern is that slight price changes may cause massive changes in terms of traffic (once a parallel route becomes cheaper), so that makes sense. Some ratelimiting is definitely necessary because competition may well cause such route-flap. And note that base+per-satoshi means "best route" selection depends on the value you're sending, so a handful of nominal values are probably required (so there may be different "best routes" for each one). There's also the question of how to handle false advertising. Ideally, you should be able to broadcast the response from a node which refuses to route your payment. That gets a little complicated with onioning: it would have to sign the hash of the onion, HTLC and the routefail message, which would be checked by the previous node and encrypted, onioned all the way back to the source. If one node signs a invalid message, that can be broadcast and the node blacklisted. The sender can reveal the onion at that point and the decode key, and show that the node refused to route. It can then be temporarily blacklisted. Sorry if this raises more questions than answers! Cheers, Rusty.