Journey Through Cairo VII — Builtins, Hints and Revoked References

Welcome to the seventh article, in our series, “Journey through Cairo”. In our last article which can be found here, we took a deep dive into how Recursions work in Cairo.

Today, we’d be looking into Builtins, Hints and Revoked References. As always, if you are just joining mid-flight, endeavour to checkout the previous articles, to better understand and flow with this series.

P.S: All code snippets used in this tutorial, makes use of the old Cairo syntaxes from Cairo-lang v0.9.0, since its what was used in our Starklings exercises as at the time of this writing.

Builtins

Builtins are predefined optimized low-level execution units, which are added to Cairo’s CPU board, to help perform predefined computations like pedersen hashing, signature verification, bitwise operations etc, which are expensive to perform in Vanilla Cairo.

Each builtin in Cairo, is assigned a separate memory location, accessible through regular Cairo memory calls using implicit parameters.

There are some Builtins struct helpers available for use in the Cairo-lang library here, which you could easily import for use in your starknet contract.

Here is a list of available builtins in Cairo:

1. output — the output builtin, accessed with a pointer to type felt, is used for writing program outputs.
2. pedersen — the pedersen builtin, accessed with a pointer to type HashBuiltin, is used for pedersen hashing computations.
3. range_check — unlike other builtins, the range_check is accessed using a type felt, rather than a pointer. This builtin is mostly used for integer comparisons, and facilitates check to confirm that a field element is within a range [0, 2^128) .
4. ecdsa — the ecdsa builtin, accessed with a pointer to type SignatureBuiltin, is used for verifying ECDSA signatures.
5. bitwise — the bitwise builtin, accessed with a pointer to type BitwiseBuiltin, is used for carrying out bitwise operations on felts.

To make use of any of the available builtins in your Cairo code, you need to specify them using the %builtins directive in an order that follows the listing convention I used above. The builtins directive, should be specified at the top of your code like this:

%builtins output pedersen range_check ecdsa bitwise

PS: Note that specifying your builtins like this is only necessary, if you are writing a Cairo program! You do not need to do this, if you are writing a Starknet contract, as this is abstracted behind the scenes for you.

If you still can’t differentiate between Cairo programs and Starknet contracts, please take a stroll back to our second article here.

Below is an example implementation of a builtin from the official docs, that uses the pedersen builtin:

from starkware.cairo.common.cairo_builtins import HashBuiltin

func hash2{hash_ptr: HashBuiltin*}(x, y) -> (z: felt):
    # Create a copy of the reference and advance hash_ptr.
    let hash = hash_ptr
    let hash_ptr = hash_ptr + HashBuiltin.SIZE
    # Invoke the hash function.
    hash.x = x
    hash.y = y
    # Return the result of the hash.
    # The updated pointer is returned automatically.
    return (z=hash.result);
}

Hints

Hints are pieces of Python codes, which contains instructions that only the prover sees and executes.

Although hints can be very useful when writing Cairo codes, it is advisable to not include them in your Starknet contracts, as hints are not added to the bytecode, and thus do not count in the total number of execution steps.

In other words, from the point of view of the verifier these hints do not exist.

To dive deeper into how useful Hints can be, checkout the official docs here.

To specify a hint in Cairo, you need to encapsulate it within %{ and%} like this:

%{ 
    # Python hint goes here 
%}

Revoked References

Revoked References has been one of the few concepts, i’ve struggled with thus far in Cairo. Thankfully, it’d be history with Cairo 1.0.

Revoked references, mostly occurs when there is a call instruction to another function, between the definition of a reference variable that depends on ap (temporary variables) and its usage. This occurs since the compiler may not be able to compute the change of ap (as one may jump to the label from another place in the program, or call a function that might change ap in an unknown way). The docs goes deeper into this here.

In simple cases you can resolve this issue, by adding the keyword, alloc_locals within function scopes, but in most complex cases you might need to create a local variable to resolve it.

Local variables

Unlike temporary variables (variables created using the tempvar and let keywords) which are based on ap registers, Local variables are based on the fp register, and as such, not easily revoked.

Local variables are created using the local keyword like this:

local y = 35

We can also re-reference a previously created variable in a process called reference binding like this:

let y = 20
local y= y

To better understand this, let’s try out the revoked reference exercise from starklings.

revoked_references01.cairo

If we try to run this piece of code, we get thrown the revoked reference error.

In this exercise, we are expected to edit the bar function to makes the test pass.

Firstly we need to add the alloc_locals keyword to the function scope, then through reference binding we would re-reference the hash_ptr implicit argument.

Our solution should look like this:

func bar{hash_ptr : HashBuiltin*}():
   alloc_locals
   hash2(1, 2)  # Do not change
   foo(3)  # Do not change
   # Insert something here to make the test pass
   local hash_ptr: HashBuiltin* = hash_ptr
   hash2(3, 4)  # Do not change
   return ()  # Do not change
end

Now let’s check to see if our test passes.

Voila! it does.

Conclusion

Congratulations! getting to this point, i’m sure you now possess a better understanding of Builtins, Hints and Revoked References in Cairo.

If you noticed, we skipped the starklings challenges associated with builtins and hints in order to shorten the article’s length, but i’d make the solutions available on the github repo associated with this series here.

As always, If you got value from this article, do well to share with others.

You could also connect with me on the following socials, especially on Twitter, where i share my little findings on Cairo!

Twitter: https://twitter.com/0xdarlington

LinkedIn: https://www.linkedin.com/in/nnamdarlington

Github: https://github.com/Darlington02