[Lightning-dev] Ionization Protocol: Flood Routing

[Anthony Towns]

On Fri, Sep 25, 2015 at 06:26:55AM +0930, Rusty Russell wrote:
> >> >> There are some twisty details here:
> >> >> 1) How many beacon nodes?
> >> >>    12, and increase on a log scale with network size.  That size can
> >> >>    be derived from previous beacons.
> >> > I think it's also something you could set per-node, like the
> >> > minrelaytxfee.
> >> That doesn't make sense, since we need to agree on who is a beacon.
> > If you have the top 10 beacons and I have the top 14 beacons, we have
> > the top 10 beacons in common. During the gossip phase, if either of us
> > see someone in the top 10, we pass it along; I pass along a few more as
> > well.
> If I want to pay you, and you give me those 4 beacons I don't accept, we
> break down.

I have 14 beacons, and I know the order in which you're most likely
to have them. If I know you can choose how many beacons you track,
why would I give you the four you're least likely to have (because you
have a lower limit, or because you've heard of four better beacons that
haven't made it to me yet)?

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.

> >> >> 2) How long between selection and a beacon becoming active?
> >> >>    10 blocks.  That gives time for others to connect to beacon node.
> >> > Beacons can be "active" as soon as you can route through them, and that's
> >> > just a DHT lookup to determine, and then a matter of comparing fees to
> >> > what the old beacons give you. So I think no artificial delay is needed,
> >> > and the real question is just when you expire your routes to/from the
> >> > old beacons?
> >> No.  Beacons will get saturated fast unless they have a chance to
> >> prepare.
> > Sure. I was thinking you have to volunteer to be a beacon, ie something
> > like:
> >
> >   1) commit to node id (anchor transaction in blockchain)
> >   2) commit to ordering (abs difference of node id versus 
> >      sha of latest blockchain block with (depth % 2016 == 0))
> >   3) volunteer to be a beacon (sign "imma beacon! depth $n anchor
> >      $txid")
> >   4) gossip (including your signed volunteer statement) and hope you're
> >      in the top 12
> > Any preparation (opening new channels etc happens between (2) and (3)),
> > transactions happen immediately after (4).
> We don't want to have to maintain a table of volunteers, hence 3 & 4 are
> merged (simple optimization: delay advertising yourself as a beacon
> longer if it's less likely).

If you want to do any setup, I think you need to advertise yourself as
a beacon to the people you want to setup with. I'm thinking that if you
win the beacon lottery, you'll want to say "hi, I'm about to be a beacon"
so people will setup channels with you without you having to put much
initial investment in that channel. The people setting up channels with
you see a bunch of people doing that, and will only want to deal with the
top 12 or so. I'm not sure that's much different to actually advertising?

> Then by convention you delay 10 blocks before using a beacon.  By that
> time, routes should be sufficient.

I wouldn't have thought 10 blocks was long enough to setup a new channel
especially to a beacon, fwiw. (If you can create a channel to a beacon
with the beacon's side initially 0, spend all that money back to yourself,
then reorg with a doublespend of the anchor inputs so the channel never
existed, you can steal the beacon's pre-existing savings. The routing's
trivial -- it's you to the beacon, and then each of your neighbours will
tell you the cheapest path from a beacon to them as soon as they know it)

> > So... doesn't this provide a /really/ juicy target for hackers? Either
> > of the "let's steal funds" variety, or of the "let's find out as much
> > info about every transaction as we can" type?
> >
> > If you just have to hack 12 systems to observe/DoS 100% of lightning
> > network transactions, that seems worrying to me. I think I'd want to avoid
> > being a beacon in that case, just to avoid painting a target on my system.
> >
> > I'm not sure if it's a realistic attack model, but if you can observe:
> >
> >   Bob -> Alice: pay me $20 to R (routes to current beacons: ...)
> >
> > and have control of the beacon Alice ends up using, then you can both
> > observe that Alice is trying to make the payment (you see an HTLC with
> > $20 and R), and prevent Alice from making the payment (you can just not
> > forward any transactions involving R).
> Sure.  But if you can observe the private conversation between Bob and
> Alice, *and* you control enough nodes that you're likely to be the
> beacon they choose, you don't need to be a beacon to block them :)

You don't have to control the nodes initially, you just have to attack
the beacons once they're announced. If they're accepting new channels,
then they've announced an IP. If you get an exploit on a node that
would have been #15 in the ranking, you just have to DoS three higher
ranked beacons to get it to have traffic.

> > Without beacons (but routing still being possible somehow!), Bob could
> > anonymously post prices and R values in public; Alice could observe them
> > anonymously without giving away that she was observing them, and Mallory
> > could not prevent Alice from paying Bob, without controlling Alice or Bob,
> > or a large proportion of the lightning network as a whole. Bob could be
> > a dissident asking for donations in this scenario, eg.
> Yes!  I've been wondering about this kind of "donation address"
> scenario.  Turns out you can encode the R value in the onion routed
> message you send, too.  Only the final recipient can read it anyway.

Yep.

> That doesn't help with routing to the donation address; maybe we will
> need a best-effort DHT for that?

If you've got a route, but no fee information; you could probe the
route with nanopayments. ie, to move $10 along me->A->B->C->D, first
try sending 0.01c to B with a 0.1% then a 0.2% fee, etc. Once you know
A's fee, repeat with B, then C. If the fees end up as 1%, 2% and 0.2%
your successful transactions are:

  0.01c to B plus 0.0001c to A
  0.01c to C plus 0.0001c to A plus 0.0002c to B
  0.01c to D plus 0.0001c to A plus 0.0002c to B plus 0.00002c to C
  $10 to D plus 10c to A plus 20c to B plus 2c to C

and the txs that had smaller fees just bounce back to you.

Totals:
  $10 to D and also
   0.01c to D
   2.01002c to C
  20.0014c to B
  10.0003c to A

for a total of $10 and 32.02172c.

0.2c = 860 satoshi, but lightning handles milli-satoshi now, so 0.0002c
= 860 msat and 0.00002c = 86 msat, so all those fees are expressible,
and the probing only increases your fees by 0.06%. If I'd been sending
10c instead of $10 but used the same nanotransaction probing I would've
paid 0.34172c instead of .32c in fees for a 6% increase in fees. So
pretty plausible even then.

(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)

> > ie, nodes do payment forwarding; wallets just spend/recieve. You'd use
> > your phone as just a wallet, but you might run a node at home or in
> > the cloud. Wallets still do the lightning protocol themselves, they just
> > don't earn fees by forwarding payments.
> I think you do want to 

"run a node on your phone" ?

In order to gain node-like return on your investment, I think you'd have
to be constantly active -- so updating your routes, tracking beacons,
etc. You'd miss out on ever being a beacon presumably, which would
pretty severely cut into your income to nodes that are beacons -- though
maybe you could sell your beacon-worthy private keys and recoup some of
that? I don't see how anyone would feel confident to buy your private
keys though.

Your phone would need to be doing fairly constant network access while
it was in your pocket as it forwarded HTLCs; 24k transactions per second
over a million nodes at 5 non-beacon hops is still around 7 tx/minute
for a random node. Each of those comes with multiple crypto ops as
well. So you'd be burning battery afaics. If you're only doing it while
you're plugged into AC, then I'd expect your ROI to drop proportionately
(so instead of $10 from $100 over a year, maybe $3.50 if you leave your
phone on charge every night).

It'd also up the latency for people routed through you a fair bit;
phones aren't that fast, and aren't that well connected. So any payment
routed over one would be that much slower than one that went via servers
on fibre. If you're slow to process a transaction and more likely to
lose connectivity, that ups the chances of an HTLC stalling -- you've
accepted it, but you lost connectivity while trying to forward it, so
everyone else is out of pocket until you get signal back.

Forwarding also introduces the risk that all your funds are tied up in
active HTLCs when you want to buy a coffee.

I just don't think everyone running a full node trying to make a profit
off routing is realistic.

> > Aside: "mesh network" seems to be a much better description than
> > hub-and-spoke... cf
> > https://www.reddit.com/r/Bitcoin/comments/3lo8mb/serious_question_for_blockstreamcom_will_you_let/
> Thanks for that: I'd somehow missed that troll.

Seemed like a legit question to me *shrug*. There's a corresponding thread
(same title) on BitcoinXT, if you really want to feel trolled.

There's also:

  /r/lightningnetwork: The Bitcoin Lightning Network

  This sub-reddit is dedicated to corporate interests trying to take over
  the decentralized world-wide ledger.

No posts unfortunately...

> >> That's a very different architecture,
> > I'm just using it as terminology (I think...).
> > The only architectural implication is that I'm assuming "most" people
> > (24999 out of 25000) don't end up doing routing. Given routing nodes
> > have to be online with hot keys and thus risk being hacked and having
> > their funds drained, I think that's fairly plausible?
> But that risk also describes a wallet.

I don't think so: if I'm only sending/receiving money, I can be offline
for the entire time I'm not doing transactions. For consumers, that's
(potentially) most of the time; for merchants, that's at least when the
business is closed (not much benefit for 24/7 online businesses though).

> And if you route, you potentially gain funds as well as privacy.

It'll only gain you a percentage of what you've got in the channel though
(or that's what I expect anyway). If you're a consumer who keeps $100 in
your wallet, that's maybe $10 in a year. But to earn that $10 you have to
worry about keeping you wallet secure and online, which I'd expect isn't
worth it. For a phone, that could be compromised by plugging it into a USB
port for power, or a flaw in a carrier's version of android, or privilege
escalation from some random app, I'd rather have it be offline and safe
for the 99% of the time I'm not buying anything.

(Caveat one: Maybe phones are so insecure there's no way to have a private
key that's reasonably convenient, but also "safe" while "offline". You
could mitigate that by introducing a second factor; having $10 on your
phone most of the time -- coffee and bus fare money, that you don't care
much if someone steals -- but having a secondary lightning wallet that
you can only use by tapping a crypto-NFC smartcard for when you want to
pay for dinner or recharge your primary wallet, eg. Having your phone
be secure directly would be better though)

(Caveat two: There's no reason not to forward transactions while you're
online and your private keys are in memory -- err, assuming they don't
lock up too many funds anyway; I just think there's good reason to be
online as little as possible)

As far as privacy goes I think you could tell which of your neighbours
is using lightning primarily as a wallet versus trying to be a
profit-generating node fairly easily: wallets will have smaller channels,
there'll be fewer transactions over them, and they'll disconnect more
often. That doesn't guarantee they're not forwarding things; but if they
are they're almost certainly arranging it out of band anyway (even if
only to know when they'll be online and thus able to forward).

(I actually think arguing the other way might make a bit of sense; if
you're running a node, you should pay profits and expenses to/from an
entirely separate lightning wallet)

> > (Or going the other way; if you're making money running a node, I think
> > it's pretty reasonable you'll try to serve on the order of 100k users
> > -- much less than that and you'll be under utilising your hardware. But
> > with only 8B potential customers, there's a limit on the number of nodes
> > that can actually do that, as calculated above. I'm assuming economics
> > somehow ends up enforcing that limit effectively)
> >
> >> which uses hosted wallets or something?  I don't think that's very
> >> interesting.
> >
> > Not hosted wallets; more along the lines of SPV clients, where you're
> > relying on the network to do most of the work (in this case working out
> > a cheap route, rather than verifying txns)?
> But the "give me a cheap route" question is exactly the same whatever
> your role.  It's "give me all your routes to beacons".

I was talking about the beacon-less alternative here, where nodes have
the full weighted-directed-graph of channels and fees to work out a route.

> That's a few hundred routes.

Also, with beacons, you don't need to know all their routes to beacons,
just their cheapest route to each beacon, so that should be just 12
routes (unless we're working with a few hundred beacons now?). No
matter which route from them, it'll always just be the same You<->Them
channel beforehand, so cheapest via them will just be that plus their
cheapest. You need to keep all your neighbours' cheapest routes to
fall back on if someone else raises fees though, if you're not willing
to repoll.

Cheers,
aj