[Lightning-dev] Outsourcing route computation with trampoline payments

[Christian Decker]

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