Zero-knowledge credentials with deferred revocation checks

AbstractThis whitepaper (written by authors affiliated with Microsoft Research and Microsoft Identity) presents zero-knowledge credentials in the setting where the issuer and the holder of the credential hold DIDs. Some interesting properties of this construction are: 1) Deferred revocation property: the verifier can check the revocation status of the holder’s credential in an asynchronous way without the holder’s participation. 2) The verifier can check if the credential of a holder has been reused in the past, even if the holder used the credential for different DIDs. The main limitation of this paper for our case is that the issuer is considered trusted and needs to sign a message or retain a private state.
Year2020
Link to the paperhttps://github.com/decentralized-identity/snark-credentials/blob/master/whitepaper.pdf
Relevance scoreRelevant
Quality score4
LabelsAnonymous CredentialsCentralized/permissionedSybil resistance insights


Melissa Chase, Esha Ghosh, and Srinath Setty, Microsoft Research

Daniel Buchner, Microsoft Identity

July 2020

https://github.com/decentralized-identity/snark-credentials/blob/master/whitepaper.pdf

This paper presents a construction for zero-knowledge credentials in the decentralized identity (DID) setting, where the holder can establish different DIDs with the issuer and the verifier. The main contribution of this construction, compared to related work such as Sovrin, is that the verifier can check if a credential is revoked without the user’s participation (by contacting the issuer in an asynchronous way). Moreover, one interesting property of this construction is that the verifier can check if the credential of a holder has been reused in the past, even if the holder used the credential for different DIDs. The main limitation of this paper for our case is that the issuer is considered trusted and it needs to sign a message or retain a private state.

Terms

Issuer: issues a credential

Holder or user: acquires credentials from one or multiple issuers

Verifier or relying party (RP): verify claims about users’ credentials made by users

Examples discussed in the paper

1) credentials related to CV on a career networking app.

In this example the holders of the credentials do not care about disclosing their work history. The verifiers should be able to verify signed statements by the issuers (Unforgeability property) and the status of the credentials e.g. if they are active or revoked :

If the operators do not care about disclosing their actual performance or reputation and correlating it with their DID, then this case would be of interest to our case.

2) proving age to gain access to services (e.g. online purchases or alcohol ).

The holders want to prove that they are over 18:

3) Banks make automated and recurring checks that loan holders maintain home insurance.

Credential

It is a set of key-values tuples (name of the attribute, value of the attribute)

e.g. (Date of Birth, 5/10/2000). A claim for this credential could be that the holder is over 18.

Desired Properties

  1. Unforgeability. The user cannot forge a credential created by the issuer. For example, a pool operator cannot create a fake certification for good performance.
  1. Unlinkability: A coalition of RPs is not able to correlate the activities of a user across multiple RPs.
  1. Minimal Disclosure: The user reveals to the RP only what is necessary (e.g. only that it is older than 18). For example, a pool operator can reveal that it has a good reputation without revealing actual data.
  1. Privacy against issuer: The issuer cannot learn if the user has used its credential and to which RP. For example, the issuer cannot track if/when the operators have used the performance certificate to join a pool.
  1. Revocability: The issuer can anytime revoke a credential (and make it invalid) without the cooperation of the user. For example, the issuer can revoke a certificate of good performance or good reputation when the operator does not have good stats for an extended period.
  1. Deferred and offline revocation checks: The RP can check if a credential is active (has not been revoked) or that a credential of a new user is valid in an asynchronous way without demanding the user to participate.

Asynchronously means that RP does not need to contact the issuer at exactly the time it wants to check the status of the credential. In this case, the revocation status is according to the last time the RP contacted the issuer.

Example. Assume that an operator wants to prove to Lido that it has good performance certified by an issuer. Then Lido could check if the credential of good performance has been revoked based on the last time it contacted the issuer. If later Lido contacts the issuer again and realizes that the credential of this operator has been revoked, then it can revoke the right of the operator to run a validator in an asynchronous way. This reduces the cost because Lido could contact the issuer only at regular intervals and not each time new operators join. Also, Lido could check if the performance credentials of the operators have been revoked without contacting the operators. Please note that in this construction the issuer holds a private state and/or needs to digitally sign which means that it is not obvious how an issuer can be replaced by a performance oracle.

  1. Protection against credential reuse: An RP can check if the same credential has been used by different DIDs. Also, RP can prevent users from using a credential related to a DID twice.

So if Bob gives the credential (and his secret key) that corresponds to his DID to Kevin, and Kevin uses this credential, then Bob loses the right to use this credential again.

This property can be useful to prevent an entity from creating multiple validators with the same DID or using the same performance or reputation credential with different DIDs. If we could guarantee that each DID corresponds to a single entity then we could mitigate Sybil attacks. One solution to this could be using Proof of Work puzzles for each DID)

Assumptions

Cryptographic Tools

Zero-knowledge Proofs, Digital Signatures (ECDSA), Hash Functions, e.g. SHA-256, SNARK Spartan (CRYPTO 2020).

Overview (A simplified construction)

The construction has two options:

  1. The RP does not need to contact the issuer at all, but it cannot check if the credential has been revoked. This could be of interest to our case if the performance certificates are valid only for a specific period, so they do not have to be revoked when the operator misbehaves. However, in this case, the pool operator has to resubmit its credentials at regular intervals.
  1. In this option, the RP should contact the issuer in an asynchronous way, but the scheme provides Deferred and offline revocation checks.

The user authenticates a DID with the issuer. It will retain the same DID when it interacts with the issuer, but it can change the public key that corresponds to this DID. Moreover, the user can use different DID to interact with RP.

Issuing credentials

The issuer picks a random rr and signs a credential c=c= (Date of Birth, 5/10/2000), with its private key. It sends the signature and rr to the user.

Then the RP (e.g. Lido) can download a digest d=H(DIDLidocr)d=H(DID_{Lido}||c||r) from the issuer.

Comments: the issuer should retain a private state, so it cannot be a smart contract.

Presenting credentials and verifying their validity

The user sends to the RP the following:

RP will :

If RP cannot access the issuer and/or does not care about deferred and offline revocation checks then:

the user will send a zero-knowledge proof that it knows a credential cc and a digital signature σ\sigma such that Verify(PKI,c,σ)=1Verify(PK_I,c,\sigma)=1, where:

Presenting claims about credentials and verifying their validity.

The user provides a ZK SNARK to prove that cc  included in dd satisfies certain claims.

For example, if c is the exact stats of the pool operator, the claim would be that the pool operator has a good reputation.

Reuse protection

If we want reuse protection then each user has a pseudonym for each RP. This pseudonym will be equal to H(DIDRP,r)H(DID_{RP},r), where rr is the randomness that was used in d=H(DIDLidocr)d=H(DID_{Lido}||c||r). the user proves with zero knowledge that indeed it used rr in dd  to construct its pseudonym.

Full Construction

Source: https://github.com/decentralized-identity/snark-credentials/blob/master/whitepaper.pdf
Source: https://github.com/decentralized-identity/snark-credentials/blob/master/whitepaper.pdf
Source: https://github.com/decentralized-identity/snark-credentials/blob/master/whitepaper.pdf
Source: https://github.com/decentralized-identity/snark-credentials/blob/master/whitepaper.pdf
Source: https://github.com/decentralized-identity/snark-credentials/blob/master/whitepaper.pdf

Note that if we remove DID and public key from the issuer state and the digest, then a user could share its credential with a friend without disclosing private information to his friend such as its private key.

Moreover, the paper discusses the following inherent limitations in credential systems and also presents the weaknesses of their construction. In addition, it provides a comparison with Sovrin.

Inherent in any credential system

Inherent in any system that supports deferred revocation

In the above construction, if Bob gives a credential dd to the RP, the RP can try to find Bob’s DID from the issuer’s stake (if it has been leaked) in the following way: the RP can compute the digest that corresponds to a DID and if this digest is equal to dd, then this DID corresponds to Bob. However, in the above scheme, this attack cannot reveal the attributes of the users, because the issuer’s state includes only the salted hashes.

Inherent in any system with reuse protection and offline representation

If the credentials of the user are compromised and rr is leaked, then RP can identify all the times the user accessed the RP (using options 2,3) with the same rr.

Weaknesses

Performance

The paper presents an estimation of the proof system’s cost in the case of Spartan over a credential with 1KB of encoded attributes. The R1CS program in their test had 2152^{15} constraints and on a single CPU core of a Microsoft Surface laptop3 took under 170 ms to produce a proof of size 15KB. The proof could be verified in 17ms.

Comparison with Sovrin

In Sovrin’s construction, the issuer publishes a list of the users who have active certificates in a cryptographic accumulator on the blockchain. The user and the RP should download the latest version of the accumulator. The user proves with zero knowledge to RP that its DID is included in the accumulator.

The disadvantage of Sovrin compared to this paper is that the user should participate in order to prove that its certificate is not revoked and also it needs to download the latest version of the accumulator. Also, the RP has to download the latest version of the accumulator every time a new user appears.

On the other hand, the advantage of the construction of Sovrin is that the accumulator can be public.

As a final comment, for our case the following part of the construction could be helpful in order to mitigate Sybil attacks: each credential is connected with a specific random value rr. When the operators try to register with a verifier or RP, they provide a pseudonym that is the hash value of rr and the RP’s DID. With this technique, an RP can check that every operator uses once a single credential, even if it tries to reregister with the same credential using different DIDs.

References

  1. Zero-knowledge credentials with deferred revocation checks, Melissa Chase, Esha Ghosh, and Srinath Setty, Microsoft Research, Daniel Buchner, Microsoft Identity, July 2020 https://github.com/decentralized-identity/snark-credentials/blob/master/whitepaper.pdf
  1. Lodder, DK Michael, and Dmitry Khovratovich. "Anonymous credentials 2.0." (2019).Lodder, DK Michael, and Dmitry Khovratovich. "Anonymous credentials 2.0." (2019)
  1. Anoncreds design. https://github.com/hyperledger/indy-crypto/blob/master/libindy crypto/docs/AnonCred.pdf
  1. M. Baza, et al.,"Detecting Sybil Attacks Using Proofs of Work and Location in VANETs" in IEEE Transactions on Dependable and Secure Computing, vol. 19, no. 01, pp. 39-53, 2022. doi: 10.1109/TDSC.2020.2993769
  1. Camenisch, J., Lysyanskaya, A. (2001). An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. In: Pfitzmann, B. (eds) Advances in Cryptology — EUROCRYPT 2001. EUROCRYPT 2001. Lecture Notes in Computer Science, vol 2045. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44987-6_7
  1. Setty, S. (2020). Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup. In: Micciancio, D., Ristenpart, T. (eds) Advances in Cryptology – CRYPTO 2020. CRYPTO 2020. Lecture Notes in Computer Science(), vol 12172. Springer, Cham. https://doi.org/10.1007/978-3-030-56877-1_25