RFC: PLUME nullifiers in mina-signer + snarkyjs

[mitschabaude]

Motivation

Nullifiers are a tool needed by privacy zkApps to keep track of actions that should be only allowed once per user, without revealing anything about the user. Examples:

• ZCash uses nullifiers to ensure that a user can't spend a UTXO twice
• Private voting zkApps use nullifiers to ensure a user can't vote twice

In concrete terms, a nullifier is a large number derived from a user's private key + some application data, which

• is only recoverable by the user in question;
• is hiding, i.e., can not be used to learn the user's private or public key.

To perform some action, like spending a UTXO, users need to check the nullifier inside a SNARK (in a way that proves its link to a certain public key) and "emit" the nullifier and public key as public output / event. The application then checks that it never saw the same nullifier before. If this is the case, the user is allowed to perform the action. The application then stores the nullifier in a list among all the other nullifiers ever spent. This ensures that, would the user attempt to perform the action a second time, the application could reject it.

Problem statement: We don't currently support any nulilfier scheme where a user can derive their identity from their Mina wallet. This inhibits secure & practical implementations of anything using nullifiers, such as private voting, mixers etc.

Requirements for a nullifier implementation

• Includes SnarkyJS code to verify nullifiers inside a SNARK
• Does not require the user's private key as SNARK input
• A method to create equivalent nullifiers should also be built into mina-signer, so that wallets can support it and users can use their normal wallet to interact with zkApps that rely on nullifiers

Proposal

I propose that we implement Aayush Gupta's "PLUME" scheme in mina-signer + snarkyjs.

• Paper: https://eprint.iacr.org/2022/1255.pdf
  • The nullifier construction to be implemented is described on pages 19 and 20 of that paper
• Blog post: https://blog.aayushg.com/posts/nullifier
• Implementation can use available primitives. The only missing primitive is a hashToCurve function, which has to be added to the snarkyjs stdlib as part of this implementation.
  • Tracked as separate issue here: Implement hashing to curve #772

We add the following interfaces:

mina-signer

• createNullifier(message: Field[], privateKey: PrivateKey): JsonNullifier

SnarkyJS

Nullifier which is a Struct with the following properties:

• nullifier.publicKey which is used to check inclusion of the public key in a given set, e.g. Merkle tree
• nullifier.message which attests that the nullifier is associated with the given message. The message is defined by the application and allows for application-specific checks such as "this is a valid nullifier for voting round no 3 of my voting zkApp"
• nullifier.nullifier which is used as the key / Merkle leaf when we check that the nullifier isn't spent yet
• extra data which won't be accessed by the developer directly but is necessary to verify the nullifier, see below

Nullifier comes with at least two essential methods:

• Nullifier.fromJSON(n: JsonNullifier): Nullifier to read in the nullifier returned from mina-signer
• nullifier.verify(): boolean which checks inside the SNARK that the nullifier belongs to the user + message

Other architectures considered, tradeoffs

A popular nullifier scheme that can easily be built with SnarkyJS (and has been built already) is Semaphore, where nullifiers are derived from a private key which also has to be input to the SNARK. In practice, this means the private key can't sit in the user wallet, since these wallets don't (and shouldn't) expose any private keys to websites. Thus, when advocating for this scheme we would shift a huge burden to zkApp developers to build their own way of managing user private keys from the browser.

[bkase]

I agree with the premise; it would be best to implement some nullified scheme that doesn’t require the private key as a private input and moreover that we should be providing some first class nullified built-in to our tool stack so other people don’t need to figure these things out.

Your proposed nullifier scheme seems like it could work! My question is: Are there other alternatives to consider before choosing this one?

[mitschabaude]

Are there other alternatives to consider before choosing this one?

I'm not aware of others but also haven't looked for them!

[mimoo]

So, the only thing wrong with just doing something like this in a circuit is that you need to use the secret_key directly?

// prove that the secret key is linked to the public key
generator.scale(secret_key).assert_equal(public_key);
// create the nullifier
let nullifier = poseidon(domain_separation, secret_key, public_key);

(I'm guessing this is what zcash-scheme nullifier looks like, although I haven't looked at these things in a long time.)

If that's the only downside is it worth fixing it now? My argument was that these things are simple enough that it might not be super useful to expose in a stdlib, but if we think it is maybe this is enough?

On the other hand, looking at the paper, you'd need an enclave to implement a number of operations (including a poseidon hash function) and I'm guessing this is not going to happen until a long time. So one idea could be to just offer the simple way (what zcash/tornadocash/etc. are doing) and mention in the lib that for schemes that want to take advantage of enclaves then they could implement that paper. wdyt?

PS: I think exposing a hash_to_curve in the stdlib would be something useful!

[mitschabaude]

On the other hand, looking at the paper, you'd need an enclave to implement a number of operations (including a poseidon hash function) and I'm guessing this is not going to happen until a long time.

The "enclave" in the paper just refers to the software that has access to the private key. In our case, this is the wallet. Wallets rely on mina-signer which already has Poseidon, EC arithmetic etc built in (needs it for signing transactions)

[mitschabaude]

So, the only thing wrong with just doing something like this in a circuit is that you need to use the secret_key directly?

Yes!

If that's the only downside is it worth fixing it now? My argument was that these things are simple enough that it might not be super useful to expose in a stdlib, but if we think it is maybe this is enough?

I don't think this is enough, because an architecture that requires you to pass a private key into a smart contract (which is running on a website) is super awkward in practice and won't be adopted.

And I don't think the zk nullifier scheme is that hard to implement either -- it's basically just implementing that hashToCurve function plus stitching together a few already existing gadgets. But it's hard enough to be useful in the stdlib of snarkyjs. And super useful to include the nullifier generation method in mina-signer, because wallets won't create this on their own and they rely on mina-signer as the lib to implement the hard stuff for them.

[mimoo]

Wallets rely on mina-signer which already has Poseidon, EC arithmetic etc built in (needs it for signing transactions)

Oh I see, so the ledger already has support for that you're saying : o? I'm wondering if we can use this scheme as a way to perform signing then (which might be cheaper than schnorr?)

[mitschabaude]

Wallets rely on mina-signer which already has Poseidon, EC arithmetic etc built in (needs it for signing transactions)

Oh I see, so the ledger already has support for that you're saying : o? I'm wondering if we can use this scheme as a way to perform signing then (which might be cheaper than schnorr?)

Ah, no I was talking about browser wallets :D Like Auro wallet -- they will load mina-signer and they'll be able to create that nullifier when they have the user's private key.

However, you bring up an excellent point that I didn't consider -- this won't support private keys which sit on a Ledger or similar. I think that's OK for now; users would need to create a hot wallet for interactions where nullifiers are needed, which presents a security trade-off but already enables lots of useful applications where security requirements are not THAT high

[Trivo25]

However, you bring up an excellent point that I didn't consider -- this won't support private keys which sit on a Ledger or similar. I think that's OK for now; users would need to create a hot wallet for interactions where nullifiers are needed, which presents a security trade-off but already enables lots of useful applications where security requirements are not THAT high

I would actually argue that hardware wallets are the easier use case here, since they could simply delegate their rights to an auxiliary key (then it could also be input to the SNARK), so I wouldn't worry too much about hardware wallets at this stage

[nicc]

Indirectly Irresponsible Individual: @Trivo25

[jasongitmail]

+1 on creating this too. Looks great. And +1 for making this part of SnarkyJS because, even if it's easy to implement, it's a fundamental piece to have and we can remove the need for people to think about it--to do research on properties it should have, etc. SnarkyJS aims to make things easy.

Sent a few small comments earlier via DM.

[mitschabaude]

From the paper, my original impression was that the wallet needs to store the "secure randomness r" (see page 19) alongside the user's private key.

However, reading it again I understand that this value can actually be ephemeral. It is not used to produce the nullifier (which we potentially should be able to reproduce), but only the additional public output s which acts as a one-time hint for verifying correctness of the nullifier. Therefore, the value r can just be created from secure randomness in mina-signer during the createNullifier method, used to create the output, and not stored anywhere.

This resolves a remaining question we had @jasongitmail @bkase

[iam-dev]

Some research I have done on this:
I understand the RFC, by reading it for a day without sleep.
In this Circom test, they verify the witnes with only public key and commitment/ without any secrets

test("a/b^c subcircuit", async () = {
const p = join(__dirname, ’a_div_b_pow_c_test.circom’)
const circuit = await wasm_tester(p)

// Verify that gPowS/pkPowC = gPowR outside the circuit, as a sanity check
const gPowS = Point.fromPrivateKey(s);
const pkPowC = testPublicKeyPoint.multiply(hexToBigInt(c))
expect(gPowS.add(pkPowC.negate()).equals(gPowR)).toBe(true);

// Verify that circuit calculates g^s / pk^c = g^r
const w = await circuit.calculateWitness({
a: pointToCircuitValue(gPowS),
b: pointToCircuitValue(testPublicKeyPoint),
c: scalarToCircuitValue(hexToBigInt(c)),
})
await circuit.checkConstraints(w)
await circuit.assertOut(w, {out: pointToCircuitValue(gPowR)});
});

https://github.com/zk-nullifier-sig/zk-nullifier-sig/blob/6052e45b8f7571b79247fb58eaef80d305dbcc82/circuits/test/vfy_nullifier.test.ts#L130

Which make it non-interactive, you only needs public key and the commitment which can be stored in Merkle Tree
But this Nullifier Scheme is a project it self

References:

• https://docs.google.com/presentation/d/1mKtOI4XgKrWBEPpKFAYkRjxZsBomwhy6Cc2Ia87hAnY/edit#slide=id.g13e97fbcd2c_0_86
• https://blog.aayushg.com/posts/nullifier
• https://github.com/zk-nullifier-sig/zk-nullifier-sig
• https://ethbogota-2022.netlify.app/
• https://github.com/piotr-roslaniec/ethbogota-2022

[Divide-By-0]

However, you bring up an excellent point that I didn't consider -- this won't support private keys which sit on a Ledger or similar. I think that's OK for now; users would need to create a hot wallet for interactions where nullifiers are needed, which presents a security trade-off but already enables lots of useful applications where security requirements are not THAT high

This scheme is specifically designed such that the nullifier signature and corresponding signals can be generated in 40kB of memory on a Ledger, and we are actively searching for devs down to take on this problem and make a PR to their wallet code!

From the paper, my original impression was that the wallet needs to store the "secure randomness r" (see page 19) alongside the user's private key. However, reading it again I understand that this value can actually be ephemeral.

Correct, it can be ephemeral! That is a great clarification, I can update the paper. (Edit: Done, should be live soon!)

On the other hand, looking at the paper, you'd need an enclave to implement a number of operations (including a poseidon hash function) and I'm guessing this is not going to happen until a long time.
The "enclave" in the paper just refers to the software that has access to the private key. In our case, this is the wallet. Wallets rely on mina-signer which already has Poseidon, EC arithmetic etc built in (needs it for signing transactions)

Sorry, my wording in the paper was a bit sloppy and should be fixed. Correct, "enclave" refers to any wallet. In terms of an actual secure hardware enclave, the scheme is designed such that the secure hardware enclave with the secret key only needs to compute exponents of the secret key (which is already an API usually), and the non-enclave chip (that's still part of the wallet) can compute all of the hash functions. In software wallets there is usually no distinction between the chip and the enclave, and I refer to both as the "enclave" in the paper. I've clarified and fixed this in the updated paper on my site.

an architecture that requires you to pass a private key into a smart contract (which is running on a website) is super awkward in practice and won't be adopted.

Yes, with this scheme, the secret key does not leave a users wallet.

Another note is that we are calling the scheme PLUME (pseudonymously linked unique message entities) to avoid confusion with guarantees on "nullifying" double-spending, as the scheme is for much more generic identities! I have also updated the blog post today to make it a bit easier to read.

[mitschabaude]

Thanks @Divide-By-0 for the feedback! I'll close this as we got broad alignment on the RFC. Next step is to implement it :D