# Sphinx onion encryption: from Zero to Hero

Lightning uses an onion encryption scheme called [Sphinx](http://www.cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf)
to guarantee privacy along a payment path.

This article describes the Sphinx construction.
It can be particularly helpful for future implementers, curious users or people who want to tinker
with the crypto to provide new functionalities (such as rendezvous routing).

## Table of Contents

* [Notations](#notations)
* [Computing shared secrets](#computing-shared-secrets)
* [Generating a filler](#generating-a-filler)
* [Creating the payload](#creating-the-payload)
* [Decrypting the hop payload](#decrypting-the-hop-payload)
* [Full diagram](#full-diagram)

## Notations

```text
Alice -> N(1) -> N(2) -> ... -> N(r)
```

N(i)'s `node_id` is P(i) = k(i) * G.
The length of the encrypted payload sent to N(i) is l(i) (this includes the inner mac).
The total payload length is 1300 bytes.

## Computing shared secrets

* session_key <- {0;1}^256
* ek(1) = session_key
* Shared with N(1):
  * E(1) = ek(1) * G (sent unencrypted in the onion header)
  * ss(1) = H(ek(1) * P(1)) = H(k(1) * E(1))
  * rho(1) = HMAC(0x72686F, ss(1))
  * b(1) = H(E(1) || ss(1))
* ...
* ek(i) = b(i-1) * ek(i-1)
* Shared with N(i):
  * E(i) = ek(i) * G (sent unencrypted in the onion header)
  * ss(i) = H(ek(i) * P(i)) = H(k(i) * E(i))
  * rho(i) = HMAC(0x72686F, ss(i))
  * b(i) = H(E(i) || ss(i))

Every N(i) is able to compute E(i+1) = b(i) * E(i).

## Generating a filler

* Generate filler for payloads 1 to (r-1)
* Total of `l(1) + l(2) + ... + l(r-1)` bytes
* filler = []
* For i <- 1..(r-1):
  * filler <- (filler + [0; l(i)]) xor stream(rho(i))[1300-l(i-1)-...-l(1):1300+l(i)]

Example filler for 3 nodes:

```text
                                        <---l(1)--->
                                        +----------+
                                        | 00000000 |
                                        +----------+
                                             (+)
<-----------------1300-----------------><---l(1)--->
+--------------------------------------------------+
|         stream(rho(1))                           |
+--------------------------------------------------+
                                              =
                                        <---l(1)---><-----l(2)----->
                                        +----------++--------------+
                                        | xxxxxxxx || 000000000000 |
                                        +----------++--------------+
                                                  (+)
                <-----------------1300-------------><-----l(2)----->
                +--------------------------------------------------+
                |         stream(rho(2))                           |
                +--------------------------------------------------+
                                                   =
                                        <---l(1) + l(2)------------><----l(3)---->
                                        +--------------------------++------------+
                                        | xxxxxxxxxxxxxxxxxxxxxxxx || 0000000000 |
                                        +--------------------------++------------+
                                                             (+)
                              <-----------------1300---------------><----l(3)---->
                              +--------------------------------------------------+
                              |         stream(rho(3))                           |
                              +--------------------------------------------------+
                                                              =
                                        <---l(1) + l(2) + l(3)------------------->
                                        +----------------------------------------+
                                        | xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
                                        +----------------------------------------+
```

## Creating the payload

The payload is encrypted hop by hop, starting from the recipient.
Every hop is authenticated.
I'm ignoring the mac handling for simplicity, but there's nothing complicated with it.

* Special case for the recipient:
  * payload(r) = ((p(r) + random bytes) xor stream(rho(r))[0:1300-l(r-1)-...-l(1)]) + filler
* For i <- (r-1)..1:
  * payload(i) = (p(i) + payload(i-1)[0:1300-l(i)]) xor stream(rho(i))

```text
                                          <--------1300------------------------------------------------------------------->
                                          <---l(r)---><-------------------------><----l(1) + l(2) + l(3)------------------>
                                          +----------++-------------------------++----------------------------------------+
                                          | p(r)     || random initial bytes    || xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
                                          +----------++-------------------------++----------------------------------------+
                                                          (+)
                                          <-------1300 - l(1) - l(2) - l(3)----->
                                          +-------------------------------------+
                                          |         stream(rho(r))              |
                                          +-------------------------------------+
                                                           =
                                          <--------1300------------------------------------------------------------------->
                                          +-------------------------------------------------------------------------------+
                                          | encrypted payload for N(r)                                                    |
                                          +-------------------------------------------------------------------------------+
                            <----l(3)----><-------1300 - l(3)----------------------------------------------->
                            +------------++-----------------------------------------------------------------+
                            | p(3)       || encrypted payload for N(r) (truncated)                          |
                            +------------++-----------------------------------------------------------------+
                                                    (+)
                            +-------------------------------------------------------------------------------+
                            |         stream(rho(3))                                                        |
                            +-------------------------------------------------------------------------------+
                                                     =
                            <--------1300------------------------------------------------------------------->
                            +-------------------------------------------------------------------------------+
                            | encrypted payload for N(3)                                                    |
                            +-------------------------------------------------------------------------------+
            <-----l(2)-----><-------1300 - l(2)--------------------------------------------->
            +--------------++---------------------------------------------------------------+
            | p(2)         || encrypted payload for N(3) (truncated)                        |
            +--------------++---------------------------------------------------------------+
                                    (+)
            +-------------------------------------------------------------------------------+
            |         stream(rho(2))                                                        |
            +-------------------------------------------------------------------------------+
                                     =
            <--------1300------------------------------------------------------------------->
            +-------------------------------------------------------------------------------+
            | encrypted payload for N(2)                                                    |
            +-------------------------------------------------------------------------------+
<---l(1)---><--------1300 - l(1)------------------------------------------------>
+----------++-------------------------------------------------------------------+
| p(1)     || encrypted payload for N(2) (truncated)                            |
+----------++-------------------------------------------------------------------+
                        (+)
+-------------------------------------------------------------------------------+
|         stream(rho(1))                                                        |
+-------------------------------------------------------------------------------+
                         =
<--------1300------------------------------------------------------------------->
+-------------------------------------------------------------------------------+
| encrypted payload for N(1)                                                    |
+-------------------------------------------------------------------------------+
```

## Decrypting the hop payload

This is where the filler matters: because it's generated with the same stream
cipher, decrypting re-creates it on-the-fly (and thus ensures macs are valid).

```text
<--------1300------------------------------------------------------------------->
+-------------------------------------------------------------------------------+
| encrypted payload for N(1)                                                    |
+-------------------------------------------------------------------------------+
                        (+)                                                      <---l(1)--->
+-------------------------------------------------------------------------------------------+
|         stream(rho(1))                                                                    |
+-------------------------------------------------------------------------------------------+
                         =
<---l(1)---><--------1300------------------------------------------------------------------->
+----------++-------------------------------------------------------------------------------+
| p(1)     || encrypted payload for N(2)                                                    |
+----------++-------------------------------------------------------------------------------+
                                                (+)                                          <-----l(2)----->
            +-----------------------------------------------------------------------------------------------+
            |         stream(rho(2))                                                                        |
            +-----------------------------------------------------------------------------------------------+
            <-----l(2)----->                     =
            +--------------++-------------------------------------------------------------------------------+
            | p(2)         || encrypted payload for N(3)                                                    |
            +--------------++-------------------------------------------------------------------------------+
                                                                (+)                                          <----l(3)---->
                            +---------------------------------------------------------------------------------------------+
                            |         stream(rho(3))                                                                      |
                            +---------------------------------------------------------------------------------------------+
                            <----l(3)---->                       =
                            +------------++-------------------------------------------------------------------------------+
                            | p(3)       || encrypted payload for N(r)                                                    |
                            +------------++-------------------------------------------------------------------------------+
                                                                  (+)
                                          +-------------------------------------------------------------------------------+
                                          |         stream(rho(r))                                                        |
                                          +-------------------------------------------------------------------------------+
                                                                   =
                                          <--------1300------------------------------------------------------------------->
                                          <---l(r)---><-------------------------><--- l(1) + l(2) + l(3) ----------------->
                                          +----------++-------------------------++----------------------------------------+
                                          | p(r)     || random initial bytes    || xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
                                          +----------++-------------------------++----------------------------------------+
```

## Full diagram

```text
Alice -> Bob -> Carol -> Dave
```

```text
1. Filler Generation

                                                                 <-----l(B)----->
                                                                 +--------------+
                                                                 | 000000000000 |
                                                                 +--------------+
                                                                        (+)
<-----------------1300------------------------------------------><-----l(B)----->
+-------------------------------------------------------------------------------+
|         stream(ss(Bob))                                                       |
+-------------------------------------------------------------------------------+
                                                                         =
                                                                 <-----l(B)-----><-l(C)->
                                                                 +--------------++------+
                                                                 | xxxxxxxxxxxx || 0000 |
                                                                 +--------------++------+
                                                                             (+)
                <-----------------1300------------------------------------------><-l(C)->
                +-----------------------------------------------------------------------+
                |         stream(ss(C))                                                 |
                +-----------------------------------------------------------------------+
                                                                              =
                                                                 <-----l(B) + l(C)------>
                                                                 +----------------------+
                                                                 | xxxxxxxxxxxxxxxxxxxx |
                                                                 +----------------------+

2. Onion Encryption

                        <-----------------1300------------------------------------------>
                        <----l(D)----><-------------------------><------l(B) + l(C)----->
                        +------------++-------------------------++----------------------+
                        | p(D)       || random init bytes       || xxxxxxxxxxxxxxxxxxxx |
                        +------------++-------------------------++----------------------+
                                        (+)
                        <---------1300 - l(B) - l(C)------------>
                        +---------------------------------------+
                        |         stream(ss(D))                 |
                        +---------------------------------------+
                                         =
                        <---------1300 - l(B) - l(C)------------><------l(B) + l(C)----->
                        +---------------------------------------++----------------------+
                        | encrypted payload for Dave            || xxxxxxxxxxxxxxxxxxxx |
                        +---------------------------------------++----------------------+
                <-l(C)-><--------1300 - l(C)------------------------------------>
                +------++-------------------------------------------------------+
                | p(C) || encrypted payload for Dave (truncated)                |
                +------++-------------------------------------------------------+
                                        (+)
                +---------------------------------------------------------------+
                |         stream(ss(C))                                         |
                +---------------------------------------------------------------+
                                         =
                <--------1300--------------------------------------------------->
                +---------------------------------------------------------------+
                | encrypted payload for Carol                                   |
                +---------------------------------------------------------------+
<-----l(B)-----><----------1300 - l(B)-------------------------->
+--------------++-----------------------------------------------+
| p(B)         || encrypted payload for Carol (truncated)       |
+--------------++-----------------------------------------------+
                        (+)
+---------------------------------------------------------------+
|         stream(ss(B))                                         |
+---------------------------------------------------------------+
                         =
<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob                                     |
+---------------------------------------------------------------+

3. Onion Decryption

<--------1300--------------------------------------------------->
+---------------------------------------------------------------+
| encrypted payload for Bob                                     |
+---------------------------------------------------------------+
                           (+)                                   <-----l(B)----->
+-------------------------------------------------------------------------------+
|         stream(ss(B))                                                         |
+-------------------------------------------------------------------------------+
                            =
<-----l(B)-----><------- 1300 -------------------------------------------------->
+--------------++---------------------------------------------------------------+
| p(B)         || encrypted payload for Carol                                   |
+--------------++---------------------------------------------------------------+
                                        (+)                                      <-l(C)->
                +-----------------------------------------------------------------------+
                |         stream(ss(C))                                                 |
                +-----------------------------------------------------------------------+
                                         =
                <-l(C)-><------- 1300 -------------------------------------------------->
                +------++---------------------------------------------------------------+
                | p(C) || encrypted payload for Dave                                    |
                +------++---------------------------------------------------------------+
                                        (+)
                        +---------------------------------------------------------------+
                        |         stream(ss(D))                                         |
                        +---------------------------------------------------------------+
                                         =
                        <-----------------1300------------------------------------------>
                        <----l(D)----><-------------------------><------l(B) + l(C)----->
                        +------------++-------------------------++----------------------+
                        | p(D)       || random init bytes       || xxxxxxxxxxxxxxxxxxxx |
                        +------------++-------------------------++----------------------+
```