Non-Revocation Tokens using zk-SAM

A Useful ZKP Revocation Scheme For BBS+ Verifiable Credentials�zk-SAM: Signed Accumulator Members

Presented at IIW XXXIII, October 2021

Government of British Columbia

Typical Revocation Models

• Issuer creates a revocation registry (or registries)
• Issuer issues credentials (with ID) to Holders
• Tracks which credential ID is issued to which Holder
• Revokes credentials as needed
• Issuer periodical publishes/updates a Revocation Registry
• Publication of revoked and/or non-revoked credentials
• On presentation:
• Holder gets revocation registry, proves non-revocation, and Verifier verifies the proof

OR

• Holder gives Verifier an identifier for their credential, and verifier gets revocation registry and checks if credential has been revoked

Example — Revocation List 2020

• Specification
• Revocation is a compressed bit array held at a particular URL
• E.g., https://example.com/revlist2020.001
• Each revocation registry is at least 131k credentials
• Each verifiable credential contains a URL plus a bit offset into the registry
• E.g., "revocationListIndex": "12948"
• Issuer periodically updates the bit array with the status of each credential
• Prover includes its URL in each presentation (VC metadata)
• Verifier retrieves the bit array and checks the bit (e.g. bit 12,948)
• No “call home” concern, as issuer doesn’t know which bit is being checked

Example — ZKP Revocation

• Similar Issuer, Holder flow, with periodic revocation updates
• Only Issuer and Holder know the ID of the issued credential
• On presentation, Holder creates a “proof of non-revocation” (if possible)
• Verifier can verify the proof, but does not know the ID of the credential
• Also, cannot monitor the revocation registry for later revocation — must ask Holder
• Example: Indy AnonCreds:
• Functional, but not scalable
• Each Revocation Registry can only be about 10-20K credentials

Useful Revocation Scheme for Verifiable Credentials

• Useful?
• 1M+ credentials per revocation registry for “hide in the crowd” privacy
• Total credential space in the “many million” (jurisdiction-level scale)
• No unique identifier given to the verifiers for non-correlation privacy
• Verifier gets the ID of the revocation registry, but not the credential
• Moderate time/storage resource requirements for a mobile holder
• Includes time to collect data and generate the proof
• See survey results from Andreas Freitag (DIF) for definition of “Moderate”
• Fast verification with few remote calls, moderate amount of data
• A heavier, but reasonable load on the Issuer to batch revoke credentials
• Nice to have — the credential registry is “just a file”, not requiring a custom service
• E.g. nice to NOT have to collect deltas

A Non-Revocation Token

• Andrew Whitehead (https://github.com/andrewwhitehead) — BC Gov
• zk-SAM — Signed Accumulator Membership
• HackMD Documents
• Basic approach: https://hackmd.io/kj223D1ZQN29WiusmnPFMA
• The math: https://hackmd.io/vTyqrJc9QoKgThqQpVtP3g
• Starter repo: https://github.com/andrewwhitehead/bbs-accum
• Currently just a test script of the processes involved
• Caveat: I don’t know the cryptographic details!!!

Approach: Revocation VCs for Issued VCs

• Revocation Registry is a set of (roughly) BBS+ signatures of non-revocation
• Plus some metadata (more about that)
• The RevReg is divided into blocks of a given size — say 1024 indices
• The blocks are special — each includes a cryptographic accumulator
• A member value is associated with each index in block, a prime number
• The accumulator is the product of all the members that are not revoked
• The blocks in this scheme are very special
• The set of member values in every block is the same

Approach: Token Registry Metadata

• The public revocation key (96 bytes)
• A block size ie. 1024 (4 bytes)
• A base accumulator value, randomly chosen (48 bytes)
• Registry member values, randomly chosen (32 bytes * block size)
• The registry member witness values (48 bytes * block size)
• ~80kb

Approach: Blocks with Accumulators

• Each issued VC is given a member value and index within a block
• Trick: Creating a ZKP that the issued VC is not revoked without telling the Verifier the block, index and member value of the credential
• The cryptographic technique is similar to AnonCreds “Tails File”
• The blocks are each a tails file
• With more information — notably a signature for each member of each block
• Within a revocation registry, each block’s members are the same and reproducible

Approach: Data for the VC and Holder

• Each issued VC has a corresponding entry in a Revocation Registry
• Each Issued VC has two extra signed values, opaque values of:
• Revocation Registry ID + Block Index
• Member Value within Block
• Holder is also given:
• The credential’s assigned block index
• The credential’s member index within the assigned block
• The URI of the token registry metadata
• The URI of the latest token registry state

Approach: Revocation Registry State

• Revocation State, generated by the Issuer:
• Effective Timestamp
• Start/End Block Indices
• Sequence of blocks, of types:
• Fully revoked — no accumulator or signature
• Fully non-revoked — base accumulator and a signature
• Bit array of credential status with signature
• Process the bit array with the registry member and witness values
• Process:
• Generate the state based on the credential status and publish
• Publish on a ledger registry entry (state) location and timestamp (other alternatives possible)

Approach: The Holder Proves Non-Revocation

• Retrieve a registry state and find the block of interest from issued data
• Usually, the most recent, but in theory, could be at any point in time
• Use the metadata to generate the accumulator and witness for the block
• Combine the accumulator, witness, signature, timestamp, block identifier, and member value to construct the token for the equality proof with the signed values in the VC
• Provide to the verifier:
• The timestamp of the registry state
• Proof of knowledge of the signature and membership in the accumulator
• Same key signed the messages in the issued VC and the non-revocation VC

Approach: The Verifier

• The verifier just does some math to check the proof
• shows that it was signed by the same issuer as the credential, and
• that it’s tied to the same block identifier and member value.
• They need to verify the timestamp
• Perhaps from a ledger entry from the issuer for each published state object

Metrics: Data Sizes

• Registry metadata: (100 + 80 * block size) bytes; 80Kb for block size 1024
• Registry state [1024 block size; 1M credentials]:
• Every block revoked: <1Kb
• No members revoked (~32 bytes per block): 30Kb
• Every block partially revoked (~160 bytes per block): 153Kb
• Serialized non-revocation token (after extraction by the prover): 344 bytes
• Non-revocation token proof of knowledge: 368 bytes + metadata

Metrics: Processing Times

• Issuer:
• Create registry metadata (performed once): 0.25s
• Output a fully non-revoked block: 1.5ms
• Output a partially revoked block: 2ms
• Output a registry state for 1000 blocks, or about 1M credentials: up to 2s
• Prover:
• Extract a non-revocation token for a partially-revoked block: up to 0.5s
• Down to 0.025s on Mac M1(!)
• Prepare a non-revocation token proof of knowledge (performed once per verification): 5ms
• Verifier:
• Token proof of knowledge: 12ms

Open Questions

• How to fit into VC Data Model?
• How to share extra data from Issuer to Holder?
• How to fit into VP Data Model? Or some other approach?
• Where to publish the Registry State?
• Including retaining previous versions
• How does the verifier express accepted timestamp intervals?
• What sizes to use for the Registries?

Status and Next Steps

• Status: Current implementation is a test script of the process steps
• Next steps:
• Community evaluation — is it viable? Useful?
• Open questions
• Specification
• Implementations