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 Netwo

[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