Is my understanding correct that given any Merkle map root and a Nullifier we can verify if it is set in that tree? And also generate a root that would have this Nullifier set and preserve the state and every other nullifier? If yes, can you point me to some references how is it possible? If not, then how to use nullifiers? Should there be a boolean Merkle map stored off-chain? Thanks!
#Nullifier and Merkle maps
runic socket
steel wave
@runic osprey can tell you more about how he used nullifiers with Protokit 🙂
rugged furnace
Here is an example how nullifier is used : https://github.com/o1-labs/o1js/blob/main/src/examples/nullifier.ts. I’m not quite sure what you are asking.. Nullifier is used to prevent double spending ( or double voting).
runic socket
I saw the example, but in the example the Merkle map access is assumed.
What if there was already multiple nullifiers set in the tree pinned on-chain How'd you create the witness then?
In other words:
let nullifierWitness = Provable.witness(MerkleMapWitness, () =>
NullifierTree.getWitness(nullifier.key())
);
This piece of code works with a tree that was captured in a closure, right? It's just an empty tree. It will not generate valid witnesses for non-initial states of the contracts. Or there's some zk magic going on that I don't understand 🤔
rugged furnace
Let me try to explain and break it down for you.
In this PayoutOnlyOnce, SmartContract, there are 2 onchain states.
- nullifierRoot
This is like a summary or a unique fingerprint of a big list (called a Merkle Tree) that keeps track of all the payment IDs (called Nullifiers) that have ever been used for payments. Think of it as a way to quickly check if a particular payment ID has been used without looking through the entire list. - nullifierMessage
This is a special message stored on the blockchain that's used to make sure the payment requests are legitimate. It's like a secret code that's needed to validate payment IDs.
This part of the code you are setting up initial onchain states:
https://github.com/o1-labs/o1js/blob/f60ef63f2a6cc1d6c20667d779f0002f33e6199b/src/examples/nullifier.ts#L80
Which are the root of the MerkleMap and the message (Field(5))
This part Generating a Nullifier:https://github.com/o1-labs/o1js/blob/f60ef63f2a6cc1d6c20667d779f0002f33e6199b/src/examples/nullifier.ts#L90
The code you're looking at is creating a special kind of payment ID (Nullifier) based on someone's private key. A private key is like a super-secure password that only one person should know. This process ensures that each payment ID can only be linked to the person who owns that private key, adding an extra layer of security.
When it says let jsonNullifier = Nullifier.createTestNullifier([nullifierMessage], privilegedKey);, it's like saying, "Let's make a test payment ID using our secret code (nullifierMessage) and a specific person's super-secure password (privilegedKey)."
Payout Conditions:
The smart contract is set up so that you can only call the payout function once for each unique payment ID. It checks the big list (Merkle Map) to see if your payment ID has been used before. If it hasn't, and if it's verified that it was generated by your private key, then the payout goes through.
Essentially, this setup prevents someone from claiming the payout multiple times with the same payment ID, ensuring fairness and security in the payout process.
AccountUpdate.fundNewAccount(sender);
zkapp.payout(Nullifier.fromJSON(jsonNullifier));
});``` This is the real transaction of the owner of the privatekey with his Nullifier. The user is sending his Nullifier and this Nullifier it's provable because it's part of the commitment of the nullifierRoot.I hope this is clear for you
nullifier.assertUnused(nullifierWitness, nullifierRoot);```My question is: where's the map stored?
rugged furnace
The real data must be store offchain, you can use any method you want. Onchain you only store the root of this Tree Map as a commitment.
For example you can use zkDatabase: https://zkdatabase.org/
runic socket
Ok. Because of the example I thought that maybe there's something magical going on with nullifiers and boolean merklemaps.