Sphinx Header Processing Example

This is another document from the Mix Implementation series. In the other two notes:

• libp2p MIX Architecture and API
• Sphinx SURBs implementation in the libp2p MIX protocol

you can find a high level overview I created interactively with OpenAI GPT-5.5. This note is fully hand-crafted though.

We also have a detailed illustrated example in Sphinx Header Processing Infographic with the web version available at https://link.excalidraw.com/readonly/6y7DRQlUhkkBMZScEONS.

In this note we are documenting how the Sphinx headers are created in our current MIX Protocol Implementation and how they are processed by the mix nodes in the reply path. Where handy, comments about forward processing are also included.

We are actually focusing on the part of the header here, but I will keep use the word “header” where convenient.

The objective is to have something that illustrates the complex mechanics of maintaining the constant size of the elements (part of the Sphinx header) using the so called fillers. It should help those who are working with Sphinx implementation and want to have a reference example to “quickly” visualize how the whole machinery works. As such it can be useful also for those who already know Sphinx very well.

Notation

To create the examples that are visual and where you can “easily” see things happening, I introduced a couple of custom constructs.

- the AES-CTR keystream derived from the per-hop shared secret . - subrange of starting at index and ending on index ([x ..< y] in Nim). - a sequence of s of length .

Now, to keep notation compact. Imagine we have a bit sequence of 0 of length : 00000000 and a keystream . Now imagine applying a subrange of of the same length to that bit sequence, e.g. :

The result is a bit stream with the bit value in the first position and in the last position. We denote the result of applying a subrange to 0-bit sequence of the same length by . Obviously .

A sequence of XOR operations may be applied to a given bit sequence:

We denote this operation as:

In particular, if is concatenation of bit sequences , , and , and size of , denoted , is , then applying a sequence of XOR operations to the sequence will be written as:

where . Notice that the result of the following two operations will be the same:

Because the two cancel each other, to make it more visible, we will write:

Sphinx Header

The Sphinx Header is defined as , where:

• is a (blinded) public key (group element; .
• is the (encrypted) routing information
• is a MAC (message authentication code)

Formal definition of and and how they are used in Sphinx can be found in note Sphinx packet format. In this document, I want to focus more on , by giving an illustrative example of its construction and processing. Special attention will be given to the so called filler, which I personally found the most challenging to “see”. This document should help in grasping the construction and processing of in a more visual manner.

The intention of this document is, in the first place, to help understanding the implementation of the current MIX protocol. Thus, some things will be make bluntly concrete, e.g. sizes, and to find more details about them and about Mix protocol implementation in general, the reader should refer to libp2p MIX Architecture and API and Sphinx SURBs implementation in the libp2p MIX protocol. For brevity, in this document I will not repeat what is written there.

The MIX implementation uses the following constants:

const
  k* = 16
  r* = 5
  t* = 6
  AlphaSize* = 32
  BetaSize* = ((r * (t + 1)) + 1) * k
  GammaSize* = 16
  HeaderSize* = AlphaSize + BetaSize + GammaSize
  DelaySize* = 2
  AddrSize* = (t * k) - DelaySize
  PacketSize* = 4608
  MessageSize* = PacketSize - HeaderSize - k
  PayloadSize* = MessageSize + k
  SurbSize* = HeaderSize + AddrSize + k
  SurbLenSize* = 1
  SurbIdLen* = k

Recall that k corresponds to the bits of security from the MIX Specification and that r is the maximum number of hopes supported and t*k ( in the spec) gives us the size of combined address and delay width. The size of - or BetaSize - is given by formula , which corresponds to ((r * (t + 1)) + 1) * k in the code snippet above. To decipher this formula let’s write it in a bit less compact form:

corresponds to the space in bytes needed to hold combined address and delay blocks ( bytes each) and blocks ( bytes each) resulting in bytes. Together with extra bytes - perhaps reserved for future use, or just in case - we arrive at fixed size of , bytes.

Knowing , we get:

But let’s focus back at . As we will see in a moment, its size - bytes - is crucial. It contains the routing information for each single hop, and at each hop, one such block will be removed and to keep the size of fixed and still indistinguishable for a potential evil observer, we use a so called filler.

Constructing the filler

What may make construction of the filler hard to understand is that three things: construction of the filler, construction of the , and then finally processing of in the forward and the reply path, all must be perfectly aligned. Moreover, because the header (and so also ) for the very first hop must contain the routing information for all the remaining hops, the header construction needs to happen in the backward direction (starting from the destination address).

The filler is pre-computed before the construction of successive -as is even started:

proc computeFillerStrings(s: seq[seq[byte]]): Result[seq[byte], string] =
  var filler: seq[byte] = @[]
 
  for i in 1 ..< s.len:
    let
      aes_key = deriveKeyMaterial("aes_key", s[i - 1]).kdf()
      iv = deriveKeyMaterial("iv", s[i - 1]).kdf()
 
    let
      fillerLength = (t + 1) * k
      zeroPadding = newSeq[byte](fillerLength)
 
    filler = aes_ctr_start_index(
      aes_key,
      iv,
      filler & zeroPadding,
      (((t + 1) * (r - i)) + t + 2) * k,
    )
 
  return ok(filler)

Let’s see how the filler will be created for a 4-hop Mix path.

As we see from the routine above for a 4-hop Mix path we will have 3 iterations (1 ..< s.len).

i = 1:

or to make it more explicit:

i = 2:

i = 3:

Constructing the header

Now that we have the filler constructed, let’s have an example of a step-by-step construction of the header.

Recall, here we will be moving backwards, and the corresponding routine is as follows:

proc computeBetaGamma(
  s: seq[seq[byte]],
  hops: openArray[Hop],
  delay: openArray[seq[byte]],
  destHop: Hop,
  id: SURBIdentifier,
): Result[tuple[beta: seq[byte], gamma: seq[byte]], string] =
  let sLen = s.len
  var
    beta: seq[byte]
    gamma: seq[byte]
 
  let filler = computeFillerStrings(s).valueOr:
    return err("Error in filler generation: " & error)
 
  for i in countdown(sLen - 1, 0):
    let
      beta_aes_key = deriveKeyMaterial("aes_key", s[i]).kdf()
      mac_key = deriveKeyMaterial("mac_key", s[i]).kdf()
      beta_iv = deriveKeyMaterial("iv", s[i]).kdf()
 
    if i == sLen - 1:
      let destBytes = destHop.serialize()
      let destPadding = destBytes & delay[i] & @id & newSeq[byte](PaddingLength)
      let aes = aes_ctr(beta_aes_key, beta_iv, destPadding)
      beta = aes & filler
    else:
      let betaPrefix =
        beta[0 .. (((r * (t + 1)) - t) * k) - 1]
 
      let routingInfo = RoutingInfo.init(
        hops[i + 1],
        delay[i],
        gamma,
        betaPrefix,
      )
 
      let serializedRoutingInfo = routingInfo.serialize()
      beta = aes_ctr(beta_aes_key, beta_iv, serializedRoutingInfo)
 
    gamma = hmac(mac_key, beta).toSeq()
 
  return ok((beta: beta, gamma: gamma))

We see that the filler is indeed pre-computed before the construction loop even starts.

Also recall, that the same routine is called for both forward and reply paths, the difference is in the routing information for the last hop.

For forward path the destHop is the real destination address, encoded as a Hop and id is set to default(SURBIdentifier), all zero bytes. The forward-path exit uses destHop to dial the destination protocol.

For the reply path the destHop is an empty Hop(), which serializes as zero address bytes. This marks that the terminal return hop is not forwarding to another destination. ‘id’ for the reply path is set to random nonzero SURB identifier generated by buildSurbs. The original sender uses it to find connCreds.

In what follows we use the reply path as an example (path length is as before).

i = 3:

As indicated above, instead of we will have , where space normally used for is used to store SURB id where bytes. Just for reference, for the forward path, the final will be set to , where is the address of the destination node.

Now, bytes. The final routing information is naturally shortest (there are no more hops after it), thus in order to keep size of constant ( bytes), we add some extra padding (PaddingLength) and the full filler ( bytes). The extra PaddingLength is the consequence of the fact, that the size of has been chosen to accommodate max hops, corresponding to bytes plus extra bytes for future use (or for some other reason), giving in total. Because for 4-hop path, the filler is bytes long PaddingLength is:

or in a more generic form:

In our case PathLength = 4, thus,

Before encryption thus, we have:

and after encryption :

Notice that in this first iteration only is encrypted and the filler is used pre-computed.

i = 2:

From , we drop the last filler segment ( bytes) and prepend the routing info:

and after encrypting we get:

which after canceling out the outer filler encryption becomes:

i = 1:

Here again, before next level of encryption, we drop the last filler segment ( bytes) from and prepend the routing info to :

and after encrypting :

which leaves us with:

i = 0: final construction step.

which after encryption gives us:

No fillers are left at this last step, thus nothing cancels out.

All those computations are happening in the entry layer of the node that wishes to use the MIX network for anonymous communication. The computed , together with and , will form the header . Each SURB header will be included in the corresponding SURB packet. All SURBs will be pre-pended to the message forming the actual payload , which after onion encryption together with the forward path header will be sent to the first forward path hop. The exit node seeing that the reply is expected will retrieve the reply message from the destination node and send it back using all included SURB packets.

Processing the header

When processing, at each hop the node removes its own routing information, i.e. the bytes, containing sequence , where is the address of the next hop, is the delay for the current hop, and is the MAC of the (encrypted) next (so, ). The tricky part is that the whole is encrypted and (further encrypted with ) inside of it is missing the last bytes that were removed during header construction to accommodate the routing information of the previous hop (remember we are be going backward during header construction) while keeping the header size constant. We already know that the current node cannot just directly decrypt the whole , and pad the last bytes with e.g. , because this would leak the information about the message position in the mix path. Instead it makes sure that the last bytes are random. It achieves this by using its own decryption keystream (derived from its secret ) it uses to decrypt . It does so, by appending before decrypting its own . Thus, for all hops except the final one, the received is:

Or using our special notation:

Before decrypting using , we first append to it. Then we perform XOR operation using :

which is nothing more than :

above is the that the next hop will receive and its MAC will have to match . The in the equation above, is part of the filler, and each hop will reveal another fragment of it. On arriving at the last hop, the whole filler will be reconstructed. For example, for a 4-hop reply path, the received by the last Mix node on the path will be:

Also, here, it will be extended and XORed using resulting in:

The filler part will be dropped leaving us with:

For the forward path the processing will be analogical, the only difference is that instead of in we will have .

Let’s take a look at an example processing in the reply path. It is largely identical to the forward path, only the processing at the final destination, which in case of SURB packets is the original sender, will be different.

The exit node sends the encrypted payload (with the key included in the given SURB), to the first hop on the return path. The address of the corresponding mix node is included in the SURB packet. Thus, our processing example starts at thevery fist hop - hop 0.

hop 0:

The node extracts , , and from the header. Using and its own private key, it derives the shared secret , from which other keys are subsequently derived. In this document we focus on the processing of the element, so the details of the key derivation are skipped. We assume that the node has - the AES-CTR keystream derived from the per-hop shared secret .

Before decrypting , the node appends to the end of it:

With more details:

which reduces to:

We see that is successfully decrypted. It is then removed and the remaining part is shifted to the left by the size of - bytes:

Yes, this is exactly the same we constructed in construction phase we shown in the previous section. Notice the appended part of the filler. If there would be any different or misalignement in the reconstructed , the next node would detect it using the received MAC . The node at hop 0 is not able to fake that , as it is keyed with , which the node at hop 0 does not have.

Now we should start seeing how it all works.

hop 1:

This reduces to:

After removing and shifting to the left, we get the original constructed :

hop 2:

which is:

which, after removing and shifting, gives us:

It matches from the construction phase, and we also now see fully reconstructed filler.

hop 3:

There is no , and of course, the filler after this last step does not make any sense anymore, but we are only interested in the first bytes:

This is the end of the processing phase for the element, and the end of this document.