Re: [Lightning-dev] Sphinx Rendezvous Update
Hi Bastien, thanks for verifying my proposal, and I do share your concerns regarding privacy leaks (how many hops are encoded in the onion) and success ratio if a payment is based on a fixed (partial) path. > I believe this makes it quite usable in Bolt 11 invoices, without blowing up > the size of the QR code (but more experimentation is needed on that). It becomes a tradeoff of how small you want your onion to be, and how many hops the partial onion can have. For longer partial onions we're getting close to the current full onion size, but I expect most partial onion to be close to the network diameter of ~6 (excluding degerenate chains). So the example below with 5 hops seemed realistic, and dropping the legacy format in favor of TLVs we can get a couple of bytes back as well. >> As an example such an onion, with 5 legacy hops (65 byte each) results >> in a 325 + 66 bytes onion, and we save 975 bytes. > > While having flexibility when choosing the length of the prefill > stream feels nice, wouldn't it be safer to impose a fixed size to > avoid any kind of heuristic at `RV` to try to guess how many hops > there are between him and the recipient? I'm currently just using the maximum size, which is an obvious privacy leak, but I'm also planning on exposing the size to be prefilled, and hence cropped out when compressing, when generating. Ideally we'd have a couple of presets, i.e., 1/4, 2/4, 3/4, and adhere to them, randomizing which one we pick. Having smaller partial onions would enable my stretch goal of being able to chain multiple partial onions, though that might be a useless achievement to unlock xD >> Compute a shared secret using a random ephemeral private key and >> `RV`s public key, and then generate a prefill-key > > > While implementing, I felt that the part about the shared secret used > to generate the prefill stream is a bit blurry (your proposal on > Github doesn't phrase it the same way). I think it's important to > stress that this secret is derived from both `ephkey` and `RV`'s > private key, so that `RV+1` can't compute the same stream. I noticed the same while implementing the decompress stage, which requires the node ID from `RV` during generation, and performs ECDH + HKDF with the `RV` node private and the ephemeral key in the *next* onion, i.e., the one extracted from the payload itself. This is necessary since the ephemeral key on the incoming onion, which delivered the partial onion in its payload is not controlled by the partial onion creator, while the one in the partial onion is. This means that the ephemeral key in the partial onion is used twice: - Once by `RV` to generate the obfuscation stream to fill in the gap - As part of the reconstructed onion, processed by `RV+1` to decode the onion. I'm convinced this is secure and doesn't leak information since otherwise transporting the ephemeral key publicly would be insecure (`RV+1` can't generate the obfuscation secret used to fill in the gap without access to `RV`s private key), and the ephemeral key is only transmitted in cleartext once (from `RV` to `RV+1`), otherwise it is hidden in the outer onion. > Another thing that may be worth mentioning is error forwarding. Since > the recipient generated the onion, `RV` won't have the shared secrets > (that's by design). So it's expected that payment errors won't be > readable by `RV`, but it's probably a good idea if `RV` returns an > indication to the sender that the payment failed *after* the > rendezvous point. Indeed, this is pretty much by design, since otherwise the sender could provoke errors, e.g., consuming all of `RV`s outgoing capacity with probes to get back temporary channel failure errors for the channel that was encoded in the partial onion, and then do that iteratively until we have identified the real destination which we weren't supposed to learn. So any error beyond `RV` should be treated by the sender as "rendez-vous failed, discard partial onion". > An important side-note is that your proposal is really quick and > simple to implement from the existing Sphinx code. I have made ASCII > diagrams of the scheme (see [1]). This may help readers visualize it > more easily. I quickly skimmed the drawings and they're very nice to understand how regions overlap, that was my main problem with the whole sphinx construction, so thanks for taking the time :+1: > It still has the issue that each hop's amount/cltv is fixed at invoice > generation time by the recipient. That means MPP cannot be used, and > if any channel along the path updates their fee the partial onion > becomes invalid (unless you overpay the fees). > > Trampoline should be able to address that since it provides more > freedom to each trampoline node to find an efficient way to forward to > the next trampoline. It's not yet obvious to me how I can mix these > two proposals to make it work though. I'll spend more time > experimenting with that. True, I think rendez-vous routing
Re: [Lightning-dev] Sphinx Rendezvous Update
Hi Christian, This is great, thanks for sharing! What's really nice with your proposal is that there is effectively no onion payload for `RV` in the partial onion, which frees up more space than mine. I believe this makes it quite usable in Bolt 11 invoices, without blowing up the size of the QR code (but more experimentation is needed on that). As an example such an onion, with 5 legacy hops (65 byte each) results > in a 325 + 66 bytes onion, and we save 975 bytes. While having flexibility when choosing the length of the prefill stream feels nice, wouldn't it be safer to impose a fixed size to avoid any kind of heuristic at `RV` to try to guess how many hops there are between him and the recipient? Compute a shared secret using a random ephemeral private key and > `RV`s public key, and then generate a prefill-key While implementing, I felt that the part about the shared secret used to generate the prefill stream is a bit blurry (your proposal on Github doesn't phrase it the same way). I think it's important to stress that this secret is derived from both `ephkey` and `RV`'s private key, so that `RV+1` can't compute the same stream. Another thing that may be worth mentioning is error forwarding. Since the recipient generated the onion, `RV` won't have the shared secrets (that's by design). So it's expected that payment errors won't be readable by `RV`, but it's probably a good idea if `RV` returns an indication to the sender that the payment failed *after* the rendezvous point. An important side-note is that your proposal is really quick and simple to implement from the existing Sphinx code. I have made ASCII diagrams of the scheme (see [1]). This may help readers visualize it more easily. It still has the issue that each hop's amount/cltv is fixed at invoice generation time by the recipient. That means MPP cannot be used, and if any channel along the path updates their fee the partial onion becomes invalid (unless you overpay the fees). Trampoline should be able to address that since it provides more freedom to each trampoline node to find an efficient way to forward to the next trampoline. It's not yet obvious to me how I can mix these two proposals to make it work though. I'll spend more time experimenting with that. Thanks, Bastien [1] https://gist.github.com/t-bast/ab42a7f52eb2e73105557957c8359601#Christian Le lun. 24 févr. 2020 à 19:22, Christian Decker a écrit : > Hi Bastien, > > seems you were a bit quicker than I was with my writeup of my > proposal. I came up with a scheme that allows us to drop a large part of > the partial onion, so that it can indeed fit into an outer onion, and > the rendez-vous node RV can re-construct the original packet from the > included data [1]. > > The construction comes down to initializing the part of the routing info > string that is not going to be used, in such a way that the incremental > unwrappings at the nodes in the partial onion cancels out. Like you > mentioned in your mail it comes down extending the filler generation to > also cover the unused part and then applying all the encryption streams > xored to the unused space. By doing this we get the middle part of the > onion consisting of only 0x00 bytes. > > I then decided to apply an additional ChaCha20 stream to this prefill, > such that the onion will not consist of mostly 0x00 bytes which would be > a dead giveaway to `RV+1` that `RV` was a rendez-vous node. > > The process for the partial onion creator boils down to: > > - Compute a path from `RV` of its choice to recipient `R`. > - Compute a shared secret using a random ephemeral private key and > `RV`s public key, and then generate a prefill-key > - Compute the prefill by combining the correct substrings of the >encryption streams for the nodes along the path, then add the >ChaCha20 stream keyed with the prefill-key. > - Wrap the onion, including payloads for each of the nodes along path >`RV` to `R` > - Trim out the unused space, which now will match the obfuscation >stream generated with the prefill-key > > As an example such an onion, with 5 legacy hops (65 byte each) results > in a 325 + 66 bytes onion, and we save 975 bytes. See [2] for an example > of how this looks like. > > The sender `S` then just does the following: > > - Compute a route from `S` to `RV` > - Build an onion with the route, specifying the trimmed partial onion >as payload, along with the usual parameters, for `RV` > - Initiate payment with the constructed onion > > Upon receiving an incoming HTLC with a partial onion the rendez-vous > node `RV` then just does the following: > > - Verify all parameters as usual > - Extract the partial onion > - Use the ephemeral key from the partial onion to generate the shared >secret and the prefill key > - Generate the prefill stream and insert it in the correct place, >before the HMAC. This reconstitutes the original routing packet > - Swap out the original onion with the
Re: [Lightning-dev] Sphinx Rendezvous Update
Hi Bastien, seems you were a bit quicker than I was with my writeup of my proposal. I came up with a scheme that allows us to drop a large part of the partial onion, so that it can indeed fit into an outer onion, and the rendez-vous node RV can re-construct the original packet from the included data [1]. The construction comes down to initializing the part of the routing info string that is not going to be used, in such a way that the incremental unwrappings at the nodes in the partial onion cancels out. Like you mentioned in your mail it comes down extending the filler generation to also cover the unused part and then applying all the encryption streams xored to the unused space. By doing this we get the middle part of the onion consisting of only 0x00 bytes. I then decided to apply an additional ChaCha20 stream to this prefill, such that the onion will not consist of mostly 0x00 bytes which would be a dead giveaway to `RV+1` that `RV` was a rendez-vous node. The process for the partial onion creator boils down to: - Compute a path from `RV` of its choice to recipient `R`. - Compute a shared secret using a random ephemeral private key and `RV`s public key, and then generate a prefill-key - Compute the prefill by combining the correct substrings of the encryption streams for the nodes along the path, then add the ChaCha20 stream keyed with the prefill-key. - Wrap the onion, including payloads for each of the nodes along path `RV` to `R` - Trim out the unused space, which now will match the obfuscation stream generated with the prefill-key As an example such an onion, with 5 legacy hops (65 byte each) results in a 325 + 66 bytes onion, and we save 975 bytes. See [2] for an example of how this looks like. The sender `S` then just does the following: - Compute a route from `S` to `RV` - Build an onion with the route, specifying the trimmed partial onion as payload, along with the usual parameters, for `RV` - Initiate payment with the constructed onion Upon receiving an incoming HTLC with a partial onion the rendez-vous node `RV` then just does the following: - Verify all parameters as usual - Extract the partial onion - Use the ephemeral key from the partial onion to generate the shared secret and the prefill key - Generate the prefill stream and insert it in the correct place, before the HMAC. This reconstitutes the original routing packet - Swap out the original onion with the reconstituted onion and forward. My writeup [1] is an early draft, but I wanted to get it out early to give the discussion a basis to work off. I'll revisit it a couple of times before opening a PR, but feel free to shout at me if I have forgotten to consider something :-) Cheers, Christian [1] https://github.com/lightningnetwork/lightning-rfc/blob/rendez-vous/proposals/0001-rendez-vous.md [2] https://gist.github.com/cdecker/ec06452bc470749d9f6d2de73651c5fd Bastien TEINTURIER via Lightning-dev writes: > Good morning list, > > After exploring decoys [1], which is a cheap way of doing route blinding, > I'm turning back to exploring rendezvous. > The previous mails on the mailing list mentioned that there was a > technicality > to make the HMACs check out, but didn't provide a lot of details. > The issue is that the filler generation needs to take into account some hops > that will be added *later*, by the payer. > > However it is quite easy to work-around, with a few space trade-offs. > Let's consider a typical rendezvous setup, where Alice wants to be paid via > rendezvous Bob, and Carol wants to pay that invoice: > > Carol -> ... -> Bob -> ... -> Alice > > If Alice knows how many bytes Carol is going to use for her part of the > onion > payloads, Alice can easily take them into account when generating her > filler by > pre-pending the same amount of `0` bytes. It seems reasonable to impose a > fixed > number of onion bytes for each side of the rendezvous (650 each?) so Alice > would > know that amount. > > When Carol completes the onion with her part of the route, she simply needs > to > generate filler data for her part of the route following the normal Sphinx > protocol > and apply it to the onion she found in the invoice. > > But the tricky part is that she needs to give Bob a way of generating the > same > filler data to unapply it. Then all HMACs correctly check out. > > I see two ways of doing that: > > * Carol simply sends that filler (650 bytes), probably via a TLV in > `update_add_htlc`. > This means every intermediate hop needs to forward that, which is painful > and > potentially leaking too much data. > * Carol provides Bob with the rho keys used to generate her filler, and the > length > used by each hop. This leaks to Bob an upper bound on the number of hops > and the > number of bytes sent to each hop. > > Since shift-and-xor kind of crypto is hard to read as equations, but very > easy to > read as diagrams, I spent a bit of time doing beautiful ASCII art [2]. > Don't
[Lightning-dev] Sphinx Rendezvous Update
Good morning list, After exploring decoys [1], which is a cheap way of doing route blinding, I'm turning back to exploring rendezvous. The previous mails on the mailing list mentioned that there was a technicality to make the HMACs check out, but didn't provide a lot of details. The issue is that the filler generation needs to take into account some hops that will be added *later*, by the payer. However it is quite easy to work-around, with a few space trade-offs. Let's consider a typical rendezvous setup, where Alice wants to be paid via rendezvous Bob, and Carol wants to pay that invoice: Carol -> ... -> Bob -> ... -> Alice If Alice knows how many bytes Carol is going to use for her part of the onion payloads, Alice can easily take them into account when generating her filler by pre-pending the same amount of `0` bytes. It seems reasonable to impose a fixed number of onion bytes for each side of the rendezvous (650 each?) so Alice would know that amount. When Carol completes the onion with her part of the route, she simply needs to generate filler data for her part of the route following the normal Sphinx protocol and apply it to the onion she found in the invoice. But the tricky part is that she needs to give Bob a way of generating the same filler data to unapply it. Then all HMACs correctly check out. I see two ways of doing that: * Carol simply sends that filler (650 bytes), probably via a TLV in `update_add_htlc`. This means every intermediate hop needs to forward that, which is painful and potentially leaking too much data. * Carol provides Bob with the rho keys used to generate her filler, and the length used by each hop. This leaks to Bob an upper bound on the number of hops and the number of bytes sent to each hop. Since shift-and-xor kind of crypto is hard to read as equations, but very easy to read as diagrams, I spent a bit of time doing beautiful ASCII art [2]. Don't hesitate to have a look at it to find more details about how that works. You can also print that on t-shirts to look fancy at conferences. I also have some sample code working in eclair [3] for those who can read Scala without getting headaches. Are there other tricks we can use to reconcile both sides of the onion at Bob's? Maybe cdecker (or someone else) has an ace up his sleeve for me there? :) One important thing to note is that rendezvous on normal onions will be costly to integrate into invoices: it takes 1366 bytes to include one onion, and if we want to handle route failures or let the sender use multi-part, we will need to have a handful of pre-encrypted onions in the invoice (hence a few kB, which may not be practical for QR codes). But I did mention before that doing rendezvous on the trampoline onion could have better properties [4]. When doing that, having Carol transmit her filler data only to Bob, via the outer onion payload becomes practical and doesn't leak information. Multi-part would work with a single trampoline onion in the invoice (~500 bytes), because nodes can do MPP between trampoline nodes thanks to the onion-in-onion construction. We simply need to decide the size of the trampoline onion to allow each side of the rendezvous to be able to insert a number of hops we're comfortable with. You can find more details in the "Rendezvous on a trampoline" section of [2]. I'm really interested in other approaches to making rendezvous work with the HMACs correctly checking out. If people on this list have drafts, intuitions or random thoughts about possible constructions, please share them, I'd be happy to dive into them to explore alternatives to the one I found, hoping we can make this work and provide this feature to our users in the near future. A small side-note on Hornet. Hornet does offer many features that I believe we will want in Lightning in the future. It may seem that doing a custom rendezvous scheme is a waste of time since we'll ditch it once/if we implement Hornet. While that is true in the long run, I believe that if we're able to find a rendezvous scheme that isn't too much work to implement, it makes sense to have something available soon-ish. Hornet will likely be a longer-term effort that we won't get as soon as we'd like (especially since it will probably require a network-wide update). But who knows, maybe we may see that we are trying to create many features that are already built into Hornet (rendezvous, directed message support, etc) and will decide to implement Hornet sooner than expected? Cheers, Bastien [1] https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-January/002435.html [2] https://gist.github.com/t-bast/ab42a7f52eb2e73105557957c8359601 [3] https://github.com/ACINQ/eclair/tree/sphinx-rendezvous [4] https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-October/002237.html ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org
