Re: [Lightning-dev] Outsourcing route computation with trampoline payments
Good morning Christian, First: > Like mentioned above the entire job of trampolines is to provide base > routing capability, and we should not make special provisions for myopic > trampoline nodes, since routing is their entire reason for existence :-) The point of providing this special provision is to increase the anonymity set of full-routemap nodes. Suppose we were to require that myopic routing nodes fail if they are unable to see the next trampoline. Then it becomes possible to profile the network and identify full-routemap vs. myopic routing nodes. Myopic routing nodes are more likely to fail than full-routemap nodes. In particular, full-routemap nodes are particularly juicy targets for attackers who wish to disrupt the Lightning Network once the LN grows in size. This is even worse if we end up proposing that full-routemap nodes announce themselves as such on gossip. Then attackers do not even need to profile the network; listening to gossip is enough to identify full-routemap targets to attack. In a world where we allow myopic routing nodes to delegate instead of fail, then it becomes much harder for a third party to profile the network. Myopic routing nodes would only have slightly higher failure rate than full-routemap nodes, possibly within the noise level, making it hard for third parties to definitely differentiate full-routemap nodes from myopic routing nodes. Anonymity loves company, and the protection of the deity Anonymous is a tremendous boon in sustaining systems from attack and censure. Another advantage of allowing myopic routing nodes to delegate is that it allows myopia to be a relative condition rather than a binary "either I know the whole routemap or not". That is, I can have 90%, 75%, 50%, 25%, 10$, or 1% of the routemap, and still I can participate in supporting the network by at least helping route to those nodes that I can route to, or delegating to someone else who might know that part of the network better than I do. This provides more graceful degradation of service than the binary "full-routemap or not" you propose. In particular, as the LN grows, fewer and fewer nodes will be able to have a full routemap, and they will have larger and larger targets painted on their back as points of attack. Another point: > I think we should not try to recover from a node not finding the next > hop in the trampoline, and rather expect trampolines to have reasonable > uptime (required anyway) and have an up to date routing table But with myopic trampoline nodes, the only requirement is high uptime; completeness of the routing table becomes unimportant. This means that selecting good trampoline nodes only requires one desiderata (high uptime). In particular, high uptime can be easily measured (just attempt to connect or ping), but completeness of routing table is not. Then: > (that's > what we're paying them for after all). This contradicts your position in the other sub-thread of this topic: > This is not an issue. Like we discussed for the multi-part payments the HTLCs > still resolve correctly, though node B might chose to short circuit the > payment it'll also clear the HTLCs through E And D (by failing them instead > of settling them) but the overall payment remains atomic and end-to-end > secure. The skipped nodes (which may include the trampoline) may lose a bit > of fees, but that is not in any way different than a failed payment attempt > that is being retried from the sender :-) In that case, E is a full-routemap node, while B may or may not be a full-routemap node, but B gets paid (more!) while E does not. E took the effort to find a route while all B did was pass the onion to the next. What gives? But regardless --- I would like to point out that it is still incentive-compatible to support myopic trampoline nodes, and that full-routemap nodes will be paid much more than a myopic trampoline node. Suppose a trampoline node is a full-routemap node. In exchange for the service of providing routes, it expects to be allocated a higher fee. Then the routing fee of nodes between it and the next trampoline node are deducted from the fee allocated to it. In particular, it will refuse to continue payment if it does not get a higher-than-normal fee for its own hop. After all, it must be paid for this service, as you insist. Suppose a trampoline node is a myopic node, that knows the next trampoline is not in its routemap, but considers that another node (the delegatee) is more likely to know the next trampoline that it does. In such a case, that myopic node would consider it more optimal to allocate only a small amount of fee for its own hop and to devote most of the fee to the delegatee. This increases the chance that the delegatee, if it knows the route to the next trampoline, will accept and continue routing. Its alternative would be to allocate too low a fee to the delegatee, leading the delegatee to reject the routing, which
Re: [Lightning-dev] Outsourcing route computation with trampoline payments
Hi ZmnSCPzj, I think we should not try to recover from a node not finding the next hop in the trampoline, and rather expect trampolines to have reasonable uptime (required anyway) and have an up to date routing table (that's what we're paying them for after all). So I'd rather propose reusing the existing onion construction as is and expect the trampolines to fail a payment if they can't find the next hop. Let's take the following route for example (upper case letters represent trampolines): ``` a -> b -> c -> D -> e -> f -> G -> h -> i -> j ``` With `a` being the sender, and `j` being the recipient. `D` and `G` are trampolines. The sender `a` selects trampolines `D` and `G` at random from their partial (possibly outdated) routing table. It creates the inner onion using those two trampolines. It then computes a route to `D` (`a -> b -> c -> D`). The `hop_payload` for `D` is a TLV payload that has a single key `t` (assuming `t` is assigned in the TLV spec) that contains the inner onion. It then initiates the payment using this nested onion (`a -> b -> c -> D` + trampoline payload for `D`). Upon receiving the onion `D` decrypts the outer onion to find the TLV payload containing the `t` entry, which indicates that it should act as a trampoline. It then decodes the inner trampoline onion and finds the `node_id` of `G`. `D` then computes the outer onion to the next trampoline `D -> e -> f -> G`, and adds the trampoline payload for `G` (the inner trampoline onion we just decoded). Upon receiving the onion `G` processes the onion like normal, finding again an inner trampoline onion and decrypting it. Since `j` did not indicate that it understands the trampoline protocol, `G` is instructed to downgrade the onion into a normal non-trampoline onion (don't include a trampoline, rather include the raw payload for `j`). It then computes the route to `j`, and it creates a normal outer base routing onion `G -> h -> i -> j`, which completes the protocol. Like mentioned above the entire job of trampolines is to provide base routing capability, and we should not make special provisions for myopic trampoline nodes, since routing is their entire reason for existence :-) Cheers, Christian >> Could this be implemented by replacing only the front of the >> trampoline-level onion? >> (presumably with some adjustment of how the HMAC is computed for the new >> trampoline layer) > > I am trying to design a trampoline-level onion that would allow replacement > of the first hop of the onion. > > Below is what I came up with. > As I am neither a cryptographer nor a mathematician, I am unable to consider, > whether this may have some problem in security. > > Now the "normal" onion, the first hop is encrypted to the recipient. > > I propose that for the "inner" trampoline-level onion, the first hop be sent > "in the clear". > I think this is still secure, as the "inner" trampoline-level onion will > still be wrapped by the outer link-level onion, which would still encrypt it. > > When a node receives a trampoline-level onion, it checks if it is the first > hop. > If it is, then it decrypts the rest of the onion and tries to route to the > next trampoline-level node. > If not, then it is being delegated to, to find the trampoline. > > If the node cannot find the front of the trampoline-level onion, then it can > route it to another node that it suspects is more likely to know the > destination (such as the mechanisms in discussion in the "Routemap Scaling" > thread). > > Let me provide a concrete example. > > Payer Z creates a trampoline-level onion C->D->E: > > C | Z | encrypt(Z * C, D | encrypt(Z * D, E)) > > Then Z routes to link-level onion A->B->C, with the payload to C being the > above trampoline-level onion: > > encrypt(Z * A, "link level" | B | encrypt(Z * B, "link level" | C | encrypt(Z > * C, "trampoline level" | C | Z | encrypt(Z * C, D | encrypt(Z * D, E) > > Upon reaching C, it sees it is given a trampoline-level onion, and if C is > unable to find D in its local map, it can delegate it to some other node. > > For example, if C thinks its neighbor M knows D, it can create: > > encrypt(C * M, "link level" | M | encrypt(C * M, "trampoline level" | D | Z | > encrypt(Z * D, E))) > > M finds that it is not the first hop in the trampoline-level onion. > So M finds a route to D, for example via M->N->D, and gives: > > encrypt(M * N, "link level" | D | encrypt(M * D, "trampoline level" | D | Z | > encrypt(Z * D, E))) > > Is this workable? > Note that it seems to encounter the same problem as Rendezvous Routing. > I assume it is possible to do this somehow (else how would hidden services in > Tor work?), but the details, I am uncertain of. > I only play a cryptographer on Internet. > > Regards, > ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Outsourcing route computation with trampoline payments
On Wed, 3 Apr 2019, 05:42 ZmnSCPxj via Lightning-dev < lightning-dev@lists.linuxfoundation.org> wrote: > Good morning Pierre and list, > > > There is another unrelated issue: because trampoline nodes don't know > > anything about what happened before they received the onion, they may > > unintentionnaly create overlapping routes. So we can't simply use the > > payment_hash as we currently do, we would have to use something a bit > > more elaborate. > > Just to be clear, the issue is for example with a network like: > > > A --- B C > / \ > / \ >/ \ > / \ > D --- E > > Then, A creates an inner trampoline onion "E->C", and an outer onion > "A->B->E". > > E, on receiving the inner trampoline onion "E->C", finds that E->B > direction is low capacity, so routes over the outer onion "E->D->B->C" with > inner trampoline onion "C". > > This creates an overall route A->B->E->D->B->C. > > When the B->C HTLC is resolved, B can instead claim the A->B HTLC and just > fail the D->B HTLC, thereby removing D and E from the route and claiming > their fees, even though they participated in the route. > This is not an issue. Like we discussed for the multi-part payments the HTLCs still resolve correctly, though node B might chose to short circuit the payment it'll also clear the HTLCs through E And D (by failing them instead of settling them) but the overall payment remains atomic and end-to-end secure. The skipped nodes (which may include the trampoline) may lose a bit of fees, but that is not in any way different than a failed payment attempt that is being retried from the sender :-) > ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Outsourcing route computation with trampoline payments
Good morning Christian,
>
> There are two ways we can use this:
>
> - A simple variant in which we just tell a single trampoline what the
> intended recipient is (just a pubkey, and an amount) and it'll find a
> route.
>
> - A complex variant in which a trampoline is given a next hop, and a
> smaller onion to pass along to the next hop. The trampoline doesn't
> learn the intended recipient, but can still route it.
The simple variant definitely tells the trampoline who the payee is, so I would
reject it.
> Multi-trampoline routing
> =
>
> The more complex proposal involves nesting a smaller onion into the
> outer routing onion. For this the sender generates a small onion of, for
> example, 10 hops whose length is only 650 bytes instead of the 20 hops
> for the outer routing onion. The hops in the inner/smaller onion do not
> have to be adjacent to each other, i.e., they can be picked randomly
> from the set of known nodes and there doesn't need to be a channel
> between two consecutive hops, unlike in the outer/routing onion. The
> hops in the smaller onion are called trampolines `t_1` to `t_10`.
>
> The construction of the smaller onion can be identical to the
> construction of the routing onion, just needs its size adjusted. The
> sender then picks a random trampoline node `t_0` in its known
> neighborhood and generates a routing onion containing the smaller onion
> as payload to `t_0` and signaling data (final recipient, amount, inner
> onion). Upon receiving an incoming payment with trampoline instructions
> a trampoline `t_i` unwraps the inner onion, which yields the next
> trampoline `t_{i+1}` node_id. The trampoline then finds a route to
> `t_{i+1}`, serializing the inner onion (which was unwrapped and is now
> destined for `t_{i+1}`) and creating the outer routing onion with that
> as the payload. Notice that, like in the simple variant, `t_i` generates
> a new outer onion, which means we don't have any issues with shared
> secrets and HMACs like in rendezvous routing. Resolution is also
> identical to above.
>
> This construction reuses all the onion primitives we already have, and
> it allows us to bounce a payment through multiple trampolines without
> them learning their position in this nested path. The sender does
> not have to have a total view of the network topology, just have a
> reasonable chance that two consecutive trampolines can find a route to
> each other, i.e., don't use mobile phone as trampolines :-)
Naively, would it not be possible?
Suppose a mobile phone keeps only a small subset of the routemap due to memory
constraints, but has high uptime because it is the precious mobile device of
somebody who uses the mobile phone at all hours.
When the mobile phone trampoline is unable to route to the next trampoline,
could it not "delegate" this by looking for some node in its smaller routemap
that it believes (by some other mechanism) to be more likely to route to the
next trampoline?
Could this be implemented by replacing only the front of the trampoline-level
onion?
(presumably with some adjustment of how the HMAC is computed for the new
trampoline layer)
If we will change to use trampoline-level onions then maybe we can change
things somewhat to support this usage better.
Otherwise it would seem that possible trampolines would have to advertise
themselves as such.
It would be better if a trampoline could be just "taken out of a hat" and
selected randomly.
And as long as the trampoline is able to *delegate* the routing to some other
trampoline, and there is sufficient fee, payment can succeed.
Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Outsourcing route computation with trampoline payments
Thanks Pierre for this awesome proposal, I think we're onto something
here. I'll add a bit more color to the proposal, since I've been
thinking about it all weekend :-)
There are two ways we can use this:
- A simple variant in which we just tell a single trampoline what the
intended recipient is (just a pubkey, and an amount) and it'll find a
route.
- A complex variant in which a trampoline is given a next hop, and a
smaller onion to pass along to the next hop. The trampoline doesn't
learn the intended recipient, but can still route it.
# Simple Variant
As the name implies it is pretty trivial to implement: the sender
computes a route to some trampoline node `t` it knows in its 2- or
3-neightborhood and creates an onion that describes this route. The
payload for the trampoline node `t` then contains two parameters:
`receiver` and `amount`. The trampoline node `t` then computes a route
from itself to the `receiver` and creates a new onion (the old onion
terminates at the trampoline node). Since the trampoline node generates
a new route, it also generates the shared secrets, HMACs and everything
else to match (no problem with matching HMACs like in the case of
rendezvous routing).
The receiver doesn't learn anything about this being a trampoline
payment (it doesn't even have to implement it itself), and resolution of
the HTLC happens like normal (with the extra caveat that the trampoline
needs to associate the upstream incoming HTLC with the resolution of the
downstream HTLC, but we do that anyway now).
# Multi-trampoline routing
The more complex proposal involves nesting a smaller onion into the
outer routing onion. For this the sender generates a small onion of, for
example, 10 hops whose length is only 650 bytes instead of the 20 hops
for the outer routing onion. The hops in the inner/smaller onion do not
have to be adjacent to each other, i.e., they can be picked randomly
from the set of known nodes and there doesn't need to be a channel
between two consecutive hops, unlike in the outer/routing onion. The
hops in the smaller onion are called trampolines `t_1` to `t_10`.
The construction of the smaller onion can be identical to the
construction of the routing onion, just needs its size adjusted. The
sender then picks a random trampoline node `t_0` in its known
neighborhood and generates a routing onion containing the smaller onion
as payload to `t_0` and signaling data (final recipient, amount, inner
onion). Upon receiving an incoming payment with trampoline instructions
a trampoline `t_i` unwraps the inner onion, which yields the next
trampoline `t_{i+1}` node_id. The trampoline then finds a route to
`t_{i+1}`, serializing the inner onion (which was unwrapped and is now
destined for `t_{i+1}`) and creating the outer routing onion with that
as the payload. Notice that, like in the simple variant, `t_i` generates
a new outer onion, which means we don't have any issues with shared
secrets and HMACs like in rendezvous routing. Resolution is also
identical to above.
This construction reuses all the onion primitives we already have, and
it allows us to bounce a payment through multiple trampolines without
them learning their position in this nested path. The sender does
not have to have a total view of the network topology, just have a
reasonable chance that two consecutive trampolines can find a route to
each other, i.e., don't use mobile phone as trampolines :-)
# Tradeoffs everywhere
## Longer Routes
One potential downside is that by introducing this two-level nesting of
an outer routing onion and an inner trampoline onion, we increase the
maximum length of a route to `num_outer_hops * num_inner_hops`, given
that each layer of the inner onion may initiate a new `num_outer_hops`
outer route. For the example above (which is also the worst case) we
have a 10 inner hops, and 9 outer hops (due to the signalling overhead),
which results in a maximum route length of 90 hops. This may result in
more funds being used to route a payment, but it may also increase
chances of the payment succeeding.
## Comparison with TCP/IP + Tor
This proposal also brings us a lot closer to the structure of Tor on the
public network, in which the nodes that are part of a circuit do not
have to be direct neighboors in the network topology since end-to-end
reachability is guaranteed by a base routing layer (TCP/IP) whereas
sender/receiver obfuscation is tackled at a higher layer (Tor).
In our case the outer onion serves as the base routing layer that is
used for point-to-point communication, but unlike TCP/IP is also
encrypted and routed anonymously, while the inner onion takes care of
end-to-end reachability, also in encrypted fashion.
## In-network retrial
>From the comparison with TCP/IP and Tor might have hinted at this, but
since the outer onion is created from scratch at each trampoline, a
trampoline may actually retry a payment multiple times if an attempt
failed, reducing the burden on the sender,
Re: [Lightning-dev] Outsourcing route computation with trampoline payments
Hello ZmnSCPxj, > Unless we propose to massively change the onion packet construction...? I'm afraid we would have to make some changes. I imagine we would have two onions: - one for the adjacent hops (this is the onion we are currently using) - one for the trampoline hops The 'trampoline onion' would be contained in the per-hop payload of the final node of the 'adjacent onion'. So in your example B would: 1) receive the htlc 2) see that it is the last hop in the route, and extract the trampoline payload 3) peel the trampoline onion and see that it should delegate the payment to C 4) find a route to C and set the trampoline onion as payload for C I haven't studied PR #593 enough to tell how easy that would be achievable though. There is another unrelated issue: because trampoline nodes don't know anything about what happened before they received the onion, they may unintentionnaly create overlapping routes. So we can't simply use the payment_hash as we currently do, we would have to use something a bit more elaborate. (maybe private keys?) Cheers, Pierre ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Outsourcing route computation with trampoline payments
Good morning Pierre, Rene, and list, I would also like to point out that even if the trampoline point does not know the next trampoline point, then it need not fail the routing. (this may occur if we start pruning the routemap as the LN size grows) As long as we can fix the issues regarding HMAC, then the trampoline point may itself delegate the routing to the next trampoline point to another trampoline point it inserts into the onion. So what we need to somehow support, is to be able to "left shift" and "right shift" arbitrarily in the onion packet. If we can handle this, then trampolining is possible and trampoline routing is feasible to delegate routing elsewhere. This also ties with deterministic methods of pruning routemaps. For instance, somebody proposed to create a false "geographic location" for each node, possibly derived only from the node public key being projected into some spatial volume. (To be clear, this does *not* mean that every node needs to register some merely-Earth-based location, which can be easily falsified anyway; instead we project the node public key to some notion of "nearness") Then a node might be expected to keep at least the nearest nodes to its "geographic location" in its routemap. Then if I happen to be a trampoline point, and I am unable to locate the next trampoline point in my local routemap, I could instead locate the node on my routemap that is "nearest" to the next trampoline point, and forward the payment there. Now, to an extent, privacy is reduced here since it is likelier than before that the "next trampoline" is actually the payee. However, as a source node, I only need to know the actual route to my first trampoline point, and let the trampoline point worry about how to get it to the next trampoline. So I can even just prune only the channels and channel relationships (endpoints of channels), and retain only the node public keys (a cheap 32 bytes), probably pruning the node public keys in some deterministically probabilistic fashion. In this case, I might still be interested in gossip about faraway channels --- I would still want to check that the channel exists (by blockchain lookup), but after I know the channel exists I can throw it away, only considering it as a proof-of-existence of a faraway node that I might use as a trampoline to improve my privacy. In effect, this lets us give a continuum: 1. At one end, the full route and every intermediate hop to the destination is known only by the source. 2. At the other end, the source only knows its direct channels, and sends to some adjacent trampoline node, and asks the trampoline node to route to the destination. The above gives a nice continuum where the amount of space dedicated to your own local routemap improves your privacy, and you can prune your routemap at the cost of privacy reduction (and probably hedging your fees by always overpaying fees). Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Outsourcing route computation with trampoline payments
Good morning Rene and Pierre, An issue here (which I think also affects Rendezvous Routing) is with compatibility of the HMAC. HMAC covers the entire 1300-byte `hops_data` field. If, in order to reach the next trampoline, more than one intermediate node is inserted, would the packet that reaches the next trampoline have a valid HMAC still? Consider that the filler data generated by the current trampoline to communicate with intermediate nodes may cause different filler data to be XORed with the 0x00 data added to left-shift the data at each intermediate node. (I am unsure if I express myself coherently here) So for example, suppose I am the source and I trampoline to nodes B and C, and pay to destination D. Suppose B is a direct neighbor of mine, but I have no idea where C and D are. Suppose for simplicity that the onion packet is just 6 hops long. So I initialize as: [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] I right shift and insert destination D: [ D, here's my payment ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] Then I encrypt with some shared secret known by me A and D: [ encrypt(A * D, "D, here's my payment") ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] Then I right shift and insert trampoline C: [ C, send this to D ] [ encrypt(A * D, "D, here's my payment") ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] Then I encrypt with some shared secret known by me A and C: [ encrypt(A * C, "C, send this to D") ] [ encrypt(A * C, encrypt(A * D, "D, here's my payment")) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ] Then I right shift and insert trampoline B: [ B, send this to C ] [ encrypt(A * C, "C, send this to D") ] [ encrypt(A * C, encrypt(A * D, "D, here's my payment")) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ] And encrypt with A * B: [ encrypt(A * B, "B, send this to C") ] [ encrypt(A * B, encrypt(A * C, "C, send this to D")) ] [ encrypt(A * B, encrypt(A * C, encrypt(A * D, "D, here's my payment"))) ] [ encrypt(A * B, encrypt(A * C, encrypt(A * D, 0))) ] [ encrypt(A * B, encrypt(A * C, encrypt(A * D, 0))) ] [ encrypt(A * B, encrypt(A * C, encrypt(A * D, 0))) ] I send this to B, who removes one layer of encryption: [ B, send this to C ] [ encrypt(A * C, "C, send this to D") ] [ encrypt(A * C, encrypt(A * D, "D, here's my payment")) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ] Now B finds the shortest route involves nodes N and O before reaching C. So B has to insert N and O, pushing out one packet from the end. But the pushed-out packet will no longer be recoverable and it cannot be re-encrypted except by A. (Unless I misunderstand the onion construction) Unless we propose to massively change the onion packet construction...? > 1.) A different fee mechanism. Let us (only as a radical thought experiment) > assume we drop the privacy of the final amount in routing. Please no. > A sending node could offer a fee for successful routing. Every routing node > could decide how much fee it would collect for forwarding. Nodes could try to > collect larger fees than the min they announce but that lowers the probably > for the payment to be successful. Even more radical: Nodes would not even > have to announce min fees anymore. Turning routing and fees to a real > interactive market Would this not also require that intermediate nodes know the ultimate destination of the payment? How would intermediate nodes find out which next hop would be reasonable? Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Outsourcing route computation with trampoline payments
Dear Pierre-Marie and fellow lightning developers, I really like that suggestion. In the context of JIT routing I was tinkering about the same idea (is it possible for sending nodes to only know a small part of the network - for example the friend of a friend network - to save Hardware / gossip bandwidth requirements) but I was thinking about a different solution which I want to drop in here. (I believe yours is better though) My thought was to use rendez-vous routing. This would mean the sender would have to provide a rendez vous point from his local (friend of a friend?) network and the recipient provides a route to him/herself. Only the recipient has to know the entire network topology. One problem with rendez vous routing is of course that the routing fails if the route from the rendez vous point does not work. This again could be mitigated with JIT routing. In the context of JIT routing it also makes sense to "overpay" fees so that JIT nodes could rebalance without loss. Making my solution also probabilistic with the fees. The fact that this pattern of probabilistic fees occurs for the second time now leads me to the following 2 more general ideas (maybe we should start a new thread if we discuss them to stay on topic here) that might help with routing. 1.) A different fee mechanism. Let us (only as a radical thought experiment) assume we drop the privacy of the final amount in routing. A sending node could offer a fee for successful routing. Every routing node could decide how much fee it would collect for forwarding. Nodes could try to collect larger fees than the min they announce but that lowers the probably for the payment to be successful. Even more radical: Nodes would not even have to announce min fees anymore. Turning routing and fees to a real interactive market 2.) A virtual hierarchical address space. Maybe we should start thinking about the creation of a semantic overlynetwork / address space for nodes similar to IP. This would allow any node to just have a pruned network view but still make smart routing decisions. Obviously we would have to find a way to assign virtual network addresses to nodes which might be hard. The second suggestion would be of particular interest in your case if N also did not know the entire network and has to decide to whom to to forward for the final destination D. Sorry for "hijacking" your suggestion and throwing so many new ideas but in my mind this seems all very connected /related. Best Rene Pierre schrieb am Do., 28. März 2019, 23:25: > Hello List, > > I think we can use the upcoming "Multi-frame sphinx onion format" [1] > to trustlessly outsource the computation of payment routes. > > A sends a payment to an intermediate node N, and in the onion payload, > A provides the actual destination D of the payment and the amount. N > then has to find a route to D and make a payment himself. Of course D > may be yet another intermediate node, and so on. The fact that we can > make several "trampoline hops" preserves the privacy characteristics > that we already have. > > Intermediate nodes have an incentive to cooperate because they are > part of the route and will earn fees. As a nice side effect, it also > creates an incentive for "routing nodes" to participate in the gossip, > which they are lacking currently. > > This could significantly lessen the load on (lite) sending nodes both > on the memory/bandwidth side (they would only need to know a smallish > neighborhood) and on the cpu side (intermediate nodes would run the > actual route computation). > > As Christian pointed out, one downside is that fee computation would > have to be pessimistic (he also came up with the name trampoline!). > > Cheers, > > Pierre-Marie > > [1] > https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-February/001875.html > ___ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
[Lightning-dev] Outsourcing route computation with trampoline payments
Hello List, I think we can use the upcoming "Multi-frame sphinx onion format" [1] to trustlessly outsource the computation of payment routes. A sends a payment to an intermediate node N, and in the onion payload, A provides the actual destination D of the payment and the amount. N then has to find a route to D and make a payment himself. Of course D may be yet another intermediate node, and so on. The fact that we can make several "trampoline hops" preserves the privacy characteristics that we already have. Intermediate nodes have an incentive to cooperate because they are part of the route and will earn fees. As a nice side effect, it also creates an incentive for "routing nodes" to participate in the gossip, which they are lacking currently. This could significantly lessen the load on (lite) sending nodes both on the memory/bandwidth side (they would only need to know a smallish neighborhood) and on the cpu side (intermediate nodes would run the actual route computation). As Christian pointed out, one downside is that fee computation would have to be pessimistic (he also came up with the name trampoline!). Cheers, Pierre-Marie [1] https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-February/001875.html ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
