Alice wants to receive a payment via rendezvous node Bob. Carol will pay this by "finishing" the onion encryption to route to Bob.
Carol -> N -> Bob -> M -> Alice
Notation:
- Bob's
node_idisP(Bob) = k(Bob) * G. - In the diagrams we note
stream(ss(N))but this is a simplification: we don't directly use the shared secret ss, we derive a key from it (HMAC-SHA256)
Everything works mostly the same as normal Sphinx, but Alice, Bob and Carol need to take a few small extra steps.
Alice acts as if she were sending a payment to herself via the following route:
Alice -> Bob -> M -> Alice
Alice generates the following secrets:
- session_key_A <- {0;1}^256
- ek_A(Bob) = session_key_A
- E_A(Bob) = ek_A(Bob) * G
- ss_A(Bob) = H(ek_A(Bob) * P(Bob)) = H(k(Bob) * E_A(Bob))
- b_A(Bob) = H(E_A(Bob) || ss_A(Bob))
- ek_A(M) = b_A(Bob) * ek_A(Bob)
- E_A(M) = ek_A(M) * G
- ss_A(M) = H(ek_A(M) * P(M)) = H(k(M) * E_A(M))
- b_A(M) = H(E_A(M) || ss_A(M))
- ek_A(Alice) = b_A(M) * ek_A(M)
- E_A(Alice) = ek_A(Alice) * G
- ss_A(Alice) = H(ek_A(Alice) * P(Alice)) = H(k(Alice) * E_A(Alice))
And uses that to create an encrypted onion. The only change she makes to the normal Sphinx protocol is that she adds X bytes at the beginning of the filler (where X is the total length of Carol's payloads - which could be fixed at 650 bytes for example). That will allow Carol to finalize the filler correctly once adding her part of the route.
She then shares that onion packet with Carol (via a Bolt 11 invoice for example). She also shares amount(Bob) and cltv(Bob) that need to be sent to Bob to allow him to forward (she can probably use those as the invoice amount and expiry - this way she doesn't leak the actual fees for the hidden part of the route).
1. Filler Generation (Alice)
<--------X-----------><---l_A(Bob)--->
+--------------------++--------------+
| 000000000000000000 || 000000000000 |
+--------------------++--------------+
(+)
<-----------------1300------------------------------------------><---l_A(Bob)--->
+-------------------------------------------------------------------------------+
| stream(ss_A(Bob)) |
+-------------------------------------------------------------------------------+
=
<--------X + l_A(Bob)----------------><-l(M)->
+------------------------------------++------+
| xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx || 0000 |
+------------------------------------++------+
(+)
<-----------------1300------------------------------------------><-l(M)->
+-----------------------------------------------------------------------+
| stream(ss_A(M)) |
+-----------------------------------------------------------------------+
=
<--------X + l_A(Bob) + l(M)----------------->
+--------------------------------------------+
| xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
+--------------------------------------------+
2. Onion Encryption (Alice)
<-----------------1300------------------------------------------>
<--l(Alice)--><---><---------X + l_A(Bob) + l(M)---------------->
+------------++---++--------------------------------------------+
| p(Alice) || r || xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
+------------++---++--------------------------------------------+
(+)
+-----------------+
| stream(ss_A(A)) |
+-----------------+
=
<-----------------><---------X + l_A(Bob) + l(M)---------------->
+-----------------++--------------------------------------------+
| encrypted for A || xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
+-----------------++--------------------------------------------+
<-l(M)-><--------1300 - l(M)------------------------------------>
+------++-------------------------------------------------------+
| p(M) || encrypted payload for Alice (truncated) |
+------++-------------------------------------------------------+
(+)
+---------------------------------------------------------------+
| stream(ss_A(M)) |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for M |
+---------------------------------------------------------------+
<---l_A(Bob)---><--------1300 - l_A(Bob)------------------------>
+--------------++-----------------------------------------------+
| p_A(Bob) || encrypted payload for M (truncated) |
+--------------++-----------------------------------------------+
(+)
+---------------------------------------------------------------+
| stream(ss_A(Bob)) |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob by Alice |
+---------------------------------------------------------------+
Carol generates the following secrets:
- session_key_C <- {0;1}^256
- ek_C(N) = session_key_C
- E_C(N) = ek_C(N) * G
- ss_C(N) = H(ek_C(N) * P(N)) = H(k(N) * E_C(N))
- b_C(N) = H(E_C(N) || ss_C(N))
- ek_C(Bob) = b_C(N) * ek_C(N)
- E_C(Bob) = ek_C(Bob) * G
- ss_C(Bob) = H(ek_C(Bob) * P(Bob)) = H(k(Bob) * E_C(Bob))
Note that ek_C(Bob) here is completely unrelated to ek_A(Bob). Because of the use of hash functions in the blinding operation which destructs all algebraic structure, there's no way we can find a clever way of making them match securely.
Carol has to make sure the total length of her payloads matches what Alice used (the simplest is to use a constant defined by the protocol). She can either add dummy hops at the beginning of the route (encrypted to herself) or add random padding in an ignored odd TLV record inside a hop's payload.
Before doing the normal Sphinx encryption, she simply applies her part of the filler. Carol then finishes the normal Sphinx onion encryption, using the onion pre-encrypted by Alice.
Carol includes Alice's value for E(Bob) in the encrypted payload for Bob.
The mac she includes in the payload for Bob is the one provided by Alice (not 0x00..00).
1. Finalize filler (Carol)
<--l(N)-->
+--------+
| 000000 |
+--------+
(+)
<--------1300---------------------------------------------------><--l(N)-->
+-------------------------------------------------------------------------+
| stream(ss_C(N)) |
+-------------------------------------------------------------------------+
=
<--l(N)--><-l_C(Bob)->
+--------++----------+
| xxxxxx || 00000000 |
+--------++----------+
(+)
<--------1300---------------------------------------------------><-l_C(Bob)->
+---------------------------------------------------------------------------+
| stream(ss_C(Bob)) |
+---------------------------------------------------------------------------+
=
<---l(N) + l_C(Bob)-->
+--------------------+
| xxxxxxxxxxxxxxxxxx |
+--------------------+
(+)
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob by Alice |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob by Alice with filler |
+---------------------------------------------------------------+
2. Onion Encryption (Carol)
<-l_C(Bob)-><--------1300--------------------------------------------------->
+----------++---------------------------------------------------------------+
| p_C(Bob) || encrypted payload for Bob by Alice with filler |
+----------++---------------------------------------------------------------+
(+) <---------->
+---------------------------------------------------------------+ truncated
| stream(ss_C(Bob)) |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob by Carol |
+---------------------------------------------------------------+
<--l(N)--><---------1300 - l(N)--------------------------------->
+--------++-----------------------------------------------------+
| p(N) || encrypted payload for Bob by Carol (truncated) |
+--------++-----------------------------------------------------+
(+)
+---------------------------------------------------------------+
| stream(ss_C(N)) |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for N |
+---------------------------------------------------------------+
When Bob decrypts the onion he receives from N, everything should be working fine.
He discovers the E_A(Bob) in the payload, indicating that he needs to decrypt a second time using this ephemeral key.
Before that, he needs to negate the filler applied by Carol.
Carol can either send the filler via additional TLVs in update_add_htlc (but that requires every intermediate node to
forward this value to the next one), or she could provide the list of (rho(i),l(i)) in the onion payload for Bob, which
allows him to generate the filler himself.
This part could be improved: if we find a more efficient way to give Bob what he needs to remove Carol's filler, it would be great.
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob by Carol |
+---------------------------------------------------------------+
(+) <-l_C(Bob)->
+---------------------------------------------------------------------------+
| stream(ss_C(Bob)) |
+---------------------------------------------------------------------------+
=
<-l_C(Bob)-><--------1300 - l_C(Bob)----------------------------><-l_C(Bob)->
+----------++---------------------------------------------------------------+
| p_C(Bob) || encrypted payload for Bob by Alice with filler |
+----------++---------------------------------------------------------------+
(+)
<---l(N) + l_C(Bob)-->
+--------------------+
| xxxxxxxxxxxxxxxxxx |
+--------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob by Alice |
+---------------------------------------------------------------+
1. Filler Generation (Alice)
<---l(N) + l_C(Bob)--><---l_A(Bob)--->
+--------------------++--------------+
| 000000000000000000 || 000000000000 |
+--------------------++--------------+
(+)
<-----------------1300------------------------------------------><---l_A(Bob)--->
+-------------------------------------------------------------------------------+
| stream(ss_A(Bob)) |
+-------------------------------------------------------------------------------+
=
<------l(N) + l_C(Bob) + l_A(Bob)----><-l(M)->
+------------------------------------++------+
| xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx || 0000 |
+------------------------------------++------+
(+)
<-----------------1300------------------------------------------><-l(M)->
+-----------------------------------------------------------------------+
| stream(ss_A(M)) |
+-----------------------------------------------------------------------+
=
<------l(N) + l_C(Bob) + l_A(Bob) + l(M)----->
+--------------------------------------------+
| xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
+--------------------------------------------+
2. Onion Encryption (Alice)
<-----------------1300------------------------------------------>
<- l(Alice) -><---><------l(N) + l_C(Bob) + l_A(Bob) + l(M)----->
+------------++---++--------------------------------------------+
| p(Alice) || r || xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
+------------++---++--------------------------------------------+
(+)
+-----------------+
| stream(ss_A(A)) |
+-----------------+
=
<-----------------><------l(N) + l_C(Bob) + l_A(Bob) + l(M)----->
+-----------------++--------------------------------------------+
| encrypted for A || xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
+-----------------++--------------------------------------------+
<-l(M)-><--------1300 - l(M)------------------------------------>
+------++-------------------------------------------------------+
| p(M) || encrypted payload for Alice (truncated) |
+------++-------------------------------------------------------+
(+)
+---------------------------------------------------------------+
| stream(ss_A(M)) |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for M |
+---------------------------------------------------------------+
<---l_A(Bob)---><--------1300 - l_A(Bob)------------------------>
+--------------++-----------------------------------------------+
| p_A(Bob) || encrypted payload for M (truncated) |
+--------------++-----------------------------------------------+
(+)
+---------------------------------------------------------------+
| stream(ss_A(Bob)) |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob by Alice |
+---------------------------------------------------------------+
3. Finalize filler (Carol)
<--l(N)-->
+--------+
| 000000 |
+--------+
(+)
<--------1300---------------------------------------------------><--l(N)-->
+-------------------------------------------------------------------------+
| stream(ss_C(N)) |
+-------------------------------------------------------------------------+
=
<--l(N)--><-l_C(Bob)->
+--------++----------+
| xxxxxx || 00000000 |
+--------++----------+
(+)
<--------1300---------------------------------------------------><-l_C(Bob)->
+---------------------------------------------------------------------------+
| stream(ss_C(Bob)) |
+---------------------------------------------------------------------------+
=
<---l(N) + l_C(Bob)-->
+--------------------+
| xxxxxxxxxxxxxxxxxx |
+--------------------+
(+)
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob by Alice |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob by Alice with filler |
+---------------------------------------------------------------+
4. Onion Encryption (Carol)
<-l_C(Bob)-><--------1300--------------------------------------------------->
+----------++---------------------------------------------------------------+
| p_C(Bob) || encrypted payload for Bob by Alice with filler |
+----------++---------------------------------------------------------------+
(+) <---------->
+---------------------------------------------------------------+ truncated
| stream(ss_C(Bob)) |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob by Carol |
+---------------------------------------------------------------+
<--l(N)--><---------1300 - l(N)--------------------------------->
+--------++-----------------------------------------------------+
| p(N) || encrypted payload for Bob by Carol (truncated) |
+--------++-----------------------------------------------------+
(+)
+---------------------------------------------------------------+
| stream(ss_C(N)) |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for N |
+---------------------------------------------------------------+
5. Decryption
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for N |
+---------------------------------------------------------------+
(+) <--l(N)-->
+-------------------------------------------------------------------------+
| stream(ss_C(N)) |
+-------------------------------------------------------------------------+
=
<--l(N)--><--------1300--------------------------------------------------->
+--------++---------------------------------------------------------------+
| p(N) || encrypted payload for Bob by Carol |
+--------++---------------------------------------------------------------+
(+) <-l_C(Bob)->
+---------------------------------------------------------------------------+
| stream(ss_C(Bob)) |
+---------------------------------------------------------------------------+
=
<-l_C(Bob)-><--------1300 - l_C(Bob)----------------------------><-l_C(Bob)->
+----------++---------------------------------------------------------------+
| p_C(Bob) || encrypted payload for Bob by Alice with filler |
+----------++---------------------------------------------------------------+
(+)
<---l(N) + l_C(Bob)-->
+--------------------+
| xxxxxxxxxxxxxxxxxx |
+--------------------+
(+)
<------- 1300 --------------------------------------------------><---l_A(Bob)--->
+-------------------------------------------------------------------------------+
| stream(ss_A(Bob)) |
+-------------------------------------------------------------------------------+
=
<---l_A(Bob)---><------- 1300 -------------------------------------------------->
+--------------++---------------------------------------------------------------+
| p_A(Bob) || encrypted payload for M |
+--------------++---------------------------------------------------------------+
(+) <-l(M)->
+-----------------------------------------------------------------------+
| stream(ss_A(M)) |
+-----------------------------------------------------------------------+
=
<-l(M)-><------- 1300 -------------------------------------------------->
+------++---------------------------------------------------------------+
| p(M) || encrypted payload for Alice |
+------++---------------------------------------------------------------+
(+)
+---------------------------------------------------------------+
| stream(ss_A(Alice)) |
+---------------------------------------------------------------+
=
<-----------------1300------------------------------------------>
<- l(Alice) -><---><------l(N) + l_C(Bob) + l_A(Bob) + l(M)----->
+------------++---++--------------------------------------------+
| p(Alice) || r || xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
+------------++---++--------------------------------------------+
Rendezvous with normal payment onions is not very space-efficient. A full onion (1366 bytes) needs to be shared with Carol. And then Carol needs to transmit to Bob either 650 bytes of filler (which all intermediate nodes need to forward) or some information about each hop (rho key and payload length). This is small information leak: Bob can deduce an upper bound on the number of hops between him and Carol, and an upper bound on the number of bytes Carol sent to each intermediate hop.
When used with trampoline, it becomes more practical. The rendezvous is only done on a trampoline onion. Carol's filler can then be transmitted inside the outer onion: only trampoline nodes need to know about it and forward it to the next trampoline node, until it reaches the rendezvous. Intermediate routing nodes don't need to know about trampoline nor rendezvous.
An intermediate trampoline hop needs up to 84 bytes. The last trampoline hop needs up to 91 bytes.
We want Alice to be able to insert a trampoline hop between herself and the rendezvous. We also want Carol to be able to insert a trampoline hop between herself and the rendezvous.
That means a trampoline onion of size 514 bytes (580 with mac and header) would be enough (252 bytes for Carol, 262 for Alice). If we want Alice or Carol to be able to insert more hops, we can tweak the size of the trampoline onion.
The payload in the outer onion for Bob would need up to 925 bytes. That leaves 375 bytes to intermediate hops, which means at least 5 intermediate hops between trampoline nodes (more if we can use TLV for some intermediate nodes, because it's more compact).
Assuming we find a more efficient way of transmitting the filler to Bob, we could increase that number.
Christian has a concurrent proposal that is more space-efficient (https://github.com/lightningnetwork/lightning-rfc/blob/rendez-vous/proposals/0001-rendez-vous.md).
In this case rendezvous always uses an inner onion, so we only care about the part between Bob and Alice.
Carol -> ... -> Bob -> M1 -> M2 -> Alice
Here is a full diagram of the scheme (parts 1 and 3 are standard Sphinx operations):
1. Filler Generation (Alice)
<---l(M1)--->
+-----------+
| 0000000000|
+-----------+
(+)
<-----------------1300------------------------------------------><---l(M1)--->
+----------------------------------------------------------------------------+
| stream(ss(M1)) |
+----------------------------------------------------------------------------+
=
<---l(M1)---><--l(M2)-->
+-----------++---------+
| xxxxxxxxx || 0000000 |
+-----------++---------+
(+)
<-----------------1300------------------------------------------><--l(M2)-->
+--------------------------------------------------------------------------+
| stream(ss(M2)) |
+--------------------------------------------------------------------------+
=
<-----l(M1) + l(M2)---->
+----------------------+
| xxxxxxxxxxxxxxxxxxxx |
+----------------------+
2. Pre-filler Generation (Alice)
1300 - l(Alice) - l(M1) - l(M2)
<------------------------->
+-------------------------+
| stream(ss(Bob)) |
+-------------------------+
(+)
<--l(Alice)-->
+---------------------------------------+
| stream(ss(A)) |
+---------------------------------------+
(+)
<--l(M2)--><--l(Alice)-->
+--------------------------------------------------+
| stream(ss(M2)) |
+--------------------------------------------------+
(+)
<---l(M1)---><--l(M2)--><--l(Alice)-->
+---------------------------------------------------------------+
| stream(ss(M1)) |
+---------------------------------------------------------------+
=
+-------------------------+
| pre-filler |
+-------------------------+
3. Onion Encryption (Alice)
<-----------------1300------------------------------------------>
<--l(Alice)--><-------------------------><-----l(M1) + l(M2)---->
+------------++-------------------------++----------------------+
| p(Alice) || pre-filler || filler |
+------------++-------------------------++----------------------+
(+)
+---------------------------------------+
| stream(ss(A)) |
+---------------------------------------+
=
<---------------------------------------><-----l(M1) + l(M2)---->
+---------------------------------------++----------------------+
| encrypted payload for Alice || filler |
+---------------------------------------++----------------------+
<--l(M2)--><--------1300 - l(M2)-------------------------------->
+---------++----------------------------------------------------+
| p(M2) || encrypted payload for Alice (truncated) |
+---------++----------------------------------------------------+
(+)
+---------------------------------------------------------------+
| stream(ss(M2)) |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for M2 |
+---------------------------------------------------------------+
<---l(M1)---><--------1300 - l(M1)------------------------------>
+-----------++--------------------------------------------------+
| p(M1) || encrypted payload for M2 (truncated) |
+-----------++--------------------------------------------------+
(+)
+---------------------------------------------------------------+
| stream(ss(M1)) |
+---------------------------------------------------------------+
=
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for M1 |
+---------------------------------------------------------------+
=
<----l(M1) + l(M2) + l(Alice)--------><---- truncated ---------->
+------------------------------------++-------------------------+
| partial onion || stream(ss(Bob)) |
+------------------------------------++-------------------------+
We can combine Christian's proposal with trampoline. That creates three layers of onion (!!!).
<---33---><--------1300---------------------------------------------------><-32-->
+------++--------++---------------------------------------------------------------++-----+
+ 0x00 || ephkey || || mac |
+------++--------++---------------------------------------------------------------++-----+
| |
+-------------------+ +-----------------+
| |
| (inside tlv record inside last hop's payload) |
<---33---><--------400-----------------------><-32-->
+--------++----------------------------------++-----+
| ephkey || || mac |
+--------++----------------------------------++-----+
| |
+----------+ +--------+
| |
| (tlv record in rdv payload) |
<---33---><--------200------><-32-->
+--------++-----------------++-----+
| ephkey || || mac |
+--------++-----------------++-----+
Alice creates a partial trampoline onion, containing the payload for herself and a payload for M.
She uses Christian's trick to compress the trampoline onion with a shared secret with Bob.
Alice also needs to provide Bob's node_id in the invoice.
Carol wants to pay the invoice. If Carol doesn't support trampoline, she finds a route to Bob and puts the partial onion inside the payload for Bob. If Carol wants to use trampoline, she creates a trampoline onion to Bob, containing the partial onion in the payload for Bob. Then she finds a route to the first trampoline node and puts the trampoline onion in the payload for the first trampoline node. We may want to tweak the relative sizes to make sure Carol can insert a trampoline node before Bob.
When Bob receives a normal onion, he decrypts it. If he finds a partial onion inside a tlv record, he re-creates the prefiller. He can try both trampoline size and normal size until the macs check out (Carol doesn't have to explicitly tell Bob whether it's using trampoline or not). Bob then forwards the payment using the reconstructed onion.
Hornet is a good middle to long term solution. Hornet will provide many features at once, and we should definitely consider it. However it's a network-wide change. If implementing a shorter term rendezvous was complex, then it would make sense to go directly to Hornet. But the code changes for rendezvous are quite simple, so I believe it makes sense to implement them today.