Problem Statement
We are currently using sphinx based onion routing to route a payment from one endpoint, the sender S, to another endpoint, the recipient R. This requires that the sender constructs the onion packet that contains the entire route of the payment, i.e., the sender has to compute the entire route and has to know who the recipient is.
This has a number of downsides, most importantly that the sender will learn the identity of the recipient and its surroundings. While it is possible to partially hide the recipient behind private channels and use aliases that hide the last part of the route using the route hints in the bolt11 payment requests, this approach is rather limited, as it still leaks the general location and route length.
A common feature in onion routed networks is the ability to rendez-vous node RV on the public network and have the recipient generate a route onion from that public location. The sender then just takes this trailing part of the route and generates a route to the public location, concatenating the two routes. This results in a route that is only partially known to either endpoint, providing anonymity to both sender and recipient.
The concatenation of the two partial routes however is not trivial, given the cryptographic primitives (EC Diffie-Hellman) used to generate shared secrets for the onion encryption. Specifically the recipient is generating an onion from RV, using an ephemeral key and ECDH with the hops' node_id. This ephemeral key is rotated on each hop using that hop's shared secret. The difficulty lies in having the ephemeral key rotated at each hop from S to RV meet up at RV, i.e., it being exactly the same as the one used by R for the RV to R route.
Proposed solution
The proposed solution is to add a new feature that allows RV to switch out the ephemeral key that it is passing on to the next hop, instead of rotating it via the shared secret that depends on the prior ephemeral key. RV receives an onion packet that contains the new ephemeral key (FIXME: Need to describe how the presence of the ephemeral key is signaled), and when forwarding the onion packet it'll simply prepend that ephemeral key.
Signaling support
Potential rendez-vous points signal their support for this feature by setting the rendez_vous global feature bit. Recipients may then select nodes that signal support for their own rendez-vous instances.
Using a rendez-vous point
When attempting to perform a payment using a rendez-vous point, the recipient R selects a random, possibly well-connected, node RV that signaled support. R then proceeds to generate an ephemeral key ek_k that will be swapped in by RV. It then generates a normal onion routing packet as described in BOLT 04 from RV to R, using a randomly selected ephemeral key ek_k. RV will perform the generation of the shared secret twice, in order to hide the fact that it was the rendez-vous point, so it generates both ss_k from ek_k and ss_{k+1} from ek_{k+1}, but it skips the payload extraction (left shift), i.e., the payloads are simply encrypted twice with 2 different shared secrets. R then serializes the onion packet as described in Packet Structure and passes it to the sender S (this discloses ek_k to S), along with the node_id of RV.
The sender then selects a route from S to RV and a new random ephemeral key ek_0 to be used when generating shared secrets along that route. S then takes the onion packet from R instead of the empty packet that is the starting point in Packet Construction. The payload at RV MUST signal that the ephemeral key should be switched out and contain ek_k. The wrapping of the onion proceeds as normal.
Notice that after switching out the ephemeral key ek_k at RV and the following decryption the onion packet corresponds exactly to the onion packet that R sent to S initially.
Rationale for double decryption
The need for the double payload decryption / filler encryption arises from the fact that the HMAC that R computes includes the padding that RV will compute. In non-rendez-vous operation this is a vector of 0x00-bytes, encrypted with a ChaCha20 bytestream that is generated from ss_rv, which itself is generated from ek_rv. The problem is that R can't know ss_rv, so it can't compute the filler for that hop.
The solution is to generate an ss_k from the ek_k that was swapped in, which R can know, and recompute the filler. So the rendez-vous point decrypts its payload which at the same time encrypts the filler with ss_rv, then notices that it should swap out the ephemeral key, and resets the filler to a 0x00-byte vector, which is then encrypted with ek_k again.