Revocation List 2020

This specification describes a privacy-preserving, space-efficient, and high-performance mechanism for publishing the revocation status of Verifiable Credentials.

Introduction

It is often useful for an issuer of verifiable credentials [[VC-DATA-MODEL]] to link to a location where a verifier can check to see if a credential has been revoked. There are a variety of privacy and performance considerations that are made when designing, publishing, and processing revocation lists.

One such privacy consideration happens when there is a one-to-one mapping between a verifiable credential and a URL where the revocation status is published. This type of mapping enables the website that publishes the URL to correlate the holder, time, and verifier when the status is checked. This could enable the issuer to discover the type of interaction the holder is having with the verifier, such as providing an age verification credential when entering a bar. Being tracked by the issuer of a driver's license when entering an establishment violates a privacy expectation that many people have today.

Similarly, there are performance considerations that are explored when designing revocation lists. One such consideration is where the list is published and the burden it places from a bandwidth and processing perspective, both on the server and the client fetching the information. In order to meet privacy expectations, it is useful to bundle the status of large sets of credentials into a single list to help with herd privacy. However, doing so can place an impossible burden on both the server and client if the status information is as much as a few hundred bytes in size per credential across a population of hundreds of millions of holders.

The rest of this document proposes a highly compressible, bitstring-based revocation list mechanism with strong privacy-preserving characteristics, that is compatible with the architecture of the Web, is highly space-efficient, and lends itself well to content distribution networks. As an example of using this specification to achieve a number of beneficial privacy and performance goals, it is possible to create a revocation list that can be constructed for 100,000 verifiable credentials that is roughly 12,500 bytes in size in the worst case. In a case where a few hundred credentials have been revoked, the size of the list is less than a few hundred bytes while providing privacy in a herd of 100,000 individuals.

Core Concept

This section outlines the core concept utilized by the revocation list mechanism described in this document. At the most basic level, revocation information for all verifiable credentials issued by an issuer are expressed as simple binary values. The issuer keeps a bitstring list of all verifiable credentials it has issued. Each verifiable credential is associated with a position in the list. If the binary value of the position in the list is 1 (one), the verifiable credential is revoked, if it is 0 (zero) it is not revoked.

One of the benefits of using a bitstring is that it is a highly compressible data format since, in the average case, large numbers of credentials will remain unrevoked. This will ensure long sections of bits that are the same value and thus highly compressible using run-length compression techniques such as ZLIB [[RFC1950]]. The default bitstring size is 16KB (131,072 entries), and when only a handful of verifiable credentials are revoked, the compressed bitstring size is reduced down to a few hundred bytes.

Another benefit of using a bitstring is that it enables large numbers of verifiable credential revocation statuses to be placed in the same list. This specification utilizes a minimum bitstring length of 131,072 (16KB). This population size ensures an adequate amount of herd privacy in the average case. If better herd privacy is required, the bitstring can be made to be larger.

diagram showing a
list of boxes at the top of the image with two of them in
red depicting revoked credentials. Text beside the boxes to the
right reads 16 kilobytes. An depiction of the boxes being
ZLIB compressed into a cylinder on the bottom of the page shows
that compression has resulted in a final size of 135 bytes. — A visual depiction of the concepts outlined in this section.

Data Model

The following sections outlines the data model for this document.

RevocationList2020Status

When an issuer desires to enable revocation for a verifiable credential, they MAY add a status property that uses the data model described in this specification.

Property	Description
id	The constraints on the `id` property are listed in the Verifiable Credentials Data Model specification [[VC-DATA-MODEL]]. The value is expected to be a URL that identifies the status information associated with the verifiable credential. It MUST NOT be the URL for the revocation list.
type	The `type` property MUST be `RevocationList2020Status`.
revocationListIndex	The `revocationListIndex` property MUST be an arbitrary size integer greater than or equal to 0, expressed as a string. The value identifies the bit position of the revocation status of the verifiable credential.
revocationListCredential	The `revocationListCredential` property MUST be a URL to a verifiable credential. When the URL is dereferenced, the resulting verifiable credential MUST have `type` property that includes the `RevocationList2020Credential` value.

{
  "@context": [
    "https://www.w3.org/2018/credentials/v1",
    "https://w3id.org/vc-revocation-list-2020/v1"
  ],
  "id": "https://example.com/credentials/23894672394",
  "type": ["VerifiableCredential"],
  "issuer": "did:example:12345",
  "issued": "2020-04-05T14:27:42Z",
  "credentialStatus": {
    "id": "https://dmv.example.gov/credentials/status/3#94567",
    "type": "RevocationList2020Status",
    "revocationListIndex": "94567",
    "revocationListCredential": "https://example.com/credentials/status/3"
  },
  "credentialSubject": {
    "id": "did:example:6789",
    "type": "Person"
  },
  "proof": { ... }
}

RevocationList2020Credential

When a revocation list is published, the result is a verifiable credential that encapsulates the revocation list. The following section describes the format of the verifiable credential that encapsulates the revocation list:

Property	Description
id	The verifiable credential that contains the revocation list MUST express an `id` property that matches the value specified in `revocationListCredential` for the corresponding `RevocationList2020Status` (see ).
type	The verifiable credential that contains the revocation list MUST express a `type` property that includes the `RevocationList2020Credential` value.
credentialSubject.type	The `type` of the credential subject, which is the revocation list, MUST be `RevocationList2020`.
credentialSubject.encodedList	The `encodedList` property of the credential subject MUST be the ZLIB-compressed [[RFC1950]], base-64 encoded [[RFC4648]] bitstring values for the associated range of verifiable credential status values. The uncompressed bitstring MUST be at least 16KB in size.

{
  "@context": [
    "https://www.w3.org/2018/credentials/v1",
    "https://w3id.org/vc-revocation-list-2020/v1"
  ],
  "id": "https://example.com/credentials/status/3",
  "type": ["VerifiableCredential", "RevocationList2020Credential"],
  "issuer": "did:example:12345",
  "issued": "2020-04-05T14:27:40Z",
  "credentialSubject": {
    "id": "https://example.com/status/3#list",
    "type": "RevocationList2020",
    "encodedList": "H4sIAAAAAAAAA-3BMQEAAADCoPVPbQsvoAAAAAAAAAAAAAAAAP4GcwM92tQwAAA"
  },
  "proof": { ... }
}

Algorithms

The following section outlines the algorithms that are used to generate and validate revocation lists as described by this document.

Generate Algorithm

The following process, or one generating the exact output, MUST be followed when producing a RevocationList2020Credential:

Let issued credentials be a list of all issued verifiable credentials.
Let RLC be an unsigned RevocationList2020Credential without the encodedList property set.
Generate a compressed bitstring by passing issued credentials to the Bitstring Generation Algorithm.
Set the encodedList to compressed bitstring.
Generate a proof for the RLC and publish it to the endpoint listed in the verifiable credential.

Validate Algorithm

The following process, or one generating the exact output, MUST be followed when validating a verifiable credential that is contained in a RevocationList2020Credential:

Let credentialToValidate be a verifiable credentials containing a status entry that is a RevocationList2020Status.
Verify all proofs associated with the credentialToValidate. If a proof fails, return a validation error.
Let revocationListCredential be set to the value of the RevocationList2020Credential.
Let compressed bitstring be the value of the encodedList property of the RevocationList2020Credential.
Let credentialIndex be the value of the revocationListIndex property of the RevocationList2020Status.
Generate a revocation bitstring by passing compressed bitstring to the Bitstring Expansion Algorithm.
Let revoked be the value of the bit at position credentialIndex in the revocation bitstring.
Return true if revoked is 1, false otherwise.

Bitstring Generation Algorithm

The following process, or one generating the exact output, MUST be followed when generating a revocation list bitstring. The algorithm takes a issuedCredentials list as input and returns a compressed bitstring as output.

Let bitstring be a list of bits with a minimum size of 16KB, where each bit is initialized to 0 (zero).
For each bit in bitstring, if there is a corresponding revocationListIndex value in a revoked credential in issuedCredentials, set the bit to 1 (one), otherwise set the bit to 0 (zero).
Generate a compressed bitstring by using the ZLIB compression algorithm [[RFC1950]] on the bitstring and then base64-encoding [[RFC4648]] the result.
Return the compressed bitstring.

Bitstring Expansion Algorithm

The following process, or one generating the exact output, MUST be followed when expanding a compressed revocation list bitstring. The algorithm takes a compressed bitstring as input and returns a uncompressed bitstring as output.

Let compressed bitstring be a compressed revocation list bitstring.
Generate an uncompressed bitstring by using the base64-decoding [[RFC4648]] algorithm on the compressed bitstring and then expanding the output using the ZLIB decompression algorithm [[RFC1950]].
Return the uncompressed bitstring.

Privacy Considerations

This section details the general privacy considerations and specific privacy implications of deploying this specification into production environments.

Revocation Bitstring Length

This document specifies a minimum revocation bitstring length of 131,072, or 16KB uncompressed. This is enough to give holders an adequate amount of herd privacy if the number of verifiable credentials issued is large enough. However, if the number of issued verifiable credentials is a small population, the ability to correlate an individual increases because the number of allocated slots in the bitstring is small. Correlating this information with, for example, where the geographic request came from can also help to correlate individuals that have received a credential from the same geographic region.

Verifier Caching

It is possible for verifiers to increase the privacy of the holder whose verifiable credential is being checked by caching revocation lists that have been fetched from remote servers. By caching the content locally, less correlatable information can be inferred from verifier-based access patterns on the revocation list.

Content Distribution Networks

The use of content distribution networks by issuers can increase the privacy of holders by reducing or eliminating requests for the revocation lists from the issuer. Often, a request for a revocation list will be served by an edge device and thus be faster and reduce the load on the server as well as cloaking verifiers and holders from issuers.