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

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);
}

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 ();
}