NEWTON
Asked
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
Newton
asked
5 months ago
1
Accepted answer
A hint is a block of Python code, that will be executed by the prover right before the next instruction.
Yes, it still output the accepted value. We should know that assert statement is used for 2 different use cases.
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.
// 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);
}
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))))
%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 ();
}
Program output:
4
Number of steps: 15
Program hash: 0x02e4a32aed1fd7fcec13c52afa33fe53d5d776e560877633f5d2b0c535ce8ffc
Ishita Rastogi
answered
5 months ago
0
res
. We need an assert
instruction to make sure the square of res
is n
.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);
}
answered
5 months ago
0
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.
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 ();
}
Prashant Banchhor
answered
5 months ago
How to use get_fp_and_pc in Cairo Lang?
How to make recursive function in Cairo Lang?
Cairo Lang / StarkNet: What are Revoked references? What is alloc_locals?
How to write a function in Cairo Lang (StarkNet)?
How to make math operation with Field Elements (felts) in Cairo lang?
What is SHARP in Cairo Language?
How to submit a StarkNet contract?
Warp Traspiler error: the warp-related package was not found. How do I generate python packages?
What are the projects on starknet that plan to do the domain .stark?
Does Account Abstraction support "Burner Accounts"?
Is there a unsigned_div_rem supporting dividing by 2**128 ?
ApeWorX: Using ape starknet accounts list
How to write "and" conditional logic in Cairo?
Is there an example of migration scripts somewhere [Cairo/StarkNet]?