Cairo Common Library

The Cairo common library contains modules that can be imported into Cairo code. They are imported with the following syntax, where MODULE is the module name, and COMPONENT is the function or struct to import:

from starkware.cairo.common.MODULE import COMPONENT

For example, to use the hash2() function from the hash module:

from starkware.cairo.common.hash import hash2

Available modules and their components:

• alloc
  • alloc(). Allocate new memory segment.
• cairo_builtins
  • BitwiseBuiltin. The struct used for a bitwise operation.
  • HashBuiltin. The struct used for a hash.
  • SignatureBuiltin. The struct used for an ECDSA signature.
• default_dict
  • default_dict_new(). Create new dictionary without a hint.
  • default_dict_finalize(). Check the default dictionary.
• dict
  • dict_new(). Create new dictionary using a hint.
  • dict_read(). Read dictionary.
  • dict_write(). Write to dictionary.
  • dict_update(). Update a value in a dictionary.
  • dict_squash(). Remove intermediate values from the dictionary.
• dict_access
  • DictAccess. The struct used for a dictionary.
• find_element
  • find_element(). Find element in an array.
  • search_sorted_lower(). Get first value larger than x in a sorted array.
  • search_sorted(). Get first value equal to x in a sorted array.
• hash
  • hash2(). Get Pedersen hash of a and b.
• hash_chain
  • hash_chain(). Get hash chain of a list, last to first.
• hash_state
  • HashState. The struct used for a state hash of a list, from first to last.
  • hash_init(). Initialize a state hash.
  • hash_update(). Add an array to a state hash.
  • hash_update_single(). Add a single item to state hash.
• keccak
  • unsafe_keccak(). Compute the Keccak hash.
• math
  • assert_not_zero(). Verify value ! = 0.
  • assert_not_equal(). Verify a! = b.
  • assert_nn(). Verify a >= 0.
  • assert_le(). Verify a <= b.
  • assert_lt(). Verify a < b.
  • assert_nn_le(). Verify 0 <= a <= b.
  • assert_in_range(). Verify value is in range [lower, upper).
  • assert_le_250_bit(). Verify a and b are in range [0, 2**250).
  • split_felt(). Get the unsigned integer lift of a value.
  • assert_le_felt(). Verify lift(a) < b.
  • abs_value(). Get the absolute value.
  • sign(). Get the sign of a value.
  • unsigned_div_rem(). Get value and remainder for integer division.
  • signed_div_rem(). Get value and remainder for integer division allowing negatives.
• math_cmp
  • is_nn(). Check if a >= 0.
  • is_le(). Check if a <= b.
  • is_in_range(). Check if a is in [lower, upper).
  • is_le_felt(). Check if lift(a) < b.
• memcpy
  • memcpy(). Copy the length of a field element.
• merkle_multi_update
  • merkle_multi_update(). Update multiple leaves of merkle tree.
• merkle_update
  • merkle_update(). Update single leaf of merle tree.
• pow
  • pow(). Get base ** exp.
• registers
  • get_fp_and_pc(). Get contents of fp and pc.
  • get_ap(). Get content of ap.
  • get_label_location(). Get runtime address of particular label in memory.
• serialize
  • serialize_word(). Append single value to the program output.
  • array_rfold(). Append an array to the program output, from right to left.
  • serialize_array(). Append an array to the program output, from left to right.
• set
  • set_add(). Add an element to a set.
• signature
  • verify_ecdsa_signature(). verifies the prover knows signature)
• small_merkle_tree
  • small_merkle_tree(). updates multpile leaves in merkel tree based on a squashed dictionary)
  • merkle_multi_update(). verify two roots
• squash_dict
  • squash_dict(). verifies dict construction sequence was valid and compresses
• uint256
  • Uint256. The struct used for 256-bit math.
  • uint256_add(). 256-bit a + b.
  • uint256_mul(). 256-bit a * b.

alloc

See the alloc module for more details.

Returns a newly allocated memory segment. This is useful when defining dynamically allocated arrays. As more elements are added, more memory will be allocated.

    from starkware.cairo.common.alloc import alloc

    # Allocate a memory segment.
    let (new_slot : felt*) = alloc()

    # Allocate a memory segment for an array of structs.
    let (local my_array : MyStruct*) = alloc()

cairo_builtins

Contains three predefined structs:

• BitwiseBuiltin
• HashBuiltin
• SignatureBuiltin

Cairo tracks hashes and signatures in discrete areas of memory. This is because AIR construction is simpler when they are handled separately. As such, hashes and signatures are tracked by the compiler in a standardised way, represented with a struct with predefined members.

The members are:

• BitwiseBuiltin: x, y, x_and_y, x_xor_y, and x_or_y.
• HashBuiltin: x, y and result.
• SignatureBuiltin: pub_key and message.

Therefore my_hash.result would access the hash of x and y, and my_signature.pub_key would access the public key of my_signature.

The builtin is used to standardise these components and to make type declaration simple.

• A pointer to my_bitwise would be of type BitwiseBuiltin*.
• A pointer to my_hash would be of type HashBuiltin*.
• A pointer to my_signature would be of type SignatureBuiltin*.

A function expecting a hash as an argument:

from starkware.cairo.common.cairo_builtins import HashBuiltin

# The function is expecting a hash.
func use_hash(a_hash : HashBuiltin*):
    # a_hash.x

See the cairo_builtins module for more details.

default_dict

A module for creating a new dictionary in StarkNet. Unlike dict_new() in the dict, module, no hints are required. Operations on a default dict can be performed by using the dict module. A default dictionary is a dictionary that will return a uniform value for all keys that have not otherwise been set.

There are two functions:

• default_dict_new(). Create new dictionary without a hint.
• default_dict_finalize(). Check the default dictionary.

See the default_dict module for more details. See a deployed dictionary for an example.

default_dict_new()

Used to create a new dictionary. Returns a pointer to a dictionary that is empty, but will return a default value for all keys.

Accepts one explicit argument:

• default_value, a felt representing the value that will be returned for all undeclared keys.

Returns:

• res, a pointer to the DictAccess struct from the dict_access module.

default_dict_finalize()

Used to ensure that the prover has correctly set the default value of a new dictionary properly.

Accepts one implicit argument:

• range_check_ptr

Accepts three explicit arguments:

• dict_accesses_start of type DictAccess*, a pointer to the first instance of a dictionary modification.
• dict_accesses_end of type DictAccess*, a pointer to the the last instance of a dictionary modification.

Returns:

• dict_accesses_start of type DictAccess*, a pointer to the first instance of a dictionary modification.
• dict_accesses_end of type DictAccess*, a pointer to the the last instance of a dictionary modification.

When a new dictionary is being made, the dict_access_start and dict_access_end may both be set to the pointer returned from default_dict_new().

dict

See the dict module for more details. See a deployed dictionary for an example.

dict_new()

Creates a new dictionary, populated using a hint. Not available in StarkNet, where default_dict_new() is used instead.

Returns:

• res of type DictAccess*, a pointer to a struct from the dict_access module.

Values may be initialized by first declaring a dictionary inside a hint using the special variable name initial_dict.

%{
    initial_dict = {
        1: 5,
        3: 15,
        5: 25
    }
%}
let (new_dict) = dict_new()  # Has three key-value pairs.

dict_read()

Returns the value of a key-value pair in a dictionary.

Accepts one implicit argument:

• dict_ptr of type DictAccess*, a pointer to the dictionary.

Accepts one explicit argument:

• key of type felt, the key of the key-value pair.

Returns one argument:

• value of type felt, the value of the key-value pair.

dict_write()

Sets the value of a key-value pair in a dictionary.

Accepts one implicit argument:

• dict_ptr of type DictAccess*, a pointer to the dictionary.

Accepts two explicit arguments:

• key of type felt, the key of the key-value pair.
• new_value of type felt, the new value of the key-value pair.

dict_update()

Sets the value of a key-value pair in a dictionary, requiring that the previous value be known.

Accepts one implicit argument:

• dict_ptr of type DictAccess*, a pointer to the dictionary.

Accepts three explicit arguments:

• key of type felt, the key of the key-value pair.
• prev_value of type felt, the old value of the key-value pair.
• new_value of type felt, the new value of the key-value pair.

dict_squash()

Takes a dictionary that has been modified and returns a new dictionary with the modifications applied. The act of modifying a dictionary in Cairo creates intermediate entries for each key-value update. The squash operation summarizes those such that each key only has one entry.

Accepts one implicit argument:

• dict_ptr of type DictAccess*, a pointer to the dictionary.

Accepts two explicit arguments:

• dict_accesses_start of type DictAccess*, a pointer to the first state in a series of dictionary state updates.
• dict_accesses_end of type DictAccess*, a pointer to the last state in a series of dictionary state updates.

Returns:

• squashed_dict_start of type DictAccess*, a pointer to the first state in a series of dictionary state updates.
• squashed_dict_end of type DictAccess*, a pointer to the last state in a series of dictionary state updates.

The pointers that are returned are use to represent the start and end of the summarized dictionary.

dict_access

See the dict_access module for more details.

find_element

See the find_element module for more details.

hash

Contains one function Hash2(), which computes the Pedersen hash of two elements. As discussed in the HashBuiltin module, Cairo segregates hashes and requires that they use the struct HashBuiltin so that it can track all the hashes.

When calling Hash2(), a pointer to the hash must be provided implicitly. This pointer is called hash_ptr.

from starkware.cairo.common.hash import hash2
from starkware.cairo.common.cairo_builtins import HashBuiltin

let hash = hash2{hash_ptr : HashBuiltin*}(3, 5)

See the hash module for more details.

hash_chain

Contains one function, hash_chain(), which is used to find the Pedersen hash of a list of elements, where each element is hashed after adding to the list. In other words, a hash chain, or a hash-of-a-hash-of-a-hash… etc.

For a list, [a, b, c, d, e], the hash chain would be:

hash2(a, hash2(b, hash2(c, hash2(d, e))))

Or, visually:

|----------| Fourth
      |---------| Third
            |--------| Second
                  |-----| First
a     b     c     d     e

The function uses hash2() and therefore requires the special hash_ptr implicit argument. The list to be hash is passed as a pointer.

from starkware.cairo.common.hash import hash_chain
from starkware.cairo.common.cairo_builtins import HashBuiltin

let hash = hash_chain{hash_ptr : HashBuiltin*}(list_to_hash*)

See the hash_chain module for more details.

hash_state

Contains one struct and four functions:

• HashState
• hash_init()
• hash_update()
• hash_update_single()
• hash_finalize()

Consider how the hash_chain module calculated a hash from the end of a list. How would more elements be added to that list? This module creates a hash from the start of a list such that elements can continue be added.

HashState is a struct with members current_hash and n_words. For a hash involving a list of three elements, n_words would be 3. HashState uses Hash2() and therefore HashBuiltin, so functions will expect the implicit argument hash_ptr.

The process is as follows:

1. Call hash_init().
2. Call hash_update() with a list or hash_update_single() with a single element.
3. Call hash_finalize() to get the hash.

For a list, [a, b, c, d, e], the hash state would be:

hash2(hash2(hash2(hash2(hash2(0, a), b), c), d), e)

Or, visually:

                   |----------| Fifth
             |----------| Fourth
        |---------| Third
   |--------| Second
|-----| First
0     a     b     c     d     e

from starkware.cairo.common.hash_state import hash_init,
    hash_update_single, hash_finalize
from starkware.cairo.common.cairo_builtins import HashState,
    HashBuiltin

# Get the state pointer
let hash_state_ptr = hash_init()
# Update the state pointer
let hash_state_ptr = hash_update_single{hash_ptr : HashBuiltin*}(
    hash_state_ptr)
# Get the hash
let hash = hash_finalize{hash_state_ptr : HashState*}(hash_state_ptr)

See the hash_state module for more details.

keccak

See the keccak module for more details.

math

Contains 14 functions:

• assert_not_zero().
• assert_not_equal().
• assert_nn().
• assert_le().
• assert_lt().
• assert_nn_le().
• assert_in_range().
• assert_le_250_bit().
• split_felt().
• assert_le_felt().
• abs_value().
• sign().
• unsigned_div_rem().
• signed_div_rem().

See below for descriptions or the math module for more details.

assert_not_zero()

Verifies that value != 0. The proof will fail otherwise.

assert_not_zero(value)

assert_not_equal()

Verifies that a != b. The proof will fail otherwise.

assert_not_equal(a, b)

assert_nn()

Verifies that a >= 0 (or more precisely 0 <= a < RANGE_CHECK_BOUND). Informally, that a is non-negative (“nn”). The proof will fail otherwise. The function requires the implicit argument range_check_ptr.

assert_nn(a)

assert_le()

Verifies that a <= b (or more precisely 0 <= b - a < RANGE_CHECK_BOUND). Informally, that a is less than or equal to (“le”) b. The proof will fail otherwise. The function requires the implicit argument range_check_ptr.

assert_le(a, b)

assert_lt()

Verifies that a <= b - 1 (or more precisely 0 <= b - 1 - a < RANGE_CHECK_BOUND). Informally, that a is less than (“lt”) b. The proof will fail otherwise. The function requires the implicit argument range_check_ptr.

assert_lt(a, b)

assert_nn_le()

Verifies that 0 <= a <= b. Informally that a and b are non-negative (“nn”) and that a is less than or equal to b. The proof will fail otherwise. The function requires the implicit argument range_check_ptr.

assert_nn_le(a, b)

assert_in_range()

Verifies that value is in the range [lower, upper). Informally, that value is both greater than or equal to lower and less than upper. The proof will fail otherwise. The function requires the implicit argument range_check_ptr.

assert_in_range(value, upper, lower)

assert_le_250_bit()

Verifies that a and b are in the range [0, 2**250). Informally, that both a and b are non-negative and less that the largest number possible in a binary system with 250 bits. The proof will fail otherwise. The function requires the implicit argument range_check_ptr.

assert_le_250_bit(a, b)

split_felt()

Splits the unsigned integer lift of a field element into the higher 128 bit and lower 128 bit and returns both numbers. The unsigned integer lift is the unique integer in the range [0, PRIME) that represents the field element.

For example, if value = 17 * 2^128 + 8, then high = 17 and low = 8.

The function requires the implicit argument range_check_ptr.

let (high, low) = split_felt(value)

See notes on integer lift for more information.

assert_le_felt()

Verifies that the unsigned integer lift (as a number in the range [0, PRIME)) of a is lower than or equal to that of b. Informally, that the integer of the larger component of the field element is less than the integer of the smaller component. The proof will fail otherwise. The function requires the implicit argument range_check_ptr.

For example, the proof for assert_le_felt(17 * 2^128 + 8) would fail because because 17>8.

assert_le_felt(value)

abs_value()

Returns the absolute value of a value. Informally, the function returns the value provided with any negative sign removed. The function requires the implicit argument range_check_ptr.

abs_value(value)

sign()

Returns the sign of value: -1, 0 or 1. Informally, for positive numbers the function returns 1, for negative numbers the function returns -1 and for zero the function returns 0. The function requires the implicit argument range_check_ptr.

let value_sign = sign(value)

unsigned_div_rem()

Returns q and r such that 0 <= q < rc_bound, 0 <= r < div and value = q * div + r. Informally, the function returns the quotient and remainder for a value and divisor, ignoring negative values. The function requires the implicit argument range_check_ptr.

let (unsigned_quotient, remainder) = unsigned_div_rem(value, divisor)

signed_div_rem()

Returns q and r such that 0 <= q < rc_bound, 0 <= r < div and value = q * div + r. Informally, the function returns the quotient and remainder for a value and divisor, ignoring negative values. The function requires the implicit argument range_check_ptr.

let (signed_quotient, remainder) = unsigned_div_rem(value, divisor)

memcpy

See the memcpy module for more details.

merkle_multi_update

See the merkle_multi_update module for more details.

merkle_update

See the merkle_update module for more details.

pow

See the pow module for more details.

registers

See the registers module for more details.

serialize

See the serialize module for more details.

set

See the set module for more details.

signature

See the signature module for more details.

small_merkle_tree

See the small_merkle_tree module for more details.

squash_dict

See the squash_dict module for more details.

uint256

Note that this module is not currently enabled by the StarkNet compiler and cannot be used until that happens.

Contains one struct and two functions:

• Uint256
• uint256_add()
• uint256_mul()

The struct Uint256 is used to represent an unsigned integer with 256 bits, and is handled by the StarkNet compiler. It is a number represented as a 256 character long sequence of 0’s and 1’s, divded into high and low components. These two values are the members of the struct.

The breakdown of a number into higher and lower parts is shown below, first in decimal, then in binary (with the middle numbers removed).

my_decimal = 8498972348
        high  ^  ||  ^low

my_uint8 =   10101110
          high^ || ^low

my_uint256 = 1010100110110......10100101111110
             high^          ||           ^low

my_uint256.high begins with 10101, and my_uint256.low ends with 11110.

The functions uint256_mul() and uint256_add() both require the imiplicit argument range_check_ptr, which is a pointer to the builtin range_check. The mul and sum functions compute the product and sum of two numbers, and return any overflow as a carry.

%builtins output range_check

from starkware.cairo.common.uint256 import (uint256_add, Uint256,
    uint256_mul)
from starkware.cairo.common.serialize import serialize_word

func main{output_ptr : felt*, range_check_ptr}():
    alloc_locals
    local num1 : Uint256 = Uint256(low=0,high=13)
    local num2 : Uint256= Uint256(low=0,high=7)
    let (local mul_low : Uint256, local mul_high : Uint256) = uint256_mul(num1, num2)
    serialize_word(mul_high.low) . # 91.

    return ()
end

See the uint256 module for more details.