Nullifier scheme

[bobbinth]

In previous discussions I've mentioned that we use two databases to keep track of unconsumed notes: the Note DB and the Nullifier DB. However, I have not described previously how exactly these two work together to accomplish this.

At the high level, these databases do the following:

• Note DB keeps track of all notes ever created using an append-only accumulator (e.g., Merkle mountain range).
• Nullifier DB keeps track of consumed notes using a Sparse Merkle tree.

Leaves in the Note DB are not individual notes but rather Merkle trees such that each tree contains all notes created in a given block. Thus, a single leaf gets added to the Note DB with each new block. The note tree for each block itself contains trees of notes aggregated in a given transaction batch - but describing the exact structure of the Notes DB is not the main point of this article. The important part is that for every note ever created, we should be able to produce an inclusion path, and at the leaf of this path we will have a note hash.

A note hash is computed simply by hashing all components of a note. Specifically, components of a note are:

where:

• vault_hash is a commitment to all assets contained within a note.
• script_root is a root of a MAST for the note's spend script.
• serial_num is a value chosen randomly by the note's recipient.

Thus, a note hash can be computed as:

note_hash = hash(vault_hash, script_root, serial_num)

Where $hash$ is a native hash function used by the VM.

The above scheme is binding: we cannot change anything about the note without changing the hash. It is also hiding in that we need to know all 3 components of a note to be able to match a note to its hash. For example, knowing a note's vault_hash and script_root is not enough to figure if note hashes to a given value. We must also know the serial_num.

As mentioned above, note hashes are appended to the Note DB whenever new notes are created. However, when notes are consumed, we record note nullifiers in the Nullifier DB. We could have recorded note hashes in the Nullifier DB, but that would make notes linkable. Specifically, when a note is consumed (assuming it is consumed in a local transaction), we don't want to reveal which note was consumed exactly. Thus, we want the nullifier to have the following properties:

1. A nullifier should be derived from the note deterministically such that it is infeasible to derive two different nullifiers for the same note.
2. Given a nullifier and a note hash, it should not be possible to tell whether these were derived from the same note. Of course, if we know all components of a note, then we should be able to tell whether a nullifier for this note was computed correctly.

Originally, I was thinking that we could compute a nullifier simply as:

nullifier = hash(serial_num)

This would satisfy the two properties mentioned above (the nullifier is derived deterministically, and nullifier and note hash are unlinkable), and it might have worked in a fully private setting, where serial_num is known only to the note's recipient. But in a setting when we have private and public notes, this creates an attack vector.

For example, let's say we create a public note with some serial number $a$. This serial number can be observed by anyone on the network. A malicious user could create another note with the same serial number, and then consume it. Once this happens, an entry will be added to the Nullifier database indicating that a note with nullifier $hash(a)$ has been consumed. This would make it impossible for us to consume our original note.

To address this issue, we can compute the nullifier like so:

nullifier = hash(vault_hash, script_root, hash(serial_num))

This is similar to note_hash computation, but here we hash the serial_num one extra time. The properties we get from this are:

1. It is infeasible to derive two different nullifiers for the same note.
2. Given a nullifier and a note hash, there is no way to tell if they came from the same note.
3. If nullifiers for two notes are the same, then these two notes must be identical.

The last point means that it would make no sense for an attacker to create a note with the same serial number as to get the same nullifier they would need to create an identical note.

While I think the above scheme should work, I haven't spent much time analyzing it and would appreciate any feedback (especially if anyone sees holes in it).

[bobbinth]

Actually, the above description did not take into account some new elements described in #356. Specifically, new structure of a note would look like this:

where block_ref is the block reference number of a note (which must be smaller or equal to the current block height at the time of note creation).

The above changes our definition of note hash and nullifier computations as follows:

note_hash = hash(vault_hash, script_root, block_ref, serial_num)
nullifier = hash(vault_hash, script_root, block_ref, hash(serial_num))

[bobbinth]

I've realized that given the structure of Note DB, specifically that each leaf contains notes for a given block (as shown below), we actually don't need to put block reference number into the note itself. This number can be unambiguously determined any time we have an inclusion proof for a note.

Thus, we can go back to the note structure described in the original post. Specifically:

And then we can define note hash and nullifier computations as follows:

note_hash = hash(vault_hash, script_root, hash(serial_num))
nullifier = hash(vault_hash, script_root, serial_num)

Here, serial_num is hashed separately before being included into note_hash to improve privacy as discussed in #441 (reply in thread). Specifically, this ensures that to compute a note hash, one does not need to know the serial number (but does need to know hash of the serial number).

[bobbinth]

It also may make sense to define note_hash as follows:

note_hash = hash(vault_hash, hash(script_root, hash(serial_num)))

It does require one extra hash, but it may simplify creating notes within a transaction kernel. Specifically, we could define a recipient value as follows:

recipient = hash(script_root, hash(serial_num))

And then we could have procedures like create_note(asset, recipient).

[vlopes11]

I have a question about who sets the serial number. Given the following scenario

1.1) Let C be an account that is deployed and provide non-fungible assets functionalities
1.2) Let A be the owner of a given asset x in C
1.3) Let B be the owner of other assets of no relevance for this example, in C

Provided A wants to send assets to B by spending the asset x and creating another asset y with serial number z

2.1) A will compute locally a proof of correctness p by executing the send script of the account C
2.2) The proof p will bind the asset x to y via serial number z. Therefore, the serial number z must be known by A so he can craft the proof p.

Wouldn't 2.2 allow A to spend the asset y (because he knows the serial number z), when only B should be allowed to do so?

It would be safe, however, if we have a form of asymmetric cryptography as serial number, allowing A to generate z given a public identify of B, but not being able to spend it if the send expects a secret knowledge of the public identity of B in order to be successful. Is that the case?

[jdkanani]

Possible that this comment might not be relevant here. Also, I am still trying to understand the Miden system. This mechanism may not work at all. Just consider it a comment from a noob.

I might be missing many discussions around this, but I was still thinking about how a simple transfer or swap would look. Here are a few thoughts -

• Recording a note on the chain and consuming it in the second tx would be the easiest way to implement the flow, but each transfer note has to include the expiry date in case the receiver doesn't claim it. Notifying the receiver and making them sign the tx in a limited period is not that intuitive. If the note transfer expires, the sender has to claim it back. Until that, the amount gets locked in between. The sender might have to re-call and send a new note again in the majority of the scenario. Not so good UX for transfer/swap.
• Sender A can create a note off-chain using the serial number provided by receiver B, sign the transaction, create the proof, and give it to B to consume it on-chain. Once B receives it, it can verify and submits the consumption tx with the note creation tx.
• Node script should include short expiry and recall if B tries to delay the transfer. But here, A shouldn't have to wait longer and doesn't have to recall if B is honest.
• Transfer/Swap must only be considered final once it is recorded on the chain.

Possible that this might break the off-chain proof creation system the way I am not able to think yet.

[bobbinth]

I'll write up a more detailed description of how I think this will work (including some thoughts I described in 0xPolygonMiden/miden-base#7 (comment)), but here are a couple of quick comments.

Sender A can create a note off-chain using the serial number provided by receiver B, sign the transaction, create the proof, and give it to B to consume it on-chain. Once B receives it, it can verify and submits the consumption tx with the note creation tx.

Assuming I understood this correctly, I am not sure this is preferable to the first option. If A gives gives a transaction to B without putting it on chain, then in the period of time between A giving this transaction to B and B executing it, A could execute a different transaction agains his account, and make the transaction he gave to B un-executable.

Recording a note on the chain and consuming it in the second tx would be the easiest way to implement the flow, but each transfer note has to include the expiry date in case the receiver doesn't claim it. Notifying the receiver and making them sign the tx in a limited period is not that intuitive.

I actually think this may not be so bad. First, in my mind, the "recall" option is there only to prevent "catastrophic" situations (e.g., sending assets to non-existent address). So, the non-recallable period could be quite long. I've always thought about it as being on the order of several months. Basically, if I screwed up somehow and the intended recipient can't receive the assets for some reason, I know I can get the assets back within a few months.

My other assumption is that vast majority of notes will be consumed in a span of a month or so. Ideally, note consumption will be either semi or fully automated at the wallet level. For example, once the wallet software detects an incoming note, it would create a transaction to consume this note automatically (or maybe present a confirmation option to the user).

Finally, we can always default to non-recallable notes. These notes don't have the same protection against screw-ups, but they give the same "finality" as regular crypto transactions (i.e., assuming A didn't screw up, B can consume such a note at any time - even a year later).

[bobbinth]

Added a detailed description of how user-to-user transfers could work here.

[jdkanani]

My comment was more around swap where I want to execute the swap and makes it invalid after sometime if it is not executed. Let me think more and get back.

[jdkanani]

One comment —

Assuming I understood this correctly, I am not sure this is preferable to the first option. If A gives gives a transaction to B without putting it on chain, then in the period of time between A giving this transaction to B and B executing it, A could execute a different transaction agains his account, and make the transaction he gave to B un-executable.

Yes. That’s true. It means that B considers this as an invalid transfer. B should only assume transfer is finalized once it is recorded on the chain. Goal is not to make transfer/swap without executing on-chain but make full-transfer/swap atomic (or rather in one tx) instead of locking amount on-chain.