From rusty at rustcorp.com.au Sat Jul 18 11:10:01 2015 From: rusty at rustcorp.com.au (Rusty Russell) Date: Sat, 18 Jul 2015 20:40:01 +0930 Subject: [Lightning-dev] Routing on the lightning network? In-Reply-To: References: <874mlm0z5k.fsf@rustcorp.com.au> <1436295968.4352.49.camel@hppg6.kloosterkade> <87pp43v6rp.fsf@rustcorp.com.au> Message-ID: <87fv4ld8mu.fsf@rustcorp.com.au> Anthony Towns writes: > On 8 July 2015 at 10:21, Rusty Russell wrote: > >> 1) Each-hop routing: >> 2) Source routing: >> Is there anything I missed? >> > > ?"Por que no los dos?" > > If you have source routing from alice to bob to carol to dave, with > specified fees for each hop, why should that preclude bob deciding to route > to carol via eliza and frank (and sharing the hop's fee correspondingly)? > Then "each-hop" routing falls out as the special case where you specify > source routing directly from your hub to the final destination. Si! As I said in a followup to CJP: It does follow logically: the node is given the next hop, the fee the transaction is prepared to pay there, and the time delta (eg. there must be 3 days left on the HTLC at that point). If it's expressed that way, there's no reason that "next hop" need be adjacent, right? In fact, you can't really avoid them using intermediaries. > Cons: > - does not let you avoid nodes > + (NSA sets up a hub with negative fees in every direction, hubs > reroute everything though it to bump their fees) Good point. Especially if they're prepared to use very tight timing (since the money is not important), so a node won't lose too much expiry time on the HTLC. > - how to work out fees? > - how to figure out how to route to other hubs you don't want to have a > direct channel with? > > I think the latter two points have to be solved with some sort of global > (but not necessarily complete) routing announcement service, so you can > query who has channels and do cheapest path finding amongst them; > clients/leaf-nodes so they can estimate fees, hubs so they can do routing, > optimise fees, and work out profitable new channels to connect. Agreed. I think some dynamic routing protocol has to give you fees and other info. That's a fun, hard problem. > Maybe that > can be derived from transactions on the blockchain though? But that's > already in the lightning paper. Joseph half-seriously suggested that the anchor txs be open-kimono, meaning that the routing info is on the blockchain already. It's cute, but since you need the dynamic info I'm not sure it saves anyyhing. > Speaking of fees, I wonder if the "fee proportional to satoshi-hours" is > backwards -- rather than saying "the intermediary wants to charge for how > long finalisation takes", couldn't you just say "the sender is willing to > pay inversely to how long finalisation takes" in every case? > > If I'm an intermediary, that works out as me being offered (F - k * t) > satoshi to deliver X satoshi within t seconds, for some F and k, then if I > want to take a cut of X*t*r to cover my costs, that just looks like me > onsending X satoshi plus a fee of up to (F - k * t - X*t*r) = (F - (k+X*r) > * t). If you can arrange that fee structure technically, a successful > transaction means everyone has an incentive to close the txn ASAP > (including the final recipient who receives the leftover fee as a > time-sensitive bonus). In that case you just want to choose r based on your > available funds in both directions, making it expensive when you're > over-committed, and potentially offering refunds (r<0) when you're > unbalanced. I think there's a natural bias to collect ASAP in every case, so I'm not sure if further incentive there is required. The problematic case is payment fail after timeout. In a naive model, if the payment succeeds (eventually), at least you get some money. If it fails, there's no transaction to skim the fees from. > I think it's possible to cancel an unroutable transaction so that the funds > can be reused (by effectively routing back to the sender?); if it is, > nominating a smaller but still time-sensitive fee to have that happen > sooner rather than later might be good too. That could also be used to > implement a fee-enforced TTL; if the success fee is characterised by (F_1, > k_1) and the failure fee is (F_2, k_2), with F_1 > F_2 and k_1 > k_2 then > failing becomes more profitable than succeeding at t > (F_1-F_2) / > (k_1-k_2). (F_2 > F_1, failing is immediately better than succeeding; k_2 > > k_1, failing never become a better option; when passing on fees, probably > would be clever to keep that time roughly constant, which is admittedly > straight-forward). That might be useful if you want the protocol to have > long timeouts for safety, but you want short timeouts in practice for > responsiveness. The TTL in practice is the time difference each node wants for timeouts. OP_CSV is cleverly implemented in terms of median blocktime, which makes it less manipulable, but I wouldn't want to use a difference of less 1 hour per hop simply because there's a non-trivial chance of getting no blocks for an hour. > Offering an insufficient fee seems like it would easily render a > transaction unroutable; if one of the hubs is on a satellite or floating > platform for anonymity purposes, it might want massively high fees; if > onion routing is in place, this may only be discoverable mid-way through > the routing. > > If you structure the transaction as " here's satoshi, locked > with to be revealed by once you deliver and as many of > those satoshi as possible to her" with the actual payment Carol's expecting > not encoded anywhere other than (encrypted) in M, then if Bob tries taking > more fees than needed, he increases the risk Carol won't unlock R and he'll > get nothing. No, I think fees need to be explicit. "I will pay you N satoshi to get M satoshi to Carol". > I don't quite see how channels can be safely used for independent > concurrent transactions though. If I (Bob) have an idle channel to Carol > for 100k satoshi, and I want to route 100 satoshi on behalf of Alice to > Dave (locked to R_1), and 200 satoshi from Anna to Doug (locked to R_2) and > 150 satoshi from Amelia to Drew through that channel simultaneously, how do > I sign things given that any combination of those transactions could fail, > breaking the potential "chain"? There's 7 scenarios that could happen then, > do I need to send potential transactions for all of them to Carol? They become separate HTLCs. That all works fine. Cheers, Rusty.