Re: [Lightning-dev] New paper on ant routing

[ZmnSCPxj via Lightning-dev]

Good morning again The Authors,

> >   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.
>
> Assuming a space whose dimensionality approaches infinity, yes, you are 
> correct.
> But not all nodes will have significant numbers of channels, and there may be 
> sections of the network that are more "plane"-like than the assumed inifinite 
> number of dimensions, meaning a limited number of nodes can be used to 
> usefully triangulate.
> It seems unreasonable to assume an infinite number of dimensions given that 
> each node will only have a finite number of channels, thus I suspect there is 
> some number of nodes that can usefully triangulate each and every pheromone.
> That number could be impractically high for most, but seems to be less than 
> infinity.
> (In particular, the blocksize limit also limits the number of channels, thus 
> limits how many possible dimensions the graph will have on average.)

A reason why I think it is unreasonable to assume that this kind of 
triangulation is possible is the existence of the Dandelion proposal for the 
Bitcoin network.

Consider that when a Bitcoin node broadcasts a transaction, what it really does 
is that it selects an arbitrary large number, in units of Planck intervals 
since the Epoch (i.e. the Big Bang), more commonly known by mere humans as "the 
current time".
Then, surveillance nodes on the Bitoin network receive the transaction with 
this counter updated by some delta number-of-Planck-intervals-since-the-Epoch.
Cooperating surveillance nodes can then compare the number at which they got 
the transaction with each other, in order to guess which node on the Bitcoin 
network originally broadcasted the transaction.

My understanding is that this triangulation is successful often enough to be a 
problem for privacy, which is why Dandelion even *exists*.
Admittedly, this is just SPV-level verification (I am looking at the fact that 
people have poured work into Dandelion and from there assume that "people can 
traingulate the broadcaster of the transaction in the Bitcoin network" is in 
fact true, without actually validating that myself).

Since the same analysis is basically possible with Ant Routing using units of 
hops rather than Planck-intervals-since-the-Epoch, I think you still have the 
same basic problem that Dandelion is solving, assuming of course that the fact 
that Dandelion exists and is being worked on implies the problem actually 
exists.

(I guess this is where the "Distance counters need not be in units of hops" 
trap card triggers.)

More importantly: on the Bitcoin network, a node can drop a connection with a 
peer and then select a new node to connect with, at very little cost or risk.
On the Lightning network, a node closing a channel and then re-opening 
elsewhere is significantly more costly and time-consuming and risky.
This means that any probes on the network topology of Lightning are likely to 
remain valid for longer than probes on the topology of Bitcoin network, meaning 
we expect this kind of triangulation to be *easier* on Lightning than on 
Bitcoin, simply because of the greater permanence of channels vs connections.

Fortunately, the fact that Dandelion exists means you can probably just reuse 
it here.
When a payee wants to broadcast a pheromone, it instead sends it to one peer 
with the "stem" flag set.
When a node receives a pheromone with the "stem" flag set, it randomly promotes 
it to "fluff" stage and broadcasts it itself, or sends it out again to one 
other peer with the "stem" flag still set.
Additional tooling will be needed to ensure a stem does not get stuck, and so 
on, I am sure the people working on Dandelion can give you additional details.
This misleads triangulation and strengthens the obfuscation you add to the 
distance counters.


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

Re: [Lightning-dev] New paper on ant routing

[ZmnSCPxj via Lightning-dev]

 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.

The Bitcoin network only propagates a transaction if it:

* Does not spend any UTXOs that are currently spent by any transaction in the 
mempool.
* OR, if it does, has a higher fee than the transactions it would remove from 
the mempool.

The number of UTXOs is finitely bounded by the existing history of the 
blockchain, and transactions can kick out transactions they double-spend only 
if they pay a higher fee, and nobody owns infinite bitcoins, so at *some* point 
you will be unable to propagate a transaction that spends the finite number of 
UTXOs you control: the total amount in those UTXOs bounds your ability to spam 
the network with more transactions.
Or: fees bound your ability to spam.
(Others may be better able to correct or more accurately present the 
spam-mitigations done by Bitcoin, but I think the above is a rough "broad 
strokes" correct.)

The current Lightning Network gossip reuses the above "fee limits your ability 
to spam" by requiring that a deeply confirmed transaction output commit to your 
channel, and you are allowed to output only so much data about this channel.
If you want to push more data into the gossip network, you need to have more 
confirmed transactions, and it is the fees involved in confirming at the 
blockchain layer which limits your ability to spam the Lightning gossip network.

No such fee-based limit exists for Ant routing, though I admit your proposals 
for otherwise limiting rates of pheromones appear sound (but I am no expert on 
spam-mitigation; what we normally do is require that people prove they have 
some funds in a Lightning channel, so anything not based on that is not 
something I have much experience using).


Regards,
ZmnSCPxj

> Best,
> The authors
>
>  
>
> De : ZmnSCPxj 
>
> Envoyé : dimanche 9 février 2020 01:57
>
> À : ZmnSCPxj 
>
> Cc : LEHÉRICY Gabriel ; GRUNSPAN Cyril 
> ; Ricardo Pérez Marco 
> ; 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:
&

Re: [Lightning-dev] New paper on ant routing

[LEHÉRICY Gabriel]

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 
Envoyé : dimanche 9 février 2020 01:57
À : ZmnSCPxj 
Cc : LEHÉRICY Gabriel ; GRUNSPAN Cyril 
; Ricardo Pérez Marco 
; 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 wi

Re: [Lightning-dev] New paper on ant routing

[ZmnSCPxj via Lightning-dev]

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.
>
> 

Re: [Lightning-dev] New paper on ant routing

[ZmnSCPxj via Lightning-dev]

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 

[Lightning-dev] New paper on ant routing

[LEHÉRICY Gabriel]

Dear All,

  I would like to announce our new paper on the ant routing algorithm for the 
lightning network. The paper is available online here:
https://arxiv.org/abs/2002.01374. It gives an estimate for the scalability of 
the ant routing algorithm.

  If you have any question regarding our work, I will be happy to answer them 
via email.

  Sincerely,

  Gabriel Lehéricy

[https://storage.letsignit.com/5bbf3d27229c7c0001b516ac/logo_5bbf3d27229c7c0001b516ac_a703125b9809706c7ecf086c8d1f365b.png]
 Gabriel LEHÉRICY
Enseignant Chercheur
Département Ingénierie Financière
Retrouvez-nous sur 
esilv.fr
[https://storage.letsignit.com/5bbf3d27229c7c0001b516ac/logo_5bbf3d27229c7c0001b516ac_fa26d4badf2c6377bc99410d39ab3e86.png]
 

 
[https://storage.letsignit.com/5bbf3d27229c7c0001b516ac/logo_5bbf3d27229c7c0001b516ac_30a7735a477788d7833988f38fa47b90.png]
  

 
[https://storage.letsignit.com/5bbf3d27229c7c0001b516ac/logo_5bbf3d27229c7c0001b516ac_959dfa6c5ceef1acde39b485b1e8493e.png]
  

 
[https://storage.letsignit.com/5bbf3d27229c7c0001b516ac/logo_5bbf3d27229c7c0001b516ac_c4b2fc296b83f99e6fc2b58a412ed46c.png]
  

 
[https://storage.letsignit.com/5bbf3d27229c7c0001b516ac/logo_5bbf3d27229c7c0001b516ac_f357ead540d478d5ef45625e199c4e1d.png]
  


___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev