owned this note   changed 2 years ago  
Published Linked with GitHub

What's Wrong with Current Nullifier Designs

This proposal analyses the design alternatives for a nullifier scheme for applications that rely on zk-based proof of membership within a set of addresses.

Context

While buidling Summa, a tooling to let CEXes generate a auditor-less proof of solvency, we are facing the challenge of integrating a nullifier scheme.

In the context of Summa, a Centralized Exchange (CEX) needs to prove that they own a certain amount of assets that is greater than their total liabilities. The privacy part makes possible to hide the amount of assets and hide the address that they claim to control.

For the scope of this article we can simplify that "CEX needs to prove that they control an address with balance \(\gt 0.1 ETH\) at a specific block without revealing the address (and therefore the balance)". This can be achieved by snapshotting the state of Ethereum at that specific block and create a (publicly available) merkle tree accumulator that contains all the addresses that own \(\gt 0.1 ETH\). The root of this Merkle Tree will be stored on a blockchain.

In order to prove control of an address with more than 0.1 ETH, the prover needs to prove inclusion to a merkle tree (identified by the merkle root publicly available) inside a zkSNARK.

Note: a similar accomplishment can be achieved without requiring to manually create a merkle tree accumulator by using Patricia Merkle Trie state proofs. In this writeup, the proposed nullifier scheme is described applying it to the "traditional" Merkle Tree apporach, altough the same scheme can equally apply in the case of using Patricia Merkle Trie state proofs.

This is a common design pattern of zero knowledge proof applications like Semaphore, Heyanon or Tornado Cash. The idea here is proving that you are part of a certain group made of ethereum addresses without revealing who you are in order to signal your opinion (in the case of Semaphore or Heyanon) or withdraw your money (in the case of Tornado Cash).

The zkSNARK will contain the following computation integrity checks:

  • Prover controls an address (achievable by ECDSA signature verification)
  • This address is included in the merkle tree committed on chain with a public available root

This allows the prover to prove that he/she is a member of the group without revealing who he/she is.

A typical problem that comes when designing cryptography schemes that involves zk is that the privacy element can be exploited to achieve double-spending. For example:

  • A same user can express double-signal and it can lead to multiple votes expressed by the same user
  • A same user can double-spend the same receipt and it can lead to multiple withdrawals performed by the same user that has performed a single deposit.

In the case of Proof of Assets, two malicious addresses can double-claim ownership of the same wallet. For example two malicious CEXs can cooperate and share the same signature. Since it's all happening in the dark of a zkSNARK, from the outside it's impossible to tell whether they used the same signature (in order to prove ownership of an address) or different ones.

Enters the nullifier, a unique identifier for each member of the group that:

Property 1: Uniquely identifies a member of the set. More precisely, the uniqueness relation should be bi-directional: a member of the set, identified by their address, should map to a unique nullifier, and a nullifier should map to a unique address.

Property 2: Preserves the privacy of the member so that no information about the member is retrievable starting from the nullifier (that is publicly visible).

In terms of Circuit Design, a nullifier is computed inside a circuit and exposed as public output. This is defined nullifier since it nullifies an address’s ability to perform an action again. Everytime that the same user generates a proof, the nullifier output will be the same.

Considering the previous example, if the same user expresses multiple votes via zkp generation, each proof will contain the same output nullifier. Therefore, the vote counter will be able to tell that these votes are coming from the same member of the set (but, still, without accessing their identity), and only count the first vote casted, while discarding the other ones.

The nullifier, together with the previous component, allows the prover to prove that he/she is a unique and consistent member of the group without revealing who he/she is.

Design Patters of Nullifiers

Here are some of the most common ways to design a nullifier. Each design is analyzed by considering how it would be applicable to Summa.

No Nullifier

Heyanon allows user to prove membership within a set of ethereum addresses and express a feedback without revealing their identity. The circuit has the following pseudocode structure

circuit ProveAssetOwnership {
  
  // ECDSASign(contentData) where contentData is the feedback they want to express
  pub input contentData 
  priv input signature

  // i.e. merkle root/proof
  pub input merkleRoot
  priv input merkleProof
  priv input ethPubkey

  // check 1: signature verification
  signature === ECDSASignVerify(ethPubkey, contentData)

  // check 2: membership check
  verifyMembership(merkleProof, merkleRoot, ethPubkey)

}

As you can see there's no nullifier that uniquely and privately identifies a proof generator. Intuitevely, someone can think of creating a nullifier starting from the signature.

circuit ProveAssetOwnership {
    
    ...
    
    pub output nullifier
    
    nullifier === H(signature)

}

It turns out that this approach is insecure because of the non-deterministic nature of ECDSA signatures. It means that the same user can generate multiple valid signatures (and, therefore, valid proofs) for the same contentData. All these signatures will pass check 1 and it would lead the generation of different nullifiers starting from the same user. This design won't satisfy property 1. The issue is largely discussed in the PLUME blog post.

In an application such as HeyAnon, the absence of a nullifier is not crucial. For Summa, the presence of a nullifier is mandatory. Let's consider the scenario of two colluding exchanges CEX1 and CEX2 where CEX1 controls an address 0x123 with 500 ETH and CEX2 controls no ETH. When generating a Proof of Solvency, CEX1 can generate two different (valid) signatures \(s_{1}, s_{2}\) from the private key associated with 0x123. CEX1 uses \(s_{1}\) to generate a valid proof of solvency \(π_{1}\), later shares \(s_{2}\) with CEX2 that will also generate a valid \(π_{2}\). CEX1 and CEX2 would be able to claim ownership of the same wallet and generate a valid proof without being detected.

Without integrating a nullifier within the circuit design, an insolvent exchange CEX2 is still able to generate a valid proof of solvency.

Plume Nullifier

As extensively described in the Plume blogpost and paper, it is possible to generate deterministic ECDSA signatures that can be verified inside a snark circuit.

The only issue here pertains to the current availability of this solution. As described in the blog post, these nullifiers can be only produced by installing a Metamask Snap Extension.

While the solution looks the way to go for the long term, requiring a Centralized Exchange to move their private keys into an experimental Metamask extension is not realistic today.

Therefore, we add another desired property for the nullifier.

Property 3: Do not require the user to upset their existing key-management infrastructure

Private-key based Nullifier

Another possible solution is to pass the private key as private input to the circuit and use the hash of the private key as nullifier.

circuit ProveAssetOwnership {
  
  // ECDSASign(contentData)
  pub input contentData 
  priv input signature
  priv input ethPrivKey

  // i.e. merkle root/proof
  pub input merkleRoot
  priv input merkleProof
  priv input ethPubkey
  
  pub output nullifier

  // check 1: signature verification
  signature === ECDSASignVerify(ethPubkey, contentData)

  // check 2: membership check
  verifyMembership(merkleProof, merkleRoot, ethPubkey)
  
  // check 3: ethPrivKey matches ethPubkey
  ethPubKey === privToPub(ethPrivKey)
  
  // generate nullifier
  nullifier <== H(ethPrivKey)
}

The solution satisfies properties 1 and 2.

The main problem related to that solution is the perceived security (and UX) for the user that is generating the proof. In order to generate such proof, the user would need to extract the ethPrivKey from the secure enclave and copy-paste it to the prover. It is really unlikely that a CEX, considering all their wallet security measures, will accept such solution. That would be even impractical for many hardware wallets that do not allow you to extract the private key.

Therefore the solution doesn't satisfy property 3.

Registry-based Nullifier

Aragon Zk team proposes a zkGlobalRegistry, a the smart contract portion of a standardized scheme for users to register commitments to secret data tied to their wallets.

In this scenario, a CEX would need to:

  • store a secret for each of their addresses (the secret is different from their private key)
  • generate a commitment to this secret, like an hash, and associate it to their address in the zkGlobalRegistry contract
  • When generating the proof, proving that they know the secret behind the commitment associated to their address and use something like H(secret, roundID) as nullifier.

The main problems of such design are 2:

  • The need for a CEX to store an additional secret. This can be mitigated using a signature for a specific message as a secret.
  • The anonimity set of possible addresses gets restricted to only the addresses who actually associated a commitment within the zkGlobalRegistry. Still, since the registry is (potentially) shared across different applications the anonimity set will be more "diluted".

Collaborative zkSNARKs

The key required feature of a zk prover scheme is that a prover should be able to prove that he's a unique member within a membership set in order to avoid double spending of the same proof. An approach based on Collaborative zkSNARKs would allow provers to come together and prove that the addresses they are using is unique and no other prover is double-spending a proof using the same address. This approach would remove the need for a 'traditional' nullifier while allowing the prover(s) to achieve the same goal.
This approach might be useful in those kind of application where the window time for the proof generation is limited, for example a private voting application, where the users must cast their vote before a certain time stamp. The zk proof of solvency can be adapted to this design, if this would be able to provide a solution to the nullifier issue.

Further Proposal: Nullfier Registry with Priviledged Aggregator

In this proposal the nullifier registry is stored on chain. Differently to the previous proposal, the address to which the nullifier is associated to is not public. That's because the updates to the registry are published by a previledged aggregator that post a proof that each nullifier belongs to a unique address without revealing which address they belong to.

In the context of Summa, all the CEXes that want to submit their hashed nullifier to the registry will need to:

  • use a signature as a secret
  • proof that the signature used as a secret has been actually generated by an address
  • provide the hash of the secret to be added to the registry
  • provide the address

The priviledged aggregator will need to:

  • receives the proofs from different CEXes
  • verify the proofs
  • verify that each address is unique
  • publish the hashed nullifier to the registry smart contract

The big advantage of the approach that relies on the Priviledged aggregator is that the addresses that joined the registry are kept private from the outside. The aggregator is priviledge in the sense that he/she is the only priviledged part that gets to know the addresses of the ones who joined the registry. The main risk of relying on an aggregator is censorship.

This has to be performed at each round of proof of solvency!

How to prove uniqueness? Order addresses used as input and proof that one is Lt than the other in a sequential order.

Conclusions

  • Plume Nullifier would be the ideal solution but as long as it not a standard it won't be viable
  • Private-key based Nullifier satisfies all the requirements of a nullifier scheme. The unfeasability of such solution relies on the hyphotesis that CEX would never pass a private key in plain text to a (local) prover. If this HP proves wrong, we can go for that.
  • Global Registry-based Nullifier looks the most realistic option at the moment, even with the drawback related to the reduction of the anonimity set.
  • Collaborative zkSNARKs is the most exotic design. Worth exploring.
Select a repo