Range Check Builtin

The Range Check builtin verifies that field elements fall within a specific range. This builtin is fundamental to Cairo's integer types and comparisons, ensuring that values satisfy bounded constraints.

Two variants of this builtin exist:

  • Standard Range Check: Verifies values in the range \([0, 2^{128}-1]\)
  • Range Check 96: Verifies values in the range \([0, 2^{96}-1]\)

This section focuses on the standard variant, though the same principles apply to both.

Purpose and Importance

While it's possible to implement range checking using pure Cairo code (for example, by decomposing a number into its binary representation and verifying each bit), using the builtin is significantly more efficient. A pure Cairo implementation would require at least 384 instructions to verify a single range check, whereas the builtin achieves the same result with computational cost equivalent to about 1.5 instructions. This efficiency makes the Range Check builtin essential for the implementation of bounded integer arithmetic and other operations that require value range verification.

Cells Organization

The Range Check builtin operates on a dedicated memory segment with a validation property pattern:

CharacteristicDescription
Valid valuesField elements in range \([0, 2^{128}-1]\)
Error conditionsValues ≥ 2^128 or relocatable addresses
Validation timingImmediate (upon cell write)

Unlike builtins with deduction properties, the Range Check builtin validates values at write time rather than read time. This immediate validation provides early error detection for out-of-range values.

Valid Operation Example

valid range_check builtin segment
Range Check builtin segment with valid values

In this example, a program successfully writes three values to the Range Check segment:

  • 0: The minimum allowed value
  • 256: A typical small integer value
  • 2^128-1: The maximum allowed value

All three values fall within the permitted range \([0, 2^{128}-1]\), so the operations succeed.

Out-of-Range Error Example

invalid range_check builtin segment
Range Check error: Value exceeds maximum range

In this example, the program attempts to write 2^128 to cell 2:2, which exceeds the maximum allowed value. The VM immediately throws an out-of-range error and aborts execution.

Invalid Type Error Example

invalid range_check builtin segment
Range Check error: Value is a relocatable address

In this example, the program attempts to write a relocatable address (pointer to cell 1:7) to the Range Check segment. Since the builtin only accepts field elements, the VM throws an error and aborts execution.

Implementation References

These implementation references of the Range Check builtin in various Cairo VM implementations:

Resources on Range Check

If you're interested in how the Range Check builtin works and its usage in the Cairo VM: