TL;DR

  • Use Circom to specify zero-knowledge "predicates" on credential attributes.
  • Circom is a DSL (Domain Specific Language) used to express computations for which zk-SNARKs need to be created.
  • Predicates are written as programs in the Circom language.
  • The programs are compiled with the Circom compiler and the artifacts are used to create zk-SNARKs.
  • The proof protocol is LegoGroth16, an adaptation of Groth16 (used by ZCash).

We have updated our anonymous credentials protocol that enables developers to express "predicates" (checks that return true or false) on credential attributes using the Circom language and then prove that these predicates are satisfied in zero-knowledge. This means that credential verifiers can check that certain credential attributes satisfy the required conditions without learning those attributes such as convincing a credential verifier that the holder is (or is not) a resident of certain cities without revealing the city or that the blood group is not AB- without revealing the blood group. In both these examples, the city and blood group were attributes of a credential and the holder convinced some facts about those without revealing them. More examples would be a holder proving that his yearly income is less than $25,000 for availing of social care where their yearly income is calculated from the pay slip of each month (adding each month's income and checking that the sum is less than desired). Similarly, the holder could prove that his yearly income is more than a certain amount to get access to a high-risk, high-reward investment fund.

Code and Examples

For folks wishing to jump right into the code, the support for Circom in LegoGroth16 is here. It has been integrated into the composite proof system here. The Typescript support is added here. The Circom circuits (.circom) and artifacts (.r1cs, .wasm) are here and here. The .r1cs and .wasm files are generated for BLS12-381 curve and wasm optimizer (wasm-opt -O3) has been run over the .wasm files. Also, we only support Circom 2.

Here are some examples that demonstrate the use of Circom along with credentials:

1. The yearly income calculated from monthly payslips is less/greater than a certain amount

2. The sum of assets is greater than the sum of liabilities where assets and liabilities are calculated from several credentials

3. The blood group is not AB-

4. The grade is either A+, A, B+, B, or C but nothing else

5. Either vaccinated less than 30 days ago OR last checked negative less than 2 days ago

6. Certain attribute is the preimage of an MiMC hash

Motivation

Previously, the expressivity of our anonymous credential proving system was limited. The holder could prove things like I have a credential(s), or certain attribute(s) across my credentials are the same or I can verifiably encrypt attribute(s) for traceability. But verifiers could not request proofs for more complicated conditions like the sum of certain attributes should be less/more than a certain value or an average of certain values is less/more than a certain value. These simple arithmetic operations might not always be sufficient and the holder might want to prove the preimage of a hash is the credential attribute, say to be used in the Merkle tree. Moreover, as library developers, we cannot imagine all the possible logic an application can require. One solution to this problem is to use a more powerful tool to express such conditions and that tool is a programming language. We wanted a developer-friendly programming language that could also be used with our proving system. We found Circom, developed by the folks at iden3, to be the most popular such language with sufficient documentation and community around it.

Developer Workflow

1. Express the predicates/arbitrary computation as a Circom program.

2. Compile the above program to get the constraints (R1CS file) and witness generator (WASM file, takes input wires and calculates all the intermediate wires).

3. Use the constraints from step 2 to generate a zk-SNARK proving and verification key of LegoGroth16.

4. Use the R1CS and WASM files from step 2 and the proving key from step 3 to create a LegoGroth16 proof.

5. Use the verification key from step 3 to verify the LegoGroth16 proof.

Steps 1-3 are done by the verifier and the result of these steps, i.e. R1CS file, WASM file, proving, and verification key are shared with any potential prover (published or shared P2P). Step 4 is done by the prover and step 5 again by the verifier.

Cryptographic Details

As mentioned in our previous post, we use LegoGroth16 protocol for creating ZK-SNARKs. LegoGroth16 is similar to Groth16 (used by ZCash), but in addition to the zero-knowledge proof, it provides a cryptographic commitment (Pedersen) to the private data (credential attributes in our case). This commitment allows us to prove that the private inputs to the proof protocol are the same as the credentials attributes using the Schnorr proof of knowledge protocol.

At a high level, the approach is to use BBS+ signatures to prove possession of a credential (knowledge of signature) and Circom to express arbitrary logic and use LegoGroth16 to get the proof of the correctness of the Circom program and use the Pedersen commitment to the witnesses in another zk-proof where I prove that the specific attributes signed under BBS+ are equal to the witnesses in the LegoGroth16 proof.

The Circom tooling however generates a Groth16 proof whereas we needed a LegoGroth16 proof. Fortunately, the Circom compiler outputs the R1CS (description of the computation) file containing the constraints and the WASM file to generate all the values in the circuit given the inputs. We use the R1CS file to do the SNARK setup, i.e. proving and verification key. This is a trusted setup and is done by the verifier. The prover uses the R1CS and WASM files and the proving key to then generate the zk-SNARK proof using our composite proof system. Here, the prover can specify which of the Circom program inputs correspond to which of his credential attributes.

We acknowledge that the verifier can create fake proofs (proof of untrue statements) as he does the trusted setup but in most cases, the verifier has no incentive to cheat itself. When this is a possibility, like in a large public system deployed by a government, care must be taken to destroy the toxic waste (trapdoor) from the trusted setup. Also, because the proofs for the Circom program are created using the trusted setup done by the verifier, these proofs are designated verifier proofs unlike the proofs with BBS+ which are publicly verifiable.

Finally, we would like developers to try this new feature to build more expressive applications which are private as well. We would love to hear what all use-cases does this tool enable for you. If you need any support writing a Circom program for your use case, please reach out to us through Github.