04-onion-routing.md

BOLT #4: Onion Routing Protocol

Overview

This document describes the construction of an onion routed packet that is used to route a payment from a origin node to a final node, over a number of intermediate nodes, called hops.

The routing schema is based on the Sphinx construction, and is extended with a per-hop payload.

Intermediate nodes forwarding the message can verify the integrity of the packet, and can learn about which node they should forward the packet to. They cannot learn about which other nodes, besides their predecessor or successor, are part of this route, nor can they learn the length of the route and their position within it. The packet is obfuscated at each hop, so that a network level attacker cannot associate packets belonging to the same route, i.e., packets belonging to a route do not share any identifying information. Notice that this does not preclude the possibility to associate packets by performing a traffic analysis.

The route is constructed by the sender, which knows a public key of each intermediate node. Knowing the intermediate node's public key allows the sender to create a shared secret using ECDH for each intermediate node, including the final recipient. The shared secret is then used to generate a pseudo-random stream of bytes to obfuscate the packet, and a number of keys used to encrypt the payload and compute HMACs ensuring integrity at each hop.

This specification describes version 0 of the packet format and routing mechanism. Should a node receive a higher version packet that it does not implement it MUST report a route failure to the sending node and discard the packet.

Conventions

There are a number of conventions we will adhere throughout the document:

• The maximum route length is limited to 20 hops.
• Nodes are addressed using 20 byte identifiers. These are computed from the node's public key, in accordance to the Bitcoin address creation, as RIPEMD160(SHA256(pubkey)) where pubkey is the serialized compressed public key of the node. Refer to OP_HASH160 for details.
• HMAC: the integrity verification of the packet is based on Keyed-Hash Message Authentication Code as defined by the FIPS 198 Standard, using SHA256 as hashing algorithm. The resulting HMAC is then truncated at 20 bytes in order to reduce the overhead.
• Elliptic Curve: for all computations involving elliptic curves, the Bitcoin curve, secp256k1, is used.
• Pseudo-Random Stream: ChaCha20 is used to generate a pseudo-random byte stream. For the generation we use a fixed null-nonce (0x0000000000000000), a key derived from a shared secret and a 0x00-byte stream of the desired output size as message.
• We use the terms hop and node interchangeably.
• A peer is a direct neighbor of the processing node in the overlay network.

Key Generation

A number of encryption and verification keys is derived from the shared secret:

• rho: used as key when generating the pseudo random byte stream used to obfuscate the routing information.
• gamma: used as key when generating the pseudo random byte stream used to obfuscate the per-hop payloads.
• mu: used during the HMAC generation.

The key generation takes a key-type (rho=0x72686F, gamma=0x67616d6d61 or mu=0x6d75) and a 32 byte secret as inputs and returns a 32 byte key.

Keys are generated by computing an HMAC, with SHA256 as hashing algorithm, using the key-type, i.e., rho, mu or gamma, as HMAC-key and the 32 byte shared secret as the message. The resulting HMAC is then returned as the key.

Notice that the key-type does not include a C-style 0x00 termination-byte, e.g., the length of the gamma key-type is 5 bytes, not 6.

Pseudo Random Byte Stream

The pseudo random byte stream is used to obfuscate the packet at each hop of the path, so that each hop may only recover the address of the next hop as well as the HMAC for the next hop. The pseudo random byte stream is generated by encrypting a 0x00-byte stream of the required length with ChaCha20, initialized with a key derived from the shared secret and a zero-nonce (0x00000000000000). The use of a fixed nonce is safe since the keys are never reused.

Packet Structure

The packet consists of 2 parts:

• The fixed size header containing meta information about the packet and the routing information necessary to forward the message.
• A fixed size per-hop payload containing information for each hop as they forward the message.

The overall structure of the packet is depicted below. The network format of the packet consists of the individual parts being serialized into one continguous byte-stream and then transferred to the recipient of the packet. Due to the fixed size of the packet it does not need to be prefixed by its length when transferred over a connection.

+--------+-----------------+
| header | per-hop payload |
+--------+-----------------+

The header is a fixed 854 byte array containing the necessary information for each hop to identify the next hop, and verify the integrity of the packet. It consists of a version byte, a 33 byte compressed secp256k1 public key, used during the shared secret generation, a 20 byte HMAC used to verify the packet's integrity and a 800 byte routing information field. For this specification the version byte has a constant value of 0x00.

+------------------+-----------------------+-----------------+------------...-----------+
| Version (1 byte) | Public Key (33 bytes) | HMAC (20 bytes) | Routing Info (800 bytes) |
+------------------+-----------------------+-----------------+------------...-----------+

The routing info field is a structure that holds obfuscated versions of the next hop's address and the associated HMAC. It is 800 bytes long, i.e., 20 byte MAC and 20 byte address times 20 hops, and has the following structure:

+-------------+----------+-------------+----------+-----+--------+
| n_1 address | n_1 HMAC | n_2 address | n_2 HMAC | ... | filler |
+-------------+----------+-------------+----------+-----+--------+

Where the filler consists of obfuscated deterministically generated padding. For details about how the filler is generated please see below. In addition every (address, HMAC)-pair is incrementally obfuscated at each hop.

The per-hop payloads has a similar structure:

+-------------+-------------+-------------+-----+------------+
| n_1 payload | n_2 payload | n_3 payload | ... | hop filler |
+-------------+-------------+-------------+-----+------------+

With the hopfiller being constructed in the same way as the routing info filler and each payload being incrementally obfuscated at each hop.

Packet Construction

Assuming a sender node n_0 wants to route a packet to a final recipient n_r. The sender computes a route {n_0, n_1, ..., n_{r-1}, n_r}, where n_0 is the sender itself and n_r is the final recipient. The nodes n_i and n_{i+1} MUST be peers in the overlay network. The sender gathers the public keys for n_1 to n_r and generates a random 32 byte sessionkey. Optionally the sender may pass in associated data, i.e., data that the packet commits to, but is not included in the packet itself. Associated data will be included in the HMACs and has to match the associated data provided during integrity verification at each hop.

For each node the sender computes an ephemeral public key, a shared secret and a blinding factor. The blinding factor is used at each hop to blind the ephemeral public key for the next hop. The node receiving the header will perform ECDH with the ephemeral public key and its private key to derive the same shared secret. However, when generating the packet we do not have access to the node's private key. Hence, we use the commutative property of multiplication and blind the node's public key with all previous blinding factors and perform ECDH using the node's blinded public key and the sessionkey.

The transformations at hop k are given by the following:

• The shared secret ss_k is computed by first blinding the node's public key nodepk_k with all previous blinding factors {b_1, ..., b_{k-1}}, if any, and then executing ECDH with the blinded public key and the sessionkey.
• The blinding factor is the SHA256 hash of the concatenation between the node's public key nodepk_k and the hop's shared secret ss_k. Before concatenation the node's public key is serialized in the compressed format.
• The ephemeral public key epk_k is computed by blinding the previous hop's ephemeral public key epk_{k-1} with the previous hop's blinding factor b_{k-1}.

This recursive algorithm is initialized by setting the first hop's (k=1) ephemeral public key to the public key corresponding with the sessionkey, i.e., secp256k1 is used to derive a public key for the randomly selected sessionkey.

The sender then iteratively computes the ephemeral public keys, shared secrets and blinding factors for nodes {n_2, ..., n_r}.

Once the sender has all the required information it can construct the packet. Constructing a packet routed over r hops requires r 32 byte ephemeral public keys, r 32 byte shared secrets, r 32 byte blinding factors and r 20 byte per-hop payloads. The construction returns one 1254 byte packet and the first hop's address.

The packet construction is performed in reverse order of the route, i.e., the last hop's operations are applied first.

The per-hop payload is initialized with 400 0x00 bytes. The routing info is initialized with 800 0x00 bytes. The next address and the HMAC are initialized to 20 0x00 bytes each.

Two fillers are generated with the shared secrets: a routing info filler with 40 byte hopsize and a per-hop payload filler with 20 byte hopsize. See below for details on filler generation.

For each hop in the route in reverse order the sender applies the following operations:

• It generates a rho-key, mu-key and a gamma-key using the hop's shared secret.
• The routing info field is right-shifted by 40 bytes, discarding the last 40 bytes that exceed the 800 bytes. The address is copied into the first 20 bytes of the routing info and the HMAC is copied into the following 20 bytes. The rho-key is used to generate 800 bytes of pseudo random byte stream and applied with XOR to the routing info field. Should this be the last hop, i.e., the first iteration, then the tail of the routing info field is overwritten with the routing info filler.
• The per-hop payload field is right-shifted by 20 bytes, and the last 20 bytes discarded, resulting in 400 bytes of per-hop payload. The current hop's per-hop payload is copied into the first 20 bytes. The gamma-key is used to generate 400 bytes of pseudo random byte stream which are then applied using XOR to the per-hop payloads field. Should this be the last hop then the tail of the per-hop payloads field is overwritten with the per-hop payload filler.
• The next HMAC is computed over the concatenated routing info, per-hop payload and associated data, with the mu-key as HMAC-key.
• The next address is computed from the current node's public key using the Bitcoin address hash derivation.

The final value for the HMAC is the HMAC as it should be sent to the first hop.

The packet generation returns the serialized packet, consisting of the version byte, the ephemeral pubkey for the first hop, the HMAC for the first hop, the obfuscated routing info and the obfuscated per-hop payload.

The following code implements the packet construction in Go:

func ConstructPacket(paymentPath []*btcec.PublicKey, sessionKey *btcec.PrivateKey,
	rawHopPayloads [][]byte) ([]byte) {
	numHops := len(paymentPath)
	
	ephemeralpks := make([]*btcec.PublicKey, numHops)
	sharedsecrets := make([][sha256.Size]byte, numHops)
	blindingfactors := make([][sha256.Size]byte, numHops)

	ephemeralpks[0] = sessionKey.PubKey()
	sharedsecrets[0] = sha256.Sum256(btcec.GenerateSharedSecret(sessionKey, paymentPath[0]))
	blindingfactors[0] = computeBlindingFactor(ephemeralpks[0], sharedsecrets[0][:])

	for i := 1; i <= numHops-1; i++ {
		ephemeralpks[i] = blindGroupElement(ephemeralpks[i-1], blindingfactors[i-1][:])
		bpk := blindGroupElement(paymentPath[i], sessionKey.D.Bytes())
		sharedsecrets[i] = sha256.Sum256(multiScalarMult(bpk, blindingfactors[:i]).X.Bytes())
		blindingfactors[i] = computeBlindingFactor(ephemeralpks[i], sharedsecrets[i][:])
	}

	filler := generate_filler("rho", numHops, 2*20, sharedsecrets)
	hopfiller := generate_filler("gamma", numHops, 20, sharedsecrets)

	// Initialize all of these to 0x00-arrays
	var header [20 * 40]byte
	var hoppayloads [20 * 20]byte
	var next_hmac [20]byte
	var next_address [20]byte

	// Compute header in reverse path order
	for i := numHops - 1; i >= 0; i-- {
		rhoKey := generateKey("rho", sharedsecrets[i])
		gammaKey := generateKey("gamma", sharedsecrets[i])
		piKey := generateKey("pi", sharedsecrets[i])
		muKey := generateKey("mu", sharedsecrets[i])

		// Shift and obfuscate header
		stream := generateStream(rhoKey, numStreamBytes)
		rightShift(header[:], 2*20)
		copy(header[:], next_address[:])
		copy(header[20:], next_hmac[:])
		xor(header[:], header[:], streamBytes[:routingInfoSize])

		// Shift and obfuscate per-hop payload
		stream = generateStream(gammaKey, uint(len(hoppayloads)))
		rightShift(hoppayloads[:], 20)
		copy(hoppayloads[:], rawHopPayloads[i])
		xor(hoppayloads[:], hoppayloads[:], hopStreamBytes)

		// Add fillers if this is the last hop
		if i == numHops-1 {
			copy(header[len(header)-len(filler):], filler)
			copy(hoppayloads[len(hoppayloads)-len(hopfiller):], hopfiller)
		}
		cipher, _ := chacha20.New(piKey[:], bytes.Repeat([]byte{0x00}, 8))

		next_hmac = ComputeMac(muKey, append(append(header[:], hoppayloads[:]...), onion[:]...))
		next_address = btcutil.Hash160(paymentPath[i].SerializeCompressed())
	}
	
	// Assemble packet
	var packet [2258]byte
	version = []byte{0x00}
	copy(packet[:], version)
	copy(packet[1:], ephemeralpks[0].SerializeCompressed())
	copy(packet[34:], next_hmac)
	copy(packet[54:], header)
	copy(packet[854:], hoppayloads)
	
	return packet
}

Packet Forwarding

Upon receiving a packet a node compares the version byte of the packet with its supported versions and aborts otherwise. This specification is limited to version 0 packets and the structure of future version may change. The receiving node then splits the packet into its fields.

The node MUST check that the ephemeral public key is on the secp256k1 curve. Should this not be the case the node MUST abort processing the packet and report a route failure to the sender.

The node then computes the shared secret as described below, using the private key corresponding to its public key and the ephemeral key from the packet. The node MUST keep a log of previously used shared secrets. Should the shared secret already be in the log it MUST abort processing the packet and report a route failure, since this is likely a replay attack, otherwise the shared secret is added to the log.

The shared secret is used to compute a mu-key. The node then computes the HMAC of the packet, starting from byte 54, which corresponds to the routing info, per-hop payloads and associated data, using the mu-key. The resulting HMAC is compared with the HMAC from the packet. Should the computed HMAC and the HMAC from the packet differ then the node MUST abort processing and report a route failure. Comparison of the computed HMAC and the HMAC from the packet MUST be time-constant to avoid leaking information.

At this point the node can generate a rho-key and a gamma-key.

The routing info is deobfuscated and the information about the next hop is extracted. In order to do so the node copies the routing info field, appends 40 0x00 bytes and generates 840 pseudo random bytes using the rho-key and applies it using XOR to the copy of the routing information. The first 20 bytes of the resulting routing info are the address of the next hop, followed by the 20 byte HMAC. The routing info for the outgoing packet, destined for the next hop, consists of the 800 bytes starting at byte 40.

The per-hop payload is deobfuscated in a similar way. The node creates a copy of the per-hop payloads field and appends 20 0x00 bytes of padding. It generates 420 bytes of pseudo random bytes using the gamma-key and applies it using XOR to the padded copy of the per-hop payloads. The first 20 bytes of the padded copy are the node's per-hop payload, while the remaining 400 bytes are the per-hop payload destined for the next hop.

A special HMAC value of 20 0x00 bytes indicates that the currently processing hop is the intended recipient and that the packet should not be forwarded.

Should the HMAC not indicate route termination and the next hop be a peer of the current node, then the new packet is assembled by blinding the ephemeral key with the current node's public key and shared secret, and serializing the routing info and per-hop payload. The resulting packet is then forwarded to the addressed peer. The addressed peer MUST be a direct neighbor of the node processing the packet. Should the processing node not have a peer with the matching address, then it MUST drop the packet and signal a route failure.

Shared secret

The sender performs ECDH with each hop of the route in order to establish a secret. For each message a new sessionkey is generated. The sessionkey is a 32 byte EC private key. The shared secret creation receives a public key and a 32 byte secret as input and returns a 32 byte secret as output.

In the packet generation phase the secret is the sessionkey and the public key is the node's public key, blinded with all previous blinding factors. In the pocessing phase the secret is the node's private key and the public key is the ephemeral public key from the packet, which has been incrementally blinded by the predecessors.

The public key is multiplied by the secret, using to the secp256k1 curve. The X coordinate of the multiplication result is serialized and hashed using SHA256. The resulting hash is returned as the shared secret. Notice that this is not the ECDH variant implemented in libsecp256k1 which also includes the Y coordinate in the hash.

Filler Generation

Upon receiving a packet each node extracts the information destined for that node from the route info and the per-hop payload. The extraction is done by deobfuscating and left-shifting the field. This would make the field shorter at each hop, allowing an attacker to deduce the route length. For this reason the field is padded before forwarding. Since the padding is part of the HMAC the sender will have to generate an identical padding in order to compute the HMACs correctly for each hop. The filler is also used to pad the field-length in case the selected route is shorter than the maximum allowed route length.

We call the number of bytes extracted from the field hopsize. In case of the route info the hopsize is 40 bytes (20 bytes address and 20 bytes HMAC), while in the case of the per-hop payload it is 20 bytes.

Before deobfuscating the field the node pads the field with hopsize 0x00 bytes, such that the total length of the field is (20 + 1) * hopsize. It then generates the pseudo random byte stream of matching length and applies it with XOR to the field. This deobfuscates the information destined for it, and simultaneously obfuscates the added 0x00-bytes at the end.

In order to compute the correct HMAC, the sender has to generate the field's state at the hop. This also includes the incrementally obfuscated padding added by each hop. The incrementally obfuscated padding is called the filler.

The following code shows how the filler is generated:

func generateFiller(key string, numHops int, hopSize int, sharedSecrets [][sharedSecretSize]byte) []byte {
	fillerSize := uint((numMaxHops + 1) * hopSize)
	filler := make([]byte, fillerSize)

	// The last hop does not obfuscate, it's not forwarding anymore.
	for i := 0; i < numHops-1; i++ {

		// Left-shift the field
		copy(filler[:], filler[hopSize:])

		// Zero-fill the last hop
		copy(filler[len(filler)-hopSize:], bytes.Repeat([]byte{0x00}, hopSize))

		// Generate pseudo random byte stream
		streamKey := generateKey(key, sharedSecrets[i])
		streamBytes := generateCipherStream(streamKey, fillerSize)

		// Obfuscate
		xor(filler, filler, streamBytes)
	}

	// Cut filler down to the correct length (numHops+1)*hopSize
	// bytes will be prepended by the packet generation.
	return filler[(numMaxHops-numHops+2)*hopSize:]
}

Notice that this implementation is for demonstration purposes only, the filler can be generated much more efficiently. The last hop does not obfuscate the filler since it will not forward the packet and will not extract an HMAC for any followup hops.

Blinding EC Points

In order to vary the ephemeral public key (the EC point) between hops, it is blinded at each hop. The inputs for the blinding process are the EC point to be blinded, the node's public key and a 32 byte shared secret, while the output is a single EC point, representing the blinded element.

Blinding is done by computing a blinding factor from the node's public key and the shared secret for that hop. The blinding factor is the result of serializing the node's public key into its compressed format, appending the shared secret and computing the SHA256 hash. The blinded EC point then is the result of the scalar multiplication between the EC point and the blinding factor.

Returning Messages

The protocol includes a simple mechanism to return messages to the origin node. The returned messages may either be failures reported by any intermediate hop, or a success message from the final node. The format of the forward packet is not usable for the return path, since no node other than the origin has the required information.

Intermediate hops store the shared secret on from the forward path along and reuse it to obfuscate the return packets on each hop. In addition each node locally stores the previous hop it received the forward packet from, in order to determine where to send an eventual return packet. The node returning the message builds a return packet consisting of the following fields:

• hmac (20 bytes): an HMAC authenticating the remainder of the packet, with a key using the above key generation with key type "um".
• failure code (4 bytes)
• message length (2 bytes): the length of the message field in bytes
• message (variable): a string representation. The message is padded to 128 bytes with 0x00 bytes.

The node then generates a new key, using the key type ammag. This key is then used to generate a 154 byte pseudo-random stream, which is then applied to the packet using XOR.

The obfuscation step is repeated by every node on the return path. Upon receiving a packet the node will generate its ammag, generate the pseudo-random byte stream and apply it to the packet before forwarding.

The origin node detects that it is the final hop of the return message since it was the origin of the corresponding forward packet. Having the shared secrets of all intermediate nodes it can unwrap the packet until the HMAC is a valid HMAC for the packet, which also identifies the sender of the return message.

The association between forward and return packet is handled outside of the protocol, e.g., by association to an HTLC in a payment channel.