An indispensable component of Nomos, the Blend Network strengthens the anonymity of block proposers by preventing them from being linked to their proposals. This unlinkability is improved with a variety of strategies - known as message blending - which include layered encryption, timing delays, and artificial traffic. This article will focus on encapsulation - the technique of layered message encryption that lies at the heart of how the Blend Network protects proposers against deanonymisation.

The Role of Encapsulation in the Blend Network

The Blend Network introduces anonymity for proposers via a “hiding in the crowd” strategy, inspired by modern mixnets with some changes to accommodate its unique use case. The most basic way the Blend Network provides anonymity is by having encrypted proposal messages pass through several intermediary nodes before being broadcast to the entire Nomos Network. The following steps illustrate the process which a proposal message goes through before being broadcast and included in the chain.

1. The message sender selects a random path of nodes along which it will relay its message to the receiver, covering the message in layers of encryption for every node on the path.
2. The sender sends the layered message to every node with which it maintains a peer-to-peer connection.
3. When a Blend node receives a message, it checks that the message is unique and has not yet been seen, relaying it to its own peers. This ensures that every message is ultimately disseminated to the entire network.
4. A Blend node that receives a message will also attempt to decrypt the message. If it is able to decrypt the outer layer of a message it receives, it relays this decrypted message (after a randomised delay) to its peers for the next node in the path to receive and decrypt.
5. When the receiver finally receives its message, it decrypts this message and is able to retrieve the original payload. This payload is then broadcast to the Nomos Network as a block proposal.

An illustration of the dissemination technique used by the Blend Network is shown in Figure 1.

The process of repeatedly encrypting the message is known as encapsulation, while the reverse process of decryption by nodes on the path is referred to as decapsulation.

Security Properties

Encapsulation is an important part of what makes the Blend Network so effective at anonymising messages. Not only is the final destination of a message not known as it travels and is transformed between nodes, even the next node on the path is only known to itself and the message sender. This is because messages are disseminated to all Blend nodes at every step, with the next node in the path only learning of its involvement when it is able to successfully decrypt a message it receives. Encapsulation is responsible for the following properties of the Blend Network:

Unlinkability

Even if an adversary controls multiple nodes in the Blend Network, they cannot link incoming and outgoing messages based on their content unless they control all nodes in a particular message's path. The cryptographic transformation at each step, or hop, ensures that messages look completely different before and after processing. Combined with random delays to prevent timing analysis, this makes linking a proposal to its proposer extremely difficult.

Preventing Message Association

When encapsulating a message, the sender uses ephemeral key pairs to ensure their messages cannot be associated with each other. The keys used for each layer of encryption are limited in number and are derived anew by the sender for every message. This property further enhances message unlinkability by ensuring that adversaries cannot deduce the sender of a group of messages based on their known common origin.

Verifiability

Despite the strong anonymity properties, nodes can verify that messages are correctly formed, that the message path was selected randomly, and that senders have not exceeded their quota of messages. The cryptographic signatures and zero knowledge proofs embedded in each message allow verification without compromising anonymity.

The Encapsulation Process

Defining the Relay Path

Before a message sender can begin encapsulating their message, they must first select the nodes through which the message will be relayed to its intended recipient. The sender selects the number of hops along their intended path, \(h\leq h_{max}\), where \(h_{max}\) is the maximum amount of hops on a path - set to 3 at the time of writing. The sender then generates \(h\) ephemeral public-private key pairs - denoted \((K_i, k_i)\) respectively. Each of these key pairs corresponds to one node on the relay path.

To ensure that the sender does not spam the Blend Network with too many messages or too many hops per message, they must generate a Proof of Quota (PoQ) for every public key. A PoQ is a zero knowledge proof of two facts:

1. That the sender is entitled to send a message. For a proposal, this would be a proof that the proposer won the consensus leadership lottery. For artificial cover messages, the sender must prove its eligibility to send such a message.
2. That the public key has been assigned a unique index in the current session - the basic time unit used by the Blend Protocol. Since the index cannot exceed a certain number, this limits the among of public keys a sender can use in a given session. As a result, the PoQ enforces an upper limit on both the number of messages from a sender and the number of hops per message.

The PoQ generation also involves generating a selection randomness derived from some of the proof inputs, as well as an associated nullifier that ensures that the proof cannot be reused.

At this point, the sender can randomly select \(h\) nodes from the set of all Blend nodes, with these nodes forming the path along which the message will travel. The set of Blend nodes is obtained from the Service Declaration Protocol (SDP), which publishes information about every participating node. To ensure that the message path has been chosen randomly, the sender must generate zero knowledge Proofs of Selection (PoS) for every node on the path. This involves proving that the index of the path node in the set of Blend nodes is derived from a pseudorandom function seeded by the selection randomness. The PoS also ensures that its derived nullifier, which prevents the reuse of Proofs of Selection, is not the same as the nullifier of the PoQ.

Finally, the sender uses public information about each node, obtained from the SDP, to derive the final keys necessary for the encapsulation process. Each path node’s unique Ed25519 public key \(P_i\), also known as its Provider ID, is combined with the associated private key \(k_i\) via the Diffie-Hellman Protocol to yield a shared key \(\kappa_i\). These shared keys allow the node at every hop to decrypt one layer of encryption, but prevent other nodes from doing so.

Structure of a Blend Message

When preparing a message, the sender derives a variety of cryptographic components, which are used to predictably transform the original proposal (the payload) into an encrypted message. All Blend messages have the same structure, regardless of their progress along their relay path. This ensures that all messages can be processed by nodes that receive them in a consistent way.

A Blend message consists of three components: a public header, an encrypted private header, and the payload. Each component serves a specific purpose in the blending process. This structure is illustrated in Figure 2 below.

The Public Header

The public header is visible to all nodes and contains the information necessary for the current node in the path to process the message. It includes:

• Public Key \(K_h\): A unique ephemeral public key, used to decrypt the outermost \(h\)th layer of encryption.
• Proof of Quota (PoQ): A zero knowledge proof demonstrating that the message creator has not exceeded their messaging allowance.
• Signature: A cryptographic signature over the encrypted portion of the message, verifiable using the public key. These signatures allow path nodes to verify that the encapsulation was done correctly.

The Private Header

The private header contains a stack of \(h_{max}\) encrypted blending headers, the maximum amount of nodes in the path. Only the node currently processing the message can decrypt its corresponding blending header. Each blending header contains:

• Public Key \(K_i\): The ephemeral public key for the next hop.
• Proof of Quota (PoQ): The proof of quota for the next hop.
• Signature: The signature for the next hop.
• Proof of Selection (PoS): A proof that the next node was randomly selected from the set of eligible Blend nodes.
• Last flag: A boolean indicating whether this is the final node in the path.

The private header is encrypted in such a way that each node can only decrypt one layer, revealing the information needed to construct the next message in the chain. After each decryption, the information in the outermost private header is used to construct the new public header.

The Payload

The payload contains the actual data being transmitted - either a block proposal for data messages or random data for cover messages. The payload is encrypted multiple times, with each layer removed by successive nodes in the path. Importantly, encrypted data and cover message payloads are completely indistinguishable until the final layer of encryption is removed.

Encapsulation

To begin encapsulating a message, the message sender starts by filling the last \(h\) private headers, corresponding to the \(h\) hops on the path, with dummy values. These values are generated by a pseudorandom function seeded by the shared key \(\kappa_i\) corresponding to hop \(i\). Then, these headers are progressively encrypted based on their position on the path:

1. The outermost private header is encrypted once, by the shared key of the first path node \(\kappa_1\).
2. The next private header is encrypted twice, by \(\kappa_1\) and then by \(\kappa_2\).
3. The \(i\)th private header is encrypted \(i\) times, by shared keys \(\kappa_1\) through \(\kappa_i\).

Any remaining private headers (if the number of hops is less than \(h_{max}\)) are filled with random values. This is done to avoid premature decryption of private headers when there are fewer than \(h_{max}\) hops, and ensures that the original message can be reconstructed during decapsulation.

The sender then starts the encapsulation process, beginning with the layer corresponding to the last node on the path and concluding with the outermost layer that corresponds to the first path node. For each stage \(i\) of encapsulation, the sender does the following:

1. Produce a signature for the concatenation of the current private header set and payload using the previous layer’s (that is, the next hop’s) public key \(K_{i-1}\). For the first encapsulation layer, generate a new ephemeral key \((K_0, k_0)\) to use for the signature.
2. Encrypt the payload with the current layer’s shared key \(\kappa_i\).
3. Shift the private headers one position deeper, truncating the last private header. The new outermost private header is filled with the signature generated above, the Proof of Selection for the corresponding path node, and the public key and Proof of Quota corresponding to the previous layer \(i-1\). For all but the first layer, the last flag is set to false. For the first encapsulation layer, use the new key \(K_0\) and a PoQ filled with random data, and set the last flag to true.
4. Encrypt each private header using the current layer’s shared key \(\kappa_i\).
5. For the final encapsulation layer, the public header is filled with the outermost public key \(K_h\), its corresponding PoQ, and a signature over the final payload using \(K_h\).

The Decapsulation Process

Once encapsulated, the message is disseminated through the Blend Network, where every node that receives it will attempt to decapsulate it. Most nodes, not being on the message’s path, will not succeed, and will simply disseminate the message to their neighbours. Path nodes that successfully decapsulate a message will disseminate the new message after a random delay to ensure that the incoming and outgoing messages cannot be linked.

Nodes that receive a Blend message will attempt to decapsulate a message according to the method described below.

1. Calculate the shared key \(\kappa_i\) from the public key \(K_i\) in the public header and the node’s own private key \(p_i\). This shared will be identical to the one used by the sender only if the node is a path node.
2. Decrypt every private header with \(\kappa_i\). Check the proofs from the outermost private header and make sure that its public key has not yet been seen. Otherwise, discard the message.
3. Define the new public header with the public key, Proof of Quota, and signature from the outermost private header.
4. Decrypt the payload with \(\kappa_i\).
5. Reconstruct the next dummy private header with the same pseudorandom function (seeded with \(\kappa_i\)) as used during the encapsulation process.
6. Shift the private headers one position up, truncating the outermost private header and filling the deepest private header with the dummy header reconstructed in the previous step.
7. Generate a signature over the new payload and private headers. If this signature does not match the signature from the public header, discard the message.
8. Check the last flag from the previously outermost private header (now truncated). If it is set to true, then the decapsulating node is the last node on the path and can safely broadcast the decrypted payload to the Nomos Network.

Note that the decapsulation process is more or less just a reversal of the encapsulation process described above. At every step, the decapsulation reverses one step of encapsulation in a verifiable manner, all while maintaining the same message structure. This allows messages to remain indistinguishable while allowing nodes to process them in a consistent way, no matter where the message is on its relay path.

Conclusion

Message encapsulation forms the cryptographic backbone of the Blend Network's anonymity guarantees. Through the layered application of encryption, zero-knowledge proofs, and ephemeral keys, this mechanism ensures that block proposals can traverse multiple network hops without revealing their origin or destination. This feature of the Blend Network, combined with additional strategies like timing delays and cover traffic, allows Nomos to protect its proposers even in the most adversarial network conditions.

Sources and Further Reading

• The Blend Network: Improving Nomos' Privacy Guarantees
• Blend Protocol Specification
• Message Encapsulation Mechanism