Railway semaphore signals. Source: WikiMedia Commons

This year, Ethereum has undergone a privacy renaissance of sorts. Encouraged by prominent members of the community, researchers, programmers, and DAO funders have collaborated to accelerate the ideation and implementation of privacy solutions, particularly those which employ zero-knowledge proofs. We are now at a stage where a key privacy building block is emerging from research and entering production: Semaphore, a means for anonymous signalling.

Semaphore is the basis of an ETH and ERC20 token mixer named MicroMix. In the near future, it can be used for other privacy-enhancing applications such as anonymous login, anonymous DAOs, anonymous voting, and journalism.

This technical blog post will explain how Semaphore and MicroMix work, and how Semaphore enables MicroMix to provide users with transaction privacy in a noncustodial manner. It will also describe its performance and tradeoffs, and finally outline how Semaphore can enable other zero-knowledge applications which would be otherwise impractical.

Readers should understand how Ethereum smart contracts work and some basic cryptography, but do not need to be familiar with zero-knowledge proofs.

About Semaphore

Originally devised by Barry WhiteHat, Harry Roberts, and Kobi Gurkan, Semaphore is a system which allows any Ethereum user to signal their endorsement of an arbitrary string, revealing only that they have been previously approved to do so, and not their specific identity. To be precise, it lets a user:

1. Register their identity in a smart contract, and then:
2. Broadcast a signal — that is:
   (i) anonymously prove that their identity is in the set of registered identities, and at the same time:
   (ii) Publicly store an arbitrary string in the contract, if and only if that string is unique to the user and the contract’s current external nullifier (more on this below). This means that double-signalling the same message under the same external nullifier is not possible.

Semaphore consists of a smart contract and zero-knowledge proof components which work in tandem. The smart contract handles state, permissions, and proof verification on-chain. The zero-knowledge components work off-chain to allow the user to generate proofs, which allow the smart contract to update its state if these proofs are valid.

How Semaphore works

When a user registers their identity, they simply send a hash of an EdDSA public key and two random secrets to the contract, which stores it in a Merkle tree. This hash is called an identity commitment, and the random secrets are the identity nullifier and identity trapdoor.

Broadcasting a signal is a little more complex. There are two parts to it: (a) anonymously proving membership of the set of registered users, and (b) preventing double-signalling via an external nullifier.

Anonymously proving membership

Zero-knowledge proofs allow a user to demonstrate that they have performed a predefined set of operations on some data, without revealing parts or all of said data.

Semaphore uses a form of zero-knowledge proofs known as zk-SNARKs. While the way that zk-SNARKs work is beyond the scope of this post, readers can refer to other materials, such as Christian Lundkvist’s introduction for more information.

In Semaphore, the user creates a proof of the following:

Preventing double-signalling

Take for example three users: Alice, Bob, and Charlie. They first register their identity in the contract, which has an external nullifier 123, and then broadcast their signals. Since this is the first time they have broadcasted a signal, the contract accepts their transactions:

 

Some time later, Charlie tries to send the same signal, but the contract rejects it because the signal is no longer unique to the external nullifier 123:

If, however, the external nullifier were changed to 456, Charlie can now send that signal again:

These properties — anonymous membership proofs and double-signalling prevention — make Semaphore suitable for its first use case, an on-chain mixer.

About MicroMix

A mixer helps Ethereum users gain privacy as its blockchain is otherwise public and transparent. A mixer is like a Secret Santa gift swap: collect gifts of equivalent value from a group of people, and then redistribute them. The difference is that in a mixer, the recipients should have no way of telling who bought the gift in the first place.

Many mixers, like Ether Mixer, are custodial and centralised. Unfortunately, this means that users have to trust them to not abscond with their funds, or store logs which would deanonymise deposits.

Noncustodial and decentralised mixers, on the other hand, do not have these drawbacks. They accept fund deposits and execute withdrawals with three key guarantees:

1. Nobody can steal deposits.
2. Nobody can link deposit and withdrawal addresses.
3. Nobody can censor or shut them down.

MicroMix uses a Solidity contract (henceforth referred to as the Mixer contract), which employs an instance of Semaphore to enforce these guarantees. MicroMix registers an identity into its Semaphore contract when a user deposits funds, and broadcasts a tailored signal when they withdraw funds. Since Semaphore double-signalling, it in turn prevents double-spends in MicroMix.

In addition, MicroMix handles ETH and token transfers, and transfers a fee to a specified address. This fee mechanism makes it possible to incentivise a third party to relay a transaction to withdraw funds on the user’s behalf. This means that the recipient does not need to already own ETH, and the depositor does not need to find a way to send them the small amount of ETH required for a transaction, which would defeat the purpose of the mixer.

MicroMix in action

MicroMix is currently deployed as a prototype on the Kovan testnet and features a simple user interface at https://micromix.app. The user interface encourages users to wait till past midnight UTC, before performing a withdrawal, so as to increase their anonymity set. It does not tell the user the size of the anonymity set as this figure is potentially misleading; an attacker could fill up the deposit pool with their own transactions, create the impression of a large anonymity set, and deanonymise unsuspecting users.

MicroMix supports both ETH and ERC20 token mixing. The contracts and user interface at https://micromix.app supports Kovan DAI which users can obtain by creating a MakerDAO CDP on the Kovan network at https://cdp.makerdao.com.

How MicroMix works

The following table lists the steps which the Mixer and Semaphore contracts take when a user deposits ETH:

An example of a deposit:

Transaction hash: 0x48a382d431185bc82890dd2f1153d66c1b070ed89cccc25fb586afb095567e51
Identity nullifier: 8031d226cb7115017239bad18ecd4564df45f9de1eaf8e593bdc7fd27d10f
Identity trapdoor: e89e6ecdf7d117ae23fd1b046e3a40123f80e4ae75d5f06a86a1c0b5b5797b
Identity commitment: 0xb79092fd0e907d744bc49ef63c2632f90e5c105a232b43647e168fa6faa27f4ac83c00d9

As seen above, the Mixer contract is responsible for managing funds, and the Semaphore contract is only responsible for identity registration. This separation of concerns is also apparent in the following table, which describes what happens when a user withdraws funds:

An example of a withdrawal:

Transaction hash: 0x43e2ca81b7dd4d23fcc8a2191b09ef0a2e7469f23051a8f79052d75b02f8d502
Signal: 0x5b062792493047ca4a1221d185ba7bc1fc57062126cc325aa24893357b53aa1a
zk-SNARK proof data:“a”:[“1077…”,”5651…"], “b”:[[“7028…”,”1337…"],[“1583…”,”1665…"]], “c”:[“1732…”,”7771…"]
Root: 10809627771503708857700183002420472828948270490531531173285172676430182712980
Nullifier hash: 9546065020171513013039253193555976067181611145828641232207963883960520778776
Signal hash: 266960622224311701018629012248271412276308136479127641500588150958540834508
External nullifier:1182878175203544938066023463435688736234343990113
Recipient’s address: 0x6158E689cae143532864A9502374AB4eE1690681
Fee: 1000000000000000 wei

Other applications of Semaphore

Like the Mixer, other zero-knowledge use cases can use Semaphore as a base layer. This is because of the principle of separation of concerns. For instance, Semaphore is agnostic to the contents of the signal which the Mixer contract passes to it. The mixer contract just handles fund transfers, and delegates the responsibility of zero-knowledge signalling and double-spending protection to Semaphore.

Use case: Mixer
External nullifier: Mixer’s contract address
Signal: The hash of the recipient’s address, relayer’s address, and fee.
Outcomes: Only depositors can withdraw funds, double-spends are impossible.

Likewise, other applications which build atop Semaphore would follow the same principle. Specifically, they would set Semaphore’s external nullifier and signal in a different fashion in order to achieve different outcomes.

For instance, Semaphore could be used by a service provider to offer anonymous logins to privacy-oriented customers, such that when a customer logs in, the provider can only know that they are a registered customer, but not which customer they are.

Use case: Anonymous login
External nullifier: The hash of the service provider’s URL.
Signal: The hash of a login token (like PASETO) and the service provider’s public key.
Outcomes: Only registered users can login, and the logged-in users can henceforth use the login token to authenticate themselves.

In this hypothetical construction, we assume that users have already registered their EdDSA public keys with the service provider, and that the service is stateless. When the user anonymously broadcasts the hash of a login token, the service provider can save it in their database and allow authentication requests (such as API calls) which contain login tokens which, when hashed, match the signal..

Gas use

A deposit transaction costs about 1.1 million gas, and a withdraw costs about 770000 gas. The high deposit cost is mainly due to the fact that all identity commitments are stored on-chain, and that the Merkle tree depth chosen is 20. As the Ethereum mainnet currently has a block gas limit of 8 million gas, and assuming an average block time of 15 seconds, it will take a minimum of 1 month to fill up Semaphore with deposits, assuming that each block contains the maximum number of deposit transactions.

Interested readers may view the spreadsheet used to calculate this here. More work has to be done to calculate the gas costs for various tree heights.

Future plans for Semaphore and MicroMix

The Semaphore team seeks to collaborate with other zk-SNARK-based mixers and Ethereum wallet providers to converge on common contracts, circuits, and standards, so as to provide the best possible anonymity for users as a public good. It will also continue to develop other useful zero-knowledge applications on Ethereum, and support the community with deployment and adoption.

Interested readers should feel free to join the Semaphore Society Telegram channel to participate in discussions and receive updates, and readers who would like specific updates about MicroMix should join the MicroMix General Discussion channel.