Proof Nullifier

Semaphore

Protocol to prove anonymous group signaling, developed by Barry Whitehat, Kobi Gurkan, et al.

Glossary:

• Groups: anonymity set containing users.
• Scope: Topic on which ProofOnce is generated
• Signal: message sent by a user
• Double-signaling: Any user inside a set cannot perform signaling twice
• Commitments: Public commitment created using user’s public key, and two private inputs, namely Identity nullifier, and Identity trapdoor.
• Nullifier: serves as the id of the user
• Trapdoor: removed in v4, initially added for extra security purposes

Utility:

• Register: User registers itself as a member of a Group, by generating a commitment from $\text{id}=H(\text{sk},\text{nullifier})$.
• Broadcast: sends a signal proving that they’re a member of the group. Links signal to external nullifier that prevents sending the same signal twice.

Components:

• Smart contract: stateful on-chain verifier
• ZK proof: off-chain proof
  • prove group membership: prove merkle membership with private inputs: private key, identity nullifier, merkle path.
    • Verifies by generating the commitment that the user is indeed correct, and checks merkle path verifying that user is actually a member of the group.
  • prove signal broadcast only once: calculate nullifier as H(secret, m)

Limitations:

• Can only send one type of signal based on external nullifier
• User has to generate new keys (nullifier) for each new group. Existing keys doesn’t work.

Plume nullifiers

Use DDH-VDF on ECDSA + Chaum-Pedersen DLog proof to create a deterministically verifiable signature. Can be created with existing pub/priv key identities.

Refer to Plume blog post.

vOPRF based Nullifier

OPRF

Compute psuedo-random function ${\text{PRF}}_k(x)$, where $x$ is the input by the client, and ${\text{PRF}}_k(\cdot )$ is the computation performed by server with secret $k$, without any knowledge of $x$.

Can we use OPRF in Origo proxy to verify correct TLS ciphertext, so that it doesn't need to happen inside circuit?

Output produced by the client is verifiable with a proof, i.e. a zero-knowledge proof is produced by the server that convinces that it computed the PRF correctly, and is verified by the client.

Protocol:

• User:
  • User generates auth ID: ${\text{comm}}_1:=H(\text{UserID,salt})$
  • Generates a random scalar $r$, and compute: ${\text{comm}}_2:=r\cdot G$, where $G=\text{HashToCurve}(\text{UserID})$
  • Generates auth proof
    • Public input: ${\text{comm}}_1,{\text{comm}}_2$
    • Private input: $\text{UserID,salt},r$
    • Compute inside circuit: ${\text{comm}}_1,G,{\text{comm}}_2$
• Notary:
  • verifies auth proof
  • replies with $\text{oprf\_response}=s\cdot {\text{comm}}_2$, where $s$ is notary’s secret key.
  • also provide a DLog proof (Schnorr/Chaum-Pedersen) that checks whether notary knows the secret
• User generates nullifier in a ZKP:
  • Private input: $r,\text{UserID, salt, DLogProof},\text{oprf\_response}$
  • Public output: ${\text{comm}}_1,\text{nullifier}$
  • Computes inside circuit:
    • ${\text{comm}}_1=H(\text{UserID, salt})$
    • $\text{DLogVerify}(\text{oprf\_response})$
    • $\text{nullifier}=r^{-1}\cdot \text{oprf\_response}$

Advantages:

• Nullifier is derived from existing userID with no external secret required to be stored by the client.
• Can use the same nullifier with any app and session as $H(\text{nullifer, appID, sessionID})$
• Notary can be scaled to be N-of-N MPC that computes ${\text{oprf\_response}}_i$ for each node, and compute nullifier together.
• Can use threshold M-of-N
• threshold secret sharing 1-of-N

Questions:

• salt and $r$ is like a password, that the client needs to store somewhere, ideally in a e2e encrypted backup cloud for repeated usage. Can this be skipped or we use any external secret key? what about ethereum account secret key, like in Plume?
• can’t anybody create a false commitments, since userID is public can be known by anyone, and other auxiliary inputs can be generated?

Pluto

Problems:

• Signature generated by notary can be used by anyone, and not just the client, any number of times.
• In some situations, we require the proof to be used only once, or to be used only by the user.

requirements:

• Signature should only be used by the client, with use only once properties.
• nullifier: user generates a proof only once.
• web2 identity: existing keys should work.
• smart contracts based blockchain Optional:
• anonymous sets: user can be member of a group, and can post message anonymously.

Let’s take an example of an economy of tickets powered by web proofs:

1. User generates a proof of it’s profile with number of hours listened for Taylor Swift concert.
2. In current system, proof generated will be used multiple times by the user for each different concerts.
3. Can generate a nullifier based on userID, and concertID based on vOPRF nullifiers as described above.
4. Nullifier proof along with notary proof can be posted on-chain, to be verified by the contract.