vOPRF-ID

The Web2-ID Nullifiers project enables pseudonymous systems for Web2 identities using verifiable Oblivious PseudoRandom Functions (vOPRFs). It addresses the lack of nullifiers in Web2 IDs, which are essential for anonymous protocols. The project aims to build an infrastructure, like Semaphore, for Web2-ID registration and reuse across applications.

Features and Capabilities

  • Implements a vOPRF protocol for private, deterministic randomness generation.
  • Uses a multi-party computation (MPC) network to enhance security.
  • Employs ZK proofs to verify Web2 identity without revealing it.
  • Aims to create a global registry for Web2 identities.
  • Generates nullifiers for Web2 IDs, crucial for pseudonymous protocols.
  • Integrates with Web2-Web3 bridges like ZK Email and TLS Notary.

Developer Capabilities

  • Build pseudonymous systems for applications like anonymous voting and forums.
  • Create privacy-preserving applications for anonymous interaction with Web2 services.
  • Integrate the vOPRF protocol with existing infrastructure.

Applications

  • Anonymous Voting with Web2 identities.
  • Anonymous Airdrops to users based on Web2 identities (e.g., GitHub).
  • Pseudonymous Forums with limited accounts and spam prevention.

Key Concepts

  • Nullifiers: Prevent double-spending or multiple voting.
  • vOPRF: Allows private, deterministic randomness generation.
  • MPC: Enhances security via multi-party computation.
  • ZK Proofs: Verifies statements without revealing information.

Web2 Nullifiers using vOPRF

Abstract

Recent development of protocols, that allow us to make Web2 data portable & verifiable such as ZK Email or TLSNotary opens new use-cases and opportunities for us. For example, we can make proof of ownership of some x.com username or email address and verify it on-chain with ZK Email. Projects like OpenPassport, Anon Aadhaar (and others) are also the case.

We can also do more complex things, e.g. forum where holders of @ethereum.org email addresses will be able to post anonymously, using zk proofs of membership.

Projects like Semaphore helps us to build pseudonymous1 systems with membership proofs for "Web3 identities".

In Semaphore users have their \( \text{public_id} = \text{hash(secret, nullifier)} \), and \( \text{nullifier} \) actually serves as an id of user - we still don't know who exactly used the system, but we'll be able to find out if they used it more than once. But the thing is we don't have any nullifiers in ZK Email/TLS, etc. - that's why it's not possible to create such systems for Web2 identities out of the box. The solution for that is vOPRF.

vOPRFs (verifiable Oblivious PseudoRandom Functions) - are protocols that allow a client to generate deterministic random based on their input, while keeping it private. So, there're two parties in the protocol - first one as I said is a client, and second one is a OPRF network (usually MPC is used for that).

With OPRF we'll be able to generate nullifiers for Web2 ID's': users will just need to ask the MPC to generate it, e.g., based on their email address (without revealing plain text of course).

We can do many things based on that:

  • anonymous votings with ported Web2 identities;
  • anonymous airdrops - projects can just list github accounts, that are eligible for airdrop, and users will be able to claim (only once) with proof of github using ZK Email;
  • pseudonymous forums - I mentioned it before, but with OPRF we can have pseudonyms and limit user to only one account + it might be easier to track & ban spammers
  • ... many more.

Detailed explanation

Main protocol:

There are three parties involved in protocol: \( \DeclareMathOperator{cm}{commitment} \DeclareMathOperator{hash}{hash} \DeclareMathOperator{hashc}{hashToCurve} \DeclareMathOperator{chaum}{chaumPedersenVerify} \)

  • User, that is trying to do some action with their Web2 identity (e.g. google account) pseudonymously (e.g. anonymously participate in voting).

  • OPRF Server/Network (will just call OPRF).

    • We use MPC, because in the case of having only one node generating nullifiers for users - it'll be able to bruteforce and find out which Web2 identity corresponds given nullifier. Every node has to commit to their identity somehow - e.g., by storing their EC public key on a blockchain. For simplicity I'll explain the case with one node OPRF first, and in OPRF-MPC section I'll explain how we can extend it to multiple nodes.

  • Ethereum (or any other smart-contract platform)

  • Nodes must be run in a TEE to add additional security

  • All of the EC operations are done on BabyJubJub Curve

  • For the \( \hash \) operation we use Poseidon Hash

  1. User makes ZK Email/TLS auth proof with salted commitment to UserID (or email, name, etc.) as a public output: $$\cm_1 = \hash(\text{UserID}, \text{salt})$$ I'll call it just Auth proof

  2. User sends new commitment to their UserID to OPRF: $$\cm_2 = r * G$$ where \( G = \hashc(\text{UserID}) \), and \( r \) is random scalar.
    We want to prevent users from sending arbitrary requests (because they would be able to attack the system by sending commitments to different user's identities), so user must additionally provide a small zk proof, that checks the relation between the commitments, where:

    • Public inputs: \( \cm_1 \), \( \cm_2 \)
    • Private inputs: \( \text{UserID} \), \( \text{salt} \), \( r \)

    and constraints: $$\cm_1 = \hash(\text{UserID}, \text{salt})$$ $$G = \hashc(\text{UserID})$$ $$\cm_2 = r * G$$

    It’s possible to do step 1 and 2 in one circuit, but that would require a lot of changes in i.e. ZK Email/TLS circuit, which is not desirable.

  3. OPRF replies with: $$\text{oprf_response} = s * \cm_2$$ where \( s \) is a private key of OPRF node; and also replies with proof of correctness of such multiplication, which is in this case might be a Chaum-Pedersen proof of discrete log equality (check this blog post) on that.

  4. User creates zk proof with the following parameters:

    • Public outputs: \( \cm_1, \text{ nullifier} \)
    • Private inputs: \( r, \text{ UserID}, \text{ salt}, \text{ chaum_pedersen_proof}, \text{ oprf_response} \)

    and validates that: $$\cm_1 = \hash(\text{UserID}, \text{ salt})$$ $$G \longleftarrow \hashc(\text{UserID})$$ $$\chaum (\text{oprf_response})$$ $$\text{nullifier} \longleftarrow r^{-1} * \text{ oprf_response}$$

Nullifiers

That's it, we have nullifier - and now users can use the system as in Semaphore. If we go a bit further, it's worth to mention that users shouldn't reveal nullifier, because it's linked with their \( \text{UserID} \); and if they use the same \( \text{UserID} \) in different apps - it'll be possible to track them. We can do it a bit differently - instead of revealing nullifier we can reveal \( \hash(\text{nullifier}, \text{AppID}) \) - where \( \text{AppID} \) is a unique identifier of the app, and that's gonna be our real nullifier.

OPRF MPC

In the example above we used only one node OPRF, but we can easily extend it to multiple nodes. There're many ways to do that, I'll explain few:

  1. N of N MPC:

    1.1. All nodes have their own pair of keys.

    1.2. Every node does step 3 individually: we get \( \text{oprf_response}_i = s_i * r * G \)

    1.3. On step 4 we verify \( \text{chaum_pedersen_proof} \) for every node

    1.4 We calculate \( \text{nullifier}_i = \text{oprf_response}_i * r^{-1} \)

    1.5 We calculate \( \sum_{i=1}^N\text{nullifier}_i = s * G \)

    Important to mention that we have to verify/calculate everything in the circuit

  2. M of N MPC using linear combination for Shamir Secret Sharing:

    Similar to N of N MPC, but we need only M shares

  3. Interactive M of N threshold MPC:

    Similar to 2, but nodes calculate one common response and one common Chaum-Pedersen proof. With that - we won’t need to verify separate Chaum-Pedersen proofs in zk circuit, we’ll only need to verify one, though with this scheme we’ll need to care about coordination between MPC nodes.

  4. Using BLS:

    3.1. Calculate common public key of all OPRF nodes by summing individual public keys

    3.2. The same as in N of N MPC case

    3.3., 3.4, 3.5. - The same as in N of N MPC case, BUT we can do it outside the circuit

    3.6. Verify BLS pairing in the circuit

There are techniques such as DKG protocol and Resharing protocol, that can be useful for production ready protocol. With them you can build a permissionless MPC network, where it’ll be possible to change the MPC node set each epoch, while having the same common secret key. You can read more about them in Nanak’s post on OPRF here.

For the alpha release we’ll stick to the N of N MPC setup, where N = 3, without DKG & Resharing.

Additional info

The same protocol can be applied to other Web2<->Web3 bridges, such as OpenPassport, TLS Notary, ZK JWT, etc.

  1. Pseudonymous system - a privacy-preserving system, where users' transactions are linked to unique identifiers (pseudonyms), but not their actual identities. ↩

This spec focuses on implementing the networking part for vOPRF protocol. It describes how nodes generate keys, process evaluation requests, and coordinate to provide secure vOPRF functionality.

Web2 Nullifiers using vOPRF - Network/MPC Specification

Overview

This specification describes the networking and MPC components of the vOPRF system. The implementation uses a non-coordinated N-of-N setup with N=3 nodes, where each node operates independently without inter-node communication.

Node Setup

Key Generation

Each node must:

  1. Generate a BabyJubJub keypair: 
    private_key = random_scalar()
public_key = private_key * G  // G is BabyJubJub base point
  2. Make their public key available for verification (store it in a public registry, e.g. Ethereum)

API Specification

Endpoint: /api/v1/evaluate

Processes vOPRF evaluation requests and returns the result with a proof of correctness.

Request

  • Method: POST
  • Content-Type: application/json
  • Body: 
    {
  "proof": {
    // ZK proof that commitment is valid
    // (as specified in [OPRF Commitment Circuit](./zk-circuits.md#circuit-1-oprf-commitment-circuit))
  }
}

Response

  • Status: 200 OK
  • Content-Type: application/json
  • Body: 
    {
  "result": {
    "x": "0x...",  // hex-encoded x coordinate
    "y": "0x..."   // hex-encoded y coordinate
  },
  "dleq_proof": {
    "c": "0x...",  // challenge
    "s": "0x..."   // response
  }
}

Processing Steps

  1. Input Validation

    • Verify that commitment point is on BabyJubJub curve
    • Verify the accompanying ZK proof

  2. OPRF Evaluation

    result = private_key * commitment2

  3. DLEQ Proof Generation Generate Chaum-Pedersen proof to prove that:

    (G, public_key) ~ (commitment2, result)

    where ~ denotes "same discrete logarithm"

    Reference: https://github.com/holonym-foundation/mishti-crypto/blob/main/src/lib.rs#L109

Client Integration

Clients must:

  1. Generate commitment using Circuit 1 (OPRF Commitment Circuit)
  2. Contact all N nodes independently
  3. Verify DLEQ proofs from all nodes
  4. Sum all responses to get final OPRF result
  5. Generate nullifier using Circuit 2 (Nullifier Generation Circuit)

Error Handling

Return appropriate HTTP status codes:

  • 400 Bad Request: Invalid input format or point not on curve
  • 401 Unauthorized: Invalid proof
  • 429 Too Many Requests: Rate limit exceeded
  • 500 Internal Server Error: Node error

Error response format:

{
  "error": {
    "code": "INVALID_POINT",
    "message": "Provided point is not on BabyJubJub curve"
  }
}


This specification can be implemented in Rust. Reusing parts of [Holonym Foundation's vOPRF](https://github.com/holonym-foundation/mishti-crypto) might be helpful.

This spec focuses on how a user commits to a userID with a random scalar r and proves consistency with their existing commitment (which comes from a separate ZK Email/TLSNotary proof). The idea is to ensure that a user cannot arbitrarily switch userIDs while reusing the same randomness.

Web2 Nullifiers using vOPRF — ZK Circuit Specification

Overview

This specification describes two ZK circuits that work together with an existing Auth Proof:

  1. OPRF Commitment Circuit: Proves that a user's commitment to the OPRF server is consistent with their previously verified identity.
  2. Nullifier Generation Circuit: Proves that a nullifier is correctly derived from the OPRF response and consistent with the user's identity.

The Auth Proof (e.g., ZK Email/TLSNotary proof) is an external component that provides commitment1, a commitment to the user's identity.

High-Level Flow

  1. User already has an Auth Proof with salted commitment to UserID as a public output:

    commitment1 = hash(UserID, salt)

  2. User creates an OPRF Commitment Proof to send to the OPRF server:

    commitment2 = r * G where G = hashToCurve(UserID)

    where r is random scalar. This proof ensures commitment2 is consistent with the same UserID in commitment1.

  3. OPRF replies with:

    oprf_response = s * commitment2

    where s is a private key of OPRF node; and also replies with proof of correctness (e.g., a Chaum-Pedersen proof).

  4. User creates a Nullifier Generation Proof that:

    • Takes commitment1 and produces nullifier
    • Verifies the OPRF response is valid
    • Computes nullifier = r^-1 * oprf_response

Circuit 1: OPRF Commitment Circuit

This circuit proves that the commitment sent to the OPRF server is consistent with the user's verified identity.

Public Inputs

  1. commitment1
    From the Auth Proof, computed as hash(UserID, salt).

  2. commitment2
    The commitment to send to the OPRF, computed as r * G where G = hashToCurve(UserID).

Private Inputs

  1. UserID
    The user's identity string (email, TLSNotary-verified name, etc.).

  2. salt
    The salt used in the Auth Proof commitment.

  3. r
    A random scalar chosen by the user.

Circuit Constraints

  1. Auth Proof Consistency

    commitment1 == hash(UserID, salt)

  2. OPRF Commitment Calculation

    G = hashToCurve(UserID)
commitment2 == r * G

Pseudocode

// OPRF Commitment Circuit

function ProveOPRFCommitment(
  // Public inputs
  commitment1,
  commitment2
) {
  // Private inputs
  user_id;
  salt;
  r;

  // 1. Verify consistency with Auth Proof
  computed_commitment1 = Hash(user_id, salt);
  Assert(computed_commitment1 == commitment1);

  // 2. Verify OPRF commitment
  G = HashToCurve(user_id);
  computed_commitment2 = ScalarMul(G, r);
  Assert(computed_commitment2 == commitment2);
}

Circuit 2: Nullifier Generation Circuit

This circuit proves that the nullifier is correctly derived from the OPRF response and consistent with the user's identity.

Public Inputs

  1. commitment1
    From the Auth Proof, computed as hash(UserID, salt).

  2. nullifier
    The final nullifier value computed as r^-1 * oprf_response.

Private Inputs

  1. UserID
    The user's identity string.

  2. salt
    The salt used in the Auth Proof commitment.

  3. r
    The random scalar used in the OPRF commitment.

  4. oprf_response
    The response from the OPRF server.

  5. chaum_pedersen_proof
    Proof of correctness for the OPRF response.

Circuit Constraints

  1. Auth Proof Consistency

    commitment1 == hash(UserID, salt)

  2. OPRF Response Verification

    ChaumPedersenVerify(oprf_response, chaum_pedersen_proof)

  3. Nullifier Calculation

    nullifier == r^-1 * oprf_response

Pseudocode

// Nullifier Generation Circuit

function ProveNullifier(
  // Public inputs
  commitment1,
  nullifier
) {
  // Private inputs
  user_id;
  salt;
  r;
  oprf_response;
  chaum_pedersen_proof;

  // 1. Verify consistency with Auth Proof
  computed_commitment1 = Hash(user_id, salt);
  Assert(computed_commitment1 == commitment1);

  // 2. Verify OPRF response
  Assert(ChaumPedersenVerify(oprf_response, chaum_pedersen_proof));

  // 3. Calculate nullifier
  r_inverse = InverseScalar(r);
  computed_nullifier = ScalarMul(oprf_response, r_inverse);
  Assert(computed_nullifier == nullifier);
}

These circuits can be implemented in various ZK proving systems such as Groth16, PLONK, Bulletproofs, or others, depending on the specific requirements of the application.

Web2 Nullifiers using vOPRF

Recommended to read Overview for understanding.

Abstract

Idea of having nullifiers for Web2 IDs is very promising. There's an explanation of the idea and how we can achieve this. As it was said - we can build a lot of applications on top of that, and this would require users to go through the same process for all apps. But can we do better? YES!

What we can do - is to create a one big global system that will hold registered identities, and people will be able to reuse them across different apps (of course while preserving nullifiers & anonimity) - kinda like global Semaphore for Web2 Identities.

In the next section I'll explain how we can do that.

How it works

In the end of the overview explanation I said: \( \DeclareMathOperator{hash}{hash} \DeclareMathOperator{cm}{commitment} \DeclareMathOperator{hashc}{hashToCurve} \)

instead of revealing nullifier we can reveal \( \hash(\text{nullifier}, \text{AppID}) \) - where \( \text{AppID} \) is a unique identifier of the app, and that's gonna be our real nullifier.

That's actually the key for building such system.

We can deploy one registry smart-contract. We'll set \( \text{AppID} = 0 \). We also gonna keep \( \text{pseudonym} = \hash(s * G, \text{ AppID}) \), where, \( s \) is "private key" of OPRF MPC, and \( G = \hashc(\text{UserID}) \). All the identities will be stored in Merkle Tree, and \( \text{pubkey} = \hash(\text{pseudonym}, \cm_1) \) will be stored in its leaves. For those who forgot, \( \cm_1 = \hash(\text{UserID}, \text{ salt}) \).

Now, let's say we registered our github identity in our global system and there's an app that gives airdrop to their contributors (of course we want to claim airdrop anonymously). The airdrop app will need to set their own \( \text{AppID} \), different from 0, because 0 is already taken; this can get checked by registry smart-contract. It will also need to create a merkle tree of github usernames that are eligible for airdrop (our github username is in that list).

Now, to claim airdrop anonymously we'll need to create zk proof with the following parameters:

  • Public: \( \text{AppID}, \text{ nullifier}, \text{ registryRoot}, \text{ appRoot} \)
  • Private: \( \text{UserID, } sG, \text{ salt} \)

and the constraints: $$\text{pseudonym} \longleftarrow \hash(sG, \text{ 0})$$ $$\cm_1 \longleftarrow \hash(\text{UserID}, \text{ salt})$$ $$\text{pubkey} \longleftarrow \hash(\text{pseudonym}, \cm_1)$$ $$\text{registryRoot} = \text{merkleTreeVerify(pubkey)}$$ $$\text{appRoot} = \text{merkleTreeVerify(UserID)}$$ $$\text{nullifier} = \hash(sG, \text{ AppID})$$


As you can see, the pair \( (sG, \text{ salt}) \) will serve as an action key, and $sG$ itself will be a viewing key.

Additional comments

While reading this, you might ask the same questions we have right now. For example, how we can prevent users spamming OPRF? It also makes sense to make system even more general and give people an option to specify which OPRF provider they gonna use and of what id-provider they will use (there can be many even for the same id-provider, e.g. bridged by zkEmail, zkTLS & OpenPassport). While they are important, they are not in the scope of this blog post.

Appendix