HackMDMull Over The Nullifier
Thanks to Kobi Gurkan and Wanseob Lim for the reviews and the feedback
We're not talking about "An item purchasable at the Main Shop, under Magical."
When I first looked into the zero-knowledge proof applications, the term nullifier confused me a lot. Many projects use nullifiers and define them differently depending on the context. In this post, we review those projects and extract the abstract idea that works for all.
A Single-Use Gadget
Nullifier is a piece of data that ensures a message only takes effect once. When we see the term nullifier, we can first restrict our attention to this primary function and take care of other details later.
Why taking effect once matters? Consider the following applications:
- Application A: A sender can send a message that instructs the system to move $10 from the sender's balance to a receiver, with the information of the sender, receiver, and value hidden from the public.
- Application B: An user deposited $10 in the system some time ago. They can hire a relayer to send a message to withdraw the $10. The depositor can't be inferred from the message.
- Application C: A voter can send a message to cast a vote to support a candidate without revealing the voter's name.
These applications have something in common:
- A message carries some economic value or causes some important things to happen.
- A message hides information, but itself is broadcasted publicly.
One can easily rebroadcast these messages to the system. Here's what would happen if we don't have a protection mechanism, and the same message takes effect twice or more.
- Application A: The sender now sends another $10 to the receiver again. The receiver can drain all sender's money by resending the message again and again.
- Application B: The user who deposited only $10 now withdraw another $10 from the system. The system can not maintain the balance and will go bankrupt.
- Application C: The voter now cast two votes for the candidate. The tally becomes meaningless because anyone can throw as many votes they like.
How can a nullifier come to help? Let's reveal the true identity of each application I choose arbitrarily.
Note that people sometimes refer "nullifier" to secret data and "nullifier hash" to the secret's hash. Sometimes people refer "nullifier" to the hash of the secret and name the secret differently. In the former case, the nullifier is private information, while it is public in the latter case.
Application A
Zcash (Sprout)
Input
Transparent 46252.81429411 ZEC
+ Shielded ? ZEC
▶JoinSplit▶
Output
Transparent 0 ZEC
+ Shielded ? ZEC
An example of shielded payment
Zcash allows a user to send a shielded payment, which hides receiver and amount information.
Nullifier = HASH(spending key, rho)
To send a shielded payment, the sender publishes an encrypted note along with its Nullifier. A note is the information of the receiver and amount. The full node tracks all the Nullifiers revealed so that a double spend can be detected.
The Nullifier is a hash of the sender's spending key and a variable rho. In the older version Sprout, rho is just a unique identifier of the note. In contrast, in the newer version, Sapling, rho is the hash of the unique identifier and the note.
Zkopru
Nullifier = HASH(nullifier_seed, utxo_leaf_index)
Zkopru also allows users to send shielded payments, but on layer 2.
Zkopru keeps the Nullifiers in a giant 254-depth Sparse Merkle Tree. A Nullifier is a hash of a secret nullifier_seed and the UTXO leaf index in the UTXO tree.
The user sends a transaction and attaches a Nullifier with it. The coordinator runs the circuit off chain and tries to update each Nullifier leaf. A successful update should change the tree root. Otherwise, if the tree root remains the same after an update, it means the Nullifier is already in the tree, and thus the transaction is a double spend.
Application B
Tornado Cash
nullifierHash = HASH(nullifier)
When attempting to withdraw money from the Tornado Cash, the user provides a zk proof of the withdraw circuit validating the public nullifierHash is the hash of the private nullifier. The Tornado contract checks the nullifierHash hasn't been set before, then marks it sent on a successful withdraw.
contract Tornado {
mapping(bytes32 => bool) public nullifierHashes;
function withdraw(... bytes32 _nullifierHash, ...) {
// ...
require(!nullifierHashes[_nullifierHash], "The note has been already spent");
// ...
nullifierHashes[_nullifierHash] = true;
// ...
}
}
Application C
OneOfUs
The voting example came from the OneOfUs (Github repo), which lets a POAP token owner register and vote on questions. Voting is anonymous, and a user can only vote once per question so that no double vote is allowed.
OneOfUs is built upon a more general private signaling framework called Semaphore. Let's talk about Semaphore first, then OneOfUs is easier to understand.
Semaphore
// Semaphore
nullifiers_hash = HASH(identity_nullifier, external_nullifier, identity_path_index)
Like Tornado Cash, arguably a specialized and simplified version of Semaphore, Semaphore contract also has a mapping nullifierHashHistory that tracks nullifier hash that has been published before.
What makes Semaphore so special is that it has an External Nullifier, a piece of public data that acts as a topic. The application designer can exploit the external nullifier to limit a user's action to a particular topic only once, or even rate limit the user action three times, or once every 5 minutes.
// OneOfUs
external_nullifier = HASH("Is the typhon going to hit Osaka?")
In the OneOfUs example, the external nullifier is just the hash of the question. Once the user answers the question 1 publishes the nullifier hash, they can't answer the question 1 again because that would publish a duplicated nullifier hash. But the user can still answer another question, say question 2 since the nullifier hash will be different and the Semaphore contract hasn't seen it before.
Commitment
We've focused on how nullifiers gurantee the signle use of the messages. The next natural question to ask is who is authorized to send that single valid nullifier in the first place?
The nullifier usually comes with its counterpart, the commitment. Some project's document calls the combination a "commitment-nullifier scheme," which is a pattern that powers many Zero-knowledge proof applications.
A commitment is a published hash of secrets, and it determines who is allowed to create a valid nullifier. As a result, the commitment hash and the nullifier hash share a common data field in their preimage so that the zk prover can cross-validate that data field for validity. Examples are:
- Zcash (Sprout): The preimage of the Nullifier shares a note id
rhowith the commitment. - Zkopru: The UTXO is the commitment. The Nullifier has nullifier_seed and utxo_leaf_index. The former is derived from the sender's secret to make sure only the sender can create the nullifier. The latter makes sure the UTXO is only spent once.
- Tornado Cash: A user deposits money and commits the secret named "nullifier." The zk proof convinces the system the user has deposited before by validating the commitment hash and nullifier hash.
- Semaphore: Require a user to be registered to the system and commit a secret data named "identity nullifier." So only a registered user can create a valid nullifier hash.
Conclusion
We reviewed how several projects use nullifier hash to gurantee the single use of the message. We also explored the relationship between the nullifier and the commitment. We hope the post makes nullifier less a dangerous weapon and contributes to health regeneration for the dear readers.
