BLEND-PROTOCOL

Field	Value
Name	Blend Protocol
Slug	95
Status	raw
Category	Standards Track
Editor	Marcin Pawlowski
Contributors	Alexander Mozeika [email protected], Youngjoon Lee [email protected], Frederico Teixeira [email protected], Mehmet Gonen [email protected], Daniel Sanchez Quiros [email protected], Álvaro Castro-Castilla [email protected], Daniel Kashepava [email protected], Thomas Lavaur [email protected], Antonio Antonino [email protected], Filip Dimitrijevic [email protected]

Timeline

2026-05-29 — 67e498e — chore: fix math issues (#350)
2026-05-28 — 15f410b — chore: fix math issue (#349)
2026-05-28 — d45eed2 — Chore: mirror blochain specs into github/mdbook (#347)

Revision History

Version	Changes	Date
1.0.0	Initial revision.	2026-04-09

Introduction

The privacy of a Proof-of-Stake (PoS) system is defined by the inability of an adversary to learn:

Which node proposed a given block. This property is known as unlinkability.
How much stake a node has. This property is known as stake privacy.

While a node can be de-anonymized based on the content of its block proposals, this angle of attack is mitigated by Private Proof of Stake systems. However, a node can also be de-anonymized based on its network activity. An adversary can observe the node’s network behavior and link the node to the proposal it sends. Because a node’s relative stake correlates with its network activity in all PoS systems, observing a node’s behavior for some time enables the adversary to estimate the node’s stake. It is this network-based de-anonymization that is addressed by the Blend Protocol, allowing Logos Blockchain to achieve a truly Private PoS system.

The Blend Protocol is designed as a way to allow nodes to send block proposals that cannot be linked back to them. The idea is to make it very difficult and costly for someone trying to figure out who sent a proposal and what stake they hold. Because the protocol spreads messages out over many nodes, it becomes even harder to attack, which enhances network privacy. The Blend Protocol increases the time to link the sender to the proposal by at least $300$ times, which makes the stake inference highly impractical (Impact of the Blend Protocol on the Time to Link and Time to Infer the Stake).

The Blend Protocol targets a specific set of requirements that differentiate it from mixnets and other general-purpose anonymous communication systems. It achieves probabilistic unlinkability in a highly decentralized environment with low bandwidth cost but high latency. It hides the sender of a block proposal, making it costly for an adversary to learn its origin with high confidence. The cost of attacking the network is high due to decentralization and the economic value of stake needed to add a single node. The protocol works well even when many nodes are involved and not much data is being sent, but it may take longer for proposals to be delivered.

In this document, we present a succinct description of the Blend protocol, which is one of the Logos Blockchain Services and is responsible for providing censorship resistance and network-level privacy for the block producers of the Logos Blockchain Bedrock ([1.1.0][Overview] Bedrock Architecture), the foundational layer of Logos Blockchain.

Privacy of Proof of Stake Systems

All Proof of Stake (PoS) systems have an inherent privacy problem — the stake of the node determines the node’s behavior. That is, by observing the node’s behavior (or impact of the node on the system), one can infer the node’s stake. More precisely, the stake that is discovered is relative to the stake involved in the PoS — stake that is used for the PoS purposes by the adversary. There are two things that can be observed:

The content of the blocks.
The network activity of the node.

Observing the content of the blocks makes it possible to execute a tagging attack. The consequence of a successful attack is that the stake of a node can be learned by controlling which transactions are included in the proposals built by the node. This is achieved by submitting a transaction only to the mempool of a targeted node — thus creating a difference in the transactions seen by this node compared to the other nodes — and observing the time when this transaction is included in the block.

The tagging attack can be addressed by designing a mempool in such a way that the node has an attestation that the transaction was seen by the majority of the network, which makes the adversary’s ability to manipulate the view of the node severely limited. This is to some extent addressed by the DA Network (DA Network Specification), where nodes receive an attestation that a certain type of transaction was seen by many nodes.

Observing the network activity of the node leads to an easier but still powerful attack that can also disclose the node stake even after the tagging attack is mitigated. That is, a node’s stake can be inferred by observing the frequency of the messages node emits during a particular portion of time — this attack is addressed by the Blend protocol.

The Blend protocol achieves network-level leader-proposal unlinkability with statistical indistinguishability. That is, a leader cannot be linked back to its proposal and cannot be distinguished from its peers based on its network behavior. This property translates into an increased difficulty of learning the node’s stake through the node’s network behavior.

To have a truly privacy-preserving system, we need to apply both techniques simultaneously. Solving one without the other will not suffice.

Terminology

Message Types

Data message is a message generated by a node (consensus leader), whose payload contains a block proposal. Any data message is indistinguishable from any other message until it is fully processed by the network. The privacy of the sender of a data message is what the protocol aims to protect.
Cover message is a message that contains meaningless content, and its goal is to create noise (anonymity pool) in which data messages can hide. The cover message is indistinguishable, from the network perspective, from a data message.

Protocol Actors

Logos Blockchain node is a node that is part of the Logos Blockchain network.
Core node is a Logos Blockchain node that declared its willingness to participate in the Blend Network Service through the Service Declaration Protocol (SDP — [1.0.0] Service Declaration Protocol). The core node is responsible for core protocol functions such as cover message generation, message relaying, message processing, and message broadcasting. Additionally, the core node generates data messages that are blended with the rest of the messages generated by the network.
Edge node is a Logos Blockchain node that is not a core node. Edge nodes connect to core nodes through which they send messages (block proposals).
Block proposer node is a core or edge node that is generating a new data message.
Blend node is a core node that processes a data or cover message.

Node Types

Honest node is a node that follows the protocol fully.
Lazy node is a node that does not follow the protocol due to a lack of incentives and only takes part in the protocol when it is directly beneficial to the node.
Spammy node is a node that does not follow the protocol and emits more messages than the protocol expects. In other words, it is a spamming node.
Unhealthy node is a node that emits fewer messages than the protocol expects. We cannot assume that this node is misbehaving deliberately, as it can be under an attack.
Malicious node is a node that does not follow the protocol regardless of incentives.
Unresponsive node is a node that does not follow the protocol due to technical reasons, such as a lack of connectivity or malfunction.

Adversary Types

Passive adversary is an adversary that cannot modify the behavior of a node, but can only observe.
Active adversary is an adversary that can modify the behavior of a node in addition to observing the network.
Local observer is an passive adversary with a limited view of the network and with the ability to observe the internals of a limited number of nodes.

Networking

Blending is an operation of cryptographically transforming and randomly delaying messages. This shuffles the temporal order of incoming and outgoing messages so that they cannot be linked back to the sender based on the network statistical analysis or message content inspection. The key difference between blending and mixing (as defined in mixnets) is in the source of the anonymity. In mixing, the anonymity comes from processing multiple messages by the same node, while in blending the anonymity comes from processing the same message by multiple nodes.
Broadcasting is the process of sending a data message payload (block proposal) to all Logos Blockchain nodes.
Disseminating is the process of relaying messages by core nodes through the network to edge and core nodes.
Communication failure is an event when a message that is disseminated through the network is not finally broadcast. The communication failure might be due to lazy, malicious, or unresponsive nodes.
Anonymity failure is an event when an adversary can link the sender to the broadcast message.

Time

Epoch is a period that is defined by the consensus. It lasts for $648,000$ slots, each slot lasting 1 second. A new block is proposed for each slot with a probability of $1/30$ , which translates to $21,600$ blocks, as on average, every $30$ slots a single block is proposed.
Session is a time during which the same set of core nodes is executing the protocol. When the session ends, a new one starts, and the set of core nodes is refreshed. In this version of the protocol, the length of the session follows the length of an epoch. However, we define the length of a session as the average number of blocks in an epoch, i.e. 648,000 slots, that is, $21,600$ blocks. This value is based on the fact that a single block is proposed on average every $30$ slots, for the justification see The Number of Time-Slots Between Two Consecutive Blocks.

The number of blocks is $21,600$ , on average, but can be less or more, as can be seen in this histogram obtained from $10^4$ samples of Bernoulli trials with parameters $T=648,000$ and $p=1/30$ .

Diagram

The numbering of sessions and epochs will not be synchronized, which is acceptable, as the protocol is independent of the epoch.

Round is the primitive measure of time in the protocol. It defines a period during which a node can emit a new message. The definition of a round is also important for defining the message releasing logic, which handles the randomized emission delay for processed messages. In this version of the protocol, the length of the round is 1 second.
Interval is a period, defined in rounds, that approximates the time between two consecutive block production events. In this version of the protocol, the length of an interval is 30 rounds.

Overview

The Blend Protocol is a peer-to-peer anonymous broadcasting protocol with cryptographic and timing obfuscation capabilities. The main purpose of the Blend protocol is to increase the difficulty of linking any block proposal to the node that proposed it, maintaining privacy before and after the election, which increases the censorship resistance and privacy of the Logos Blockchain Bedrock. More precisely, the Blend protocol attempts to hide that the consensus leader is sending a leader message (a block proposal) by unlinking the sender from the message through cryptographic and timing patterns obfuscation mechanisms.

The Blend Protocol is one of the Logos Blockchain Bedrock Services. It consists of nodes that declare their intention to serve as core nodes through the Service Declaration Protocol (SDP, [1.0.0] Service Declaration Protocol).

The protocol works as follows:

Core nodes form a network by establishing encrypted connections with other core nodes at random.
A block proposer node selects several core nodes and creates a data message (containing a block proposal) that can be processed only by the set of selected core nodes (according to the order given by the block proposer node).
The block proposer node sends the data message to its neighbors (core nodes). If the block proposer is an edge node, it connects to randomly selected core nodes to send the data message.
Core nodes disseminate (relay) the message to the rest of the network.
Core nodes generate new cover messages every round, which are blended with other messages.
When the data message reaches a blend node (designated core node), then it is processed by the node, that is:
It is cryptographically transformed, so the incoming and outgoing messages cannot be linked together based on the content of the message.
It is randomly delayed, so the outgoing message cannot be linked to the incoming message based on the timing observation of the message.
The blend node disseminates the processed message to the network so that the next selected blend node can process the message.
When the message reaches the last blend node, then:
The blend node processes the message.
1. Decrypts the message.
2. Delays the message.
It extracts the message payload (the block proposal).
It broadcasts the block proposal to the Logos Blockchain network.

Below we present a simplified diagram of the protocol, which depicts how the protocol is evolving in time.

Diagram

_{The sender is an edge node or a core node. The sender sends a data message to its neighbor (a core node). In addition to data message, core nodes send cover messages. The neighbor/relayer relays messages to other core nodes. The blend node relays all received messages immediately, but it also relays messages that it processed once every release window. There is no delay when disseminating/relaying a message due to the processing of messages.}

The current version of the protocol is optimized for the privacy of core nodes. The level of privacy that edge nodes gain is not as high as core nodes. The problem with maintaining a high level of privacy for edge nodes is that it would require increasing the delay of the network significantly (which is bad for the resilience of the consensus) or increasing the number of messages that an edge node emits (which is bad for the core nodes’ bandwidth). This is acceptable as we assume that edge nodes are mobile and do not have any static long-term network identifier. Therefore, they cannot be tracked easily. Moreover, edge nodes should have lower stake than the core nodes so they will connect to the network sporadically. Which makes identifying them even harder.

Network

In this section, we briefly discuss the way the network is created and maintained.

Bootstrapping

The process of creating a network is called bootstrapping.

At the beginning of a session, all core nodes retrieve a fresh set of core nodes’ connectivity information from the SDP protocol. Then each core node selects at random a set of other core nodes and connects to them through fully encrypted connections. After some time, when all core nodes connect to other core nodes, a new network is formed.

Minimal Network Size

The minimal network size is $32$ . This is the minimum number of nodes (unique ProviderIds from declarations) that must be retrieved from the SDP to consider the Blend protocol safe to use.

This minimal size of $32$ nodes allows the network to release, on average, a single message per round under the assumption of $50\%$ unresponsive nodes. With fewer nodes, the network would need to either release more messages per round or queue them. This would increase the time messages take to traverse the network, potentially compromising the safety of the consensus.

The calculations supporting this requirement are provided in the Releasing section, where the number of $16$ nodes has been estimated without assuming any unresponsive nodes. Therefore, we have doubled that value to accommodate the potential $50\%$ unresponsive nodes.

Fallback

If the minimal network size is not reached, nodes must not use the Blend protocol. In such cases, nodes must broadcast data messages directly, bypassing the Blend network.

Maintenance

To maintain an adequate quality of the network, all connections must be monitored by the nodes.

Nodes monitor connections with their neighbors by verifying the correctness of messages and the number of messages they receive.

If the messages are badly constructed or the number of messages is above a certain acceptable level, then:
The connection with that neighbor must be closed.
Then a new connection with a randomly selected core node must be established.
If the number of messages is below a certain acceptable level, then a new connection with a random core node must be established.

The above logic enables a node to maintain the quality of the network by closing connections with abusive, malicious, lazy, and unresponsive nodes. All honest nodes, by following this mechanism in the long run, will isolate themselves from other nodes, which will increase the overall performance of the network.

Messages

The protocol defines two types of messages: data, and cover.

Data messages contain a meaningful payload, which is used by the Logos Blockchain network to advance the Bedrock consensus. The mechanism that triggers data message generation is external to the Blend Protocol and is defined by the leader election process of the Bedrock consensus.
Cover messages do not contain any meaningful payload and are generated by nodes to increase network noise and to blend with data messages. Cover messages mimic the behavior of data messages, meaning that they are disseminated and processed by core nodes in the same manner as data messages. Data and cover messages are indistinguishable, which means that a local observer cannot tell the difference between the data and cover message by looking at it.

Cover messages make learning the communication patterns of core nodes harder, even from the perspective of a local observer.

Generation

A message is generated according to the following logic:

The node generates a message payload $p$ :
The payload is a block proposal, then a data message is generated.
The payload is a random number, then a cover message is generated.

Both types of messages are created at random by independent processes.

The payload $p$ is cryptographically processed as follows:
$k$ core nodes are selected at random from the set retrieved by SDP,
The message $m^k = E_k(...(E_2(E_1(p)))...)$ is generated, which encapsulates the payload $p$ in $k$ layers of encryption. Each $i$ ’th layer can be decrypted by the $i$ ’th node from the selected set.
The message $m^k$ is relayed.

Relaying

A message is relayed according to the following logic.

If the message is the outcome of the generation logic, then the message is sent to all neighbors (core nodes) of the node.
If the message is the outcome of the processing logic, then:
1. If the message is not unique, then the message is dropped;
2. The message is randomly delayed;
3. Then the message is sent to all neighbors (core nodes) of the node.
If the message is received from the neighbor:
1. If the message is not unique, then the message is dropped;
2. Else, the message is sent out to the rest of the node's neighbors (core nodes) and concurrently is processed by the node.

Processing

A message $m^k$ is received by a node.
If the node is the $k$ ’th node, then:
The $m^{k-1}$ message is decapsulated from the $m^k$ message;
The $m^{k-1}$ message is relayed.
Else, the message is discarded as the node cannot process the message. Note that the message was previously relayed according to the Relaying logic.
After $k-1$ decryptions, the last node can determine the type of the message by examining the payload $p$ :
If the payload contains a block proposal, then it is broadcast to the entire Logos Blockchain network;
Otherwise, the message is discarded.

Broadcasting

Broadcasting is a process of delivering a block proposal extracted from a data message to the entire Logos Blockchain network by the core node that received it. Only block proposals that are constructed correctly can be broadcast. Any badly constructed block proposal must be rejected. The logic behind the verification of the block proposal is out of the scope of the Blend protocol. It is defined by the Logos Blockchain Bedrock ([1.1.0][Overview] Bedrock Architecture).

Rewarding

A node must be encouraged to follow the protocol, which means that it must be rewarded for the contribution it is making. Otherwise, honest nodes might become lazy nodes, nodes that are not motivated to follow the protocol due to a lack of incentives. In simple terms, a lazy node will not work until it gets paid. Therefore, we motivate the following set of protocol actions:

Message generation: a node must be motivated to generate messages according to the protocol, where generation means that a new message is created that is not the outcome of the processing. This is especially important for cover messages. Data messages already incentivize the node that is generating them, since they include a block proposal, and it rewards the sender of the message directly through the consensus-defined rewarding mechanism ([1.0.0] Anonymous Leaders Reward Protocol).
Message relaying: a node must be motivated to relay every received message, where relaying means that a node forwards all messages it received to its neighbors to deliver messages to their next destinations (blend nodes).
Message processing: a node must be motivated to process every received message, where processing means that a node has decapsulated and delayed the message.
Message broadcasting: a node must be motivated to broadcast any data message it processed, where broadcasting means that a node sends the processed message to the Logos Blockchain network broadcasting channel.

Motivations

We address the above motivations in the following manner:

Cover message generation is motivated by the node’s individual need for privacy.

The node must generate and emit cover messages to keep itself private. Otherwise, it will lose the protection given by the protocol.
The node must also limit the number of cover messages to generate to be indistinguishable from all other nodes. That is, for every data message a node generates it must generate one less cover message; otherwise the node could be distinguished from other nodes based on the number of emitted messages.

Message relaying is motivated by monitoring the connection quality with the node by its neighbors.

The node must relay messages according to a network-defined limit. Otherwise, the neighbors will close the connection with the node. This will lead to a network-level isolation of that node, and if the node is isolated, it will not receive any messages to process, so it will earn no rewards.
The node must relay processed messages. If it does not, the node that generated the message will learn this fact and might stop addressing messages to the relaying node. This is possible because a node can select the recipients of the messages freely but from a random subset of all nodes.

Message processing is motivated by calculating a reward as a node’s activity function.

The node collects message-unique information (blending tokens); the number of tokens collected increases the chances for a reward. The node receives a base reward after showing that it performed a minimal amount of work, which is verified by the step 3 of the Rewarding Mechanics.
The node that collects more tokens increases its chances of winning a premium reward through a lottery mechanism. The node receives a premium reward after showing that it performed extra work, which is verified by the step 4 of the Rewarding Mechanics.
The distinction between the base and premium reward is necessary to reward nodes for the work they perform and to continue to motivate them. The base reward provides a level of fairness, meaning every node should receive it if they were active enough. However, a lazy node might stop providing service after collecting just enough tokens to get the reward, which might be less than what an honest node collects. Therefore, the premium reward continues to motivate the lazy node to work more and collect more tokens. The premium reward is paid on a randomized competition basis, which cannot be biased by the node.

Message broadcasting is motivated by increasing the base reward.

The node is motivated to broadcast the block proposal message as each block proposal that extends the chain directly increases the Blend Network Service income pool. That is, the block rewards and/or fees for each block are summed up and form the service income pool, which is then shared with active core nodes.

There is a subtle distinction between the broadcasting and relaying motivation logic:

The broadcasting action is motivated by the fact that each broadcast block is contributing to the service income pool $\mathbf I$ .
The relaying action is motivated by a fear of losing a reward, which impacts the chances for winning a reward (node’s activity $\mathcal A$ ).
The reward is calculated as a multiplication of both $\mathcal R=\mathcal A⋅\mathbf I$ .

Therefore, the nuance between such a distinction is with the “direction” of the motivation. For broadcasting, it is positive (earning), and for relaying, it is negative (losing).

Messaging abuse is limited by a quota construction.

The quota limits message generation, which helps maintain network health and enables fair reward calculation.
This is achieved by limiting the number of unique encryption keys that can be used for message generation. That is, processing a single message consumes a number of keys, which effectively limits the number of messages that can be processed by the network.

Mechanics

Every node during the session of the protocol collects some bits of information, which are called blending tokens, from processed messages.
After the session, every node selects a single blending token that has a certain property: it is most similar to the next Session Randomness. This token is registered on the ledger.
Every node that submitted a token receives a base reward if the token’s similarity to the next session randomness is above a certain (predefined) threshold (called the activity threshold).
Every node that submitted a token receives a premium reward if the token is in the set of the most similar tokens (as defined below) to the next session randomness.

Protocol

Network Maintenance

In this section, we present the part of the protocol responsible for maintaining the network connectivity.

Diagram

_{A simple diagram representing the Blend Network, where core nodes (denoted as C) form a Core Network (bold connections) and edge nodes (denoted as E) form an Edge Network (thin connections).}

Since the network is built based on two types of nodes, we define two network types. The Core Network is built with core nodes, while the Edge Network is built with edge nodes that connect to the core nodes. This distinction is necessary as the process of bootstrapping and maintaining each network is different.

Core Network

Bootstrapping

The bootstrapping defines the process of creating the network, which happens at the beginning of each session.

A core node at the beginning of a session retrieves a set of core nodes’ information from the SDP protocol ([1.0.0] Service Declaration Protocol).
If the number of core nodes is below the minimum number of nodes (Minimal Network Size), then stop and use regular broadcasting.
It starts opening new connections.
It selects at random (without replacement) a node from the set of core nodes.
It establishes a secure connection with the selected node, that is:
1. It opens a TLS connection using ephemeral keys to the node according to the Connection Details.
2. It identifies its neighbor using the Neighbor Distinction Process (NDP).
  1. The node learns that the neighbor is a core or an edge node.
  2. The neighbor learns that the node is a core node.
  3. The node stops connecting to selected peer after reaching the maximum number of tries ( $\Omega_C$ parameter: Core Node Parameters). Then a new random peer is selected.
It repeats the above steps until it connects to the minimal core peering degree of nodes. That is, 4 according to the $\Phi_{CC}^{Min}$ parameter: Core Node Parameters. Both incoming and outgoing connections count toward this minimal degree.
It starts accepting incoming connections and maintaining all connections as defined in Maintenance.
It can maintain up to the maximum number of connections with core nodes ( $\Phi_{CC}^{Max}$ parameter: Core Node Parameters). For example, a node initiates $\Phi_{CC}^{Min}=4$ connections and $\Phi_{CC}^{Max}=8$ , then it can still accept $\Phi_{CC}^{Max} - \Phi_{CC}^{Min} = 4$ connections from core nodes.
It can receive up to the maximum number of connections with edge nodes. That is, 300 according to the $\Phi_{CE}^{Max}$ parameter: Core Node Parameters.
If two nodes open two connections with each other, so that both have incoming and outgoing connections to the same neighbor (core node), then:
The node with the lower public key value (provider_id from SDP) must close the outgoing connection to the node with the higher public key value.
The node with the higher public key value (provider_id from SDP) must close the incoming connection from the node with the lower public key value.

Public key values are compared lexicographically. Specifically, we use the libp2p peer_id format of the provider_id and apply standard Base58 encoding (to_base58() libp2p function) for the comparison.

Maintenance

This process defines the way the network connections are maintained during the sessions.

A core node monitors the connection quality of each connection with its neighbors, according to the Connectivity Maintenance:

It monitors the transmission rate of each neighbor’s connection.
1. If the transmission rate drops below a certain threshold, then the neighbor is marked unhealthy.
2. If the transmission rate goes above a threshold, then the neighbor is marked spammy.
A connection with a spammy neighbor is dropped, and a new one (with another randomly selected core node) must be established to maintain the minimum peering degree.
A connection with an unhealthy core node neighbor is maintained, but an additional connection is established.
1. The number of open connections must be below the maximum core connections.
2. If the maximum core connections is exceeded, then:
3. A message is added to the logs informing about this situation;
4. Possibility to establish new connections is paused until the maximum number of established connections goes down.
A connection with an unhealthy edge node is closed.

Edge Network

Bootstrapping

The edge network is maintained by core nodes because edge nodes can only establish connections with core nodes.

Each core node defines individually the maximum number of edge connections allowed. Therefore, every core node is a potential entry point to the network, but not every node is connectable.

The bootstrapping logic of an edge node:

At the beginning of a session, the edge node retrieves a set of core nodes’ information from the SDP protocol.
If the number of core nodes is below the minimum number of nodes (Minimal Network Size), then stop and use regular broadcasting.
Whenever an edge node needs to send a message, it selects at random (without replacement) a node from that set.
It establishes a secure connection with the selected node.
It opens a TLS connection using ephemeral keys to the node according to the Connection Details.
It identifies itself and authenticates using the Neighbor Distinction Process.
1. A core node learns that the neighbor is an edge node.
2. An edge node confirms that the neighbor is a core node.
3. A core node might drop the connection if the maximum number of edge connections, defined by the core node, is reached.
4. An edge node must drop the connection if the neighbor is not the intended core node. Please note that technically it is done during TLS handshake, where the handshake will fail if the core node is using a different key than provided in the SDP declaration.
When the connection is established, it sends the message and closes the connection.
Concurrently to the above, it repeats steps 4 and 5 until it is sends the message to a number of nodes equal to the communication redundancy number defined by the edge node. It stops connecting to each node after a certain number of tries, which is defined by the edge node.

Message Lifecycle

Generation

Generation of a message is triggered by any of the following events:

A core or edge node won a consensus lottery and has a proof of leadership, which entitles the node to emit a data message. The payload of the message is a block proposal.
A cover message is released at random by the core node, as described in Cover Message Schedule section. The payload of the message contains random data.

When this happens, a number of messages (limited by the Quota) are generated as follows:

A number of keys are generated according to the [1.0.0] Key Types and Generation.
Each key uses a message-type-specific allowance as described in the Quota.
The correct usage of the allowance is proven by Proof of Quota.
The payload of the message is formatted according to the [1.0.0] Payload Formatting.
The above set of keys is used to encapsulate the payload of a message according to the [1.0.0] Message Encapsulation Mechanism.
Each key is used for a single encapsulation of a message, which can be processed (decapsulated) by a single node.
The node selection is random and deterministic, and is provable by Proof of Selection. This restricts the possibility of targeting a specific node by an adversary. The adversary is limited only to a subset of keys that can be used to generate a message to a particular node.
The message is formatted according to the [1.0.0] Message Formatting.
The message is released by the node to the Blend network according to the Releasing logic.
Core nodes send the message to their neighbors.
Edge nodes send the message to randomly selected core nodes.

For a complete description of the generation logic, refer to Generation.

Relaying

When a node receives a message from one of its neighbors, it does the following:

Checks the public header of the message, that is:
The version of the message must equal to 0x01; if not, then discard the message.
The proof of quota nullifier must be unique; if not, then discard the message.
The signature must be valid; if not, then discard the message.
The message is released to the network as defined in the Releasing section.
Concurrently to the above, the message is handled by the processing logic as defined in the Processing section.

For a complete description of the relaying logic, refer to Relaying.

Processing

Every message that passes Relaying verification is processed as follows:

The message is decapsulated as defined in the decapsulation section of the [1.0.0] Message Encapsulation Mechanism. This means the node successfully decrypted the blending header and can now read and process it.
If decapsulation succeeds, the decrypted blending header is processed:
If the proof of selection is invalid, discard the message.
Information is extracted from the message and saved as proof of processing a blending token and is used to claim rewards.
If the last flag of the decrypted blending header is turned on, the message is completely decapsulated. The payload can then be processed according to the [1.0.0] Payload Formatting:
1. If the type is a data message, add the payload to the broadcasting queue.
2. If the type is a cover message, discard the payload.
Otherwise, examine the decapsulated header:
1. Verify the proof of quota is valid; if not, discard the message.
2. Verify the signature is valid; if not, discard the message.
3. Verify the public key is unique; if not, discard the message.
4. Format the message according to the [1.0.0] Message Formatting.
5. Attempt a subsequent decapsulation to validate whether the node is the recipient (return to step 1). This must be done recursively to remove all consecutive encapsulation layers where the node is the intended recipient.
6. If the decapsulation fails (meaning no more layers remain), randomly delay the message and release it to all neighbors.
If decapsulation fails, return the appropriate decapsulation failure message.

For a complete description of the processing logic, refer to Processing.

Broadcasting

Every payload that is added to the broadcasting queue is processed as follows:

The correctness of the payload content is verified; that is, the payload must contain a valid block proposal structure — the block proposal is not validated; otherwise, it is discarded.
The block proposal is extracted from the payload and is broadcasted to the Logos Blockchain broadcasting channel after a random delay.

For a complete description of the processing logic, refer to Broadcasting.

Rewarding

Every active core node receives a reward. The activity of a node is verified in a probabilistic manner, where a more active node has higher chances of getting a reward and a premium reward. To claim a reward, the node must do the following:

Generate a proof of its activity for a specific session as defined in Activity Proof. The proof confirms that the node was processing messages during the session. The node activity confirmation is probabilistic, and the odds increase with the number of collected blending tokens.
Use SDP active functionality (Active) to request a reward as described in Rewarding Distribution Logic, that is:
Create a Active Message.
Send it as a part of the reward message (Active Message).
The reward is calculated as defined in Reward Calculation, that is:
The number of correct activity messages is calculated.
The number of correct and winning messages is calculated. Where winning message is defined by a lottery mechanism.
Every node that sends a correct activity message receives a base reward.
Every node that sends a correct and winning message receives a premium reward.
The rewards are distributed by the mechanisms provided by the [1.2.1] Service Reward Distribution Protocol.

Details

Notation

$\Phi_{CC}$ denotes the actual number of established connections of the core node with other core nodes;
$\Phi_{CE}$ denotes the actual number of connections of the core node with edge nodes;
$\Phi_{EC}$ denotes the actual number of connections of the edge node with core nodes;
$h(x)$ denotes a function that returns the number of healthy connections of a given type, where type is: $x \in \{ \Phi_{CC}, \Phi_{CE}, \Phi_{EC} \}$ ;
$\Delta_{max}$ denotes a maximal delay time between two release rounds;
$\beta_{max}$ denotes a maximum number of processing rounds for a single message;
$\mu$ denotes the upper bound on the number of messages to be released during a single release round;
$S$ denotes a number of rounds in a session;
$I_{end}$ denotes the last interval in a session;
$I_{max}$ denotes the last interval of a safety buffer;
$W$ denote the observation window expressed in the number of rounds;
$F_1^W$ denote a frequency at which messages are observed during an observation window $W$ ;
$\lceil F_1 \rceil^W$ denote the maximal frequency at which messages can be generated during an observation window $W$ ;
$\lfloor F_1 \rfloor^W$ denote the minimal frequency at which messages must be generated during an observation window $W$ ;
$F_C$ denote a frequency at which cover messages are generated per round;
$F_D$ denote a frequency at which data messages are generated per round;
$C = S \cdot F_C$ denote the expected number of cover messages that are generated during a session by the core nodes;
$H_C$ denote the expected number of blending operations for each cover message;
$H_D$ denote the expected number of blending operations for each data message;
$R_C$ denote a redundancy parameter for cover messages, defining the number of “replications” of the same message;
$R_D$ denote a redundancy parameter for data messages, defining the number of “replications” of the same message;
$\mathcal{N} = \text{SDP}(s)$ denote a set of core nodes providing the Blend service for the session $s$ returned by the SDP protocol ([1.0.0] Service Declaration Protocol);
$N = |\mathcal N|$ denote a number of core nodes providing the Blend service;
$\text {CSPRNG}()$ is a cryptographically secure pseudo-random number generator, implemented as a BLAKE2b-Based PRNG Construction;

Global Parameters

$\Delta_{max}=3$ , as defined in the Delaying section below.
$S=648000$ , the average number of rounds per session.
$|I|=30$ , the length of an interval is $30$ rounds.
$I_{end} = 21600$ , the last interval of a session.
$I_{max}=I_{end}+100$ , the last interval of the safety buffer is $21700$ , as discussed in the Cover Message Schedule.
$\beta_{max} = 3$ , the maximum number of blending operations of a single message.
$\beta_C=3$ , the expected number of blending operations for each cover message;
$\beta_D=3$ , the expected number of blending operations for each data message;
$W=10 \cdot \Delta_{max}=30$ , the observation window is $30$ rounds.
$\lceil F_1 \rceil^W = W \cdot \mu=30 \cdot \mu$ , the maximum number of messages per-connection during the observation window is a function of the $\mu$ , which is defined in the Releasing section.
$\lfloor F_1 \rfloor^W = 3 \cdot \mu$ , the minimum number of messages per-connection during observation is a function of the $\mu$ , which is defined in the Releasing section.

Core Node Parameters

A core node maintains the following set of parameters:

$\Phi_{CC}^{Max}$ denotes the maximal peering degree a core node can maintain with other core nodes. It is set by a core node individually. It is set to $8$ by default.
$\Phi_{CC}^{Min}$ denotes the minimal peering degree a core node must maintain with other core nodes. It is set by a core node individually. It is set to $4$ by default.
$\Phi_{CE}^{Max}$ denotes the maximum number of connections with edge nodes. It is set by the core node individually. It is set to $300$ by default.
$\Omega_C$ denotes the maximum number of retries a core node will do to connect with another core node. It is set to $3$ by default.

Edge Node Parameters

An edge node maintains the following parameters:

$\Phi_{EC}$ denotes the connection redundancy number for the edge node. A node must send a single message that needs to be blended to this number of core nodes. It is set to $4$ by default.
$\Omega_E$ denotes the maximum number of retries an edge node will do to establish a connection with a core node. It is set to $3$ by default.

Network Maintenance

Connection Details

The connections are established using libp2p with TLS version 1.3 (not older). The cryptographic scheme is Ed25519 with ephemeral keys**.** The libp2p protocol name is /logos-blockchain/blend/1.0.0 for mainnet and /logos-blockchain-testnet/blend/1.0.0 for testnet.

Neighbor Distinction Process

The Neighbor Distinction Process (NDP) enables the core node to distinguish between node types (core, edge) of its neighbors in the Blend Network. The process is straightforward:

A node extracts peer_id from the TLS metadata of the accepted connection.
If the peer_id is found in the set of provider_ids, then the neighbor is a core node; otherwise, the peer is an edge node.

Connectivity Maintenance

The core node is responsible for maintaining the level of connectivity and monitoring the state of connection with its neighbors. The neighbors must comply with the maximum and minimum frequencies of emitting messages. Otherwise, the connection with that node may be dropped.

The monitoring logic is defined as follows:

The messages are counted after successful connection-level decryption of the message for each neighbor.
The node counts the number of messages during a window of observation $W$ . The frequency of observed messages $F_1^W$ is calculated as the number of messages recorded during the observation time divided by the length of the observation window (denoted in rounds).
If the measured message frequency is higher than maximal ( $F_1^W \gt \lceil F_1 \rceil^W$ ), then the node marks the neighbor as spammy, and the connection with that node must be closed.
The node can mark the neighbor as spammy with high confidence, as the neighbor is the true source of messages due to the usage of the TLS protocol, which eliminates the possibility of executing replay attacks by the adversary.
To maintain the minimal number of connections, a new one must be established when a connection with an abusive node is closed.
The neighbor is added to a black list, and its selection must be avoided.
If the measured frequency is lower than the minimum ( $F_1^W \lt \lfloor F_1 \rfloor^W$ ), then the connection is marked unhealthy.
If the number of healthy connections is below the minimum number of connections ( $h(\Phi_{CC}) \lt \Phi_{CC}^{Min}$ for core-to-core connections), then another connection must be opened with a new randomly selected core node. We cannot assume that the neighbor is spammy, as it might be under a denial-of-service attack or other censoring attack.
An unhealthy connection is monitored continuously. If the message frequency goes above the minimal value during the next observation window, then the connection must be treated as healthy, and the node must remove the unhealthy marking for that connection.
If the number of open connections is above the maximum ( $\Phi_{CC} \ge \Phi_{CC}^{Max}$ ) then:
Add an entry to the log that the maximum number of connections has been reached*.*
Pause the ability to establish new connections until the number of open connections drops below the maximum.
If the neighbor is an edge node, then the edge node must send a message immediately after establishing the connection with the core node and then close the connection. Otherwise, the connection must be closed by the core node.
If the node receives a message that has been discarded during the relaying process due to invalidity of the signature (Relaying), then:
If the sender is a core node, then it must be marked as malicious, and the connection with that node must be closed.
If the sender is an edge node, then do nothing as the connection must already be closed with that node.
If a node receives a second message from its neighbor (core node) that is using an already seen message identifier, then the connection with that neighbor must be closed.

The message identifier is the message proof of quota nullifier embedded in the public header of the message. It is used for signing the message and must be unique; otherwise, the message must be discarded.

We do not force any action when the measured transmission rate is below the thresholds defined above, which means that the sender is not emitting enough messages. The primary reason is security; a node might be under an attack, and an adversary is trying to exploit the node and force the node to connect to a different peer (who might be malicious). The severity of that attack is high, as it is not attributable to the adversary. That is, the adversary can execute this attack without disclosing its identity even if it is not controlling the other end of the connection. Therefore, it is better not to close the connection immediately but to establish another one with a randomly selected node from the list.

However, this must also be carefully engineered as the number of connections must not rise above the maximal connection values. The reaction of the node operator to the situation when the number of connections reached maximum is a complex matter, which needs to be handled according to the privacy requirements of the operator. For example, it might be a sign that the node is under attack. Therefore, we have decided to define a privacy-first strategy that is to inform the operator about the potential problem (through logs) and pause the ability to establish new connections until the number of open connections goes below the maximum.

Transition Period

When a new session or epoch begins, the set of public information checked against proofs embedded in messages changes, which renders some messages invalid. However, these messages may still contain valid payloads that must reach their destination. Therefore, we implement a Transition Period (TP, $T$ ) during which the network can gracefully react to the change and allow these messages to safely exit the network.

The duration of the TP is calculated as follows:

T = (\Delta_{max} +d)\cdot \beta_{max} +d

where:

$\Delta_{max} = 3$ defines the maximal blending delay;
$d$ defines the network dissemination delay;
$\beta_{max}=3$ defines maximum number of blending operations of a single message.

We assume that $d=0.5$ is an average message dissemination delay, then:

T = (3 + 0.5)\cdot 3 + 0.5= 11

That means that after $11$ rounds, all messages for the past session or epoch should have been processed and disseminated.

However, to provide an additional safety buffer, we round up the transition period to a single interval: $T=30$ rounds. After this period, all old connections can be safely terminated, and messages for the past session or epoch must not be processed anymore.

When a new session begins:

The node validates message proofs against both new and past session-related public input for the duration of TP. This allows messages generated using core quota to safely transit through the network, as their validity is bound to the session in which they were generated.
The node must open new connections to process new messages for the new session.
The node needs to maintain old connections and process all messages received from these connections for the duration of TP.

When a new epoch begins:

The node must validate message proofs against both new and past epoch-related public info for the duration of TP. This allows messages generated using leadership quota to safely transit through the network, as their validity is bound to the epoch in which they were generated.

Quota

The quota limits the number of messages that can be generated during a session. This bound is necessary for the health of the network as it decreases the bandwidth usage and enables us to calculate rewards fairly.

Core Quota

The core quota ( $Q_C$ ) defines the messaging allowance that can be used by a core node during a single session. The purpose of $Q_C$ is to limit the number of cover messages and the number of blending operations that can be used for a single message. We assume that the core quota is used for generating cover messages, but the core node is not limited by this assumption. We define it as follows:

Q_C = \left\lceil \dfrac{C \cdot (\beta_C+R_C \cdot \beta_C)}{N} \right\rceil

Where:

$C = S \cdot F_C$ denotes an expected number of cover messages that are generated during a session by the core nodes;
$\beta_C$ denotes the expected number of blending operations for each cover message;
$R_C$ denotes a redundancy parameter for cover messages, increasing the number of core node messages a node can send;
$N$ denote a number of core nodes providing the Blend service for the session $s$ returned by the SDP protocol ([1.0.0] Service Declaration Protocol).

Additionally, we introduce the total core quota, which defines the total number of generated cover messages that the whole network can emit (independently of the number of nodes):

Q^{Total}_C = N \cdot Q_C = C \cdot (\beta_C+R_C \cdot \beta_C)

Leadership Quota

The leadership quota ( $Q_L$ ) defines the number of blending operations a block proposer (consensus leader) node can perform within the network. A single quota is used per single proof of leadership. Therefore, a single node can use multiple leadership quotas during a single session. We assume that the leader is interested in using most of its quota to generate data messages; however, the leader is not limited by this assumption. We define the leadership quota as follows:

Q_L = \beta_D + \beta_D \cdot R_D

where:

$\beta_D$ denotes the expected number of blending operations for each data message;
$R_D$ denotes a redundancy parameter for data messages, defining the number of “replications” of the same message.

We can calculate an average data message number ( $D_{Avg}$ ) which informs us about the average number of data messages generated per session:

D_{Avg} = L_{Avg} \cdot Q_L

where $L_{Avg}$ is the average number of leaders per session.

The $L_{Avg}$ depends on the consensus leader election algorithm, which at the time of writing can be estimated as follows:

L_{Avg} = S \cdot F_D = \dfrac{648000}{30} = 21600,

where $S=648000$ and $F_D=1/30$ are taken from the [1.0.2] Cryptarchia Protocol. This is equivalent to the average rate of a slot having an elected leader.

Finally, let us define the leadership quota for node $n$ ( $Q^{n}_L$ ), which can only be calculated by the node $n$ :

Q^{n}_L = x \cdot (\beta_D + \beta_D \cdot R_D)

where $x$ is the exact number of leader elections won by the node $n$ in a session. The value of $x$ is known only to the node because its value is a function of the stake of a node $n$ , which is kept private.

Quota Application

We define a mechanism that applies the quota to the protocol and makes the messaging restriction effective. We start by modifying the mechanism that governs message generation, processing, and relaying. That is:

We require every message introduced to the network to be identified by a unique (ephemeral) key.
We restrict the number of messages a node can generate to the value of the quota.

For this to happen, a node creates a pool of keys that can be used for message generation and processing (the pool is session-specific):

\mathbf K^{n,s}_q = \lbrace(K^{n}_{0}, k^{n}_{0}, \pi_{Q}^{K_{0}^{n}}),...,(K^{n}_{q-1}, k^{n}_{q-1}, \pi_{Q}^{K_{q-1}^{n}}) \rbrace,

which describes a collection of $q$ key pairs for a node $n$ with proofs of quota for the session $s$ , where $K_{i}^{n}$ is the $i$ -th public key, $k_{i}^{n}$ is its corresponding private key, and $\pi_{Q}^{K_{i}^{n}}$ is its proof of quota. Additionally:

$q=Q_C + Q_L^n$ is the sum of core quota and leadership quota for the node $n$ .
$\pi_{Q}^{K_{i}^{n}}$ is a proof of quota which confirms that $i \lt h$ for every key $K^{n}_{i}$ from the key pool $\mathbf K^{n,s}_h$ of a node, without disclosing the identity of the node $n$ .

Keys Generation

This protocol uses multiple types of keys that are described in the following specification: [1.0.0] Key Types and Generation

Proof of Quota

One of the key ideas behind the Proof of Quota (PoQ — [1.0.1] Proof of Quota) is to guarantee that honestly generated messages are relayed and will be disseminated to the entire network. This is because an honestly generated message uses a unique identifier; otherwise, the network will eventually flag the message as duplicated and halt its dissemination.

If two messages use the same identifier, then the network does not guarantee that the message will be relayed. In such a case, any node that observes the second message with the same identifier will drop it.

This might lead to a situation where part of the network will see the first message and another part of the network will see the second. In this scenario, both messages are not disseminated to the whole network, as expected, due to spam limits in the network. However, this does not mean that either message has not reached its destination and was not processed.

The PoQ is constructed from two parts.

The first part of the PoQ is dedicated to the core quota. We define the proof of core quota ( $\pi^{K_{a}^{n}}_{Q_C}$ ) as true when all of the following conditions are met:

$n \in \mathcal{N} = \text{SDP}(s)$ : there exists a node $n$ that is part of the set of registered nodes $\mathcal{N}$ , which is retrieved from the SDP protocol for the session $s$ . The value identifying the node $n$ must be hidden.
$K_{a}^{n} \in \mathbf K^{n,s}_h$ : the public key $K_{a}^{n}$ is generated by the node $n$ for the session $s$ .
$a \lt Q_C$ : the number (index) $a$ of proof nullifiers that limits the number of proof of quotas a core node can generate in one session.

The proof of the core quota assumes:

Public input: $s$ , $K_{a}^{n}$ , $Q_C$ .
Private input: $n$ , $a$ .
Public output: $\nu_s$ .

Where $\nu_s$ is a PoQ nullifier and uniquely identifies the PoQ.

The second part of the PoQ is dedicated to the leadership quota. The proof of the leadership quota ( $\pi^{K_{b}^{n}}_{Q_L}$ ) is true when all of the following conditions are met:

$\exists~\pi^{n,e}_{L}$ : there exists a valid proof of leadership for node $n$ valid for epoch $e$ .
$K_{b}^{n} \in \mathbf K^{n,s}_h$ : the key $K_{b}^{n}$ is generated by the node $n$ for the session $s$ .
$b \lt Q_L^n$ : the number $b$ of key nullifiers that limits the number of proof of quotas a leader can generate per won slot.

The proof of the leadership quota assumes:

Public input: $e$ , $s$ , $K_{b}^{n}$ , $Q_L^n$ .
Private input: $\pi^{n,e}_{L}$ , $n$ , $b$ .
Public output: $\nu_s$ .

Where $\nu_s$ is a PoQ nullifier and uniquely identifies the PoQ.

Finally, we use both constrains and create a single proof of quota ( $\pi^{K_{i}^{n}}_{Q}$ ). That is, the proof is true when any of the following conditions are met:

$\pi^{K_{i}^{n}}_{Q_C}$ constraints are true.
$\pi^{K_{i}^{n}}_{Q_L^{n}}$ constraints are true.

This means that the proof of quota is a logical sum of the proof of core quota and the proof of leadership quota, $\pi_{Q}^{K_{i}^{n}} = \pi_{Q_C}^{K_{i}^{n}} \lor \pi_{Q_L^{n}}^{K_{i}^{n}}$ .

Please refer to the document below for more details.

The set of PoQ for leaders must be precomputed for each epoch to minimize the impact of proof generation on the proposal broadcast delay.

For more details see [1.0.1] Proof of Quota.

Message Lifecycle

Proof of Selection

The proof of selection (PoSel, $\pi^{K^{n}_{i},m_{i}}_{S}$ ) is a construction that makes the selection of nodes for message processing a random and verifiable process. The reasons behind such restrictions are:

Due to random (unbiased) sampling of blend nodes, messages are distributed uniformly across the whole set of nodes. Therefore, we avoid creating communication hotspots, and through this, we make the rewarding process fair.
The restriction on the selection of the blend node limits the possibility of targeting a specific node by an adversary. The adversary is limited only to a subset of keys that can be used to generate a message to a particular node.
It limits the possibility of selfish behavior where a node “consumes” all of its keys and “sends” all messages to itself to increase its reward.

Note that the Proof of Selection alongside the Proof of Quota restricts the set of nodes that can be used for blending path construction. However, the selection of blend nodes from the set and the particular order they are used for path construction is not restricted. Therefore, a node can freely select nodes from the set of blending nodes defined by the PoSel and PoQ mechanisms to construct blending paths for any of the messages it wants to send.

The PoSel assumes:

Public input: $\pi_{Q}^{K_{i}^{n}}$ .
Shared secret: $\rho$ .
Public output: $m_i$ .

Where $\rho$ is the secret selection randomness generated by the $\pi_{Q}^{K_{i}^{n}}$ and shared only with the recipient (node $i$ ), and $m_i$ is an index of the node $i$ on the list of core nodes.

The PoSel ( $\pi^{K^{n}_{i},m_{i}}_{S}$ ) is true when all of the following conditions are met:

$m_i = \text{CSPBRG(}H_{\mathbf N}(\rho))_{8} \mod N$ , where:
- $\rho$ is secret selection randomness that is encoded using little-endian,
- $m_i$ is the index of the recipient node (from the SDP list of core nodes) encoded as little-endian,
- $\text {CSPRBG}()_{8}$ is a cryptographically secure pseudo-random bytes generator whose output is restricted to $8$ bytes which is encoded using little-endian,
- $H_{\mathbf N}()$ is a domain separated blake2b hash function,
- and $N$ is the number of core nodes.
This operation is statistically secure for relatively small $N$ that we assume to have in our system as analyzed in Statistical Analysis of Selection Bias of Modulo Operation.
$v==v'$ , where $v$ is the PoQ nullifier of the $\pi_{Q}^{K_{i}^{n}}$ and $v'=H_{\Psi}(b\text{"KEY\_NULLIFIER\_V1"}, \rho)$ is the PoQ nullifier derived from the secret $\rho$ and $H_{\Psi}()$ is the Posiedon2 hash function.

The PoSel must be used alongside the PoQ, as the PoSel is tightly coupled with the PoQ.

When performing modulo operation on the hash we do the following:

def modular_bytes(data: bytes, modulus: int) -> int:
    # Convert data into an unsigned big integer using little-endian.
    return int.from_bytes(data, byteorder='little') % modulus

Cover Message Schedule

Generation of cover messages is handled by each core node individually. The only protocol-enforced limitation is through the Core Quota ( $Q_C$ ), which limits the number of messages a node can generate.

To protect its own privacy, a core node should emit cover messages in a fully random manner to ensure that the cover messages are evenly distributed across the duration of a session. For example, it can follow the algorithm presented below.

However, before we give the details of the cover message scheduling algorithm, we need to discuss a problem of the deviation of the session length. We have defined the session length as a constant number of blocks, but the block production is a random process that is expected to last for $30$ rounds on average. Due to that randomness of the block production, the length of a session is not deterministic when it is expressed in rounds. Additionally, we define the core quota as the number of messages a core node can emit during a single session. Therefore, we need to address a problem when a session (due to the randomness of block production) lasts longer than expected. This can lead to a situation when the core quota depletes before we transition to another session. Which is not good for privacy as no cover messages are to be generated at the end of a session.

Therefore, in the below algorithm, we define a safety buffer ${I_{end+1}}, ..., {I_{max}}$ , which is used to save some cover messages for the period when no blocks are produced for a longer time. The main idea is to distribute the cover messages beyond the expected end of the session defined as the last interval $I_{end}$ . Then, when the session lasts longer, the node can consume the cover messages from the safety buffer.

We are estimating that the probability of having a period of more than $295$ rounds of no blocks is greater than $0.62$ (The Number of Time-Slots Between Two Consecutive Blocks). This probability is high; therefore, we introduced a safety buffer where a number of cover messages can be stored and used in this case.

We define the length of the safety buffer as $100$ intervals (see Screenshot 2025-05-22 at 08.28.07.png)

Algorithm

Given:

the core quota $Q_C$ ;
the expected number of blending operations for cover messages $\beta_{C}$ ;
the last interval of a session $I_{end}$ ;
the last interval of the safety buffer $I_{max} \gt I_{end}$ , as discussed in the Cover Message Schedule;

For every session do:

Calculate the maximal number of cover messages a node can generate per session:

c = \left\lceil \dfrac{Q_C}{\beta_{C}} \right\rceil

For $i \in \{1,...,c\}$ do:
Select at random interval from session $I \in \{ 1, ..., I_{max} \}$ .
Select at random round from the interval $r \in \{1,..., |I|\}$ .
If the pair was already selected $(I, r) \in W$ , then repeat above steps. Else add the pair to the winning slots.

Then, during each interval $I \in \{ 1, ..., I_{max} \}$ and for every round $r \in I$ , if the $(I,r) \in W$ a cover message can be generated, as defined in the Generation section below.

The number of generated cover messages must be reduced by the number of data message that a node generates during the session. This is important for maintaining statistical indistinguishability of the node.

Message Structure

For this document, we present a definition of the message structure as defined in the [1.0.0] Message Encapsulation Mechanism. For simplicity, we omit the versioning of the message as defined in [1.0.0] Message Formatting.

A node $n$ constructs a message $\mathbf M = (\mathbf H, \mathbf h, \mathbf P)$ according to the format presented below.

Diagram

$\mathbf H$ is a public header:
$K^{n}_i$ , a public key from the set $\mathbf K^n_h$ .
$\pi^{K^{n}_i}_{Q}$ , a corresponding proof of quota for the key $K^{n}_i$ from the $\mathbf K^n_h$ and contains its PoQ nullifier $\nu_i$ .
$\sigma_{K^{n}_{i}}(\mathbf P_i)$ , a signature of the $i$ -th encapsulation of the payload $\mathbf P$ , that can be verified by the public key $K^{n}_{i}$ .
$\mathbf h = (\mathbf b_1,...,\mathbf b_{\beta_{max}})$ is an encrypted private header:
$\mathbf b_l$ is a blending header:
1. $K^{n}_{l}$ , a public key from the set $\mathbf K^n_h$ .
2. $\pi^{K^{n}_{l}}_{Q}$ , a corresponding proof of quota for the key $K^{n}_l$ from the $\mathbf K^n_h$ and contains its PoQ nullifier $\nu_l$ .
3. $\sigma_{K^{n}_{l}}(\mathbf P_l)$ , a signature of the $l$ -th encapsulation of the payload $\mathbf P$ , that can be verified by the public key $K^{n}_{l}$ .
4. $\pi^{K^{n}_{l+1},m_{l+1}}_{S}$ , a proof of selection of the node index $m_{l+1}$ assuming a public key $K^{n}_{l+1}$ .
5. $\Omega$ , a flag that indicates that this is the last blending header.
$\mathbf P$ is a payload.

Encapsulation Overhead Calculation: Assuming that we use Groth16 SNARKs as a proving system, we need $160$ bytes per PoQ ( $128$ for proof and $32$ for nullifier) quota. Which gives us $289$ bytes per hop (proof of quota $160$ bytes + proof of selection $32$ bytes + public key $32$ bytes + signature $64$ bytes + last flag $1$ byte) plus $256$ bytes for the public header. Which for $3$ hops gives us $1123$ bytes in total. That increases the block proposal message defined in [1.1.1] Block Construction, Validation and Execution, of $33129$ bytes by $\approx 3\%$ .

Formatting

The payload of the message must be formatted according to the following document: [1.0.0] Message Formatting

The payload must be encapsulated according to the following document: [1.0.0] Payload Formatting

Every encapsulated message must be formatted according to the following document: [1.0.0] Message Encapsulation Mechanism

Generation

Generation of a message is triggered by any of the following events:

A core or edge node won a consensus lottery and has a proof of leadership, which entails a node to emit a data message. The payload of the message is a block proposal.
A Cover Message Schedule. The payload of the message contains random data.

When this happens, a number of messages (limited by the Quota) are generated as follows:

A number of keys are generated according to the [1.0.0] Key Types and Generation.
Each key uses a message-type-specific allowance as described in the Quota.
The correct usage of the allowance is proven by Proof of Quota.
The payload of the message is formatted according to the [1.0.0] Payload Formatting.
The above set of keys is used to encapsulate the payload of a message according to the [1.0.0] Message Encapsulation Mechanism.
Each key is used for a single encapsulation of a message, which can be processed (decapsulated) by a single node.
The node selection is random and deterministic, and is provable by Proof of Selection.
The message is formatted according to the [1.0.0] Message Formatting.
The message is released according to the Releasing logic.

Relaying

The relaying logic is defined as follows:

The node checks the header of the message that was received from its neighbor, according to the [1.0.0] Message Formatting.
If the neighbor is a core node, then update the message counter for the neighbor.
If the neighbor is an edge node, then close the connection with the neighbor.
If the header of the message is incorrect, then discard the message and mark the neighbor as malicious and close the connection. We assume that adversary cannot inject any spoofed message to the connection.
If the PoQ nullifier $\nu_i \in \mathbf H$ from the public header of the message was already seen, then the message is a duplicate and must be discarded. The PoQ nullifiers are valid during a single session, therefore, they need to be stored for the duration of the current session and during the Transition Period.
If the signature $\sigma_{K^{n}_{i}}(\mathbf P_i) \in \mathbf H$ from the public header of the message is invalid, then the message must be discarded, and the neighbor must be marked malicious.
Release the message according to the Releasing logic.
Concurrently to the above step, add the message to the processing queue, where it is handled by the Processing logic.

The node must cache the PoQ nullifiers ( $\nu_i$ ) for every message it relays for a duration of a single session plus the safety buffer (see Algorithm) and Transition Period (TP). Then the node can clear the cache. That means that size of the cache must be at least:

\begin{aligned} (S + \mathrm{safety\ buffer} + \mathrm{STP})\cdot (F_C +F_D) \cdot \beta_{max} \cdot |\nu_i| &=(648000 + 3000 + 30) \cdot \left(1+\dfrac{1}{30}\right) \cdot 3 \cdot 32 \\ &= 64582176 \approx 65\,\mathrm{MB} \end{aligned}

Processing

When a message $\mathbf M$ is received by the node, then it is processed by this logic:

If the proof $\pi^{K^{n}_i}_{Q} \in \mathbf H$ from the public header of the message is not correct, then the message must be discarded.
Decapsulate the message as defined in the decapsulation section of the [1.0.0] Message Encapsulation Mechanism.
If the decapsulation is successful, then:
If the proof of selection ( $\pi^{K^{n}_l,l}_{S} \in \mathbf b_1$ ) is invalid, then the message is discarded. A valid proof of selection points to the index of the node $l$ in the list of nodes returned from the SDP.
Store the blending token which is the collection of the proof of quota from the header ( $\pi^{K^{n}_l}_{Q} \in \mathbf H$ ), and the proof of selection from the private header ( $\pi^{K^{n}_l,l}_{S} \in \mathbf b_1 \in \mathbf h$ ):

t = ( \pi^{K^{n}_l}_{Q} \in \mathbf H, \pi^{K^{n}_l,l}_{S} \in \mathbf b_1 \in \mathbf h).

If the last flag is set ( $\Omega == 1$ ) then examine the header type of the payload as defined in the [1.0.0] Payload Formatting, then: 1. If the payload is a block proposal, then the payload structure is verified and broadcast, as defined in the Broadcasting section. 2. If the payload is a cover message, then the payload is discarded.
Else:
1. Examine the decapsulated public header:
  1. If the PoQ nullifier $\nu_i \in \mathbf H$ from the public header of the message was already seen, then the node was not allowed to use the same PoQ nullifier and the message must be discarded. The PoQ nullifiers are valid during a single session, so they do not need to be stored for more than a single session.
  2. If the signature $\sigma_{K^{n}_{i}}(\mathbf P_i) \in \mathbf H$ from the public header of the message is invalid, then the message must be discarded.
  3. If the proof of quota $\pi^{K^{n}_i}_{Q} \in \mathbf H$ from the public header of the message is not correct, then the message must be discarded.
2. Format the message according to the [1.0.0] Message Formatting.
3. Attempt a subsequent decapsulation to validate whether the node is the recipient (return to step 1). This must be done recursively to remove all consecutive encapsulation layers where the node is the intended recipient.
4. If the decapsulation fails (meaning no more layers remain), randomly delay the message and release the formatted message according to the Releasing logic.
If decapsulation fails, return the appropriate decapsulation failure message.

Blending tokens are stored by the node for rewarding purposes, as they prove that the node processed the message. The blending tokens are stored alongside context information such as the session number. We denote the set of blending tokens from a session $s$ stored by a node $l$ as $\mathcal{T}^{l,s}$ .

Delaying

The purpose of message delaying is to hide timing correlations between incoming and outgoing messages from a node. That is, a message is delayed in a random manner, which makes it harder to link the incoming and outgoing messages based on the network timing observation.

The message anonymity pool is the total number of messages that have been seen by the node between two subsequent message release events. The set of seen messages does not necessarily include a message that the node is the recipient of.

The key design objective is to release messages with an upper bound on the delay. Therefore, the design assumes that there is a $\Delta_{max}$ maximum delay between two subsequent message release attempts that define the longest waiting time for message release. This also defines the maximal message anonymity pool (assuming a single message is released in a round by the network).

Now we can define the delaying logic:

Select at random a delay: $\delta \in (1, \Delta_{max})$ .
Start counting rounds: $r_s$ is the starting round.
Every round check if the current round ( $r_c$ ) is the delayed one $r_c == r_s+\delta$ , then:
Release messages from the queue according to the Releasing logic.
Select at random a delay: $\delta \in (1, \Delta_{max})$ .
Start counting rounds: $r_s$ is the starting round.

If the queue is empty, then we do not release any message.

However, the release round selection must work independently of the queue state. Otherwise, the maximal anonymity set is going to be $\Delta_{max} \over 2$ , which must be scaled by the number of messages that are released in a single round.

Releasing

The process of releasing messages involves the following steps:

Upon receiving a message, it is immediately released to all neighboring.
All processed messages are queued and released at the next release round determined by the Delaying logic.
Every generated message is released at the beginning of the next round after its generation.
As soon as a data message is generated, one random unreleased (future) cover message must be removed from the release schedule to maintain the node’s statistical indistinguishability.
If more than one message needs to be released for the same round, they must be randomly shuffled before release.

The cover and data message generation processes are independent, and there is a non-zero probability that more than one message will be scheduled for the same round. Therefore, the number of messages that can be released during a single round is not restricted.

However, a node can calculate the expected number of messages to be released per release round. This depends on the value of $\Delta_{max}$ , the network size (number of core nodes), and the generation quota. This number can be used to detect spammy nodes as part of the Connectivity Maintenance logic.

For sufficiently large networks, the number of processed messages queued in a node will be smaller than $1$ on average.

However, in smaller networks, the number of messages queued in a node will be larger than $1$ . We must avoid this property because the additional delay negatively impacts the consensus protocol's safety. Therefore, we need to determine the network size threshold where the number of messages to be released exceeds $1$ .

The expected number of messages to be released during a single release round for a single node is:

\mu = \left\lceil{\Delta_{max} \cdot \beta_C \cdot \alpha \over {N }}\right\rceil

Where:

$\Delta_{max}$ is the maximal delay time between two release rounds;
$\beta_C$ denotes an expected number of blending operations for each cover message;
$\alpha$ is a message number normalization constant;
$N$ is the number of core nodes in the network.

Let us assume:

$\Delta_{max}=3$ is our target value, as defined in the Delaying section above;
$\beta_C=3$ , which means that every round, $3$ nodes are going to be processing messages generated by the network, which is a reasonable assumption as it defines the maximum number that the protocol can tolerate due to the quota limitations;
$\alpha \approx 1.03$ , corrects the number of messages to include data messages.

This gives us:

For $N=16$ core nodes; $\mu=1$ message per release round on average.
For $N=8$ core nodes; $\mu=2$ messages per release round on average.
For $N=4$ core nodes; $\mu=3$ messages per release round on average.

We use the $\mu$ estimator for calculating the maximum and minimum number of messages that can be received by a node, as listed in the Global Parameters section.

Broadcasting

Every payload that is added to the broadcasting queue is processed as follows:

The block proposal is extracted from the payload.
The block proposal is sent to a Logos Blockchain broadcasting channel after a random delay, as defined in the Releasing section.

The broadcasting happens through an independent protocol. All Logos Blockchain nodes form the broadcasting network, which means that it is larger than the blend network.

Rewarding

To better understand the context of the constructions defined in this section refer to the overview of the Mechanics, and for the motivation of the processing of messages in Motivations.

Session Randomness

The rewarding protocol requires a common and unbiased randomness. We assume that it is provided by the consensus, but at a limited frequency, once per epoch. Therefore, we define the following function:

R_{s}=H(D_{\mathrm{blend}}\mathbin{\|}R_e(s)\mathbin{\|}s,512)

where:

$R_s$ is the session randomness;
$D_{\mathrm{blend}}$ is the domain separator BLEND_SESSION_RANDOMNESS_V1;
$H()_{512}$ is a the blake2b hash function returning $512$ bits output;
$||$ is a binary concatenation operator;
$R_e(s)$ is the epoch nonce from the consensus epoch state, where the epoch number corresponds to the block beginning session $s$ ;
$s$ is the session number.

The block $b$ that marks the beginning of a session $s$ can be derived from the session number $b=s \cdot S$ , where $S$ is the length of a session expressed in blocks.

With this approach, we achieve independence from the epoch randomness and maintain a common view and unbiasability of the randomness among all nodes.

Activity Proof

The node activity proof ( $\pi_{A}^{l,t,s}$ ) is a construction that attests in a probabilistic manner that a node $l$ was active during the session $s$ , by presenting a blending token $t$ .

In other words, the activity proof is $\text{true}$ when:

A node $l$ has a blending token $t \in \mathcal{T}^{l,s}$ collected during session $s$ , and that:
- Proof of Quota $\pi^{K^{n}_l}_{Q} \in t$ is true assuming session $s$ .
- Proof of Selection $\pi^{K^{n}_l,l}_{S} \in t$ is true assuming session $s$ .
- $K^{n}_l$ , a public key from the set $\mathbf K^n_h$ , that is used to verify the above proofs.
The Hamming distance ( $\Delta_{\mathcal H}(a,b)$ — returns the number of different bits between $a$ and $b$ binary strings) between the blending token $t$ and the next session randomness $R_{s+1}$ is smaller than the node activity threshold $\mathcal A _{\epsilon}$ . That is:

\Delta_{\mathcal H}(H(t)_{\epsilon},H(R_{s+1})_{\epsilon}) < {\mathcal A}_{\epsilon}

Where:

$H()$ is a hash function (the implementation of the hash function is blake2b returning $\epsilon$ bits).
$\epsilon$ is a number of bits that can represent an expected number of blending tokens generated during a session. The number is rounded up to full bytes as required by the blake2b hash algorithm:

\epsilon = \left\lceil \log_2(Q_C^{Total}+1) \over 8\right\rceil\cdot8

The Hamming distance verification prevents nodes from the grinding or pre-computation attacks due to the unpredictability of the randomness of the next session. However, the unpredictability of the session randomness is not guaranteed as it depends on the consensus transitioning to the next epoch before transitioning to the next session. Even if a node knows the value of the randomness in advance, it will not increase its chance for getting a reward as the node does not control the process of generating blending tokens. However, a dishonest node could use that knowledge to refrain from sending a message with a token that has a potential (probabilistic, not deterministic) of granting a premium reward for the recipient blend node.

The node activity proof construction is:

class ActivityProof:
    session_number: SessionNumber
    signing_key: SigningKey
    proof_of_quota: ProofOfQuota
    proof_of_selection: ProofOfSelection

Where:

SessionNumber is the number of the session for which the activity proof is generated.
ProofOfQuota is defined as in [1.0.1] Proof of Quota.
ProofOfSelection is defined in Proof of Selection.
SigningKey is the key used to sign the ProofOfQuota.

Activity Threshold

The activity threshold ${\mathcal A}_{\epsilon}$ defines the expected maximal Hamming distance from the session randomness to the blending token expressed as an integer smaller or equal $\epsilon$ .

We define the activity threshold as follows:

{\mathcal A}_{\epsilon} = \chi - \nu- \theta

Where:

$\nu=\left\lceil \log_2(N + 1) \right\rceil$ represents the number of bits that are needed to express the number of nodes in the network $N$ , it makes the lottery difficulty a function of the network size;
$\chi=\left\lceil\log_2(Q_C^{Total}+1)\right\rceil$ represents the number of bits needed to express all blending tokens generated during a session, where $Q_C^{Total}$ is the total number of cover messages generated by the network during a session (as defined here);
$\theta=1$ represents a sensitivity parameter that controls the winning conditions of the lottery.

We assume that setting $\theta = 1$ is enough to eliminate nodes that have not been active enough without too aggressively eliminating nodes that worked but had less luck with the lottery. However, we are going to revise this parameter in the future version of the protocol.

Active Message

A node $l$ for every session must construct an active message $M_A= \{l, t, s, \pi_{A}^{l,t,s} \}$ , which must follow the Active Message.

The active message metadata field must start with a header that contains a one byte version field which is fixed to 0x01 value, the rest of the metadata is populated by the Activity Proof.

The active message is stored on the ledger.

The active message is used for calculating the node reward.

The active message is constructed after the current session, when the next session randomness is known.

The active message for session $s$ must only be sent during session $s+1$ ; otherwise, it must be rejected.

The node $l$ selects the activity proof to include in the active message such that the Hamming distance between the proof and the new randomness is minimal.

\pi_{A}^{l,t,s} = \min_{\Delta_{\mathcal H}}(\mathrm{true}(\pi_{A}^{i,t,s}))

The ledger must only accept a single active message per-node per-session. Any duplicate must be rejected.

Reward Calculation

The node rewards for session $s$ are calculated according to the following schema:

Rewards are not calculated if the number of nodes (unique ProviderIds from declarations) retrieved from the SDP protocol is lower than the Minimal Network Size.
Count the number of true activity proofs registered on the ledger: $B = \sum_{i=1}^{N}\mathrm{true}(\pi_{A}^{i,t,s})$

This value is used for calculating the base reward paid for all active nodes.
Count the number of true activity proofs registered on the ledger with the smallest Hamming distance—that is, calculate the number of nodes with the minimal distance among all submitted active messages: $P = \sum_{i=1}^{N}\min_{\Delta_{\mathcal H}}(\mathrm{true}(\pi_{A}^{i,t,s}))$

This value is used for calculating the premium reward, which is paid for all active nodes that have their activity proofs closest to the session randomness.
Calculate the base reward: $R = {I \over B + P}$

where $I$ is the value of income for the Blend Network service for the session $s$ . For more details about the income calculation, refer to linked reference.
Calculate the reward of the node $n$ : $R(n) = R \cdot [\mathrm{true}(\pi_{A}^{i,t,s}) + \min_{\Delta_{\mathcal H}}(\mathrm{true}(\pi_{A}^{i,t,s}))]$

That is, a base reward ( $R$ ) is paid out to all nodes who have submitted a true activity proof, and the reward is doubled for nodes that submitted a true proof with a minimal Hamming distance.

Rewarding Distribution Logic

The reward is paid out to the node $n$ based on the node's activity declaration and the above reward calculation.

The rewards are distributed according to [1.2.1] Service Reward Distribution Protocol. Here we are briefly sketching the main idea of the reward distribution protocol. For more details refer to the above document.

To receive a reward, a node must send an Active Message as described in the Active Message, where the Metadata field consists of a node activity proof. The node must point to a single declaration (declaration_id) and use a single provider identity (provider_id) for constructing the Active Message. Any reuse of the provider_id must make the Active Message invalid.
The Active Message must be sent after the end of a session ( $s$ ), that is, during the next session ( $s+1$ ), and after the session transition period as defined in the Transition Period section. The delay allows nodes to include blending tokens collected during the session transition period for rewarding purposes.
When the following session begins ( $s+2$ ) Mantle distributes rewards ([1.2.1] Service Reward Distribution Protocol). This delay is required to calculate the partition of rewards as defined in the above section.
If a node does not send the Active Message on time, then it will not receive a reward.

Analysis

Impact of the Blend Protocol on the Time to Link and Time to Infer the Stake

The main objective of the Blend protocol is to reduce the probability of linking a sender with the proposal, which also translates to increasing the time of learning the node’s (relative) stake.

The average latency penalty does not include the network delay.

The Blend Protocol increases the Time to Infer (TTI — Inference of relative stake) the stake $300$ times (assuming a network of a peering degree 4) in comparison to not using the Blend Protocol. This TTI increases $10$ times for every additional Blend node used, reaching more than $10$ years ( $487$ epochs) to infer a node stake.

When the peering degree is increased to 6 the time to infer the stake increases $200$ times that means that higher peering degree decreases the time as an adversary has more chances to observe traffic.

(*) Our TTI calculations are capped at more than $487$ epochs, which can be interpreted as more than $10$ years — a relatively safe threshold.

The time to infer the node stake depends on the confidence of the adversary. The confidence increases as the network observation time increases. Assuming $10\%$ node adversaries in the network and stake inference confidence of $60\%$ (which tells us about the confidence of the adversary when learning the node stake), we obtain the following values.

TTI — peering degree 4:

	1% node stake	0.1% node stake	0.01% node stake	Average latency increase
No Blend	0.32 epochs	3.2 epochs	32.2 epochs	0
1-hop Blend	94 epochs	more than 487 epochs (*)	more than 487 epochs (*)	1.5s
2-hop Blend	more than 487 epochs (*)	more than 487 epochs (*)	more than 487 epochs (*)	3s
3-hop Blend	more than 487 epochs (*)	more than 487 epochs (*)	more than 487 epochs (*)	4.5s

TTI — peering degree 6:

	1% node stake	0.1% node stake	0.01% node stake	Average latency increase
No Blend	0.32 epochs	3.2 epochs	32.2 epochs	0
1-hop Blend	68 epochs	more than 487 epochs (*)	more than 487 epochs (*)	1.5s
2-hop Blend	more than 487 epochs (*)	more than 487 epochs (*)	more than 487 epochs (*)	3s
3-hop Blend	more than 487 epochs (*)	more than 487 epochs (*)	more than 487 epochs (*)	4.5s

When the Blend protocol is applied, then the the Time to Link (TTL — The Unlinkability of Block Proposers) is non-instant, and it increases with the number of blend nodes used. For each additional blend used, the time increases $10$ times and the cost is of additional $1.5$ seconds of average latency.

Without the Blend protocol, the TTL is instant as the proposal is directly broadcast by the sender. Below we present a table where we show how long it takes to link a node to a single message with more than $50\%$ probability.

TTL — peering degree 4:

	1% node stake	0.1% node stake	0.01% node stake	Average latency increase
No Blend	instant	instant	instant	0
1-hop Blend	0.9 epochs	9 epochs	91 epochs	1.5s
2-hop Blend	9 epochs	91 epochs	917 epochs	3s
3-hop Blend	91 epochs	917 epochs	9175 epochs	4.5s

TTL — peering degree 6:

	1% node stake	0.1% node stake	0.01% node stake	Average latency increase
No Blend	instant	instant	instant	0
1-hop Blend	0.7 epochs	6.7 epochs	67.3 epochs	1.5s
2-hop Blend	6.7 epochs	67.3 epochs	673.4 epochs	3s
3-hop Blend	67.4 epochs	673.4 epochs	6734 epochs	4.5s

Statistical Analysis of Selection Bias of Modulo Operation

Applying a modulo $N$ operation to the output of a pseudorandom number generator (here the Blake2b hash function) with a large range (here from $0$ to $2^{256}-1$ ), introduces a statistical bias when mapping to the smaller domain $\{0,1,\ldots,N-1\}$ . This bias arises because $2^{256}$ is typically not divisible by $N$ , meaning that some residues modulo $N$ will occur slightly more often than others. Specifically, let $R:=2^{256}$ , then $R=q\cdot N+r$ with $0 \leq r \lt N$ . The first $r$ values modulo $N$ will appear $q+1$ times, while the remaining $N-r$ values will appear $q$ times. Thus, the maximum bias between two values $a\leq r$ and $b \gt r$ in $\{0,1,\ldots,N-1\}$ is:

|Pr[a]-Pr[b]| \leq \left| \frac{q+1}{R} - \frac{q}{R} \right| = \frac{1}{R}

Where $Pr[a]$ is the probability that $a$ is the result of the modulo $N$ operation and $Pr[b]$ the probability that $b$ is the result of the modulo $N$ operation.

The maximum per-value bias is exactly $\frac{1}{R}$ , regardless of $N$ , as long as $N \lt R$ . That means no single output differs from uniform by more than $2^{-256}$ .

But now we consider total variation distance, a better global metric of distinguishability between the true distribution and uniform. This is:

TV := \frac{1}{2}\sum_{x=0}^{N-1}\left| Pr[x] - \frac{1}{N} \right| = \frac{1}{2} \left( r \cdot \left| \frac{q+1}{R} - \frac{1}{N}\right| + (N-r) \cdot \left| \frac{q}{R} - \frac{1}{N} \right|\right)

We know then:

\begin{align} &R=q\cdot N+r \implies \frac{1}{N} = \frac{R}{NR} = \frac{qN+r}{RN} = \frac{q}{R}+\frac{r}{NR}\\ &\frac{q+1}{R}-\frac{1}{N} = \frac{q+1}{R} - \frac{q}{R} - \frac{r}{NR} = \frac{1}{R} - \frac{r}{NR} > 0 \; \text{because} \; \frac{r}{N} < 1 \\ &\frac{1}{N} - \frac{q}{R} = \frac{q}{R} + \frac{r}{NR} - \frac{q}{R} = \frac{r}{NR} > 0 \end{align}

Reinjecting in the formula of $TV$ :

\begin{aligned} TV&=\frac{1}{2} \left( r \cdot \left( \frac{1}{R} - \frac{r}{NR} \right) + (N-r) \cdot \frac{r}{NR} \right)\\ &=\frac{1}{2} \left( \frac{r}{R} - \frac{r^2}{NR} + \frac{Nr}{NR} - \frac{r^2}{NR} \right)\\ &= \frac{r}{R} - \frac{r^2}{NR}\leq \frac{r}{R} \leq \frac{N}{R} \end{aligned}

So the distribution deviation is less than $\frac{N}{R}$ which is cryptographically negligible when $\frac{N}{R} \leq 2^{-128}$ . Since $R=2^{256} \implies N \leq 2^{128}$ . Since the number of nodes participating in Blend is expected to be less than 10 million (less than $N=2^{24}$ ) we can safely skip the rejection process necessary to draw random numbers uniformly in $\{0,1,\ldots,N-1\}$ .

Logos LIP