Anonymous Credentials with Zero Knowledge Proofs (ZKPs) on the Factom Protocol

Secured
#1
The following was written by @Valentin Ganev of Factomatic and is being reposted with their permission.
______________________________________________________________________________________________________________

Zero-knowledge proofs (ZKPs) are a family of probabilistic cryptographic protocols, which allow one party, the prover, to demonstrate to another party, the verifier, that they know some secret without revealing any information about it. Specific protocols exists which allow, e.g.:
  • passwordless authentication & authorization without exchange of any sensitive information over the Internet, which can be used for generic logins or for access to particular resources
  • proof of knowledge of a private key corresponding to a public key, without generation of a digital signature, which can be used as a building block for privacy-preserving applications, such as anonymous on-chain voting
  • range proofs, i.e. proofs which check if a given number is in a given interval, which can be used for proving liquidity, without disclosing exact holdings, amongst others
In addition to this, more powerful protocols exist (such as zk-SNARKs, zk-STARKs and Bulletproofs), which allow the verifiable execution of an arbitrary computer program. Recent theoretical advances and an increasing number of ZKP libraries enable a growing number of applications. One of them -- anonymous credentials -- we describe next.

Imagine you have a digital identity/identity credential issued to you by the government (this is not science fiction, it's happening now, e.g. in Estonia). It contains all your personal details: date of birth, address, etc. Then, let's say you want to use some service which requires you to be over 18 (e.g. betting website). The way this usually works is that you have to undergo some form of KYC process in which you disclose a lot of personal information, which might not strictly be required. Using a digital identity and a zero-knowledge proof, you can demonstrate to anyone that you're above 18, without revealing any other information (and without the hassle of sending pictures, etc.). The scheme would proceed as follows:
  • the government (or another trusted authority such as a bank or a telecommunication company) issues you an identity credential that is sent to you encrypted with your public key. It can be sent via an off-chain channel, or it could be recorded on-chain (potential EC usage)
  • the trusted authority records a signed hash of the identity credential on-chain; this is mandatory for the protocol to work (EC usage)
  • the person trying to authenticate as being over 18 to some service, runs in zero-knowledge the following computation, which has as a secret parameter the plain text of the identity credential, and as public parameters the age threshold and the hash of the credential:
    • hashes the plain text and ensures that the hash matches the publicly available hash (this proves that the person running the computation knows the plain text and is using the correct input)
    • extracts from the plain text only the age of the person
    • compares the extracted age with the publicly available age threshold and returns True if the condition is satisfied, False otherwise
  • the person trying to authenticate records the proof on-chain, such that anyone can verify it (EC usage)
  • the service provider verifies the proof
More generally, the Factom blockchain is the ideal layer for recording ZK proofs, such as the above, because a proof is pure data: it is a bunch of numbers, together with a bunch of publicly available checks to run on those numbers. Furthermore, the Factom blockchain is ideal for recording the data commitments (such as the hash of the identity credential). Our vision is that -- if zero-knowledge protocols are to take off -- there is virtually limitless potential for such commitments to be stored and utilized in verifiable computation:
  • you can store a "proof of funds" commitment from a bank for any individual (EC usage). The individual can then prove that they have a balance of above X without revealing their exact holdings (useful for all sort of large purchases or as part of a proof that you qualify as an accredited investor).
  • you can do proofs of liquidity of exchanges, as described here: http://www.jbonneau.com/doc/DBBCB15-CCS-provisions.pdf (requires commitments from the exchange => EC usage)
  • you can do real-time compliance: by committing to a collection of sensor readings on-chain (EC usage), any entity could prove in zero-knowledge that all their sensor readings are within certain bounds (could also be used for insurance)
Overall, we believe Factom is the perfect data layer for such applications. So far, people have concentrated mostly on building applications which are entirely data-centric. We think there is potentially huge value to be unlocked by using data recorded on the Factom blockchain, as the basis for verifiable computation.