Introduction

A Substrate Mix Network enables anonymous submission of transactions to a blockchain. The Substrate Mix Network design is loosely based on Loopix.

A Substrate Mix Network has two main components:

• A network of nodes.
• A blockchain, which provides consensus on which nodes should operate as "mixnodes", and accepts the anonymously submitted transactions.

This specification details the behaviour required of a node. It is primarily aimed at those creating alternate node implementations.

This specification does not attempt to:

• Describe the blockchain runtime logic; only the interface to the runtime is covered.
• Describe any particular node implementation.
• Justify design decisions.

Conventions and definitions

Code snippets roughly follow Rust syntax. a ++ b means the concatenation of arrays a and b.

X25519

X25519 is a Diffie-Hellman key exchange function, based on the elliptic curve Curve25519. It is described in detail in the Curve25519 paper.

X25519 is used to generate shared secrets for packet encryption and such. All X25519 keys and shared secrets are encoded as described in the paper.

The Curve25519 function, which multiplies a curve (or twist) point by a "scalar" value (such as a secret key), is defined in the paper. The clamp_scalar function is defined as follows:

fn clamp_scalar(scalar: [u8; 32]) -> [u8; 32] {
    scalar[0] &= 248
    scalar[31] &= 127
    scalar[31] |= 64
    scalar
}

It clamps a raw 32-byte value to the set of secret keys (scalars) defined in the paper.

BLAKE2b

BLAKE2b is a cryptographic hash function. It is described in detail in BLAKE2: simpler, smaller, fast as MD5.

blake2b(personalisation, seed, key) is defined as the BLAKE2b hash of the empty string computed with the given personalisation (ASCII encoded), seed (little-endian encoded), and key.

Generation of exponentially distributed random numbers

The exp_random function is defined as follows:

fn exp_random(seed: [u8; 16]) -> f64 {
    rng = rand_chacha::ChaChaRng::from_seed(seed ++ seed)
    rng.sample::<f64, _>(rand_distr::Exp1).min(10.0)
}

Where rand_chacha and rand_distr match the behaviour of the crates.io crates with versions 0.3.1 and 0.4.3 respectively.

Given random 16-byte seeds, it produces exponentially distributed random f64s with a mean of 1.

The following assertions should all succeed:

assert_eq!(
    exp_random([
        0xdc, 0x18, 0x0e, 0xe6, 0x71, 0x1e, 0xcf, 0x2d,
        0xad, 0x0c, 0xde, 0xd1, 0xd4, 0x94, 0xbd, 0x3b
    ]),
    2.953842296445717
)
assert_eq!(
    exp_random([
        0x0a, 0xcc, 0x48, 0xbd, 0xa2, 0x30, 0x9a, 0x48,
        0xc8, 0x78, 0x61, 0x0d, 0xf8, 0xc2, 0x8d, 0x99
    ]),
    1.278588765412407
)
assert_eq!(
    exp_random([
        0x17, 0x4c, 0x40, 0x2f, 0x8f, 0xda, 0xa6, 0x46,
        0x45, 0xe7, 0x1c, 0xb0, 0x1e, 0xff, 0xf8, 0xfc
    ]),
    0.7747915675800142
)
assert_eq!(
    exp_random([
        0xca, 0xe8, 0x07, 0x72, 0x17, 0x28, 0xf7, 0x09,
        0xd8, 0x7d, 0x3e, 0xa2, 0x03, 0x7d, 0x4f, 0x03
    ]),
    0.8799379598933348
)
assert_eq!(
    exp_random([
        0x61, 0x56, 0x54, 0x41, 0xd0, 0x25, 0xdf, 0xe7,
        0xb9, 0xc8, 0x6a, 0x56, 0xdd, 0x27, 0x09, 0xa6
    ]),
    10.0
)

Peer IDs

The peer IDs published on the blockchain and used in forward actions are raw 32-byte Ed25519 public keys, encoded as described in the Ed25519 paper. They are convertible to normal libp2p peer IDs as described in the libp2p Peer Ids and Keys specification.

Sessions

The blockchain runtime divides time up into sessions, indexed starting from 0. Note that mixnet sessions need not be the same as eg BABE sessions.

In the context of a session, the network nodes are split into two classes: mixnodes and non-mixnodes. Mixnodes are responsible for mixing traffic. Non-mixnodes may send requests into the mixnet and receive replies from the mixnet, but do not mix traffic. Non-mixnodes can join and leave the mixnet freely, but it is expected that if a node is a mixnode in a session, it will participate for the duration of the session.

The mixnodes for each session are determined by the blockchain runtime. The mixnodes for a session need not be related in any way to the mixnodes for the previous/following sessions.

Every node generates an X25519 key pair per session. Nodes use these keys to generate shared secrets for packet encryption and such; see the Sphinx chapter for more details. Mixnode public keys are published on the blockchain and are thus available to all nodes. Non-mixnode public keys are not published.

When a packet is constructed, it is constructed explicitly for a particular session. A packet's session is implicitly determined by the X25519 keys used to build it (again, see the Sphinx chapter).

Phases

Mixnet traffix is switched from one session to the next gradually, not instantly. Each mixnet session is divided into 4 phases. The current phase is determined by the blockchain runtime. The phases are as follows:

The session traffic columns indicate which packet classes should be sent using the previous/current session keys/mixnodes during each phase:

• None: no packets should be sent.
• Cover and forward only: cover packets should be generated and forwarded. Request/reply packets should not be sent.
• All: no restrictions.

In the first 3 phases (where traffic is sent using both the previous and current session keys/mixnodes), cover and request/reply traffic should be sent at half the usual rate in each session.

The default session column indicates which session should be preferred for new requests.

Note that once the last phase has been reached, the X25519 key pairs for the previous session are no longer needed, and nodes should discard them.

Topology

The mixnodes for a session should be fully connected. That is, all mixnodes should attempt to maintain connections to all other mixnodes. The connections should be maintained for the whole session, as well as for the first 3 phases of the following session.

Mixnodes should also accept connections from non-mixnodes. Non-mixnodes should attempt to connect to a small number of "gateway" mixnodes in each active session.

Route generation

Routes through the mixnet are always generated in the context of a session, for a single packet/SURB. If multiple packets are to be sent, or multiple SURBs are to be built, a separate route should be generated for each one.

There are three kinds of route that a node may need to generate:

• From the node to a mixnode. For requests and drop cover traffic.
• From a mixnode to the node. For SURBs (sent in requests to enable replies).
• From the node to itself. For loop cover traffic.

Routes should be no longer than 7 nodes, including the source and destination nodes. The intermediate mixnodes should be uniformly randomly chosen, subject to the following constraints:

• If the generating node is not a mixnode, any nodes immediately preceding/following it must be connected gateway mixnodes.
• No mixnode should appear in a route more than once, unless this is unavoidable. For example, when a non-mixnode is generating a loop route, if there is only a single connected gateway mixnode, the gateway must necessarily appear twice.
• No node should ever appear twice consecutively in a route.

Note that although very short routes are possible, longer routes provide more anonymity. As such, it is recommended that by default nodes generate the longest routes possible (7 nodes).

Blockchain runtime interface

The blockchain runtime provides functions to query the current session status and the mixnodes for the previous/current sessions. It also provides a function to attempt to register a mixnode for the next session.

Mixnode type

Mixnode instances are passed to the registration function and returned by mixnode queries.

struct Mixnode {
    kx_public: [u8; 32],
    peer_id: [u8; 32],
    external_addresses: Vec<Vec<u8>>,
}

kx_public is the X25519 public key for the mixnode in the session (the session is implicit).

peer_id is the peer ID of the mixnode. It is a raw 32-byte Ed25519 public key.

external_addresses is a list of external addresses for the mixnode. Each external address is a UTF-8 encoded multiaddr.

Note that the peer ID and external addresses for a mixnode are not validated at all by the blockchain runtime. Nodes are expected to handle invalid peer IDs and addresses gracefully. In particular, an invalid peer ID or invalid external addresses for one mixnode should not affect a node's ability to connect and send packets to other mixnodes.

Queries

struct SessionStatus {
    current_index: u32,
    phase: u8,
}

fn MixnetApi_session_status() -> SessionStatus

MixnetApi_session_status returns the index and phase of the current session.

enum MixnodesErr {
    InsufficientRegistrations { num: u32, min: u32 },
}

fn MixnetApi_prev_mixnodes() -> Result<Vec<Mixnode>, MixnodesErr>
fn MixnetApi_current_mixnodes() -> Result<Vec<Mixnode>, MixnodesErr>

MixnetApi_prev_mixnodes returns the mixnodes for the previous session. MixnetApi_current_mixnodes returns the mixnodes for the current session. The order of the returned mixnodes is important; routing actions identify mixnodes by their index in these vectors. These functions can return Err(InsufficientRegistrations) if too few mixnodes were registered for the session (num, less than the minimum min). The mixnet is not operational in such sessions, although nodes should still handle traffic for the previous session in the first 3 phases.

Nodes should always call query functions in the context of the latest finalised block.

Registration

fn MixnetApi_maybe_register(session_index: u32, mixnode: Mixnode) -> bool

To register a mixnode for the next session, MixnetApi_maybe_register should be called in the context of every new best block. session_index should be the index of the current session, and mixnode should be the mixnode to register for the next session. If true is returned, a registration extrinsic was created; MixnetApi_maybe_register should not be called for a few blocks, to give the extrinsic a chance to get included.

MixnetApi_maybe_register may call the host functions ext_crypto_sr25519_sign_version_1 and ext_offchain_submit_transaction_version_1.

Networking

Nodes send mixnet packets to each other using a Substrate notifications protocol. The protocol name is derived from the genesis hash of the blockchain:

/{genesis_hash_hex}/mixnet/1

or (in the case of a blockchain fork):

/{genesis_hash_hex}/{fork_id}/mixnet/1

Notifications with sizes not matching the Sphinx packet size should be discarded. All other notifications should be handled as Sphinx packets.

Nodes should use the peer IDs and external addresses published on the blockchain to connect to mixnodes according to the mixnet topology. If no external addresses have been published for a mixnode, or none of them work, nodes should attempt to discover addresses using the libp2p DHT.

All mixnet node peer IDs should be derived from Ed25519 public keys, "hashed" with the identity function. Nodes may assume this. Note that the peer IDs published on the blockchain and used in forward actions are raw 32-byte Ed25519 public keys.

Sphinx

Substrate Mix Networks use a packet format based on Sphinx.

Packet structure

All packets are the same size: 2,252 bytes. These bytes are split as follows:

The kx_public, mac, and actions fields together form the header.

Key exchange

The X25519 public key kx_public is combined with the receiving node's X25519 secret key for the session recv_kx_secret to produce a 32-byte shared secret kx_shared_secret:

kx_shared_secret = Curve25519(recv_kx_secret, kx_public)

The same shared secret can be derived by combining the secret key corresponding to kx_public, kx_secret, with the receiving node's public key recv_kx_public:

kx_shared_secret = Curve25519(kx_secret, recv_kx_public)

Note that kx_public bears no relation to the source node's X25519 key pair for the session; the corresponding secret key is randomly generated per packet.

Secret derivation

From the 32-byte shared secret, a number of other secrets are derived:

• A 32-byte X25519 blinding factor kx_blinding_factor.
• A 16-byte MAC key mac_key.
• A 32-byte routing actions encryption key actions_encryption_key.
• A 16-byte forwarding delay seed delay_seed.
• A 192-byte payload encryption key payload_encryption_key.

These are derived as follows:

kx_blinding_factor = clamp_scalar(
    blake2b("sphinx-blind-fac", 0, kx_public ++ kx_shared_secret)[..32])

mac_key ++ actions_encryption_key ++ delay_seed =
    blake2b("sphinx-small-d-s", 0, kx_shared_secret)

payload_encryption_key =
    blake2b("sphinx-pl-en-key", 0, kx_shared_secret) ++
    blake2b("sphinx-pl-en-key", 1, kx_shared_secret) ++
    blake2b("sphinx-pl-en-key", 2, kx_shared_secret)

MAC verification

mac should equal the BLAKE2b hash of actions computed with the key mac_key.

The receiving node determines the packet's session by which X25519 secret key results in the hash equalling mac. If neither the previous nor current session key results in a hash equalling mac, the packet is simply dropped.

Routing actions

The routing actions in actions dictate how the packet should be routed. There should be a "forward" action for each intermediate node, followed by a single "deliver" action for the final node.

Actions are two-byte little-endian unsigned integers, with some actions being followed by additional data:

Actions are tightly packed, with the first two bytes of actions giving the first action.

actions is encrypted with the ChaCha20 stream cipher, keyed by actions_encryption_key, using a nonce of zero. Actions past the first are encrypted further with different keys; only the first action can be fully decrypted by the receiving node.

Forward actions

If the first action is a forward action, and the receiving node is a mixnode in the session, it should attempt to forward the packet to the specified node. If the receiving node is not a mixnode, the packet should be discarded. Before forwarding, the packet should be artificially delayed, and transformed.

The artificial delay should be calculated as exp_random(delay_seed) * mean_delay, where mean_delay is the mean forwarding delay (see the parameters chapter).

The packet should be transformed as follows:

Note that:

• The number of zero bytes appended to actions should match the length of the first action (2 plus the length of any additional data); after dropping the first action the total length should match the original length prior to extension.
• Decryption of the extended actions simply means XORing with the ChaCha20 keystream derived from actions_encryption_key.

In the forward-to-peer-ID case, the peer ID is a raw 32-byte Ed25519 public key.

Deliver actions

If the first action is a deliver action, the packet is destined for the receiving node.

If the packet is a cover packet, it should simply be discarded.

If the packet is a request packet, and the receiving node is a mixnode in the session, the payload should be decrypted using payload_encryption_key. If the receiving node is not a mixnode, the packet should be discarded.

If the packet is a reply packet, the receiving node should lookup and remove the payload encryption keys corresponding to the SURB ID from its SURB keystore. If the keys are not found, the packet should be discarded. Otherwise, the keys should be used, one at a time in reverse order, to encrypt the payload. See the SURBs section below for more on SURBs.

After decryption/encryption of a request/reply payload, if the last 16 bytes of the payload are 0, the rest of the payload should be handled as a message fragment. If the last 16 bytes are not all 0, the packet is invalid and should be discarded.

Invalid actions

If the first action is invalid, the receiving node should discard the packet.

Payload encryption

The LIONESS cipher, instantiated with BLAKE2b as the hash function and ChaCha20 as the stream cipher, is used for payload encryption. LIONESS is described in detail in Two Practical and Provably Secure Block Ciphers: BEAR and LION.

Encryption keys, such as payload_encryption_key, are the concatenation of K₁, K₂, K₃, and K₄ (see the linked paper), with K₁ and K₃ being 32 bytes, and K₂ and K₄ being 64 bytes.

The ChaCha20 stream cipher is initialised with a zero nonce.

The lioness crate on crates.io provides a compatible implementation.

Replay filtering

If a node receives multiple packets which have the same kx_shared_secret, it must avoid forwarding or delivering more than one of them. Note that:

• When a secret key is discarded (eg due to a session switch), all shared secrets which were derived from the secret key may be forgotten.
• If a packet is discarded before being forwarded or delivered, its shared secret need not be remembered.
• It is not necessary to record reply packet shared secrets, as the lookup in the SURB keystore will fail for replayed SURBs. Further, as cover packets are simply discarded, and request and forward packets are not accepted by non-mixnodes, if a node is never a mixnode, it need not do any explicit replay filtering.
• It is expected that nodes will use a probabilistic data structure, such as a bloom filter, to record which shared secrets have been derived from each secret key. The false-negative rate of the data structure should be zero. The false-positive rate should be below 1% (ie there should be at most 1% packet loss caused by faulty filtering). Shared secret hashes should be cryptographic, and keyed to avoid DoS attacks.

Packet construction

This section covers the construction of request and cover packets. Reply packet construction is slightly different as it is split into two parts, which take place on different nodes: SURB construction (receiving node) and SURB use (sending node). This is covered in the SURBs section below.

Key generation

The first step in constructing a Sphinx packet is key generation. An X25519 key pair should be generated as follows:

kx_secret = clamp_scalar(random())
kx_public = Curve25519(kx_secret, 9)

Where:

• random() generates 32 random bytes.
• 9, the X25519 base point, is little-endian encoded.

Shared secret computation

The shared secrets can then be computed incrementally:

kx_secrets[0] = kx_secret
kx_shared_secrets[i] = Curve25519(kx_secrets[i], recv_kx_publics[i])
kx_publics[i] = Curve25519(kx_secrets[i], 9)
kx_secrets[i + 1] = (kx_blinding_factors[i] * kx_secrets[i]) % order

Where:

• recv_kx_publics[i] is the X25519 public key of the ith node in the route (excluding the source node).
• kx_blinding_factors[i] is computed from kx_publics[i] and kx_shared_secrets[i] as described above.
• order is 2²⁵² + 27742317777372353535851937790883648493; the order of the group generated by the X25519 base point.

Routing actions

Generating the encrypted routing actions (actions) is non-trivial; the MACs attached to the forward actions depend on the "padding" (encrypted zeroes) the receiving nodes will see. One method is as follows:

• Write the routing actions, unencrypted, into actions. Leave any MACs uninitialised. Fill any unused bytes with random data.
• Compute the padding that each node along the route will observe on packet arrival. The length at each node should match the total length of all earlier actions. The padding is generated by zero-extension and encryption at each node along the route; it can be determined from the action sizes and kx_shared_secrets.
• For each action, in reverse order:
  • Encrypt all bytes from the start of the action to the end of actions, using the encryption key for the node that will process the action.
  • Compute the MAC of the concatenation of the just-encrypted part of actions with the corresponding padding computed in the second step, using the MAC key for the node that will process the action. In the case of the first action, write the MAC to mac; for other actions, write it into actions immediately before the action.

Whichever method is used, it is important that any unused decrypted data the final node sees is indistinguishable from random. If this is not the case, the final node may be able to infer the route length. The above method achieves this by filling unused bytes with random data in the first step.

Note that the 140-byte actions is just large enough to handle the worst case route:

• 4 forward-to-mixnode actions (18 bytes each, 72 bytes total).
• One forward-to-peer-ID action (50 bytes).
• One deliver action with a 16-byte ID (18 bytes).

Payload

Constructing payload is straightforward. For cover packets, simply fill payload with random bytes. For request packets:

• Write zeroes to the last 16 bytes. Write the unencrypted message fragment to the other bytes.
• Derive the payload encryption keys for the nodes along the route from kx_shared_secrets.
• Encrypt payload using each encryption key, in reverse order (starting with the encryption key for the destination node).

SURBs

A SURB (single-use reply block) can be used to send a reply packet to the node that generated it. As the name suggests, each SURB should only be used once. SURBs are always 222 bytes, split as follows:

SURB construction

Equipped with a route, a node can build a SURB as follows:

• Set first_mixnode_index to the index of the first mixnode in the route, excluding the source node.
• Build the Sphinx header header as normal, with the last action being a deliver reply action with a randomly generated SURB ID.
• Randomly generate shared_secret.
• Derive the payload encryption keys for the nodes along the route from kx_shared_secrets, excluding the source and destination nodes.
• Derive a payload encryption key from shared_secret in the same way.
• Store the payload encryption keys (the one derived from shared_secret, followed by the ones derived from kx_shared_secrets) in the SURB keystore, keyed by the SURB ID.

The payload encryption keys corresponding to a SURB ID may never get used, for example if the SURB or the reply packet are lost. It is expected that nodes will only keep a limited number of keys, for the most recently generated SURBs.

SURB use

Constructing a reply packet from a SURB is straightforward:

• Split header into kx_public, mac, and actions.
• Write zeroes to the last 16 bytes of payload. Write the unencrypted message fragment to the other bytes.
• Derive a payload encryption key from shared_secret in the same way that payload_encryption_key is derived from kx_shared_secret above.
• Decrypt payload using the derived key.

The constructed packet should be sent to the mixnode with index first_mixnode_index. The session is implicit: it should match the session used by the request message containing the SURB.

Message fragmentation

Request and reply messages are split into 2,048-byte fragments. Each fragment of a message is wrapped in a Sphinx packet and sent along a different route to the destination. The destination node is responsible for collecting the fragments together and reassembling the message.

Fragment structure

The 2,048 bytes in a fragment are split as follows:

payload has data_size bytes of message data at the start, and num_surbs SURBs tightly packed at the end. Any unused bytes in the middle should be written as 0 by message senders, but ignored by receivers.

Reassembly

Received fragments should be grouped by message_id. Once a full set of fragments for a message_id has been received, the message data and SURBs from each fragment should be concatenated, in index order, to give the original message and an array of SURBs that can be used to reply. The fragments should then be discarded; it is important that no SURB is used more than once.

The session and type (request/reply) of a message should be inferred from the last received fragment, and the message data and SURBs handled appropriately. In the case of a reply message, the corresponding request message ID should also be inferred from the last received packet: request message IDs should be stored alongside payload encryption keys in the SURB keystore.

Note that:

• Malicious nodes may send fragments with the same message_id but differing num_fragments_minus_1. Simply discarding all fragments with a different num_fragments_minus_1 to the first-received fragment is acceptable.
• Nodes should enforce a limit on the number of fragments per message (see the parameters chapter), by simply discarding fragments with a too-large num_fragments_minus_1.
• Multiple fragments with the same message_id and fragment_index may be received. It is recommended that only one be kept.
• Invalid fragments, with fragment_index > num_fragments_minus_1 or (data_size + (num_surbs * 222)) > 2025, should be discarded.

It is expected that nodes will only keep a limited number of fragments, for the most recently seen message_ids.

Construction

Message IDs should be randomly generated. When retransmitting a message, the message ID should be reused. If a new destination is chosen for retransmission however, or if the retransmission is in a different session, a new message ID should be generated.

There are essentially no rules on how message data and SURBs may be split amongst fragments; the only constraints are:

• The message data and SURBs assigned to each fragment must fit.
• The fragments-per-message limit must not be exceeded.

It is important however that the same split is used if a message is retransmitted with the same message_id.

When retransmitting a fragment, exactly the same message data should be sent, but new SURBs must be generated: no SURB should ever be sent twice. When generating SURBs for a request, the message ID should be stored in the SURB keystore alongside the payload encryption keys.

Requests and replies

Request and reply messages are SCALE encoded. Requests have the following type:

enum Request {
    #[codec(index = 1)]
    SubmitExtrinsic(Extrinsic),
}

Where Extrinsic is the extrinsic type of the blockchain.

Replies have types of the form Result<T, RemoteErr>, where T depends on the request, and RemoteErr is defined as follows:

enum RemoteErr {
    Other(String),
    Decode(String),
}

Decode means the node failed to decode the request. Other means the node encountered some other error. In both cases the String is a description of the error, suitable for presenting to the user.

Note that nodes may simply ignore malformed requests, instead of responding with Err(Decode).

SubmitExtrinsic

A SubmitExtrinsic request can be sent to anonymously submit an extrinsic to the blockchain. The reply type is Result<(), RemoteErr>. Ok(()) means the receiving node successfully imported the extrinsic into its transaction pool. It does not mean that the extrinsic was included in the blockchain.

After receiving a SubmitExtrinsic request, a node should wait before attempting to import the extrinsic. The delay should be determined from the request message ID as follows:

seed = blake2b("submit-extrn-dly", 0, message_id)[..16]
delay = exp_random(seed) * mean_delay

Where mean_delay is the mean extrinsic delay; see the parameters chapter.

Packet queues

Nodes should maintain a bounded request/reply packet queue for each session. Packets from a session's queue should be dispatched in place of drop cover packets for the session (provided the current phase permits request/reply packets to be sent). The queue bound should be the same for all mixnodes in a session; see the parameters chapter.

Reply packets should simply be dropped if they cannot be pushed onto the request/reply queue. It is recommended however that nodes use additional queues and/or back-pressure to avoid dropping request packets.

Request sending

The session for a request should be chosen according to the table in the sessions chapter. The destination node should be uniformly randomly picked from the mixnodes for the session, excluding the source node and, if there is exactly one, its connected gateway mixnode. The same session and destination should be used for retransmission, unless:

• The phase changes such that request packets may no longer be sent in the chosen session.
• The destination fails to reply too many times.

In these cases, a new session and destination should be selected.

The request message should be split into fragments, which should then be wrapped in Sphinx packets and pushed onto the session's request/reply queue. The route for each packet should be generated independently as described in the topology chapter.

Multiple copies of each fragment may be sent to improve the chance of success. Each copy of a fragment should contain different SURBs, and should be sent along a different route to the destination.

Retransmission

The round-trip time for a request can be conservatively estimated as follows:

(s, n, m, r) = if request_period > reply_period {
    (request_period, request_len, reply_len, reply_period / request_period)
} else {
    (reply_period, reply_len, request_len, request_period / reply_period)
}
queue_delay = s * (4.92582 + (3.87809 * sqrt(n + (r * r * r * m))) + n + (r * m))

net_delay = per_hop_net_delay * num_hops

rtt = forwarding_delay + queue_delay + net_delay + handling_delay

Where:

• request_period and reply_period are the average periods between drop cover packet dispatches for the session from the source node and the destination node respectively. Note that:
  • All mixnodes in a session should dispatch drop cover packets at the same (average) rate; see the parameters chapter.
  • From the perspective of the nodes, the session phase may change at any time. As such, it should be assumed, for a conservative estimate, regardless of the current phase, that traffic will be sent at half rate in all sessions.
• request_len is the number of request/reply packets queued ahead of the last request packet, plus one.
• reply_len is the maximum length of the destination node's request/reply queue. Note that all mixnodes in a session should have the same queue bound; see the parameters chapter.
• The queue_delay expression is an approximation of the 99.995th percentile of the sum of two independent gamma-distributed random variables with different scales (s, s * r) and shapes (n, m).
• per_hop_net_delay is a conservative estimate of the network (and processing) delay per hop.
• num_hops is the maximum number of hops for any of the fragments to reach the destination, plus the maximum number of hops for any of the SURBs to come back. The number of hops in a route is the number of nodes (including both source and destination) minus one.
• forwarding_delay is the maximum total forwarding delay for any request fragment, plus the maximum total forwarding delay for any SURB.
• handling_delay is a conservative estimate of the time taken to handle the request at the destination and post the reply. In the case of a SubmitExtrinsic request for example, this should include the artifical extrinsic delay.

If a complete reply message is not received within this time, the request message may be retransmitted. When retransmitting, different packet routes should be used, and new SURBs should be generated.

Request handling

Sending a reply message is similar to sending a request message. The message is split into fragments, which are then wrapped in Sphinx packets (using the SURBs attached to the request message) and pushed onto the session's request/reply queue. Multiple copies of each fragment may be sent, provided enough SURBs were attached to the request message, and there is enough space in the request/reply queue.

To avoid handling the same request multiple times, reply messages should be cached by request message ID. When sending a cached reply, the original reply message ID should be reused, but the Sphinx packets should be constructed from different SURBs (eg the ones attached to the triggering request message).

If two request messages with the same ID are received in short succession (as determined by the reply cooldown parameter), the second message should be assumed to be a copy sent at the same time as the first, rather than a retransmission, and should be ignored.

Reply handling

The request message ID corresponding to a received reply message should be inferred from the last received packet; the SURB keystore stores request message IDs alongside payload encryption keys. The request to which the message is a reply should be determined from this ID. If the ID is no longer recognised, the reply message should simply be dropped.

Any SURBs attached to a reply message should be ignored.

Cover traffic

There are two types of cover traffic: drop and loop. They differ in two ways:

• Destination selection for a drop cover packet is the same as for a request: a random mixnode, excluding the source node and, if there is exactly one, its connected gateway mixnode. Loop cover packets are always sent from a node to itself.
• Drop cover packets are replaced by packets from the request/reply queue for the session. Loop cover packets are never replaced.

Nodes should dispatch drop and loop cover packets in each active session according to Poisson processes. The average drop/loop rates should be the same for all mixnodes in a session, and for all non-mixnodes in a session; see the parameters chapter. Note that the rates should be halved in some phases; see the sessions chapter.

Parameters

All nodes in a Substrate Mix Network should agree on the following parameters:

• Mean forwarding delay. This is the average artificial packet delay at each hop.
• Mean extrinsic delay. This is the average artificial delay between receipt of a SubmitExtrinsic request and import of the attached extrinsic.
• Maximum fragments per message. See the message fragmentation chapter.
• Maximum length of a mixnode's request/reply queue. Note that in sessions where a node is not a mixnode, it is free to choose the queue bound itself.
• Reply cooldown. If a node receives two requests with the same message ID within this time period, it should not reply to both of them. See the requests and replies chapter.
• Average cover traffic rates. There are four independent rates: mixnode loop, mixnode drop, non-mixnode loop, and non-mixnode drop. See the cover traffic chapter.