[Lightning-dev] New paper on ant routing

LEHÉRICY Gabriel gabriel.lehericy at devinci.fr
Wed Feb 12 10:11:38 UTC 2020


Hello ZmnSCPxj,

   Thank you for your comments, we are glad for your interest in our work. Below some answers to your comments.

  Concerning the information that intermediary nodes can gather from counters: We are working under the assumption of a large highly connected network (with thousands of nodes and node connection larger than 10, or nodes connected to highly connected nodes if they are newcomers).  Such a network has a very different geometry from the plane. In particular, triangulation is not feasible in general. Typically the distance between the majority of any pair of nodes is between 3 and 7 for a worldwide network. We want to obfuscate the counter to avoid giving information to immediate neighbours (that in principle are more trustable than others) about the origin or end of the transaction. Also, finding the shortest path in a highly connected graph is not our primary concern since most paths are quite short, which is why we are not considering optimization with a Dijkstra type algorithm.

Concerning spamming, this is unavoidable (as for the Bitcoin network) and scrutinity from nodes is required. Nodes are free to relay the seeds that they want. In particular, if a node N notices that one of its neighbours, say node M, starts spamming the network with pheromones (with a traffic much larger than its historical average share), then N can choose to ignore the seeds coming from M. It is even in N's best interest to be careful not to relay what he perceives as spams, because N itself could otherwise be branded as "spammer" by its neighbours. For this reason it is advisable for nodes to keep historic data on behaviour of neighbours and close the channels if they suspect them of acting maliciously (which can be revealed with the historical data).

Concerning payment failures: it was our understanding that the reason for the high failure rate of the current routing algorithm is because
Alice doesn't know the channel balances of other nodes, and thus cannot be sure that her choice of path has enough funds to forward her payment. Ant routing
solves this problem during the pheromone phase: a node  forwards the pheromone to a neighbour only if the channel balance allows the amount of the transaction to go through. This way, when Alice receives a matched seed, she is certain that the channel balances on the path have enough funds to forward her whole payment. It is also our understanding that the gossip network (that can also be a source of spamming) is used to update the channel balance in the routing tables. Note that the update of these channel balances, which seems necessary with the current routing, reveals and deanonimizes who has made transactions in the last period (and we can even reconstruct very easily a lot of transactions if updates are made often).

When you say "Distance measurements need not be in units of hops", I am not sure what you mean here, and why this is a problem; could you elaborate?

Concerning your "main objection": as you noticed, the size of pheromones is significantly less than bitcoin transactions (16 Bytes, as we indicate in the paper) and they are deleted after 3 seconds (this keeps the seed mempool small). Pheromone Ids can be so small because they only need to distinguish between the about 30k tx present in the seed mempool (for a regime of about 10k tx/sec). The purpose of our paper is to prove scalability up to 10.000 tx/sec, we don't claim anything else, and certainly not infinite scalability. In that regard,theoretical O-estimates seem irrelevant to us (any O-estimate is dependent of the implicit constants and the hardware used, and is only relevant when we aim for "infinite scalability"). In the paper, we have a more practical and direct approach and we use the Bitcoin network that scales to 5-7 tx/sec as a proxy for the flooding algorithm . The argument is given in Section 6 of the paper. If you have any objection to that section we will be glad to discuss it and we would like to understand why your objection does not apply to the Bitcoin network or the other networks that are given as examples.

Best,

The authors



________________________________
De : ZmnSCPxj <ZmnSCPxj at protonmail.com>
Envoyé : dimanche 9 février 2020 01:57
À : ZmnSCPxj <ZmnSCPxj at protonmail.com>
Cc : LEHÉRICY Gabriel <gabriel.lehericy at devinci.fr>; GRUNSPAN Cyril <cyril.grunspan at devinci.fr>; Ricardo Pérez Marco <ricardo.perez.marco at gmail.com>; lightning-dev at lists.linuxfoundation.org <lightning-dev at lists.linuxfoundation.org>
Objet : Re: [Lightning-dev] New paper on ant routing

Good morning Gabriel,

Some further thinking:

--

I notice as well that you propose to add a random number to the initial hop distance counter.
This does not quite obscure as much as you might think.

Suppose I have two nodes I control in the Lightning Network, which we will pretend is this blank sheet of paper.

    +------------------------------------------+
    |                                          |
    |                                          |
    |                                          |
    |                                          |
    |                                          |
    |                                          |
    |       X                          X       |
    |                                          |
    |                                          |
    |                                          |
    |                                          |
    |                                          |
    |                                          |
    |                                          |
    +------------------------------------------+

Now suppose my two nodes happen to receive the same pheromone, and the distance counters are equal.
I can then conclude that the originating node has the same distance to my two nodes, or:

    +------------------------------------------+
    |                    :                     |
    |                    :                     |
    |                    :                     |
    |                    :                     |
    |                    :                     |
    |                    :                     |
    |       X            :             X       |
    |                    :                     |
    |                    :                     |
    |                    :                     |
    |                    :                     |
    |                    :                     |
    |                    :                     |
    |                    :                     |
    +------------------------------------------+

The originating node is now known to be somewhere along the above dotted line.
(the same analysis can be done even if the distance counters received by both nodes are not equal: I can just take the difference between them, which automatically cancels out the random number you are trying to use to obscure the distance, and get an indicator of whether the dotted line should be nearer to one node or the other.)

Worse, if I have a *third* node, then I can get two more such lines, and then triangulate where the originator of the pheromone is.

You can bet that any surveillor is going to run multiple nodes.
So the added random number is just going to protect against single-node operators, but even medium-corporate-level surveillors will be able to run as few as 3 nodes on the network.
And since pheromones are broadcast to the *entire* network, 3 nodes is enough to make a mapping of pheromone-to-node.

Of course, the real Lightning Network is not a sheet of paper, so maybe 3 nodes will still not be enough, but a small number of nodes will be able to make such a mapping.
And of course since every node and channel in Ant Routing is unpublished, such a surveillor will still need to do some extra work to map out the network by other means.

--

An advantage of the current published network is that it automatically gives a way to discover other nodes you can connect to and make channels with.

This even gets spam-capping for free, since we only gossip about nodes which have a proof that they have at least one channel somewhere.

--

Channel rebalancing seems difficult with Ant Routing.
Rebalancing is basically making a payment to oneself, and the shortest path to yourself is to do nothing.

--

Nothing prevents someone spamming the network with pheromones for payments they are not going to receive anyway.
Creating pheromones for broadcast would have to be costly, but that now allows certain initiator-does-not-pay attacks where the sender keeps requesting invoices from the receiver, which creates a pheromone for each apparent invoice, but the sender does not actually make any payments.

--

One can observe that Dijkstra algorithm is a simulation of pheromones in Ant Routing, and is why Dijkstra can actually discover shortest paths.

Thus, one might consider Ant Routing to be a sort of "distributed Dijkstra".
We observe as well that, without an "early-out" case, Dijkstra really forms a shortest-path tree of the entire routemap.

Regards,
ZmnSCPxj


> Good morning Gabriel,
>
> Interesting idea and it helps to reduce routemap size by completely eliminating the routemap, and also removes distinctions between published and unpublished channels by making every channel unpublished.
> However there seem to be some considerations as well.
>
> -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> A node which is able to match the payee seed pheromone and the payer seed pheromone knows the total distance traversed between the payer and payee, and also knows exactly the distance between itself and the payee/payer.
> Admittedly this only gives an upper bound on the distance, but the pheromone system with its ability to find shorter and shorter paths will, over time, give such a matcher better and better information about distance to payer and payee.
> A surveillance node would deliberately defer broadcasting each pheromone it receives, in the hope that the matching pheromone reaches it as well and it can determine upper bounds on distance to both a payer and the corresponding payee.
>
> This can be fixed by having just the payee broadcast the pheromone, and have the payer wait for incoming pheromones from the payee.
> Further, it preserves the current privacy of the payer, which is much harder to find in the current Lightning Network source-pathfinding onion-routing scheme, and adds privacy to the payee (the payer only knows its distance to the payee, not the exact node ID of the payee).
>
> -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Having a single pheromone seed (or a pair of matched seeds) that is recognizable for the entire path prevents us from implementing any kind of path decorrelation.
> This is fine when considering just the current HTLCs (which have the same property that a single path is recognizable as being a single path solely from the hash used), but PTLCs can buy us some privacy (the entire path has no single "smoking gun" that identifies it, just coincidences like being near in sidereal time, having similar value, having decrementing locktime...), which is then lost with the pheromone system.
>
> It is unclear to me whether this is fixable: you would need something that intermediate nodes can malleate, but which the matcher (which, if we go with the above "only the payee sends out pheromones", the payer is the only possible matcher) must somehow still recognize and match to the payment.
>
> This is a big weakness of Ant Routing.
>
> ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> There have been some discussions as well of performing particularly complicated payment schemes by taking advantage of homomorphism of points and scalars, enabled by PTLCs.
> It is not clear to me as well if the pheromone system can help or hinder such schemes.
>
> ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Confirming the path length is an additional step.
> It can be elided by recognizing that the timelock component of the PTLC/HTLC routing must decrement at each hop.
>
> Suppose some node under-reports the distance that a pheromone travelled, in the hopes that the payment will go through them and they can earn fees thereby.
> The payer can allocate only enough timelock to cover the reported length.
> Since the true length of that path is actually longer, some other node will refuse to forward the payment due to insufficient timelock, and the payment fails and the under-reporting node will not earn fees anyway.
>
> Against this, however, we must caution that an under-reporting node might NOT be interested in earning fees, but instead to get payment statistics.
> Thus it would be able to "pheromone-hijack" and acquire information about the amount of the payment and its payment hash/point, even though it knows the payment cannot push through.
>
> So this is not a perfect solution in terms of privacy.
>
> -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Routing failures seem somewhat harder to handle.
> Because the payer itself does not know the whole path to the payee, it would be pointless to reveal which node actually failed to forward; the payer can do nothing about this information anyway.
> The payer can only just try with a different peer that has also reported the target pheromone.
>
> Against this, however, we can point out that we can reduce payment failures.
> The fact that a pheromone reached the payer recently indicates that the forwarding nodes along that path have also recently been online and working, so the chances of it going offline soon are expected to be low.
> Further, if a channel is imbalanced with most of the value owned by a forwarding node, the forwarding node can simply avoid sending a pheromone down that channel, since it would not be likely to be routable via that channel anyway.
>
> Perhaps in terms of failure, a forwarding node could also remember the second-lowest distance pheromone, and report a failure back as an increase in the effective pheromone distance along that path (or a "true failure" where it knows of no second-lower distance pheromone).
> Further a forwarding node which has received more than one equal-distance pheromone can just retry the HTLC along those pheromone distances.
> This is similar to how JIT Routing works, with payments effectively getting rerouted via alternate paths without telling the original payer the exact details of the payment rerouting.
>
> ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Distance measurements need not be in units of hops.
>
> ------------------------------------------------------
>
> Finally: a MAJOR objection against Ant Routing.
>
> The main reason why Lightning is a scaling solution is that it drastically reduces how many nodes you tell about a payment.
> Compare this to the blockchain layer, where every node has, at minimum, to be told about every confirmed transaction, and this is the reason why we have a block size limit in the first place.
>
> With Ant Routing, every payment needs to have a pheromone broadcasted.
> This pheromone will reach out to every part of the network.
> (Even with pheromones emitted at both the payer and payee end, it is likely that one or the other pheromone will reach the entire network.)
> Thus, we are still sending out data that has to reach each and every node on the network at each payment.
>
> This negates the big-O scaling achieved by Lightning.
>
> Admittedly, constant factors are much lower with Ant Routing and it may remain practical.
> If you use a pheromone emitted only by the payee, we can probably use just 160 bits or even 128 bits of entropy for the pheromone identifier; it only has to be a universally-unique identifier without any special mathematical properties, and the invoice could contain the pheromone identifier as well, thus reducing the communications rounds between payer and payee to a single communication, the invoice (same as current Lightning).
> The distance count could be a single byte (if we use units in terms of hops).
> This means 17 bytes broadcasted to the entire network per payment (compared to the hundred bytes or so needed per payment on the blockchain layer).
>
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> In summary, two main objections:
>
> -   Ant Routing sends data proportional to p payments to n nodes or O(pn).
>     Current source routing just sends data proportional to p payments to a constant limit of nodes or O(p).
>
> -   Surveillors can easily determine payments and the maximum distance to the destination and likely source.
>     This is same as current Lightning but we already have proposal (path decorrelation by using payment points) to remove it, it seems not to be useable with Ant Routing.
>
>     Regards,
>     ZmnSCPxj
>
>
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20200212/c17dd0e2/attachment-0001.html>


More information about the Lightning-dev mailing list