The Many Saints of Privacy: Nullifiers in o1js

We like privacy

That’s a bold statement, isn’t it? (no pun intended) But it’s true! zkApps are paving the way for the future of programmable cryptography and user-owned privacy. However, zkApps alone are just the foundation - a powerful one, but only a starting point. To unlock their full potential, we need to enhance them with the right building blocks, enabling developers to create robust, privacy-preserving applications.

So, why does this matter? Privacy-preserving primitives are like the clockwork of a beautiful watch. Just like gears, these primitives are hidden beneath the surface but are essential for the system to function. Each primitive has a specific, interconnected role that keeps the entire watch running smoothly. Without these gears, the watch - our zkApp! - either stops working entirely or loses its precision and reliability (or, in our case, privacy). Transactions on Mina aren't private by default, but zkApps and o1js provide all the tools you need to build powerful, privacy-preserving applications.

Nullifiers: The First Gear in the Privacy Machine

Nullifiers are the gatekeepers of privacy - quite literally! Imagine attending an exclusive crypto event. At the entrance, the bouncer checks a secret passphrase you provided earlier. The key here is that the bouncer doesn’t need to know who you are, only that the passphrase hasn’t been used by anyone else. Once inside, you seamlessly blend into the anonymous crowd, but there’s no sneaking back in later with the same passphrase.

This is essentially how a nullifier works! It’s the gatekeeper of your zkApp - a unique, anonymous, one-time entry pass that lets you participate in the system (whether it’s spending a token, redeeming an airdrop, or casting a vote) while keeping your identity private. And just like at the party, it ensures no one, not even you, can use the same passphrase twice.

What Makes a Nullifier Tick?

Nullifiers are used as a public commitment to a specific anonymous account, to forbid actions like double spending, or allow a consistent identity between anonymous actions. In order to achieve this behaviour, we use the power of cryptography! In the case of o1js, we closely followed the paper PLUME: An ECDSA Nullifier Scheme for Unique Pseudonymity within Zero Knowledge Proofs by Aayush Gupta and Kobi Gurkan (thanks you two, great work!). PLUME defines a Nullifer scheme that works nicely within zkSNARKs and o1js. There’s a few properties that a Nullifier should have:

Determinism: This means that an algorithm, when given the same inputs, always produces the same outputs. It’s important to develop a deterministic Nullifier in order to prove the correctness of it. If a Nullifier produces a different output, it would be impossible to prove that a Nullifier truly is valid and belongs to a certain action.

Example: Think of the crypto event. Imagine that every guest at the exclusive crypto event is handed a unique, stamped token at the entrance, proving they’re allowed inside. The stamp on the token is based on their secret passphrase. Now, if the stamp changes each time the same passphrase is checked, the bouncer wouldn’t be able to confirm if a guest is legitimate or if they’re trying to sneak in with a fake token. The system would fall apart!

Uniqueness: When a user generates a Nullifier that belongs to a specific topic (e.g. a specific smart contract or use case), it is important that the same Nullifiers cannot be used for two different topics. This means, the user will always generate a unique Nullifier for each unique message - which cannot be reused for a different message or topic. If considered from a different perspective, we want to avoid replay attacks: A user should never be able to use the same Nullifier for more than one interaction.

Example: It's like issuing the same ticket to two different users—once the first enters the crypto event, the second is denied entry.

Non-Interactive: The protocol should be non-interactive. This means that the user will generate a Nullifier and send it off to the verifier, without the need to require a back and forth communication between the two parties.

Example: At the crypto event, imagine if, every time a guest tried to enter, the bouncer had to call someone to verify the guest’s identity. It would create a chaotic bottleneck, slowing down the entire process. Instead, the system is designed so that your stamped token works as a standalone proof - you show it once, and the bouncer lets you in, no questions asked.

Last but not least, Verifiability and Privacy: The verifier must be able to confirm the validity of the nullifier without accessing any of the user’s private data—no private key, no sensitive information. Instead, the nullifier is verified using a zkSNARK proof, all within the user’s browser. This makes it a nullifier instead of just a list of identifiable participants.

Example: Think of the crypto event again. If the bouncer had to check every guest’s ID before letting them in, it would defeat the purpose of keeping identities private. The system works because the bouncer can verify the passphrase without knowing who you are. Similarly, a nullifier ensures that actions are legitimate while preserving the user’s privacy.

One Vote, One Claim: How Nullifiers Power Airdrops and Voting

So, we already established that Nullifiers are pretty cool little primitives, but what can we actually build with them? Theory is nice, but what matters are real-world applications and use cases!

We already hinted at some of the use cases and problems Nullifiers solve in the previous sections, but let’s look at a few examples in more detail.

Voting with Nullifiers: One Vote, One Privacy-Preserved Choice

Imagine you're casting your vote in an online election. Whether it's for a school project or a decision in a decentralized governance system like a blockchain, the goal is simple: you want to express your opinion privately, and everyone should only be able to vote once - otherwise, it wouldn't be fair, would it?

This is where nullifiers come in. By generating a one-time, unique nullifier for each election, we can ensure that each voter casts their vote once while remaining anonymous throughout the process, without revealing their preferences or identity. The nullifier acts as your "vote token" - a cryptographic blob that proves you're eligible to vote without leaking any private data. Once voted, the nullifier ensures you can't vote again, preserving the integrity of the election and preventing any attempt to influence the outcome.

Airdrop Redemption: Claim Your Rewards, Privately

Airdrops are popular in the web3 space! They’re a way to reward early supporters and adopters of a project. However, airdrops can be tricky to get right. You want to reward everyone fairly, ensure each user can only redeem their drop once, and protect their privacy. So, how do you do that? Well, who would have thought... Nullifiers!

Note that with an airdrop and public transactions on the Mina network, achieving full privacy requires additional considerations. This example assumes an ideal scenario.

When an airdrop is launched, a set of eligible users is defined by the application. Each user then generates a nullifier, a one-time key that proves they are eligible to redeem their token - without revealing any private information. Just like a raffle ticket, each airdrop claim is verified and tracked through the nullifier, preventing double claims and protecting privacy. This ensures the process remains fair, preventing anyone from claiming multiple airdrops, all while safeguarding the participant’s anonymity.

Nullifiers, Line by Line

Now that we understand some of the use cases for nullifiers, let’s take a closer look at how we can actually use them in o1js!

First, a zkApp developer needs to specify something called the nullifier message (sometimes referred to as a topic). This piece of data is essential for uniquely identifying the nullifier’s purpose. It could be anything: a random piece of data, the address of the zkApp account, or something arbitrary. The key is that it helps differentiate nullifiers and ties them to specific applications. Think of our two examples above - we definitely wouldn’t want an airdrop nullifier to be reused in a completely unrelated voting application! That would defeat the whole purpose of having a unique nullifier and compromise the integrity of the system.

Secondly, we need a place to store our nullifiers! On Mina and in zkApps, this is typically done using a Merkle Map, which is a hash-map built on a Merkle Tree. Merkle Trees are ideal for this purpose because they allow us to securely store all previously redeemed nullifiers without leaking any private information. This ensures the system can efficiently check for duplicates while preserving user privacy.

With these fundamental components in place, users can generate their nullifier. This entails providing some private input, including the nullifier message (aka topic), and using the relevant Merkle Tree sibling hashes to compute the Merkle Witness that proves their inclusion.

After that, we can verify the nullifier to ensure it hasn’t been used before. Once verified, we update our storage to include the new nullifier, ensuring the system remains secure and no duplicate actions can occur.

Once all of this is done, we can finally invoke our action! Whether it’s casting a vote, redeeming an airdrop, or initiating a fund transfer, the nullifier ensures everything is secure and private.

For a more in-depth walkthrough, be sure to check out the o1js example repository!

How Nullifiers Do Their Thing (Math Edition)

Please note that some of the cryptographic concepts and mathematical details are excerpted from the paper PLUME: An ECDSA Nullifier Scheme for Unique Pseudonymity within Zero Knowledge Proofs by Aayush Gupta and Kobi Gurkan.

In o1js, two key actors are involved in constructing and verifying a nullifier:

The Secure Enclave: This refers to your private key, which is stored in a hardware wallet or a browser wallet. It's crucial that no application has direct access to your private key - ever! Instead, we interact with the secure enclave (the wallet) and request it to sign specific messages on our behalf.

The Zero-Knowledge Proof (zkApp): This is the application running in the user's browser, designed to preserve the user's privacy. It handles the application logic and eventually gets verified on the Mina blockchain to trigger network effects. To ensure the security of the user's information and private key, the private key never leaves the wallet and never interacts directly with the browser or the application. The secure enclave ensures that the key remains protected.

Please note that, to implement an efficient nullifier scheme in o1js and Mina, we use Schnorr signatures and the Poseidon hash function over the Pasta curves, rather than ECDSA over secp256k1 and SHA256 as proposed in the original paper.

The Algorithm:

The secure enclave - your wallet - computes the following two values:

In o1js, the hash function used is a map-to-curve Poseidon hash function over the Pasta curves.

Here’s what the variables represent:

• sk: Your secret key (private key).
• m: The nullifier message, which defines the nullifier's purpose.
• pk: Your public key, derived from your private key (your Mina address).
• r: A random scalar, also known as an ephemeral key.
• c: This value is also computed by the secure enclave but is kept strictly private. It will be derived in the next step.

The computed values, nullifier and s, become public inputs in your zkSNARK proof. These inputs are used to verify the validity of the nullifier without compromising the user's private data.

To manage the distinction between public and private values of the nullifier, we use a specific Nullifier type defined within o1js:

Secondly, the secure enclave computes additional values that serve as private inputs to the zkSNARK proof. These values are critical to the proof's integrity and must never be made publicly available:

Please note that g^sk and g^r represent elliptic curve scalar multiplication, where g is a generator of the Pallas curve.

Hash Functions Explained

• hash2: Refers to the standard Poseidon hash function, used for hashing field elements.
• hash: Represents a hash-to-group function, which hashes a list of field elements to a point on the Pallas curve.

These private inputs ensure that the proof remains valid while preserving user privacy. By separating public and private components, we maintain the security and correctness of the nullifier scheme.

The Final Verification

Finally, the zkApp verifies the nullifier by checking the following computation:

This step ensures that all computed values are consistent and the nullifier is valid.

Eligibility Check

In addition to verifying the nullifier, the zkApp also checks that the public key (pk) belongs to the set of eligible users:

This guarantees that only authorized participants can perform the action, further securing the application.

Ready to Build? Let’s Get Started!

Nullifiers are just one piece of the privacy puzzle, but they’re a powerful one. From enabling anonymous voting to secure airdrops, they demonstrate how zkApps can empower users while keeping their data private.

If you’re ready to dive in, head over to the o1js GitHub repository and explore the example implementations where Nullifiers are used in conjunction with Merkle Trees or Merkle Maps. Start experimenting with nullifiers, and discover how you can integrate them into your zkApps to unlock privacy-preserving features.

Got questions or want to share your creations? Join our community and connect with developers who are shaping the future of zkApps. Let’s build something extraordinary together!