From laurentmt145 at gmail.com Sun May 1 16:26:50 2016 From: laurentmt145 at gmail.com (laurentmt) Date: Sun, 1 May 2016 18:26:50 +0200 Subject: [Lightning-dev] Fwd: Re: Routing & Beacons In-Reply-To: <87oa8x5hdu.fsf@rustcorp.com.au> References: <570E333F.8030401@gmail.com> <5710DC8F.70902@gmail.com> <87oa8x5hdu.fsf@rustcorp.com.au> Message-ID: <57262E4A.7060403@gmail.com> Thanks for the information. Indeed, it raises questions but this is exactly why I find the subject so interesting :) WRT the update of routing tables, let me try to summarize my understanding with this scenario: 1/ Landmark nodes periodically send a message to their neighbours (every 30s ?). This message initiates a new temporal frame (symbolized by counter embedded in the message and sequentially increased by the landmark node). 2/ When a node receives the first message associated to a new temporal frame for a given landmark, it waits for a delay before forwarding the message to its own neighbours (it gives a chance to receive the same message from a better route). After this delay has elapsed, the node computes the best route to the landmark node and forward the message (information defining the temporal frame + best route to landmark node) to its neighbours. 3/ Every node repeats the same process (step 2). When the process has completed, every node knows the best route to/from a given landmark. When a node needs to send a payment, the receiver sends her its best routes to each landmark node. Therefore the sender is able to compute the best route to reach the receiver and onion routing is possible. Random remarks / questions: - Agreed that the "base+per-satoshi" fee model creates a difficulty to define the best route. I don't know if I'm right, but I see the base fee as a way to say "I don't want to transfer amounts lower than X satoshis" (the base fee makes them economically unviable). So, as you wrote, a solution may be a set of nominal values and the forwarding of a set of best routes (a route for each range of amounts between 2 nominal values). - A shower thought: with this model, fees seem conceptually associated to the node and there's no distinction related to the direction of the payment (sending or receiving). A different model would be to associate fees to individual payment channels (with a different fee defined for sending and receiving on this channel). It means that for a given landmark, a node would forward 2 best routes (for sending/receiving payments to/from the landmark). That may be useful to cope with unbalanced channels because it allows the node to signal that, for instance, it's ok to receive payments on a given route but sending payments is not encouraged. - Would it be useful to have simulations ? (that may be an interesting side project on my hand). laurent Le 26/04/2016 02:43, Rusty Russell a ?crit : > 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. >