cMix Whitepaper

Mixing with Minimal Real-Time Asymmetric Cryptographic Operations

Executive Summary

Elixxir is a privacy-protecting decentralized transaction platform supporting messaging, payments, and decentralized applications (dApps). That platform runs on a system called cMix, a mixnet protocol for anonymous communications. This paper explains in detail how cMix works as well as the resulting breakthroughs in speed, privacy, security, and scale. The team behind the creation of Elixxir is composed of pioneers who developed early practical, anonymous and verifiable cryptographic systems. Its members are among the first to propose and deploy digital currencies, mix networks, unpermissioned cryptography, verifiable voting systems and many other advances in cryptography. By understanding how cMix synthesizes their prior work, readers can evaluate more fully the opportunity that Elixxir offers to dApp developers, node operators, and consumers seeking unparalleled privacy.

Over the past 25 years, as the internet has become increasingly pervasive, many aspects of our lives have been digitized and recorded as data by centralized entities. Economic incentives to exploit this data as well as an increase in massive data breaches has resulted in a huge uptick in privacy violations. To protect consumers, some platforms promise end-to-end encryption thus limiting access to message content. But this isn’t enough: greater protection is needed for each user’s metadata. Metadata consists of the who, what, when, where, and how details of any message or activity.

To illustrate, consider a group of schoolchildren on a playground. Without directly eavesdropping on conversations, an observer could form an educated guess about the latest schoolyard gossip by simply noticing who is talking to whom, for how long, and under what circumstances. The harvesting and exploitation of this metadata is known as traffic analysis. With increasingly sophisticated traffic analysis tools in the hands of adversaries such as nuisance advertisers, scammers, identity thieves, and even hostile governments, online privacy protection has never been more urgently needed.

Elixxir is working to provide this protection by implementing cMix at consumer scale, fulfilling two core values fundamental to achieving true security and privacy. The first value is anonymity, protecting the identity of participants in activities; for example, a message sender and recipient. This means that an adversary cannot map any input to the corresponding output with any higher probability than random guessing, even if the adversary has compromised most of the system. The second value is integrity--verifying the trustworthiness of the transaction system. This means, for example, that at any given point, either the cMix system delivers all messages without alteration, or, in the event of a failure, any malicious mixnode is identified with high probability.

To achieve both anonymity and integrity, the cMix system brings together two key concepts: mixnets and precomputation. Mixnets, also known as mixing networks, were first described by Elixxir CEO and Founder David Chaum in 1981. A mixnet lays down cryptographic rules for messages or transaction activity from a set of users to be relayed by a sequence of trusted intermediaries known as mixnodes. Mixnodes are computer servers that receive a batch of encrypted messages, randomly permute or “mix” them, and then send them forward. Mixnets typically protect the contents of messages with public key encryption. The mixing process provides anonymity, while the public key encryption provides integrity. The main drawback to traditional mixnets is that they are slow; the public key encryption process takes computers a long time to perform, making mixnets too slow for most consumer uses. cMix solves this problem by using precomputation. Precomputation allows mixnodes to do all the time-consuming work of public key cryptography before the real-time phase of handling messages between senders and recipients. The result is a very efficient kind of mixnet that allows users to send and receive messages in real-time without compromising on security and privacy.

Mixnodes perform the work of decrypting messages and mixing traffic to hide the associations between senders and recipients. The work of mixnets is performed in three phases: setup, precomputation, and real-time. In the setup phase, mixnodes establish secret and shared public keys, which can be used as a seed to derive unique values for every session. The precomputation phase is performed once for each real-time phase. The mixnodes establish shared values to circumvent the need for public key operations during the real-time phase, with each mixnode in an n-member team doing 1/n of the decryption work. In the real-time phase, mixnodes receive messages, perform the decryption work prepared for with precomputation, and pass the message on to the next mixnode.

The Elixxir team is also working to make the cMix user experience simpler than in previous mixnets. When users first enroll in the cMix system, they establish keys that they share with all mixnodes. This will likely be the only time a user is required to perform a cryptographic operation. Thereafter, when a user sends a message on the cMix system, the nodes in the real-time phase perform the mixing to hide the association between sender and receiver while using their keys to decrypt the message, sending the result to the user’s intended recipient. This real-time process happens at a speed comparable to consumer messenger applications in wide use today.

Another approach to understanding cMix is to consider the level of adversary planned for by cMix’s designers, and compare this with other approaches to online privacy and security. One of the most popular other approaches is onion routing, as implemented by the TOR system. Onion routing is designed to thwart an adversary with access to one part of the system. Accordingly, onion routing networks wrap a message in several layers of encryption forming an “onion.” As a message passes through the system along a set path, each onion router unwraps one layer of encryption. To quote Paul Syverson, one of the authors of the original TOR paper, “Thus, onion routing networks are designed to resist a local adversary, one that can only see a subset of the network and the traffic on it.” [1] By contrast, mixnets like cMix are designed to thwart more powerful adversaries capable of observing all traffic on the system. Batches of cMix messages and transaction activity travel through the same fixed cascade of mixnodes, making traffic analysis of specific messages infeasible.

The paper that follows, first published in 2016, explains in detail each feature of the cMix system. It also describes the early progress iin developing cMix; the conceptual work, considerations about adversaries and how to defeat them, and the results of a proof-of-concept test. Today, Elixxir is moving forward with implementing cMix on a much larger scale. Elixxir has successfully deployed a small AlphaNet and is in the process of selecting nodes for a larger BetaNet. Following deployment of the BetaNet, Elixxir will implement a MainNet, bringing security and privacy to consumers with unprecedented speed and scale.