From aj at erisian.com.au Sat Jul 18 09:46:35 2015 From: aj at erisian.com.au (Anthony Towns) Date: Sat, 18 Jul 2015 19:46:35 +1000 Subject: [Lightning-dev] Routing on the lightning network? In-Reply-To: <87pp43v6rp.fsf@rustcorp.com.au> References: <874mlm0z5k.fsf@rustcorp.com.au> <1436295968.4352.49.camel@hppg6.kloosterkade> <87pp43v6rp.fsf@rustcorp.com.au> Message-ID: 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. 3) Extensible source-routing - client chooses how many layers are required (fees, reliability vs anonymity) - at any point, holder of transaction may extend the route by adding intermediary hops (optimise fees, channels, hub/hub balances, etc) Pros: - only hop endpoints are visible at any step - adaptable to changing network conditions - source can be anonymous to destination, source and destination anonymous to intermediaries - clients need minimal info (ability to estimate fees, info on hub reputation for anonymising) 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) - 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. Maybe that can be derived from transactions on the blockchain though? But that's already in the lightning paper. I think a routed "transaction" looks something like: To: Bob - Here's 200 satoshi from Alice locked with R - You need to send 195 satoshi to Carol with message X, who will unlock R. So extending the route would just be Bob making a new transaction: To: Dave: - Here's 198 satoshi from Bob locked with R - You need to send 195 satoshi to Carol with message X, who will unlock R. which seems plausible -- though I haven't checked it against the actual protocol so maybe it fails in the details... If it's okay, then maliciously routing to /dev/null just means R never gets revealed, no one gets paid, and the transaction eventually is considered refunded/cancelled; and if it does get where it's going the only consequence versus going directly is it takes a little longer and Bob loses some fees. 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 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. 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. 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? CHANNEL -> [a] Bob 999,900 | Carol + R_1 100 CHANNEL -> [b] Bob 999,800 | Carol + R_2 200 [a] -> [c] Bob 999,700 | Carol + R_2 200 CHANNEL -> [_] Bob 999,850 | Carol + R_3 150 [a] -> [_] Bob 999,750 | Carol + R_3 150 [b] -> [_] Bob 999,650 | Carol + R_3 150 [c] -> [_] Bob 999,550 | Carol + R_3 150 If you can't have concurrent independent txns on a channel, then it seems like you want /really/ short timeouts (seconds not days) to keep things flowing -- your txn doesn't block just the satoshis its spending, it blocks /all/ the unspent satoshis in the channel... Cheers, aj (hoping the above is adding to the discussion) -- Anthony Towns ?? -------------- next part -------------- An HTML attachment was scrubbed... URL: