NEWTON

NEWTON

# How to use Hints in Cairo Lang?

5 months ago

92

views

0

Hello! This is day 14 of the 17 days of the Cairo Challenge. And I have no idea how to solve the playground exercise “Hints”. Perhaps you can help me?

``````// The following function uses hints to efficiently compute the square root `res`
// of the argument `n`.
// The idea is that the verifier only needs to be convinced that res * res = n,
// it doesn't really care how res was computed.
// In such cases, we don't have to compute res in pure Cairo - we can write a
// piece of Python code inside the Cairo program, which is called a "hint".
// A hint is a piece of code that the prover runs to initialize
// some memory cells. Note that it is completely transparent from the verifier's
// point of view, so the result of the hint *must* be verified using pure Cairo
// instructions (e.g., the "assert n = res * res" instruction below).
//
// 1. Comment out the line "assert n = res * res;" and run the code. Does it still output
//    the expected value? Can you explain why the assert is nonetheless essential?
//    Hint: Recall that from the verifier's point of view, the hint does not exist.
// 2. Uncomment the assert line and change the function to compute the fourth
//    root.

%builtins output

from starkware.cairo.common.serialize import serialize_word

// Computes the square root (over the integers) of `n`.
// Prover assumption: The square root exists.
func sqrt(n) -> (res: felt) {
alloc_locals;
local res;

// Set the value of res using a Python hint.
%{
import math

# Use the ids variable to access the value of a Cairo variable.
ids.res = int(math.sqrt(ids.n))
%}

// From the verifier's point of view, the hint is completely transparent.
// The following line guarantees that `res` is the square root
// (either the positive or negative) of `n`.
assert n = res * res;
return (res=res);
}

func main{output_ptr: felt*}() {
let (res) = sqrt(256);
serialize_word(res);
return ();
}
``````

Answers to this question are a part of the ✨ 17 days of Cairo Lang with Playground & Newton. ✨

Vote for your favorite answer - the best answer will win a \$10 award. A new day – a new reward! During the next 17 days, our goal is to attract more developers to the Cairo language and to systematize the knowledge of Cairo lang. Read rules

#17daysOfCairocairo-beginnerscairoplayground

Newton

5 months ago

1

# Solution

A hint is a block of Python code, that will be executed by the prover right before the next instruction.

## 1. commenting out the line "assert n = res * res;"

Yes, it still output the accepted value. We should know that assert statement is used for 2 different use cases.

1. Check if two variables are the same
2. Set a variable's value if it's currently not set

Here assert is verifying the computation done by the prover(first use case) that the variable res is actually the sqrt of n. As we know hints are not visible to verifier so at prover side we need to make sure sqrt of n is res. res can be -16 or +16.

## 2. Uncomment the assert line and change the function to compute the fourth root.

``````// Computes the fourth root (over the integers) of `n`.
// Prover assumption: The fourth root exists.
func sqrt(n) -> (res: felt) {
alloc_locals;
local res;

// Set the value of res using a Python hint.
%{
import math

# Use the ids variable to access the value of a Cairo variable.
ids.res = int(math.sqrt(int(math.sqrt(ids.n))))
%}

// From the verifier's point of view, the hint is completely transparent.
// The following line guarantees that `res` is the fourth root
// (either the positive or negative) of `n`.
assert n = res * res * res * res;
return (res=res);
}
``````

### Explanation

To access the cairo contant ,we use the expression ids.res and ids.n

This line compute the square root of number n and set value to res.

`ids.res = int(math.sqrt(ids.n)) `

To compute the fourth power again take the square root of the above statement.

`ids.res = int(math.sqrt(int(math.sqrt(ids.n))))`

## Final Solution

``````%builtins output

from starkware.cairo.common.serialize import serialize_word

// Computes the fourth root (over the integers) of `n`.
// Prover assumption: The square root exists.
func sqrt(n) -> (res: felt) {
alloc_locals;
local res;

// Set the value of res using a Python hint.
%{
import math

# Use the ids variable to access the value of a Cairo variable.
ids.res = int(math.sqrt(int(math.sqrt(ids.n))))
%}

// From the verifier's point of view, the hint is completely transparent.
// The following line guarantees that `res` is the fourth root
// (either the positive or negative) of `n`.
assert n = res * res * res * res;
return (res=res);
}

func main{output_ptr: felt*}() {
let (res) = sqrt(256);
serialize_word(res);
return ();
}
``````

# Output

``````Program output:
4
Number of steps: 15
Program hash: 0x02e4a32aed1fd7fcec13c52afa33fe53d5d776e560877633f5d2b0c535ce8ffc
``````

Ishita Rastogi

5 months ago

0

# 1. Comment out the line "assert n = res * res;" and run the code.

• Does it still output the expected value? - Yes
• Why the assert is nonetheless essential? - Because the verifier cares only about the initial state and that the solution is valid. So, when the prover chooses a value for `res`. We need an `assert` instruction to make sure the square of `res` is `n`.

# 2. Change the function to compute the fourth

• Use math.sqrt twice to calculate the fourth root of n.
• Similar to `assert n = res * res`, I will `assert n = res * res * res * res `.
``````func sqrt(n) -> (res: felt) {
alloc_locals;
local res;

// Set the value of res using a Python hint.
%{
import math

# Use the ids variable to access the value of a Cairo variable.
square_root = int(math.sqrt(ids.n));
ids.res = int(math.sqrt(square_root))
%}

// From the verifier's point of view, the hint is completely transparent.
// The following line guarantees that `res` is the fourth root
// (either the positive or negative) of `n`.
assert n = res * res * res * res;
return (res=res);
}
``````

5 months ago

0

1. assert is essential as this constitutes verification part. If we remove assert, then we are omitting verification and the program won't be able to verify correctness of output.

2. My solution for fourth root:

``````%builtins output

from starkware.cairo.common.serialize import serialize_word

// Computes the square root (over the integers) of `n`.
// Prover assumption: The square root exists.
func sqrt(n) -> (res: felt) {
alloc_locals;
local res;

// Set the value of res using a Python hint.
%{
import math

# Use the ids variable to access the value of a Cairo variable.
#ids.res = int(math.sqrt(ids.n))
ids.res = int(math.sqrt(int(math.sqrt(ids.n))))
print(f"res = {ids.res}")
%}

// From the verifier's point of view, the hint is completely transparent.
// The following line guarantees that `res` is the square root
// (either the positive or negative) of `n`.
assert n = res * res * res * res;
return (res=res);
}

func main{output_ptr: felt*}() {
let (res) = sqrt(256);
serialize_word(res);
return ();
}
``````