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 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 neglects the possibility that an intermediate node might propagate a pheromone outward, then suddenly the neighbors, who happen to be Alvin & the Chipmunks, blow up the street post that happens to be supporting the power supply going into the node before the payment could be routed through. Granted, the probability of an intermediate node happening to have Alvin & the Chipmunks as neighbors is exceedingly low, possibly below 1 in 2^128 , but I think the more general case of a node failing *after* it propagates a pheromone but *before* it could be routed through must be considered. Ant Routing makes this probability smaller, but does not eliminate it completely, and robust payment systems still need to handle this. If the payer only has a single channel, how can intermediate nodes help it find alternate routes? It seems to me that intermediate nodes need to store other pheromones with higher distance counters as well, not just the payer, in the extreme case where the payer has only one channel, intermediate nodes will have to assist the payer by saying "actually you have to adjust your distance estimate by +N now because something bad happened". And since you need to support retrying, you may need to extend your pheromone timeout from 3s. The additional memory and timeout probably means you have to shave off a 0 from your scaling estimates as well. -- Another thing: it is unreasonable as well to promote the assumption "the payee must be online to receive" to the assumption "the payee is *contactable by the payer* to receive". Consider this (hopefully very very common) case: * A fan decides to donate to me over Lightning and asks me (over IRC or email) for an invoice to donate to. * Since I am ZmnSCPxj, my node is only contactable over an .onion service and is not contactable over IPv4 or IPv6. * My fan, unfortunately, did not install Tor. Thus, while my node is *online*, it is *not contactable by the payer*. With the current Lightning Network, this is perfectly fine, because I only need to transmit a single invoice, and I can access email / IRC over Tor myself. With the Ant Routing proposal, the payer is now stymied as it needs some way to directly contact my node, and that means more engineering and implementation work to let a Tor-less payer contact a Tor-only payee. Any routing proposal that requires continuous communication between payer and payee, instead of a one-time send of an invoice from payee to payer, makes this unreasonable assumption. -- It seems to me you can use just a one-byte distance counter, if we assume that the network graph cannot have a diameter greater than 127 hops. This seems a reasonable assumption, given you are already assuming a well-connected network as well, which tends to reduce graph diameters. With wraparound, I can implement a less than operation based on subtraction modulo 256, then cast it to a signed byte and then use the sign bit to determine which of two distance counters is lesser or greater. Distances are expected to be small anyway, so any extra range in the original subtraction modulo whatever is wasted anyway. Regards, ZmnSCPxj _______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
