Wargo: Zero-Knowledge Proof Perfect Square Verification on Starknet

Wargo is a privacy-preserving application that verifies if a number is a perfect square without revealing the number itself. It combines the power of Zero-Knowledge Proofs (ZKPs) with Starknet's scalable Layer 2 infrastructure to create a privacy-focused, efficient, and cost-effective application.

Project Overview

This project demonstrates how to:

1. Create zero-knowledge circuits using Noir
2. Generate and verify proofs using Barretenberg's UltraHonk proving system
3. Deploy and interact with Cairo smart contracts on Starknet
4. Build a React frontend that interfaces with ZK proofs and blockchain contracts

Architecture

The project consists of three main components:

1. Circuit (Noir)

The Noir circuit implements the cryptographic logic that:

• Verifies an input is a perfect square using an unconstrained binary search algorithm
• Maintains privacy by keeping the actual input hidden
• Prevents replay attacks by tracking previously used inputs via Poseidon hashes
• Generates nullifiers to prove uniqueness without revealing the input

wargo/circuit/src/main.nr

2. Smart Contracts (Cairo)

Two Cairo contracts handle the on-chain verification:

Verifier Contract: Auto-generated by Garaga, this contract implements the UltraKeccakHonk verification algorithm that checks proof validity.

Main Contract: Custom contract that:

• Acts as the entry point for proof verification
• Makes library calls to the verifier contract
• Maintains on-chain state to prevent duplicate submissions
• Validates public keys and nullifiers

wargo/contracts/verifier/src/honk_verifier.cairo
wargo/contracts/main/src/lib.cairo

3. Frontend Application (React/TypeScript)

A user-friendly interface that:

• Allows users to input a number to verify
• Generates a zero-knowledge proof using Noir and Barretenberg
• Connects to Starknet wallets
• Submits the proof to the smart contract for verification
• Displays the verification status

wargo/app/src/App.tsx

Technical Stack

• Circuit Language: Noir (v1.0.0-beta.3)
• Proving Backend: Barretenberg UltraHonk (v0.86.0-starknet.1)
• Smart Contract Language: Cairo (Starknet's native language)
• ZK Tooling: Garaga (Cairo verifier generator)
• Frontend: React, TypeScript
• Libraries:
  • @noir-lang/noir_js - JavaScript bindings for Noir
  • @aztec/bb.js - JavaScript interface to Barretenberg
  • @garaga/honk - Utilities for handling UltraHonk proofs
  • starknet - Starknet JavaScript SDK

Zero-Knowledge Concepts Used

Perfect Square Verification

The circuit verifies that an input is a perfect square by:

1. Computing the square root using an unconstrained function
2. Verifying that squaring this result equals the original input
3. Producing a proof of this verification without revealing the input

Privacy Through Poseidon Hashing

The circuit uses Poseidon hash (a ZK-friendly hash function) to:

1. Create a public key derived from the secret key
2. Generate a unique nullifier for each input to prevent double-counting
3. Allow public verification without compromising privacy

UltraHonk Proving System

This project uses Barretenberg's UltraHonk proving system because:

• It offers faster proving times than UltraPlonk
• It uses less RAM during proof generation
• The higher verification costs are mitigated by Starknet's efficient execution model

Getting Started

Prerequisites

• Node.js (>= 16.0.0)
• Noir (v1.0.0-beta.3): noirup --version 1.0.0-beta.3
• Barretenberg (v0.86.0-starknet.1): bbup --version 0.86.0-starknet.1
• Garaga CLI (v0.18.0): pip install garaga==0.18.0
• Starknet CLI (for deployment)

Setup and Installation

Prerequisites

Ensure you have:

• Node.js >= 20
• Python 3.10 (for Garaga)
• Bun (recommended for package management)

Installation Steps

1. Install required tools

   # Install Bun
   curl -fsSL https://bun.sh/install | bash
   
   # Install Noir (specific version required)
   curl -L https://raw.githubusercontent.com/noir-lang/noirup/refs/heads/main/install | bash
   noirup --version 1.0.0-beta.3
   
   # Install Barretenberg
   curl -L https://raw.githubusercontent.com/AztecProtocol/aztec-packages/refs/heads/master/barretenberg/bbup/install | bash
   bbup --version 0.86.0-starknet.1
   
   # Install Starknet tools
   curl --proto '=https' --tlsv1.2 -sSf https://sh.starkup.dev | sh
   
   # Install Starknet devnet
   asdf plugin add starknet-devnet
   asdf install starknet-devnet 0.4.1
   
   # Install Garaga (you may need to use a Python virtual environment)
   python3.10 -m venv garaga-venv && source garaga-venv/bin/activate
   pip install garaga==0.18.0

2. Build and prepare the circuit

   # Build the Noir circuit
   cd circuit
   nargo build
   
   # Generate witness from sample inputs in Prover.toml
   nargo execute witness
   
   # Generate verification key
   bb write_vk --scheme ultra_honk --oracle_hash starknet -b ./target/circuit.json -o ./target

3. Generate and build the verifier contract

   # Generate Cairo verifier contract using Garaga
   cd ../contracts
   garaga gen --system ultra_starknet_honk --vk ../circuit/target/vk --project-name verifier
   
   # Build the verifier contract
   cd verifier
   scarb build

4. Start local Starknet devnet

   In a separate terminal:

   starknet-devnet --accounts=2 --seed=0 --initial-balance=100000000000000000000000

5. Deploy contracts to Starknet

   In a new terminal:

   # Generate accounts file for deployment
   curl -s http://localhost:5050/predeployed_accounts | jq '{"alpha-sepolia": {"devnet0": {address: .[0].address, private_key: .[0].private_key, public_key: .[0].public_key, class_hash: "0xe2eb8f5672af4e6a4e8a8f1b44989685e668489b0a25437733756c5a34a1d6", deployed: true, legacy: false, salt: "0x14", type: "open_zeppelin"}}}' > ./contracts/accounts.json
   
   # Declare the verifier contract
   cd contracts
   sncast declare --contract-name UltraStarknetHonkVerifier
   
   # Deploy the verifier contract (update the class hash with result from declare command)
   sncast deploy --salt 0x00 --class-hash <CLASS_HASH_FROM_DECLARE_STEP>

6. Prepare and run the frontend application

   # Copy necessary artifacts
   cp ./circuit/target/circuit.json ./app/src/assets/circuit.json
   cp ./circuit/target/vk ./app/src/assets/vk.bin
   cp ./contracts/target/release/verifier_UltraStarknetHonkVerifier.contract_class.json ./app/src/assets/verifier.json
   
   # Update contract address in App.tsx with the deployed contract address
   
   # Install app dependencies and run
   cd app
   bun install
   bun run dev

How It Works

1. User enters a secret key and input number (which should be a perfect square)
2. The application computes the public key and nullifier using Poseidon hashes
3. It generates a zero-knowledge proof that:
   • The input is a perfect square
   • The public key and nullifier were correctly derived
4. The proof and public outputs (public key and nullifier) are sent to the Starknet contract
5. The contract verifies the proof and checks that the nullifier hasn't been used before
6. If verification succeeds, the nullifier is recorded to prevent reuse

Advanced Technical Details

Proof Generation Flow

1. The circuit is compiled to ACIR (Aztec Circuit Intermediate Representation)
2. The ACIR is transformed into an arithmetic circuit compatible with UltraHonk
3. Witness generation occurs based on the private and public inputs
4. The UltraHonk proving system creates a succinct proof of knowledge
5. The proof and public inputs are prepared as calldata for the Starknet contract

Verification Process

1. The MainContract receives the proof as a serialized array of field elements
2. It calls the UltraKeccakHonkVerifier contract via a library call
3. The verifier performs complex cryptographic checks including:
   • Multi-scalar multiplication (MSM)
   • Pairing checks on the BN254 elliptic curve
   • Keccak hash function evaluations
4. If verification succeeds, the public inputs are returned
5. The main contract validates the public key and records the nullifier

Why This Architecture?

1. Noir: Provides a developer-friendly language for writing ZK circuits with strong safety guarantees
2. UltraHonk: Offers faster proving times than alternative systems, making it suitable for interactive applications
3. Starknet: Provides a scalable, low-cost platform for running the verification logic
4. Cairo: As Starknet's native language, it offers optimal performance for on-chain verification

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgments

• Aztec Protocol for Noir and Barretenberg
• Starkware for Starknet and Cairo
• The Garaga team for the verifier generation tools