Zero-Knowledge Magic for Cheap

So you arrive at this club, but you forgot your ID and the bouncer is staring.
If only you could prove you’re old enough without revealing too much info.

Well, that’s exactly what zero-knowledge proofs do.

TL;DR:

• You can now use Starknet to verify zk-SNARKs
• Starknet is the cheapest web to publish zero-knowledge proofs¹
• Profit? You heard it here first.

The ZK Starter Pack 🎒

We’re going to need 3 ingredients.

Starknet is like a super-powered highway where complex smart contracts can run fast for cheap. Think of it as Ethereum’s speedy cousin.

Circom² is your neighborhood proof builder. It lets developers write programs that can hide some of their inputs.

Garaga is Starknet’s proof checker. Like a very sophisticated bouncer who can verify mathematical proofs directly on Starknet.

How It All Works Together 🔄

First, we need to code the computation we want to check in a language supporting zk-proofs. Such languages allow to specify private inputs, and can be compiled into what we call a zk-circuit.

a ZK-circuit acting as a black box

Then, we need to chose a framework to generate and verify proofs, depending on whether you only need local verification or if you prefer to publish proofs on-chain for everyone to see.

So the flow is like this:

1. 🧑‍💻 Code and compile your zk-circuit
3. 🧮 Prove: Generate a proof
4. 🏗️ Deploy a verifier on-chain
5. ✅ Verify: Publish and verify a proof on-chain

DO NOT READ the rest if you want to keep the magic intact. 🙈

One (Cairo) Step At A Time ✨

Step 1: Create your Circuit

pragma circom 2.0.7;

include "../../node_modules/circomlib/circuits/comparators.circom";
include "../../node_modules/circomlib/circuits/poseidon.circom";

template Auth() {
    signal input password;
    signal input hash;
    signal output out;

    component hasher = Poseidon(1);
    hasher.inputs[0] <== password;

    // Add the hash to output for testing
    out <== hasher.out;

    component eq = IsEqual();
    eq.in[0] <== hasher.out;
    eq.in[1] <== hash;

    1 === eq.out;
}

component main {public [hash]}= Auth();

This Circom program verifies someone knows a password by checking it against its Poseidon hash value.

*Bonus Points:* Try to make it work on zkrepl.dev, click here to generate Poseidon hashes.

Once compiled, you get a private proving key and a verifier key.
Now, given a private input,

{
  "password": "0x476172616761526f636b73",
  "hash": "137293068078....58724960716461"
}

you can generate a proof on your machine using the proving key:

• a proof file in the groth16 format proof.json
• all public inputs in the file public.json

Technical deets: Proof generation can also be done using zkrepl.dev. Also, git clone one this repository to generate a proof locally using the snarkjs framework.

Now, the zk-magic ensures two things:

1. Anyone can verify this proof and be sure you know the password
2. Nobody can learn the password by just looking at the proof.⁴

Step 2: Write a verifier with Garaga

Now that we’ve got our proof.json, let’s deploy a verifier on Starknet to publish the proofs for everyone to see.

1. First, Garaga can auto-generate a Starknet verifier contract for your circuit. We only need the verifier key tied to the compiled circuit:
   garaga gen --system groth16 -vk verification_key.json
2. Declare the verifier using, no need to deploy yet. You can use:
   starkli declare target/dev/verifier.contract_class.json
3. Use the verifier inside your contract to deal with proofs

fn verify_login(proof: Span<felt252>) {
  // Get the caller 
  let caller = get_contract_address();
  // Get the verifier implementation
  let class_hash = self.verifier_class.read();
  let garaga_verifier = IVerifierLibraryDispatcher { class_hash };

  // Check the proof
  let result = garaga_verifier.verify_groth16_proof_bn254(proof);
  assert!(result.is_some(), "invalid proof");

  let expected_hash = *result.unwrap()[0];
  assert(self.hash.read(caller) == expected_hash, "Wrong authentication")
}

4. Publish a proof using Garaga CLI to generate the transaction data and send the transaction with starkli.

garaga calldata --system groth16 \ 
                --vk verification_key.json \ 
                --proof proof.json \ 
                --public-inputs public.json

Wait a second?!🫴

We didn’t solve the initial “I’m over than 21 year-old” problem did we?
Indeed, but we’ve shown two things:

1. The difficult part of zk-apps is writing the checker circuit.
2. Anything is possible. Use OpenPassport to access a citizen’s birth-date privately, or just use their API to create the proof without the hassle.

Starknet fees and Garaga state-of-the-art optimizations makes this cheap.
Cost table:

• Deployment: ~$5 USD
• on-chain proof verification: < $1 USD

A challenge, brother? 🤺

Ready for practice? Prove it and get rewards.

Show that you can factor integers by sending a zk-proof of factorization of your Starknet address to this contract: Challenge Contract

You must provide a list of 32 integers whose product equals your address.

For instance, if your address is 0x31337 = 201527 in decimal,
possible factors are 1, 137, 1471, 201527.
One valid input is: [201527,1,1,1,1….,1] (31 ones)

The more factors, the bigger the score, and the reward.
Factors of 1 don’t count, format your input as an array of 32 integers.

Check the zk-mint repository for more clues on how to generate and publish proofs.

Tweet at https://x.com/tek_kac if you manage to solve :)

Footnotes:

[¹] … cheapest … that I know of, don’t quote me on that.
[²] We use Circom but other zkDSL³ are handled by Garaga: Gnark or Risc0
[³] zk-DSL: Zero-Knowledge Domain Specific Language.
[⁴] Trust me for now, the mathematical proof doesn’t fit in this footnote.