Trampoline onion format (Feature 56/57)

[t-bast]

Trampoline routing uses layered onions to trustlessly and privately offload the calculation of parts of a payment route to remote trampoline nodes.

A normal onion contains a smaller onion for the last hop of the route, and that smaller onion contains routing information about the next trampoline hop.

Intermediate trampoline nodes "fill the gap" by finding a route to the next trampoline node, and sending it the peeled trampoline onion, until that reaches the final destination.

This PR details the onion construction and requirements for supporting nodes. I advise readers to also have a look at https://github.com/lightningnetwork/lightning-rfc/pull/829 which gives a more high-level view of the different components, how they interact, and provides nice diagrams that help understand the low-level details.

[t-bast]

@arik-so @valentinewallace I have added a draft spec of trampoline payments to blinded paths in https://github.com/lightning/bolts/pull/836/commits/296ce2114a54487030389033b0c019dd32db01b6. It is probably a bit confusing because it depends on Bolt 12 types that are defined in the offers PR, and I should more explicitly spell out the requirement of which tlvs are included where, but combined with the discussions we had in this comment, we should be able to understand each other.

I'm particularly looking for feedback on the shared secret extension I'm using for the recipient trampoline payload to include an ECDH with the invoice_request's payer_id, let me know what you think (see @TheBlueMatt's comment for more context).

Once we have a good enough rough consensus, I'll spend some time rebasing this PR, I'll re-write the requirements in a way that is similar to what was done in #1181 and more precise that what I've currently done, and I'll finalize the test vector.

[arik-so]

Awesome, thank you so much! Will update corresponding test vectors ASAP!

[t-bast]

@arik-so I slightly changed the last commit:

• I'm now providing complete test vectors for trampoline to blinded paths (with and without a trampoline onion for the recipient)
• I changed the invoice_request shared secret mechanism: instead of modifying the derivation of rho and mu, I use this shared secret in the HMAC's associated data for the final hop: this is simpler and avoids changing the internals of Sphinx

[t-bast]

There is one point that is worth discussing here: do we want to include an extension for Bolt 11 to introduce trampoline routing hints? If we want to be able to make non-blinded trampoline payments between wallets that have only private channels (e.g. Alice -> LSPA -> ... -> LSPB -> Bob), I see two possible options.

The first one is that we don't introduce any new routing hint, but if the invoice contains the (optional) trampoline feature bit, Alice assumes that nodes included in Bob's routing hints support trampoline and uses them as such. In the example above, Alice would use LSPA as her trampoline node and LSPB as Bob's trampoline node, and assume that LSPB is able to route to Bob. This option is nice because it doesn't increase QR code size, but when receiving wallets provide multi-hop routing hints, Alice may get that heuristic wrong. In practice I don't think this is an issue, in the worst case Alice could make several attempts where she assumes that different nodes in the routing hints support trampoline, until one works.

The second option is that we introduce a trampoline routing hint field to Bolt 11 invoices, that are very similar to routing hints but don't include a short_channel_id. This will be ignored by existing nodes that don't support trampoline. The issue with that option is that it increases QR code size, because the invoice must work for non-trampoline senders as well, so it will include both the normal routing hints and the trampoline hints.

Thoughts?

[TheBlueMatt]

On our end we only care about trampoline with blinded path destinations, really. I don't see much reason to care about trying to add a second trampoline hop of the recipient's LSP when they aren't using blinding, if the sender wants privacy from their trampoline hop(s), they should just add more trampoline hops!

[t-bast]

@arik-so @JssDWt this PR has been updated to match the discussions of the lightning summit. It now fully supports Bolt 11 and Bolt 12, as described in https://github.com/t-bast/trampoline-blinded-paths. The test vectors should be really helpful to figure out where each piece of data goes.

This is implemented in https://github.com/ACINQ/lightning-kmp/pull/688 if you want to see some code (I need to update eclair as well, but it's going to be a bigger chunk because it will need to support backwards-compat with the experimental trampoline version from years ago).

[arik-so]

Incredible, thanks so much!

[t-bast]

@arik-so I've made a small change in https://github.com/lightning/bolts/pull/836/commits/faeea3f2da4dceae0e772f95d18f5fd2bf1d35a7 to allow omitting the MPP field in the outer onion when not using MPP to reach a trampoline node. This is implemented in eclair in https://github.com/lightning/bolts/pull/836 if you want to make some cross-compat tests.