Introduction
Cairo provides a built-in hash2 function to calculate the Pedersen hash of two felts. In this challenge, we will recursively compute the hash of an array of felts.
The challenge
ex_hash_chain.cairo
// Task:
// Develop a function that is going to calculate Pedersen hash of an array of felts.
// Cairo's built in hash2 can calculate Pedersen hash on two field elements.
// To calculate hash of an array use hash chain algorithm where hash of [1, 2, 3, 4] is H(H(H(1, 2), 3), 4).
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2
// Computes the Pedersen hash chain on an array of size `arr_len` starting from `arr_ptr`.
func hash_chain{hash_ptr: HashBuiltin*}(arr_ptr: felt*, arr_len: felt) -> (result: felt) {
return (result=1);
}
test_ex_hash_chain.cairo
%lang starknet
from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.cairo_builtins import HashBuiltin
from exercises.programs.ex_hash_chain import hash_chain
@external
func test_hash_chain{pedersen_ptr: HashBuiltin*}() {
alloc_locals;
let (local array: felt*) = alloc();
assert array[0] = 1;
assert array[1] = 4;
let (result) = hash_chain{hash_ptr=pedersen_ptr}(array, 2);
assert 1323616023845704258113538348000047149470450086307731200728039607710316625916 = result;
let (local array: felt*) = alloc();
assert array[0] = 2; // YES
assert array[1] = 100;
assert array[2] = 12;
assert array[3] = 2; // YES
assert array[4] = 422; // YES
assert array[5] = 898;
assert array[6] = 10;
assert array[7] = 31;
assert array[8] = 22;
assert array[9] = 5;
let (result) = hash_chain{hash_ptr=pedersen_ptr}(array, 10);
assert 2185907157710685805186499755291718313025201005027499629005977263373594646427 = result;
return ();
}
Solution
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2
func hash_chain{hash_ptr: HashBuiltin*}(arr_ptr: felt*, arr_len: felt) -> (result: felt) {
if (arr_len == 2) {
return hash2([arr_ptr], [arr_ptr + 1]);
}
let (hash) = hash_chain(arr_ptr, arr_len - 1);
return hash2(hash, [arr_ptr + arr_len - 1]);
}
Explain the solution
For a better explanation, I added another test case
let (local array: felt*) = alloc();
assert array[0] = 1;
assert array[1] = 2;
assert array[2] = 3;
assert array[3] = 4;
let (result) = hash_chain{hash_ptr=pedersen_ptr}(array, 4);
assert 2151680050850558576753658069693146429350618838199373217695410689374331200218 = result;
As usual, we handle the base case for our recursion function:
if (arr_len == 2) {
return hash2([arr_ptr], [arr_ptr + 1]);
}
The base case is to calculate the H(1, 2). Next, we handle the recursive case:
let (hash) = hash_chain(arr_ptr, arr_len - 1);
return hash2(hash, [arr_ptr + arr_len - 1]);
After the arr_len reaches 2, the call stack starts to offload its box starting from the base case:
arr_len = 2
result = H(1, 2)
--------------------
arr_len = 3
hash = H(1, 2)
result = H(H(1 , 2), 3)
--------------------
arr_len = 4
hash = H(H(1 , 2), 3)
result = H(H(H(1 , 2), 3), 4)
done!
Conclusion
I don't often use recursion in other languages which have loop standards. However, since there is no loop in Cairo, things usually get done by recursion. I am getting used to it.
I hope you found this guide insightful. If you have any questions, feel free to reach out. Happy coding!
Here is the Github repo for the code in this article
Top comments (0)