Brief history of anonymity in crypto

Cryptographic protocols providing anonymity contain zero-knowledge proofs of (some of) the following claims:

• Membership. I am a member of the given set.
• One-shot. I have not made a claim before in this context.
• Message. And I want to state this.

Pre-history: signatures

Anonymous transactions started with David Chaum's eCash (1982) which introduces blind signatures and uses central services to achieve this goal. It uses numbers in a central database to track spend coins, the ancestor of nullifiers. In ST99 this was improved to add a public Merkle tree commitment to spend coins, now called 'serial numbers'. The blind signatures developed into ring signatures (2001) which provide the membership claim but not the one-shot claim. CryptoNote (2014) introduces what became known as 'stealth addresses' which anonymise public keys. Monero (2014) combined these techniques to create a decentralized anonymous currency. Ring signatures scale linearly so in practice the anonymity sets are much smaller than the full set of users. Further work like BDHKS19 improved on ring signatures. See my notes on signature schemes for details.

Zero-knowledge proofs

Ian Miers et al's Zerocoin (2013) introduces the construction with a zero-knowledge proof of membership and one-shot claims. It's basically the construction in it's modern form, but using RSA accumulators for the set of spend 'serial numbers'. The follow up work on Zerocash (2014) uses zk-SNARKs and changes the set commitment to a Merkle proof. Zerocash also develops the protocol in many ways. but that has little to do with anonymity and deals mostly with keeping transaction amounts private. The Zerocash protocol is the basis for ZCash (2016) which introduces the term 'nullifier'. Further developments such as Zexe (2018) extend the transaction semantics further, but retain the same design of the anonymity construction.

Anonymity on Ethereum started with the inclusion of affordable zero-knowledge proof support in Byzantium (2017) (i.e. EIP-196 and EIP-197). This was motivated in part by ZCash's success and a desire to support similar constructions. Aztec protocol (2018) implemented the first Ethereum private transactions. It has an unprecendent protocol for transaction privacy but uses stealth addresses for anonyimity. Tornado Cash (2019) only implements the anonymity part of the ZCash protocol and skips the transaction privacy, greatly simplifying the protocol. Tornado Cash has only two kinds of transactions, deposit and withdrawal, both with the same fixed size.

Note that Monero, ZCash, Aztec and TornadoCash have all since made major changes to their designs. What is described here is the initial version to the extend I could find out.

Semaphore (2019) takes the anonymity part from Tornado Cash and offers it as a standalone protocol. It introduces the context part of the one-shot claim to make it a reusable system and it introduces the message that allows for applications such as voting.

In retrospect, the hard part was never anonymity but most effort went into transaction privacy. It would seem obvious to unbundle the easy part from the hard part and make anonymity a standalone primitive. So why did it take so long? My guess is the UTXO design of early blockchains made it hard to think of the two as separate.

Thanks Ian Miers for answering some questions.