From ZmnSCPxj at protonmail.com Sun Feb 9 00:57:24 2020 From: ZmnSCPxj at protonmail.com (ZmnSCPxj) Date: Sun, 09 Feb 2020 00:57:24 +0000 Subject: [Lightning-dev] New paper on ant routing In-Reply-To: References: Message-ID: <_Hg2RxjffacuScYcnJZu_ItoWo9onrxkNS9Nv6Oyv7dghlOim0e3xz2yn2lOuHCpv30Wa5EcqpD5vWrvaazVh3IzJ3ULfab09S7f7MpIzfk=@protonmail.com> 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