[Lightning-dev] Ionization Protocol: Flood Routing

Rusty Russell rusty at rustcorp.com.au
Wed Sep 30 05:12:54 UTC 2015


Anthony Towns <aj at erisian.com.au> writes:
> Batch-replying.
>
> On Sun, Sep 27, 2015 at 01:54:45PM +0930, Rusty Russell wrote:
>> Anthony Towns <aj at erisian.com.au> writes:
>> > On Fri, Sep 25, 2015 at 09:56:02AM +0930, Rusty Russell wrote:
>> >> [ Pieter Wuille Cc'd for pubkey recovery, search for "recovered" ]
>> >> Mats Jerratsch <matsjj at gmail.com> writes:
>> >> >> Indeed.  Random selection helps, here, but analysis will be interesting.
>> >> > How have you ended up with a number of beacons you need? 12 seems so
>> >> > low, I can’t imagine so few nodes to support all transacting for even
>> >> > 10 minutes..
>> >> As we keep the last 100 sets of beacons, the load is spread a little.
>> > Does that actually work? Old beacons don't do any good if the payee
>> > doesn't use them when advertising a route; but old beacons also don't
>> > get their fee updates propogated, and aren't known by people who only
>> > just joined the network. I don't think you could usefully keep more than
>> > the last 2 or 3 sets of beacons?
>> I was thinking they all count as active.  No point turning over all the
>> beacons every block.
>
> Okay, in that case I was misled by your original description.

Did I somehow give you the impression I'm making it up as we go along?
I'm so sorry, let me reinforce that now...

> You're
> actually talking about n*k beacons at any point in time, of which the
> oldest k are replaced every d days. If k=12 and n=8, that gives 96 beacons
> at any point in time. Any given beacon is operation for n*d days, for n=8,
> then d=1 gives 8 days, while d=7 gives 2 months.

Pretty much.

I was thinking there's some delay before activation (so, we have 10
blocks worth of "chosen but inactive" beacons), 100 blocks of active
beacons.  n beacons per block (though it may increase with <formula>).

We can play with the parameters.  And we might select every N blocks if
we want longer-lived beacons.

> The "d" parameter would be "consensus-critical"; I don't think it's
> possible to agree on any beacons without agreeing on d. You could vary k
> or n as the network scales though, but in that case I think it'd generally
> be easier to vary n than k?
>
> If you identify a given beacon by its cohort (from 1..n), its rank
> (1..k), its visibility (how long ago you first heard about it in
> seconds) and its currency (how recently the last route update to that
> beacon was), then I think the odds of a random other node also knowing
> about that beacon works out as:
>
>  - worse for the most recent cohort (older cohorts should have more fully
>    propogated)
>
>  - potentially worse for the very oldest cohorts
>     + if being a beacon wears you out (channels may have been used
>       up; they may have been hacked; they may have cashed out their
>       profits and bought an island)
>     + if nodes have varying settings for n, so older cohorts don't have
>       as effective route propagation
>
>  - worse for recent visibility (newly advertising beacon, that hadn't
>    fully propagated, same deal as for a new cohort)
>
>  - worse for non-recent currency (beacon might be offline, or routes to
>    that beacon might have failed)
>
>  - worse for low rank in recent cohorts (new beacons shouldn't show up
>    for old cohorts; if new beacons show up in recent cohorts, its the
>    low rank beacons that will be offloaded)
>
>  - worse for low rank in any cohort if other nodes have lower values for
>    k

In practice, more recent beacons last longer.  The other effects are
less clear.  I'm assuming nodes remember routes to older beacons than
they would actually give out to others (handwave).

> When picking beacons to advertise for accepting a payment, I think you'd
> want to take most of the above into account, to avoid only suggesting
> coincidently unreachable beacons, and having the payment fail.
>
> I don't think you could really take route price into account, since the
> real price is "consumer to beacon" plus "beacon to merchant"; and those
> could trivially be inversely related. Having 10%-30% of your suggestions
> be selected by cheapness would still be useful though.

Still the best choice, I think.  Simulations welcome, but on a large
network random nodes are likely to be terrible for both.

> Choosing, say, two of the cheapest beacons, and three beacons from
> cohorts 3-n with recent currency and long term visibility would probably
> work okay though.
>
> If nodes are identified by a 160b address, and it takes around 4 hops
> to get to/from a random beacon, then a route is 4*160b=80B and five
> routes as above is 400B. That's ~550 bytes with base58
> encoding by my count, or about 7 lines of 76 column text. Kinda lame:
>
> "please pay to 1ajaj31PWNVZEzd68S8PqAPof4EFbeZaf via lightning route:
> 5PSGzi9R6k6G2mdFPx2ZsfyVdiz9gSaA7EegpTvzbxLb13yMEuNuK7m1DhJuJvwkMe4BrfdU2V5q
> cKf825oYmikQMzpfAvVkavA3AyXZEgGWx9j3j5gUxMUE8LhawnfTWWSQMc2gChzKEz1puFcyveMa
> QHVdhbcJY73M4Aev7KDWqnrAYNid2keGRzDtUDfZarSsABR4RWjshCtBctekjvxYQpsBqD4NrzvV
> DCGQNNWbKibSawkt18xdPGxR3rwMwkEqU5rE8EfXmFrFaj7t2nB8DWQa1oe4QhvPe9BYsyAumJtG
> SZFmRknJ2E5feDCzYfqAu8tVcaW6yhKUgxdrxqBVfzdTBFVtt2p5PPrz4C9d3MQsrerfSHSbbX7Q
> VcUqhotinoMHX2UyfbRYX4BJgNjLqaXE33EthhF7BBmBRkP6V7EyZYrc53XtEi1ocuKNiejWcEQe
> neajEMR9rFpHHSnzSX8AXXn13TYsGirHiFG7KYu7tzg6EFEifLeAz2wxaaaMs2K6J488kxWpDy1s
> GtG3zX3v5msToo"
>
> (I 100% approve of urandom generating bytes that encoded to "aj" twice
> in the length I estimated for a route... Sure, it probably means my RNG
> is compromised and identifying me, but how sweetly personalised!)

In the future, we'll all be using the payment protocol.  From our flying
cars.  Right?

OK, so we ahve to use a 177x177 QR code.  Lucky about high-res cameras,
I guess?

> If you're going to have parameters that need to be changed as things
> scale, seems useful to have them accept changes gracefully, rather than
> relying on flag days. I'm still pretty sure that k (and/or n) here work
> that way, as described.

That's true, if we think of changing the numbers over time.

I was thinking of scaling n with log2(number nodes).  And we can intuit
number nodes from proximity of beacons to ideal <insert smoothing and
formulae here>.

>> > Since I have to update my beacon-to-me routes regularly because of fee
>> > changes, I could regularly select different groups of beacons so you
>> > could just ask again.
>> Yech... you really want this to be single pass "pay me $5, and here are
>> three routes from beacons near me".
>
> Well, so far a "route" consists of a path with fees; symbolically:
>
>  pay [MY ADDRESS] $5 via:
>    [BEACON 1] 1c [N1A] 1c [N1B] 2c [N1C] 2c [N1D] 4c [ME]
>    [BEACON 2] 2c [N2A] 1c [N1C] 2c [N1D] 4c [ME]
>    [BEACON 3] 1c [N3A] 3c [N3B] 1c [N3C] 1c [N3D] 1c [ME]
>
> So even if you keep the same set of beacons, you have to regularly
> update the route info as fees/routes change, eg:
>
>  pay [MY ADDRESS] $5 via:
>    [BEACON 1] 1c [N1A] 1c [N1B] 2c [N1C] 2c [N1D] 4c [ME]
>    [BEACON 2] 2c [N2A] 2c [N2B] 1c [ME]
>    [BEACON 3] 1c [N3A] 3c [N3B] 1c [N3C] 1c [N3D] 1c [ME]
>
>  (N2A to N2B dropped it's previously uncompetitive fee from 10c to 2c in
>   this example, nothing else changed. N1C->N2A costs 8c)
>
> Even just sitting on the "checkout" page for a minute might be long
> enough to require a new route suggestion, eg.
>
> If you're doing that anyway, might as well select a different set of
> beacons each time as well.
>
> (The only way to not have to do that (afaics) is to just say "pay [MY
> ADDRESS $5" and query the network for the route; which either means
> keeping the entire graph available for path finding, or having DHTs to
> lookup routes from beacons and fees)

Yes, we could use the DHT for routes/fees.  I think it's a layer on top
though.

>> But you're right makes more sense to have two-phases: an immediate one
>> after the block is broadcast where you compete (via SPV proof of some
>> tx) to be a beacon, then another closer to activation where you
>> broadcast routes.  Between those two you can expect an influx of channel
>> offers.
>
> If you've got n cohorts of beacons anyway, it seems like you'd just
> always have the newest cohort be "in setup phase". ie, they'd announce
> and compete fairly quickly (minutes or hours), and then spend some time
> getting fully setup (new channels, rebalancing), and obviously still
> forwarding any transactions that find their way to them, but everyone
> would still tend to use the more established cohorts. Then once the /next/
> cohort gets selected, it's game on.
>
> That'd just require merchants to not select the latest cohort of
> beacons when advertising routes from beacons. As far as everyone else
> is concerned, brand new beacons are fine to use as normal if they turn
> out to be the best route.

Makes sense.  Selecting a new cohort every block is probably silly then,
since they come too fast.

>> Interestingly, the former idea means you get some leakage of routes,
>> from nearby almost-beacons (until defeated by better beacons).
>> Remembering those might help shortcircuit some routes (if there's some
>> geographical correlation between nodes).
>
> I don't think this works: old route info also means old fee info; and
> you can only shortcircuit if the fees are actually less, which you no
> longer know.

No, you get updated fee information when your message gets bounced.

> *However* this is all probably a moot point: if beacons aren't used
> while they're in the newest cohort, then they don't particularly
> need to use the new channels immediately, and new anchors get
> safely buried anyway. Something like:
>
>  * 1 hour (6 blocks): pretty good global consensus on who the beacons are
>  * 20 hours (120 blocks): plenty of time to setup new channels
>  * 3 hours (18 blocks): plenty of time for the new channels to be buried
>
> And voila, 24 hours later, the new cohort has new channels and is ready
> to go active, and a new newest-cohort can be chosen.

I like your random formula, and shall slavishly adopt it!

> It feels a lot like doing economic stimulus by randomly selecting
> some people, giving them a million dollars, and announcing their home
> addresses. Sure, it's the first story on the news, but the second is
> how they were found mugged and broke two hours later...

It's a true Bitcoin story!

> In reality, to me those numbers just say "it's not worth running a node
> if you're not a beacon", so the best strategy is to commit a few cents in
> pretend channels on the blockchain to buy tickets in the beacon lottery,
> but only start actually routing when you win. So there maybe ends up being
> a few thousand nodes that have direct relationships with customers to
> earn profits based on subscription fees, and a bunch of beacon-specialists
> who play the beacon lottery and run 90% of the beacons at any given time,
> earning profit from investment and routing.

Perhaps the entire network becomes corrupted.  But the alternatives seem
to lead even faster to centralization.

Joseph suggested that to be in the lottery, your anchor tx would have to
be above some amount.  I resisted that as another centralization force,
but perhaps we'll end up there.

> Also, if the only routes you know are to and from beacons, it seems
> a bit difficult to do much in the way of "scenic" routing to make the
> onion routing more obscure. I'm not sure this actually matters if you
> have a total path length of more than six or seven though.

Or, something added up one layer.  Ask me my routes, and I will tell
you?

> (TBH: at this point beacons are seeming (to me) like a clever idea, that's
> totally implementable, but won't actually work out at all. YMMV obviously)

Quite possibly.  It's implementable, but not sure it's going to be
robust.

> I was figuring it would just be a "couldn't route" message with no
> additional info (could be no channel, not enough fees, bad R, mistake
> in crypto...) -- otherwise you're kind-of unwrapping the onion (ie, C
> tells B, "C's fee is 1%"; B tells A "C's fee is 1%"; A says "oh, trying
> to send money to C, huh? how interesting!". C could encrypt the info to the
> symmetric key A sent C, but... seems like a lot of hassle at that point)

Yep, you have to onion up error messages.  (Except timeout, that needs
exposure, to prove you broke a channel).

It's not that hard to do though, since every hop has a shared secret
key.

>> I was more concerned about the "there's no channel from B->C any more".
>
> Sure. In that case you can't make the payment until they tell you new
> routes, or you use some other protocol for route finding. The beacons
> are going to change soon enough anyway, so no suggested route will
> work for all that long, even ignoring fee changes.
>
>> > (If probing was the main use for nanotransactions, nodes might set higher
>> > fees on them though, if they assume you've already chosen a route, and
>> > they therefore don't need to compete on price with other possible routes)
>> Maybe nodes will offer some kind of routing service in future.  Seems
>> like it'd be a layer up though.
>
> I kind-of think routing is actually already a layer up, and effectively
> sort-of pluggable. ie, you've got:
>
>  0: direct connection to someone, can establish a channe, update HTLCs
>
>  1: onion-routed packets, can be forwarded on level 0
>
>  2: route-finding
>
> If you've got a bunch of beacon routes, that's one way of implementing
> level 2. If you know a whole bunch of channels, then you can do it that
> way. If you have an oracle you can query, that's another way. If you've
> got multiple different systems (some nodes don't participate in the
> main routing network because of persecution fears eg), with some nodes
> in common, you can join them up.

Indeed.  Perhaps there's a smarter way to segment the network than
global beacons though.  Maybe some limit on path length?

> Hmm, I think that actually explains the lightning/bitcoin fee nexus a
> bit: lightning nodes earn x% of lightning transactions; then to reinvest
> this profit in lightning, they spend on the blockchain generating $f
> in fees for miners. It's not /spending/ the profits from lightning fees
> that generates fees for miners (because that could be done withing the
> lightning network in theory), it's /reinvesting/ them in the lightning
> network. (And also buying into lightning in the first place, or cashing
> out eventually, or rebalancing your investment)

Indeed.

> That's not a problem here. Say every other beacon costs 1% to route
> through, give or take. You have neighbours A, B, C and D. You set the
> following prices:
>
>    A -> Me: 0.45%
>    B -> Me: 0.45%
>    Me -> A: 5.1%
>    Me -> B: 5.1%
>
>    C -> Me: 5.1%
>    D -> Me: 5.1%
>    Me -> C: 0.45%
>    Me -> D: 0.45%
>
> A route that goes X -> A -> Me -> C -> Y will still only pay you 0.9%
> so is completely competitive for transactions; but hardly anyone will
> ever see a route like Z -> D -> C -> Me, because Z -> W -> V -> U -> A ->
> Me will be cheaper despite the extra hops. That in turn means means no
> one will figure out that Z -> D -> C -> Y is a valid path, missing out
> going through me.
>
> To make it work dynamically, you'd need to swap the channels you apply
> the ~5% penalty so the transaction flows balance out, but I think the
> general principle works.

Clever.  I'll have to think about that more...

>> It
>> seems to me that a beacon wants many connections, to avoid the
>> "short-circuit" case.  At 100 connections, it's only 1%, though
>> that's the best case which assumes they're all equally likely.
>
> Maybe... Establishing an extra 100 connections per beacon per cohort is a
> fair chunk of blockchain transactions; and presumably they'll expire once
> the beacon stops being a beacon, rather than lasting for months/years.
> 500kB per cohort, maybe? At 1MB/block and a cohort per day, that's 0.3%
> of the blockchain already.
>
> (Is 100 realistic, or would every node want a direct channel to a beacon,
> so that it would be more like 1000/beacon (100k nodes, 100 beacons)
> or more?)

I don't know.  I think that the most likely connects will be distant
nodes which are also hubs.  Deciding which ones to accept will be a fun
problem....

>> Good points.  If we reject all routes less than (say) 3 hops by default
>> it might mean that local payments are *less* efficient.  Oops.
>
> I was thinking, at least at this stage, that there wasn't any point
> differentiating local vs global payments; I'm hoping global payments are
> quick enough for buying a coffee anyway, and online microtransactions
> will probably be global anyway. And as above, I think route finding is
> separate enough that you can always improve it while leaving the lower
> layers (HTLCs and onion-forwarding) the same.

Indeed.  This conversation is about medium-to-long term.  For now,
everyone blasting their routes & fees on IRC is workable.

Cheers,
Rusty.


More information about the Lightning-dev mailing list