# Cheap Zero-Knowledge Magic ... (and a puzzle to solve 👀).

Source: https://medium.com/@tekkac/zero-knowledge-magic-on-starknet-56ac2453234f

## Summary

This tutorial shows how to build a zero-knowledge proof that a user knows a password, then verify it on Starknet using Garaga, at a stated cost of about $5 for deployment and under $1 per proof verification. It walks through writing a Circom circuit that checks a password against its Poseidon hash, generating a Groth16 proof, and generating a Starknet verifier contract with Garaga's CLI. The author notes that writing the checker circuit is the difficult part of zk-apps. The article closes with a challenge: submit a zk-proof that a Starknet address factors into up to 32 integers whose product equals the address, with more factors earning a bigger reward.

## Article

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:

Anyone can verify this proof and be sure you know the password

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.

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

Declare the verifier using, no need to deploy yet. You can use: starkli declare target/dev/verifier.contract_class.json

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:

The difficult part of zk-apps is writing the checker circuit.

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.