NYM Mechanism Introduction -- Proof of Mixing

Brief Introduction

Nym network (“NYM“) is a decentralized and incentivized infrastructure to provision privacy to a broad range of message-based applications and services. It supports all networked applications and prevents them from possible threat models.

Prerequisites

Before illustrating the main concept, I am supposed to give you a brief introduction of NYM components and how it works to protect privacy.

There are three roles in NYM network: gateways, mix nodes, and validators. Gateway is the first journey of messages, handling interaction with users and temporarily caching replies from mixnodes when users are offline. Mix node provisions communication privacy to users through relaying data packets randomly and anonymously. After receiving messages from successors, the last mix node sends final data packets to service providers, destinations you’d like to go. Above these components, decentralized validators are responsible for core functions performance and credential issuances.

Proof of Mixing

Node operators are able to choose which role they’d like to be in NYM and mix nodes account for a large fraction of the network. In order to make sure NYM works smoothly, mix nodes need correctly and reliably process, route, and deliver messages. Nodes in the mix net are rewarded via proof of mixing scheme that proves that mix nodes are providing a high quality of service. Quality of service (QoS) is measured by the performance factor PF, denoting the fractions of packets correctly routed by the mix node.

How to calculate PF in such an anonymous network is the next challenge. In NYM, measurement messages generated by mix nodes and users are routed and spread. After a specific period, an epoch, each mix node submits its own proof of mixing, and validators evaluate QoS and rewards are distributed to the mix net.

Generation of measurement messages

Measurement messages are generated by mix nodes and end users, following circular routes. Moreover, mix nodes cannot distinguish between these messages and normal data packets. Both of them are relayed, routed, and delivered in the same way. Here, I illustrate the process of mix nodes, which is similar to that of users (Read the whitepaper for details).

Each mix node has a public key pair (pk, sk). Before an epoch, validators publish random information to the network. Through VRF calculations with this information and private keys, mix nodes generate output values y (numbers) and node proofs. All participants can use node proofs and public information to verify the correctness of output values, which will be used in the subsequent step. Then, mix nodes feed their output values y and public network information to a sampler, outputting reproducibly random values to form the measurement packets. Like output values y, these random values can be calculated again with y and network information. This feature will benefit the verification part.

Routing measurement messages

Now, all mix nodes have a measurement packet and send them at the beginning of an epoch. We request mix nodes to record the tag of every packet they receive and deliver. Combining tags with timestamps, the mix node stores a list of records in a local Merkle tree (A data structure usually used in the blockchain field to prevent contents from being changed). At the end of an epoch, mix nodes are asked to broadcast the hash value of the Merkle root (As long as the hash value keeps the same, contents of this Merkle tree are not modified) to validators. Failing to broadcast the value would result in a mix node being considered as having PF = 0 for this epoch, and thus receiving no reward.

Opening measurement messages

Once all H(Root)s have been published, all measurement mix nodes submit their output values y and corresponding node proofs. At the same time, validators publish this information to the network, enabling all participants to verify y and recreate measurement packets spread in the epoch. Output values y can be verified through node proofs and public information issued by validators, and packet reconstruction is done by feeding y and network information to the sampler again. For those nodes doing this, they need to find packets they handled before, search relative records with packet tags in their Merkle trees, and report matches. This procedure is called Proof of Mixing. Like the previous step, failing to do so reduces their performance factor and rewards.

Evaluation of quality of service

Through packet tags matches and output value y verifications, all measurement nodes can tell packets’ status, like how many packets were received, or which packets were lost. After statistics, rewards can be determined and distributed (detailed distribution rules will be discussed in other chapters).

Note

This blog only covers important steps of Proof of Mixing and some descriptions may be inaccurate and even wrong due to my limited knowledge and understanding. Please feel free to drop me an email, myz1237@outlook.com, or DM me in Twitter, @myz12371. I am happy to discuss with you and correct my mistakes.

Reference

NYM Whitepaper, The Nym Network The Next Generation of Privacy Infrastructure, https://nymtech.net/nym-whitepaper.pdf.

Some icons used in my pictures are from Google Images.