Duplicated nullifiers

[hackaugusto]

This issue is coming from the points in this comment: #43 (comment)

The observations are:

• nullifiers are not enforced by the protocol to be unique, i.e. it is possible to construct notes with the same nullifier if tokens are burned
• the primary means to synchronize with the rollup and get updates, including for nullifiers, is to use the state sync endpoint
• it is possible for an attacker to produce a note n1 with nullifier l, then some time later produce another note n2 with the same nullifier l. Clients can learn about the note n2, verify there is no nullifier l produced after n2, and try to consume that note. This won't work because n1 has been consumed already, and the same nullifier has been produced

[hackaugusto]

Two proposed solutions:

• add another endpoint to fetch nullifiers from any tree verified by the transaction kernel. this endpoint would be time independent, so it would include the nullifier l produce by consuming the node n1.
• change the nullifier scheme so that an attacker can not control the nullifier. This could be done by using different slices of a XOF function. Introducing some random element to the nullifier's hash that is out of control from the attacker (this could also be done by changing the nullifier from a hash to another construction, perhaps every note would have an associated ephemeral key and the nullifier is a signature from said key).

[bobbinth]

One observation: for public notes there could be a mitigation mechanism at the node level. Specifically, nodes would know if a given note has a duplicate nullifier and could take various actions based on that. For example:

• A node could discard any transaction which outputs a public note with a duplicate nullifier (probably not a good idea).
• A node could send info to the client on whether a given public note already has a nullifier together with the note info (i.e., when it is downloaded for the first time).

These, of course, don't solve the issue with private/encrypted notes as the nodes won't be able to compute nullifiers for these - so, a separate endpoint will still probably be required to address these.

[hackaugusto]

We now have an endpoint to list the nullifiers:

miden-node/proto/proto/store.proto

Line 17 in 58be273

rpc ListNullifiers(requests.ListNullifiersRequest) returns (responses.ListNullifiersResponse) {}

If we add filtering to the request, it would be sufficient to fix this issue.

[bobbinth]

ListNullifiers was intended primarily for internal testing (and so we didn't expose it via RPC). If we are to make it public, we should also add pagination and maybe other things.

[bobbinth]

Closing as we now have CheckNullifiersByPrefix endpoint (implemented in #419).