Better privacy for sender when making LN payments

[addressleakt]

Privacy problem

I have only private channels from my node and one of them is with Merchant (autopilot did it, not my fault). I pay an invoice from my node to Merchant and Merchant can see that it comes from the private channel I have with them. As the merchant did not include this private channel in the bolt11 as a route hint they can be pretty sure that it was my node who is the one who paid and that it was not a payment I relayed for someone else.

Solution

Make sure that the payment is relayed through at least X hops before it reaches its destination.

Solution today

This can be solved today by taking the node id and amount from the bolt 11 invoice, send it to queryroutes, removing any routes with not enough hops and then pay it with sendtoroute.

Proposed future solution

An easier solution for the user would be to add an option to sendpayment to specify minimum amount of hops. For example "--min_hops 3"

[Crypt-iQ]

Taking this one

[Crypt-iQ]

I can't think of a straightforward way to solve this problem. The use case described in the issue needs a way to use the sendpayment call with at least 2 hops. Otherwise it's trivial for the merchant to deanonymize the sender. But if we want to allow min_hops to be set to any value, things get tricky!

The queryroutes call uses Yen's algorithm which is not guaranteed to determine a minimum number of hops, just k shortest paths with weight as the distance. Using Yen's algorithm might require multiple iterations with increasing k if none of the k shortest paths have enough hops. This is iffy at best IMO.

My suggestion is that when the min_hops flag is specified, a modified path finding algorithm is used. If an initial run of Djikstra's algorithm fails to return a route with enough hops, we use this new path finding algorithm. This algorithm would use a product construction on our graph G = (V, E). The new graph would be G' = (V', E') where V' = V x {0, 1, 2, ..., 20} and E' = {((v, i), (w, i+1)) : (v, w) in E}. When provided min_hops, it would then try to find the shortest path (using Djikstra's?) from source (s, 0) to target (t, k) where k >= min_hops. For example, if the shortest path from (s, 0) to (t, 15) is less than all other shortest paths from (s, 0) to (t, k), the algorithm would return the path from (s, 0) to (t, 15).

I think this would work and has a worst-case complexity of O(k * (E+V *logV)). The resulting product graph might be large though. Comments appreciated!

Related:

1. https://en.wikipedia.org/wiki/Cartesian_product_of_graphs
2. https://cs.stackexchange.com/questions/53192/dijkstras-algorithm-to-compute-shortest-paths-using-k-edges

[Crypt-iQ]

Since we don't allow cycles, I think the above is NP-Complete. The use case described in the issue really just needs hops != 1 so we can just find two paths using Yen's k=2 and take the second one if the shortest path is 1 hop.

[Crypt-iQ]

Since findPaths is going to be deprecated in the next release and I don't think adding another complex path finding algorithm is the solution. I think this can be solved by having a restriction to findPath which ensures the payment is not via a direct channel to the target. This could also be solved via pegged hops #2444 but that also uses findPaths, and finding a hop to go through requires more work for the end user.

If a user has a channel with the target, this could also be solved by having an outgoing channel restriction that is not with the target, but this requires knowing that one has a channel with the target and then choosing an outgoing channel. In cases where the user doesn't know that they have a channel with the target or if they do, don't want to perform more mental work (i.e. choosing an outgoing chan), then adding an --indirect flag to sendpayment would suffice.

[addressleakt]

Thank you Crypt-IQ, I also think --indirect would suffice.

[saubyk]

Closing this issue as the problem is better posed to and addressed at the spec level, rather than coming up with implementation level "hack"