Hints

Introduction

Cairo supports non-deterministic instructions. For example, to compute the root of 25 one may simply write:

[ap] = 25; ap++
[ap - 1] = [ap] * [ap]; ap++

While this is fine for the verifier, the prover cannot handle such an expression implicitly (for example, the value can be both 5 or -5) and we have to instruct it what to do in order to compute the root. This is done by adding what we call ‘hints’. A hint is a block of Python code, that will be executed by the prover right before the next instruction.

The format is as follows:

[ap] = 25; ap++
%{
    import math
    memory[ap] = int(math.sqrt(memory[ap - 1]))
%}
[ap - 1] = [ap] * [ap]; ap++

To access [ap] in the hint we use the syntax memory[ap] (note that while [ap] is a valid Cairo expression, it is not a valid expression in Python). In addition, if we want to access a Cairo constant, x, in a hint, we use the expression ids.x. Function arguments and references, can be accessed in the same way.

Note that a hint is attached to the next instruction and executed before each execution of the corresponding instruction. The hint is not an instruction on its own. Thus,

%{ print("Hello world!") %}
jmp rel 0  # This instruction is an infinite loop.

will print Hello world infinitely many times (rather than printing once and then starting an infinite loop).

Exercise

Make the code in the example above (of computing the square root) compile, and then run it. Then change the hint to:

memory[ap] = int(math.sqrt(memory[ap - 1])) + 1

You should get an An ASSERT_EQ instruction failed error. Make sure you understand it.

Exercise

What is the difference between the following code segments?

[ap] = 25; ap++
%{
    import math
    memory[ap] = int(math.sqrt(memory[ap - 1]))
%}
[ap - 1] = [ap] * [ap]; ap++

and

[ap] = 25; ap++
[ap] = 5
[ap - 1] = [ap] * [ap]; ap++

Split your answer into two parts: the difference from the prover’s point of view and the difference from the verifier’s point of view.