Using Cairo’s Range‑Check Builtin to Constrain Felt Values Efficiently

Problem: Avoiding Costly Assertions for Felt Ranges

When a Cairo program must guarantee that a felt variable stays inside an unsigned interval—for example, a user‑supplied ID that should never exceed 2³²‑1—the straightforward way is to add a chain of assertions like assert value < 2**32. Each assertion translates into extra constraints for the prover, increasing proof size and verification time. This overhead becomes noticeable when many values need range checks or when the program runs on‑chain where proof size directly impacts gas costs.

Thesis: The range_check Builtin Gives a Native, Low‑Overhead Check

Cairo’s range_check builtin is a dedicated memory segment that the prover can use to verify that a felt lies in [0, 2ⁿ‑1] without exposing the exact value. By allocating a cell in this segment and writing the felt to it, the compiler automatically emits the appropriate range‑check constraint. Compared with manual assertions, the builtin typically reduces the number of constraints by a factor proportional to the bit‑width, yielding smaller proofs and faster verification.

How the Builtin Works

• Declare the range_check builtin in the function signature using the #[builtin(name: "range_check")] attribute.
• The builtin provides a pointer to a memory segment; each cell corresponds to one range‑check instance.
• When you write a felt v to a cell, the compiler adds a constraint that v must be representable with the declared bit‑width n (i.e., 0 ≤ v < 2ⁿ).
• At the end of execution the prover verifies all cells; a value outside the range makes the proof fail.

Worked Example: Checking a 32‑Bit Timestamp

The following minimal Cairo 1.0 program declares a 32‑bit range‑check builtin, writes a felt timestamp to it, and returns. If the timestamp lies in [0, 2³²‑1] the program executes successfully; otherwise the prover rejects the proof.

%lang starknet
// Using Scarb, the program can be a simple contract or a standalone program.
#[builtin(name: "range_check")]
func check_timestamp{range_check_ptr: RangeCheckPtr<32>}(timestamp: felt) -> () {
    // Write the timestamp to the first (and only) range‑check cell.
    *range_check_ptr = timestamp;
    return ();
}

To try it locally:

Create a new Scarb project: scarb new range_check_demo.
Replace the generated src/lib.cairo with the code above (or add it as a module).
Build with scarb build. The compiler will emit Sierra and CASM artifacts.
Run the program through the Cairo‑run interpreter (included with the Cairo toolchain) providing a felt as input. For a valid 32‑bit value:
cairo-run --program=target/dev/range_check_demo_contract.json \
    --program_input 4294967295 --print_output --print_info
The command should exit with status SUCCESS and no range‑check error.
To see the generated constraint, inspect the CASM file:
cairo-compile target/dev/range_check_demo_contract.json --casm --output out.casm
Look for a range_check instruction that references the allocated cell.
Finally, verify with a StarkNet devnet (e.g., starknet-devnet) to confirm that out‑of‑range inputs trigger a proof failure:
starknet-devnet --http-port 5050
# Deploy the contract, then invoke check_timestamp with 4294967296 (2**32)
# The transaction reverts with a range‑check error.

Trade‑Offs and Limitations

Unsigned only: The builtin treats the felt as an unsigned integer. Supplying a negative felt (i.e., a value whose most‑significant bit is set) will cause a verification error.
Width must fit: If the declared bit‑width n is too small for the maximum possible value, the proof will fail. Choose n large enough to cover the expected range or add an explicit reject‑out‑of‑range check before the builtin.
Atomic per cell: Each range‑check cell verifies exactly one felt. Checking many values requires allocating multiple cells, which grows the memory segment linearly with the number of checks.

Actionable Closing
To start using the range‑check builtin in your own Cairo contracts:

Determine the smallest unsigned bit‑width that safely encloses your data (e.g., 16 bits for a uint16, 64 bits for a timestamp).
Add the #[builtin(name: "range_check")] attribute to the function and include a range_check_ptr: RangeCheckPtr<n> parameter where n is the chosen width.
Write the felt to the dereferenced pointer (*range_check_ptr = value;) before the function returns.
Build with scarb build and inspect the generated CASM to confirm the range_check instruction appears.
Run a test on a StarkNet devnet to ensure that out‑of‑range inputs cause a proof failure.

By replacing a chain of assertions with a single, prover‑native range‑check you keep proofs compact and verification costs predictable.