Suggested improvement for using ZKPs to prevent the revocation index from being revealed to the verifier

[kdenhartog]

Privacy-Enhanced Bitstring Status List Protocol

High-Level Interaction Diagram

┌────────┐                     ┌────────┐                     ┌────────┐
│ Issuer │                     │ Holder │                     │Verifier│
└───┬────┘                     └───┬────┘                     └───┬────┘
    │                              │                              │
    │ 1. Generate index and        │                              │
    │    commitment C = g^index*h^r│                              │
    │                              │                              │
    │ 2. Sign credential with C    │                              │
    │    and encrypt (index,r)     │                              │
    │                              │                              │
    │ 3. Issue credential          │                              │
    │ ─────────────────────────────>                              │
    │                              │                              │
    │ 4. Publish status list       │                              │
    │ ───────────────────────────────────────────────────────────>│
    │                              │                              │
    │                              │ 5. Request verification      │
    │                              │ <─────────────────────────────
    │                              │                              │
    │                              │ 6. Send nonce                │
    │                              │ <─────────────────────────────
    │                              │                              │
    │                              │ 7. Generate ZK proof:        │
    │                              │    - C = g^index*h^r         │
    │                              │    - Status bit at index is b│
    │                              │                              │
    │                              │ 8. Send credential + proof   │
    │                              │ ─────────────────────────────>
    │                              │                              │
    │                              │ 9. Verify:                   │
    │                              │    - Issuer signature        │
    │                              │    - ZK proof using C        │
    │                              │    - Status list bit         │
    │                              │                              │
    │                              │ 10. Return verification result│
    │                              │ <─────────────────────────────
┌───┴────┐                     ┌───┴────┐                     ┌───┴────┐
│ Issuer │                     │ Holder │                     │Verifier│
└────────┘                     └────────┘                     └────────┘

Status List Data Model updates

The status list published by the issuer would be structured to support efficient verification while maintaining privacy. Here's how it would be structured:

BitstringStatusListCredential (Enhanced Version)

{
  "@context": [
    "https://www.w3.org/ns/credentials/v2",
    "https://w3id.org/zkp-privacy-status/v1"
  ],
  "id": "https://example.com/credentials/status/3",
  "type": ["VerifiableCredential", "BitstringStatusListCredential", "ZKPSupportedStatusListCredential"],
  "issuer": "did:example:12345",
  "validFrom": "2021-04-05T14:27:40Z",
  "validUntil": "2021-07-05T14:27:40Z",
  "credentialSubject": {
    "id": "https://example.com/status/3#list",
    "type": "BitstringStatusList",
    "statusPurpose": "revocation",
    "encodedList": "uH4sIAAAAAAAAA-3BMQEAAADCoPVPbQwfoAAAAAAAAAAAAAAAAAAAAIC3AYbSVKsAQAAA",
    "zkpParams": {
      "generators": {
        "g": "base64-encoded-point",
        "h": "base64-encoded-point"
      },
      "supportedProofTypes": ["bulletproofs", "groth16"],
      "verificationKeys": {
        "bulletproofs": "base64-encoded-verification-key",
        "groth16": "base64-encoded-verification-key"
      },
      "circuitDigest": "sha256-hash-of-verification-circuit"
    },
    "ttl": 86400000
  }
}

VC structure addition

"credentialStatus": {
  "id": "https://example.com/credentials/status/3#privacy",
  "type": "BlindedBitstringStatusListEntry",
  "statusPurpose": "revocation",
  "statusListCredential": "https://example.com/credentials/status/3",
  "indexCommitment": "base64-encoded-commitment-C",
  "indexCommitmentSignature": "base64-encoded-sig_i",
  "indexBlindingFactor": "base64-encoded-r", // Only visible to holder
  "index": "encrypted-index-i" // Encrypted for holder only might be better to send externally
}

Key Enhancements to the Status List

1. ZKP Support Indicator: The ZKPSupportedStatusListCredential type signals that this status list supports zero-knowledge proofs.

2. ZKP Parameters: The zkpParams object includes:

   • The same generators (g, h) used for the Pedersen commitments
   • Supported proof systems
   • Verification keys for each supported proof system
   • A digest of the verification circuit for integrity

Implementation details

Cryptographic Building Blocks

This protocol would use:

1. Pedersen Commitments: To commit to the index value without revealing it
2. Zero-Knowledge Range Proofs: To prove the index is within valid range of the bitstring
3. Bulletproofs: For efficient range proofs with small proof sizes
4. Schnorr Signatures: For the issuer to sign the index value

Pedersen Commitment

Commit(i, r) = g^i * h^r mod p

Where:

• g and h are group generators
• p is a large prime
• i is the index
• r is the random blinding factor

Range Proof

Bulletproofs would be ideal for the range proof component, as they:

• Are small (logarithmic in the size of the range)
• Don't require a trusted setup
• Can be efficiently verified

3. Compatibility: The standard encodedList is still included, allowing backward compatibility with non-privacy-enhanced implementations.

Detailed Protocol Flow

1. Issuance Phase

1. Issuer Setup:

   • Generates public parameters (generators g, h)
   • Publishes these in the status list credential

2. Credential Issuance:

   • Selects random index for the credential
   • Create a Pedersen commitment C = Commit(i, r) where r is a random blinding factor
   • Includes commitment in the credential
   • Encrypts (index, r) for the holder
   • include the signed commitment in the credential: sig_i = Sign_issuer(C)
     • Generate a Schnorr signature over this commitment:
       • Select random k from [1, q-1] where q is the group order
       • Compute R = g^k
       • Compute e = H(R || C || issuerPublicKey)
       • Compute s = k - e * issuerPrivateKey mod q
       • The signature is sig_i = (R, s)
   • Issues to holder in the verifiable credential (currently the schnorr signature is in the indexCommitmentSignature property, but there's likely a better way to restructure this.

The Schnorr signature provides cryptographic proof that the issuer has authorized the specific index commitment C, preventing holders from generating their own arbitrary index commitments.

3. Status List Publication:
   • Creates and maintains the bitstring status list
   • Publishes the enhanced status list credential with ZKP parameters
   • Updates the list periodically as statuses change
   • Uses the Data model defined above

2. Verification Phase

Range proofs are used during the status verification phase.

1. Initial Request:

   • Verifier requests credential presentation from holder
   • Verifier sends a fresh nonce n_v and send in VC presentation request

2. Holder Preparation:

   • Decrypts and retrieves (index, r)
   • Fetches the current status list (optional, for holder to check their own status)
   • Selects appropriate ZKP system based on verifier capabilities
   • Holder sends to verifier
     • The commitment C
     • The issuer's signature sig_i
     • The status bit b
     • The range proof generated π

3. Proof π Generation:

   • Retrieve the status bit b at position i from the bitstring
   • Generates zero-knowledge proof that:
     • They know (index, r) such that C = g^index * h^r
     • The bit at position index in the status list has the claimed value
     • Includes the verifier's nonce for freshness

4. Verification:

   • Verifier fetches the status list credential from issuer
   • Verifier extracts ZKP parameters
   • Verifies the issuer's signature on the credential (sig_i)
   • Verifies the range proof π using:
     • The commitment C from the credential
     • The status list bitstring
     • The ZKP parameters from the status list credential
     • The verification confirms that:
       • The prover knows a value i and blinding factor r such that C = g^i * h^r
       • 0 ≤ i < bitstring_length
       • The bit at position i in the bitstring equals b

3. Status List Update Process

1. Issuer Updates:

   • Issuer updates the bitstring when credential statuses change
   • Issues new status list credential with updated validFrom and encodedList
   • Maintains the same ZKP parameters for consistency

2. Verifier Caching:

   • Verifiers can cache the status list based on the ttl value
   • Verifiers should respect the validity period

Integration with Existing Specification

This protocol could be added to the specification as a new credential status type called BlindedBitstringStatusListEntry, which would extend the existing BitstringStatusListEntry type.

Implementation Notes

1. Bitstring Encoding: The bitstring remains encoded exactly as in the original specification (GZIP-compressed, Multibase-encoded).

2. Circuit Optimization: For large status lists, the ZK circuit can be optimized to use Merkle proofs instead of checking the entire bitstring.

3. Multiple Status Types: For credentials with multiple status types (revocation, suspension), separate commitments can be used for each type.

4. Backwards Compatibility: Systems can implement both traditional and privacy-enhanced verification methods, falling back to the standard method when ZKP is not supported.

This enhanced protocol provides strong privacy guarantees while maintaining the efficiency benefits of the bitstring status list approach, and ensures the verifier can confirm they're checking the exact index the issuer assigned without learning what that index is.

Author's Note

Usage of LLMs disclaimer

I had a Claude LLM help me write this up and made some modifications to it to speed this suggestion up a bit. The security properties of this look correct to me enough to publish this, but requires further scrutiny and detailed exploration of the usage. However, I feel it sets the idea on a good enough path that it's worth exploring further.

The prompt I used was:

Can you provide me with an example protocol to improve this specification such that the index value isn't revealed to the verifier, but can still be committed to by the issuer?

Specifically, I'd like the index to be signed by the issuer and sent to the holder within a verifiable credential. From there, when the verifier submits a request for proof of revocation they'll submit a blinding nonce value to the holder such that they can blind the index that's been signed over and send it back blinded to the verifier. The verifier would then be able to use the blinded index plus a copy of the bitstring list they downloaded from the issuer to verify the index in zero knowledge.

Please specify the cryptography necessary to achieve this relying on current state of the art of zero knowledge proof schemes.

I then followed up on it with:

This looks good, can you also add a high level interaction diagram plus details about how the revocation list data model downloaded by the verifier from the issuer would be structured?

I used Claude 3.7 as a model with Brave's integrated Leo Agent to send the page as context from https://w3c.github.io/vc-bitstring-status-list/ to produce this.

Further improvements based on my reading of it

I'm less certain that encrypting the index when issuing the credential is necessary. I think a simpler solution is to just send that as metadata outside the issued credential to the holder since managing the key agreement between the issuer and holder seems to be additional unnecessary complexity.

I also, think the signature over the credentialStatus object that's included in the VC should either be made more aligned with VCDI, or separated out into it's own separate credential. The data model for this could likely be improved.

[brentzundel]

Related: comment source

Additionally, it should consider the factor of a scheme that proves status without revealing correlatable global identifiers. The authors do indirectly acknowledge this later in §6 but it is a very desirable trait and should be mentioned upfront in the overview. §6 Privacy Considerations should also discuss the ability/inability of using Zero-knowledge proofs for proving status.

[iherman]

This was discussed during the vcwg meeting on 25 April 2025.

View the transcript

BSL

<brent> w3c/vc-bitstring-status-list#203, w3c/vc-bitstring-status-list#204

brent: First comment is about usefulness, but privacy section is useful. We don't need to respond to this because there are no changes requested.

<brent> "§2 Data Model has a table that is not titled/labeled. Additionally, it should consider the factor of a scheme that proves status without revealing correlatable global identifiers. The authors do indirectly acknowledge this later in §6 but it is a very desirable trait and should be mentioned upfront in the overview. §6 Privacy Considerations should also discuss the ability/inability of using Zero-knowledge proofs for proving status."

<brent> comment source

brent: There is a table without a title, raised issue 204 to track that.

brent: The second comment was about ZKPs and anti-correlation and if we could figure out a way to do this using a ZKPs.

brent: proposed response is to acknowledge that this would be useful and we will continue to explore this in a future version of the spec.

ivan: can we add the title and get rid of issue 204?

manu: yes

brent: I will convey that to the commenter.

---

[msporny]

Great write up, @kdenhartog (and our AI overlords). While it's unlikely that we will apply such a solution to the ECDSA or EdDSA cryptosuites, we are actively working on how to apply a mechanism such as this to BBS and possibly use some of the underpinnings for the Ligero/Sumcheck stuff that Google is working on.

I expect we're a bit far off from being able to standardize anything, as IETF is moving slowly on these sorts of foundational cryptographic primitives, but the new excitement in the cryptographic circuits areas are making it such that we have multiple interesting avenues to pursue here, which we can prototype fairly rapidly in the Data Integrity CCG work item as well as this group. We have a few folks exclusively working on efficient cryptographic circuits for Data Integrity (not trying to shoe-horn them into ECDSA as a starting point, but trying to figure out the most efficient path forward from a math, algorithms, and data structures perspective).

If that work is successful, I expect it would result in a new status list type that is optimized for everlasting unlinkability.

In any case, thanks for the comment, we're looking into approaches similar to this in the weekly Data Integrity CCG work item calls.

[kdenhartog]

@msporny I assume you're looking in the direction of zk-creds?

Using SNARKS seems to simplify this to generate more arbitrary proofs using circuits, so I'm a fan of going that proposed direction instead of the one I throughout there. It likely makes claim based proof generation simpler to work at the expense of more complex circuits being authored per credential, but that seems reasonable to technically solve such that a trust framework requires particular circuit usage for a particular credential.

[msporny]

@msporny I assume you're looking in the direction of zk-creds?

Yes, we are tracking, thanks for the pointer. There was a meeting about it w/ Abhi's team at Google just this past week in CCG:

https://lists.w3.org/Archives/Public/public-credentials/2025Apr/0067.html

... and we are actively discussing SNARKS in the Data Integrity calls (10am ET Fridays: https://meet.google.com/dph-vtuc-iof)

Using SNARKS seems to simplify this to generate more arbitrary proofs using circuits, so I'm a fan of going that proposed direction instead of the one I throughout there. It likely makes claim based proof generation simpler to work at the expense of more complex circuits being authored per credential, but that seems reasonable to technically solve such that a trust framework requires particular circuit usage for a particular credential.

The current thinking is the SNARK-based approach has benefits worth further study. There is also concern that some of the complexity needs further discussion:

• Having to get to agreement on circuits per credential is problematic (political scaling issues -- who approves circuits?)
• The proof sizes get huge with inputs larger than a few KB (and many real world VCs are 100KB - 5MB in size)
• Revocation seems to require a correlating "phone home" or download of large data sets for large revocation amounts
• Pseudonyms are possible, but we're still trying to figure out if they provide everlasting unlinkability
• Not post-quantum resistant for ECDSA
• There is no cryptographic standard-setting body that has even begun work on this stuff (govt. acceptance feels like it's 7-10 years away)

So, yes, SNARKs have us excited about how we could apply to VCs... but at present, it feels like a ball of (workable) hacks that will need some refinement (years) to scale to the use cases we see in production today.

[brentzundel]

@kdenhartog just to confirm, this issue should not be considered any part of a formal privacy review of Bitstring Status List, but rather as a place to explore next steps for a possible future version?

[kdenhartog]

just to confirm, this issue should not be considered any part of a formal privacy review of Bitstring Status List, but rather as a place to explore next steps for a possible future version?

I'm not too sure about the formalisms of the privacy review process. Whether it's apart of the formal review or not, I do not believe it's something that should be considered a blocker for the horizontal privacy review and limit this specification from moving to the recommendation status.