or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
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:
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:
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
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.
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 passcheck 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.
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:
H(secret, roundID)
as nullifier.The main problems of such design are 2:
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:
The priviledged aggregator will need to:
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