Cairo 0 GCD Program

A Greatest Common Divisor (GCD) implementation in Cairo 0 that demonstrates zero-knowledge proof verification of mathematical computations.

Overview

This program calculates the GCD of two integers using Python's built-in gcd function and then proves the correctness of the result using Cairo's constraint system.

Prerequisites

• Python 3.10 (required due to compatibility issues with Python 3.12+)
• Cairo toolchain

Installation

1. Create Python 3.10 Virtual Environment

python3.10 -m venv cairo_env

2. Activate Virtual Environment

source cairo_env/bin/activate

3. Install Cairo Lang

pip install cairo-lang

Compilation

Compile the Cairo program:

cairo-compile gcd.cairo --output gcd_compiled.json

Running the Program

1. Prepare Input

Create or modify program_input.json with your input values:

{
  "a": 144,
  "b": -12
}

2. Run the Program

source cairo_env/bin/activate
cairo-run --program=gcd_compiled.json --program_input=program_input.json --layout=recursive --print_output

Example Output

Program output:
  12

Program Structure

• main(): Entry point that reads inputs, ensures a >= b, and outputs the result
• gcd(): Computes GCD using Python's math library
• assert_common_divider(a,b,d): Verifies that d divides both a and b
• div_remainder(): Performs division with remainder and validates the operation

Verification Process

1. Divisor check: Verifies the result divides both input numbers
2. Coprime check: Proves no greater common divisor exists
3. Range validation: Ensures all values are within 64-bit bounds
4. Mathematical correctness: Validates division and remainder operations

Troubleshooting

Python Version Issues

If you encounter dataclass errors, ensure you're using Python 3.10/11:

python3 --version  # Should show 3.10.x

Virtual Environment

Always activate the virtual environment before running Cairo commands:

source cairo_env/bin/activate

License

This project demonstrates Cairo 0 programming concepts and is provided for demonstration purposes.