# Considerations about Anonymous credentials

# Introduction
We give an overview of what we desire from an anonymous credential system, how the desired properties may be in contention with each other, and explore a few known anonymous credential systems discussing their strengths and weaknesses.

## Desired properties of an anonymous credentials system
An anonymous credential system should ideally have the following properties:

- **Unlinkable & Untraceable:** A verifier learns nothing about the credential holder other than the fact that they hold a valid credential. Furthermore the credential issuer should not know when a (particular) credential they issued is in use.
- **Selective disclosure:** The credential may contain several attributes which a holder may disclose only a subset of.
- **Predicates:** The holder may disclose that an attribute is less than, equal to, or greater than a specified value without revealing the attribute itself.
- **Key binding:** The holder can prove that all of the presented credentials are bound to the same secret that is not known to anyone else.
- **Revocability:** There is a way for an issuer to revoke a credential they issued. It should ideally be possible for a holder, a verifier (that the issuer trusts), or the issuer themselves to initiate this revocation process. The revocation mechanism should ideally preserve the privacy of all parties involved (holder, issuer and verifier).
- **Interoperability:** It should be possible to issue credentials without having to commit to a particular SSI framework/implementation.
- **(Optional identity on demand):** By collaborating with the issuer and/or a revocation authority it is possible to disclose the identity (or at least a recognizable pseudonym) of an (anonymous) credential holder.
- **Privacy preserving for the verifier:** The verifier cannot be tracked by the credential issuer upon credential verification.
- **Efficient proof generation:** The holder can efficiently compute proof of knowledge with the resources available to them (PC, smart phone, maybe even IoT device)
- **Efficient verification:** The verifier can efficiently verify a proof of knowledge with the resources available to them (cluster, server, possibly a PC, smart phone or even IoT devivce).
- **Efficient issuance:** Issuing a credential should be fast under realistic hardware constraints for the issuer (and the holder in case of an interactive process).
- **Efficient revocation:** Revoking a credential should be a fast process for all parties involved.

At a first glance the desire for the *key binding* and *identity on demand* properties may not be entirely clear hence we elaborate a bit more on these now. The *key binding* property is the privacy preserving equivalent of the `CredentialSubject["id"]` property in a standard (non-anonymous) verifiable credential. Normally when verifying a presentation we check that the holder corresponds to the subject on all the credentials in the presentation. Similarly when verifying an anonymous presentation one can prove in zero knowledge that all the anonymous credentials contained in the presentation are bound to the same key. This helps the verifier trust that the presenter is not aggregating credentials issued to different identities.

The *identity on demand* property can be desirable if a user starts breaking the terms of use of a service they got access to by presenting anonymous credentials.

Note that the entries in the list of desirable properties are not necessarily independent of each other and can be in contention. Selective disclosure should be seen as a privacy enhancing feature, rather than privacy guaranteeing. Revocation can be in conflict with the untraceable property especially if it requires holders and/or verifiers to go online. Finally using a signature scheme that easily supports predicates may lead to significantly less efficient proof generation.

## Zero knowledge signature schemes
The anonymous credential systems in use typically rely on proving in zero knowledge that one has a signature on a hidden secret. The two signature schemes mostly discussed in the context of anonymous credentials within SSI are CL02 signatures and BBS+.
### CL02
This signature scheme was introduced in the paper "A signature scheme with efficient protocols" by Jan Camenisch and Anna Lysyanskaya. This is one of the first signature schemes to be used in the context of anonymous credentials in production.
#### Properties
- Compatible with selective disclosure
- Compatible with key binding
- Compatible with predicates

#### Prior art
- [IBM Idemix](https://abc4trust.eu/index.php?option=com_content&view=article&id=187)
- [IRMA](https://petsymposium.org/2017/papers/hotpets/irma-hotpets.pdf)
- [Hyperledger Indy](https://github.com/hyperledger/indy-hipe/blob/main/text/0109-anoncreds-protocol/README.md)
- PoC by a research partner

#### Standardization
To the best of our knowledge there is no ongoing standardization effort to prescribe how such signatures are to be represented in a verifiable presentation.

#### Performance indicators:
Idemix (based on CL signatures): Presenting + Verifying a credential with five attributes in zero knowledge using 1024 bit key size takes around 120 ms in total (Intel Core i7 1.8 GHZ, 2 cores, L2 cache/core 256 KB, L3 cache 4 MB, memory 4 GB 1333MHZ DDR3, Mac OS X). This scales linearly with the number of credentials. Disclosing attributes is relatively cheap (just a few ms more per attribute). The effort distribution is about 55% for proving and 45% for verifying. See "Evaluation of Privacy-ABC Technologies - A Study on the Computational Efficiency" by "Fatbardh Veseli and Jetzabel Serna". This paper states that their experiment shows that doubling the key size decreases efficiency by a factor of four on average.

IRMA (built around Idemix which is based on CL signatures): Presenting + Verifying with a credential with three attributes in zero knowledge using 4096 bit keys takes about 1.3 seconds (Intel Core i7-8650U CPU with 16 GB of RAM GNU/Linux) according to the paper "EL PASSO: Efficient and Lightweight Privacy-preserving Single Sign On" by Zhiyi Zhang, Michał Król, Alberto Sonnino, Lixia Zhang, and Etienne Rivière. The same paper also measures the performance using a Raspberry PI model 3b (RPI) with an A53 quad-core ARMv8 CPU and 1 GB of RAM. In this case Presenting + Verifying the same credential takes about 34 seconds. Cheapish smartphones and tablets frequently have SoCs (system on chip) containing between 4 and 8 A53-cortex processors thus we still expect proof CL-based proof generation and verification to both take seconds on many popular mobile devices.

#### Technical implementation considerations
Issuance of anonymous credentials based on CL02 signatures require prime generators and all other relevant operations such as proof generation and verification operate on large integers due to the RSA based nature of this signature scheme. There is limited support for big integers in the Rust ecosystem and finding something that is both portable (i.e. it can be compiled to Wasm) and reasonably performant may be a challenge. On the other hand we have a PoC in Python supplied by a research partner and [Hyperledger Ursa](https://github.com/hyperledger/ursa) has implemented many aspects of CL signatures in Rust that may possibly be adapted to be used in the Iota Identity framework.

### BBS+ signatures
The BBS+ signature scheme (inspired by the BBS scheme due to Boneh et al.) was introduced in "Constant-size dynamic k-TAA" by Man Ho Au, Willy Susilo, and Yi Mu. Furthermore the paper "Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited" by Jan Camenisch , Manu Drijvers and Anja Lehmann introduced a more efficient way to prove knowledge of BBS+ signatures.

Although this signature scheme does not directly support predicates and is therefore perhaps somewhat less flexible than CL02 signatures, it is known to be significantly more efficient.

#### Prior art
- [MATTR](https://github.com/mattrglobal/bbs-signatures) offers (currently experimental) selective disclosure utilizing BBS+ signatures backed by the [bbs crate](https://crates.io/crates/bbs) (from Hyperledger).
- [Hyperledger Fabric is now using an implementation of Idemix with BBS+](https://hyperledger-fabric.readthedocs.io/en/release-1.3/idemix.html#underlying-cryptographic-protocols)

#### Properties
- Compatible with selective disclosure
- Compatible with key binding
- Does NOT directly support predicates
- More efficient than CL02

To overcome the lack of (direct) support for predicates issuers may issue credentials with ambiguous fields such as for instance "older than 18 years".

#### Standardization
The Credentials Community Group at the W3C is currently working on the [BBS+ Signatures 2020 specification](https://w3c-ccg.github.io/ldp-bbs2020/) which utilizes BBS+ signatures to describes how to derive proofs of possession of anonymous credentials with support for selective disclosure. Moreover [this post](https://www.evernym.com/blog/bbs-verifiable-credentials/) advocates for it to be adopted universally by SSI implementers. On the other hand the aforementioned blog post also points out that there is still work left to be done at this point. Perhaps most importantly one has yet to decide on a privacy preserving revocation strategy.

#### Technical implementation considerations
We could consider using the [bbs crate](https://crates.io/crates/bbs), but this crate is not yet stable and has to the best of our knowledge not received an audit yet.

## Revocation schemes for Anonymous credentials
The article "Scalable Revocation Scheme for Anonymous Credentials Based on n-times Unlinkable Proofs" explains nicely the different categories of revocation schemes available for anonymous credentials with different pros and cons. Let us quickly consider a few of these here:

### Credential identifiers/revocation list
Each issued credential has a unique identifier that has to be disclosed. The verifier checks whether this identifier has been added to the issuer/revocation authorities revocation list. This is a simple approach, but it has the downside that the holders transactions then become linkable.

#### Prior art
- Microsoft U-Prove (TODO: Link citation)
- WIP for standard credentials in IOTA Identity (https://github.com/iotaledger/identity.rs/pull/861)

### Credentials with lifetimes
The issuer issues credentials that are valid for a short period of time which requires the user to frequently renew their credential with the issuing authority which is in contention with the system being untraceable and unlinkable. This also has the downside that revocation cannot instantaneously take place, but most revocation schemes suffer from this problem.

#### Prior art
- Some implementations of IBM Idemix (TODO: Add citation).
- The solution presented by a research partner offers this kind of revocation. Note that their proposed solution does not require the entire credential to be issued again, one just updates a single attribute. The technical paper we received mmentions that the issuer could alternatively publish updates to the ledger (presumably by updating their DID Document?), but the message size on ledgers are typically rather small (32KB max for the Tangle) hence this alternative way will most likely not be suitable when there are thousands of credential holders.

### Cryptographic accumulators
A user proves efficiently in zero knowledge that they are part of an encrypted set of valid users. The downside here is that if any user gets revoked then the accumulator must be recomputed and also a witness per valid user which requires provers to go online to update their witness. A witness file will typically be too large to be stored on-chain.

#### Prior art
- Hyperledger Indy Anonymous credential revocation: Uses the [CKS accumulator](https://eprint.iacr.org/2008/539.pdf). This scheme has much faster witness updates than other accumulators (see "Performance Analysis of Accumulator-based Revocation Mechanisms" by Jorn Lapon, Markulf Kohlweiss, Bart Decker and Vincent Naessens). On the other hand the size of the public key is linear in the maximum number of values that can be accumulated. Although most protocols do not need the state information contained in the public key, it is necessary for witness updates. Hence in the case of massive deployments witness updates will require special purpose servers. Hyperledger Indy uses Tails files to accommodate for witness updates. See [the explanations in the bcgov/indy-tails-server repository](https://github.com/bcgov/indy-tails-server) and [the RFC here](https://github.com/hyperledger/indy-hipe/tree/main/text/0011-cred-revocation) for further explanations. Note the former of the two aforementioned resources mentions that with a revocation registry size of 32768 (the maximum number of accumulated values) proof generation takes about 7 seconds using the Lissi-Wallet on an iPhone 12 pro.

### Revocation list of private keys
This approach is similar to the Credential identifiers approach, except that instead of using an identifier the credential contains an additional field with a private key/revocation handle (known by the issuer (TODO: in all implementations?)) which is never disclosed in an open form (utilizing zero knowledge proofs). When the credential gets revoked this private key gets added to a list which all verifiers have access to and verifiers can check in `O(Number of revoked credentials)` time whether the credential they are presented is revoked. The downside to this approach is that if a credential gets revoked, then all past and future uses of this credential becomes linkable. A somewhat oversimplified explanation of how this works is that verifiers have a one way function which they place each entry of the list of revoked keys into and see if the result matches the proof they were sent from the holder.

### N-times unlinkable proofs:
This can be thought of as something in between the cryptographic accumulator and lifetime approach. A benefit over the lifetime approach is that in this case the user does not need to renew their credentials if they are not revoked. The user is also not required to recompute a witness in contrast to the cryptographic accumulator approach and can stay completely offline after receiving their credential. The verifier will however need to go online and fetch an encrypted revocation set each epoch. The size of this revocation set scales linearly with the number of revoked users and is up to 7.5 MB in the case of 10'000 revoked users, hence it can unfortunately not be stored on-chain. Furthermore the N-times unlinkable proofs offers identity on demand, as well as issuer, verifier and user driven revocation. Another interesting property is that the user may only anonymize themselves N-times per epoch which could be seen as a feature or a bug depending on the application. The implementation by Camenisch et al. uses weak Boneh-Boyen signatures, but they mention that it also works with other signature schemes.

Note the various trade offs involved with the different revocation schemes. Either the holder's transactions become linkable, or the issuer needs to frequently reissue credentials, or some encrypted revocation set needs to be fetched by either the user or verifier. If the issuer/revocation authority needs to be contacted by either the prover or verifier then this can have privacy implications as the issuer/revocation authority may decide to store ip addresses. Hence we need to decide on which trade offs we want in order to implement revocation.