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 <zmnsc...@protonmail.com>
Envoyé : dimanche 9 février 2020 01:57
À : ZmnSCPxj <zmnsc...@protonmail.com>
Cc : LEHÉRICY Gabriel <gabriel.leher...@devinci.fr>; GRUNSPAN Cyril
<cyril.gruns...@devinci.fr>; Ricardo Pérez Marco
<ricardo.perez.ma...@gmail.com>; lightning-dev@lists.linuxfoundation.org
<lightning-dev@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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
_______________________________________________
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
