Christian Decker [ARCHIVE] on Nostr: 📅 Original date posted:2019-04-01 📝 Original message: Thanks Pierre for this ...
📅 Original date posted:2019-04-01
📝 Original message:
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, and increasing chances of the
payment succeeding.
# Conclusion
Overall I'm really excited about this proposal. It decreases the need
for a complete network view at the endpoints, may delegate some of the
burden of finding routes to in-network trampolines, may increase the
successrate of our payments, and increases the total length of a
possible route (may be a negative as well).
Cheers,
Christian
Pierre <pm+lists at acinq.fr> writes:
> 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
📝 Original message:
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, and increasing chances of the
payment succeeding.
# Conclusion
Overall I'm really excited about this proposal. It decreases the need
for a complete network view at the endpoints, may delegate some of the
burden of finding routes to in-network trampolines, may increase the
successrate of our payments, and increases the total length of a
possible route (may be a negative as well).
Cheers,
Christian
Pierre <pm+lists at acinq.fr> writes:
> 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev