Sovrin : digital identities in the blockchain era
(2016)

In this paper we describe a practical digital identity project of a global scale, which solves a number of privacy and scalability problems using the concepts of anonymous credentials and permissioned blockchains. Even though both ideas have been known and developed for a number of years, our system appears to be the first amalgamation. The prototype has been developed, tested, and published as open source. I. DIGITAL IDENTITY: HISTORY AND CHALLENGES The idea of digital identity can be traced to the beginning of the computer era, when the user profiles were first transferred across networks. In the real world, different authorities issue licenses, passports, identification cards, credit cards, checks, etc., generally called credentials, to ordinary users for their presentation to various service or goods providers. This brings the concept of Issuer, User, and Verifier as subjects of the identity system. It immediately became clear that issuance, storage, and presentation procedures must follow a number of security requirements to be competitive with the traditional paper credentials: • Compatibility. Credentials issued by different Issuers can be combined for a single presentation by User who is required to prove several properties simultaneously: e.g. that he is at least age 18 employed by XYZ Corp. with a driver license and good eyesight (does not require corrective lenses). • Unforgeability. A malicious User is unable to present a credential not issued by a legitimate Issuer. • Scalability. A system must handle hundreds of Issuers and billions of Users, such as an international passport system. It might be required to handle thousands of transactions per second like the Visa system [1]. • Performance/Low latency. Verification of credentials must be almost instant and not require broadband network connectivity per credential, even if it is issued by a previously unknown Issuer. Credentials can be stored and processed easily by the User even if he is offline. • Revocation. An Issuer can revoke any credential such that a User and any Verifiers can know within a reasonable amount of time that credential was revoked. Additionally, a digital identity system could provide features impossible or difficult to implement in a paper identity system: • Minimal dependencies. Aside from an earlier issuance, an Issuer should not be involved during the preparation and presentation of proofs, and the verification of credentials, including proof of nonrevocation. • Privacy/Anonymity. The real identity of a User can be kept secret from Verifiers who do not need it. • Unlinkability. Different presentations of the same credential cannot be linked together. • Selective disclosure. Any subset of attributes embedded in a credential can be kept secret from Verifiers. The latter group of properties is particularly attractive for Users from authoritarian countries or those who are concerned about leaks of their data from careless Issuers or Verifiers. The privacy-oriented digital identity schemes have been proposed as U-Prove [2] (mainly Microsoft, primarily based on Brands’ credentials [3]) and Idemix [4] (mainly IBM, primarily based on the Camenisch-Lysyanskaya credentials [5]), with the ABC4Trust and FIDO [6] projects encompassing these two. Despite significant effort expended on both projects, neither is in widespread use today. We deduce that all these systems lack compatibility and scalability, as an actual implementation would require a meta-system that congregates multiple Issuers and Verifiers and manages credential schemas. Before recently, all such system would require a (trusted) global third party for the exchange and distribution of Issuers’ data and parameters. It seems that such a centralized party on a global scale could not exist. II. OUR CONTRIBUTIONS We designed and implemented a system called Sovrin, which integrates anonymous credentials with revocation [7], [8] for privacy, unforgeability, performance, unlinkability and a distributed ledger, taking best practices from Ethereum [9] and BFT protocols. The implementation is mostly finished and will go live in the near future. A. Anonymous credentials for privacy It is well known that the anonymity and unlinkability properties are provided by various kinds of anonymous credentials, the concept dating back to seminal works by David Chaum in 1980s [10] and refined in a number of follow-up papers including well-known [3], [7], [11]. Zeroknowledge proofs allow a User to prove the possession of a credential without showing the credential itself, thus providing unlinkability. Additional features include delegation [11] and revocation [8]. We reference the Idemix specification [4], [12] as the basis for our anonymous credential module as it provides unlinkability by default (in contrast to U-Prove). Although Idemix is available as a Java library, for portability and fast prototyping we select the Charm framework [13], which provides a Python API for large integers, signature schemes, and pairings. It also allows us to integrate the pairing-based revocation module easily. B. Our treatment of the revocation feature The revocation feature was missing in the original papers behind U-Prove and Idemix and was added later in different ways. The revocation procedure assumes that each credential has special Revocation-ID attribute with value iR, and Issuer can at any moment revoke a particular iR. For Verifiers this means that if a User with a revoked iR presents his credential, this can be detected by the Verifier. We observe that in addition to various drawbacks described above, the revocation feature provides quite a privacy leak. Indeed, consider a typical attack setting: a Verifier colludes with an Issuer to disclose the identity of a User. The Issuer then revokes half of the issued credentials, and the Verifier asks the User to update his revocation data. If the User succeeds in presenting a valid non-revocation proof, he is among the users with non-revoked iR. Then the Issuer reinstates the earlier revocations and revokes another group of revocation IDs of equal size. Repeating this procedure logN times, the Issuer-Verifier team can uniquely identify one of N users. C. Our selection of revocation methods Since 2001, the following revocation methods have been proposed: • Signature lists [14]. Issuer regularly releases a list of signatures, one per non-revoked iR. User proves that his credential has the same ID as in some signature. Verification is fast, but the amount of data retrieved by User and computation he does is huge, and multiple presentations are linkable. • Cryptographic accumulators [7], [8]. The issued iR is added to (or removed from) a constant-size accumulator A, and a User must prove that his (non-disclosed) ID is still contained in A. This approach is reasonably fast for all parties. • Forward revocation lists [15]. For each revoked iR, an Issuer generates a revocation entry f(iR). A User presents a non-revocation proof to a Verifier, who then tests the proof against every entry in the list. If all matches fail, the credential is deemed valid. This method requires significant computational resources from the Verifier. We decided to use accumulators based on bilinear maps [8] for performance reasons. The small order of the target group allows for short accumulators and witnesses. We have our own implementation of accumulators, which is based on a corrected version of paper [8]. The drawback is that the User must be aware of all revoked credentials, as the proof is updated every time another credential is revoked and needs (public) Issuer-specific data for the update. If User has small capacity, the data he needs to update the nonrevocation proof reveals his ID. Existing research papers suggest User connecting to Issuer every time before creating a non-revocation proof [8], which is privacy-vulnerable if Issuer or his agent colludes with Verifier. D. Revocation with attribute-based sharding. The accumulator-based revocation procedure requires the User to maintain his non-revocation data w using the indices {iR} of the credentials revoked and issued from the last update. To update w the User also needs to access a global set G = {gi} of validity tails, published by Issuer. The tail set G is immutable but should be generated in advance and occupy quite big space (256 bytes per credential). Even though the number of tails needed for the update is proportional to the number of revoked credentials in the period, the tails retrieved by the User effectively disclose his own index iR and thus his identity. For a global Issuer the User would be unable to carry the entire set of tails at his device, as they would require GBytes of storage. To prevent the privacy leak, we propose to partition the credential IDs I into shards I1, I2, . . . , Is of limited size so that the tail set G(Ij) for each shard would be feasible to download and carry (say, a dozen of MBytes). Together with the credential to present, the User will then inform the Verifier of his shard number j so that the Verifier uses the corresponding accumulator data Aj . To make the shard index privacy-oblivious, we suggest attribute-based sharding, when Issuer selects q attributes {ai} of necessary granularity (year of birth, zip code, etc.) and partitions the credential set by each ai independently. For each attribute ai and each shard an accumulator Ai,j will be published. Nevertheless, since accumulators are of constant size, the total amount of space consumed by q× s accumulators is negligible. At the time of presentation the User selects the attribute on which he will prove the nonrevocation. This attribute should be among those that are already disclosed to the Verifier. Before presentation, User downloads the entire set Gi,j of tails that correspond to his share j at attribute i. As the tails are signed, he ask the Verifier to download, and this does not reduce the privacy. We also implement the revocati