NEWTON
Asked
8 months ago
104
views
0
Hello! This is day 13 of the 17 days of the Cairo Challenge. And I have no idea how to solve the playground exercise “Pedersen Hash”. Perhaps you can help me?
// The following code implements a Pedersen hash chain.
// Given the [Pedersen hash](https://docs.starkware.co/starkex-docs/crypto/pedersen-hash-function) function `H`, which
// takes two field elements and returns one representing their hash,
// a hash chain on inputs x_0, x_1, ..., x_n is the result of
// H(H(...H(H(x_0, x_1), x_2), ...,x_{n-1}), x_n)
// For example, the hash chain of (1, 2, 3, 4) is H(H(H(1, 2), 3), 4).
//
// Fix the function `hash_chain` to correctly implement the
// hash chain. Run your code to test it.
//
// Note: Don't use starkware.cairo.common.hash_chain (it computes the chain differently).
// Use the Pedersen builtin.
%builtins pedersen
from starkware.cairo.common.alloc import alloc
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 `length` starting from `data_ptr`.
func hash_chain{hash_ptr: HashBuiltin*}(data_ptr: felt*, length: felt) -> (result: felt) {
if (length == 2) {
let (result) = hash2(x=[data_ptr], y=[data_ptr + 1]);
return (result=result);
} else {
// Fix here:
return (result=123456);
}
}
func main{pedersen_ptr: HashBuiltin*}() {
alloc_locals;
// Allocate a new array.
let (local data_ptr: felt*) = alloc();
// Fill the new array with field elements.
assert [data_ptr] = 314;
assert [data_ptr + 1] = 159;
// Run the hash chain.
let (result) = hash_chain{hash_ptr=pedersen_ptr}(data_ptr=data_ptr, length=2);
// Check the result.
assert result = 307958720726328212653290369969069617958360335228383070119367204176047090109;
// Fill two more cells in the array.
assert [data_ptr + 2] = 265;
assert [data_ptr + 3] = 358;
// Compute the hash chain on all four cells.
let (result) = hash_chain{hash_ptr=pedersen_ptr}(data_ptr=data_ptr, length=4);
assert result = 1828757374677754028678056220799392919487521050857166686061558043629802016816;
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
8 months ago
0
Accepted answer
A felt array
example: [1 ,2 ,3 ,4 ,5]
Pedersen hash of input
example: hash(hash(hash(hash(1, 2), 3), 4), 5).
hash_chain
function to calculate the output.Use temp
to store the last hash value. temp
starts with 0. the hash_chain
look like
hash_chain(temp: felt, data_ptr: felt*, length: felt)
length == 2
:
temp == 0
: our array has two elements, return hash(array[0], array[1])
temp != 0
: this is the end of the array, return hash(hash(temp, array[0]), array[1])
length > 2
:
temp == 0
: this is the top of the array. So we need to calculate the hash value of the two first elements and skip them in the next hash calculation. Then use recursion with arguments:
temp = hash(array[0]), array[1])
data_ptr = data_ptr + 2
length = length -2
temp == 0
: We calculate the hash value of the last hash value (temp
) and the next element. Then skip one element and use recursion with arguments:
temp = hash(temp , array[0])
data_ptr = data_ptr + 1
length = length - 1
func hash_chain{hash_ptr: HashBuiltin*}(init_value:felt, data_ptr: felt*, length: felt) -> (result: felt) {
if (length == 2) {
if (init_value == 0){
return hash2(x=[data_ptr], y=[data_ptr + 1]);
}
let (temp) = hash2(x=init_value, y=[data_ptr]);
let (result) = hash2(x=temp, y=[data_ptr + 1]);
return (result=result);
} else {
if (init_value == 0){
let (temp) = hash2(x=[data_ptr], y=[data_ptr + 1]);
return hash_chain{hash_ptr=hash_ptr}(init_value=temp, data_ptr=data_ptr + 2, length=length - 2);
}else{
let (temp) = hash2(x=init_value, y=[data_ptr]);
return hash_chain{hash_ptr=hash_ptr}(init_value=temp, data_ptr=data_ptr + 1, length=length - 1);
}
}
}
Because I changed the input of the hash_chain
function. So in main function is a little different when I invoke the hash_chain
function:
func main{pedersen_ptr: HashBuiltin*}() {
alloc_locals;
// Allocate a new array.
let (local data_ptr: felt*) = alloc();
// Fill the new array with field elements.
assert [data_ptr] = 314;
assert [data_ptr + 1] = 159;
// Run the hash chain.
let (result) = hash_chain{hash_ptr=pedersen_ptr}(init_value=0, data_ptr=data_ptr, length=2);
// Check the result.
assert result = 307958720726328212653290369969069617958360335228383070119367204176047090109;
// Fill two more cells in the array.
assert [data_ptr + 2] = 265;
assert [data_ptr + 3] = 358;
// Compute the hash chain on all four cells.
let (result) = hash_chain{hash_ptr=pedersen_ptr}(init_value=0, data_ptr=data_ptr, length=4);
assert result = 1828757374677754028678056220799392919487521050857166686061558043629802016816;
return ();
}
answered
8 months ago
0
My solution
// Use the Pedersen builtin.
%builtins pedersen
from starkware.cairo.common.alloc import alloc
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 `length` starting from `data_ptr`.
func hash_chain{hash_ptr: HashBuiltin*}(data_ptr: felt*, length: felt) -> (result: felt) {
alloc_locals;
if (length == 2) {
let (result) = hash2(x=[data_ptr], y=[data_ptr + 1]);
return (result=result);
} else {
// Fix here:
let (result_int) = hash2(x=[data_ptr], y=[data_ptr+1]);
// data_ptr = data_ptr+2, new_length = length-2
let (result) = cal_hash(result_int=result_int, data_ptr=data_ptr+2, length=length-2);
return (result=result);
}
}
func cal_hash{hash_ptr: HashBuiltin*}(result_int : felt, data_ptr : felt*, length: felt) -> (result : felt) {
if(length == 0) {
return (result=result_int);
} else {
let (result_int2) = hash2(x=result_int, y=[data_ptr]);
let (result) = cal_hash(result_int=result_int2, data_ptr=data_ptr+1, length=length-1);
return (result=result);
}
}
func main{pedersen_ptr: HashBuiltin*}() {
alloc_locals;
// Allocate a new array.
let (local data_ptr: felt*) = alloc();
// Fill the new array with field elements.
assert [data_ptr] = 314;
assert [data_ptr + 1] = 159;
// Run the hash chain.
let (result) = hash_chain{hash_ptr=pedersen_ptr}(data_ptr=data_ptr, length=2);
// Check the result.
assert result = 307958720726328212653290369969069617958360335228383070119367204176047090109;
// Fill two more cells in the array.
assert [data_ptr + 2] = 265;
assert [data_ptr + 3] = 358;
// Compute the hash chain on all four cells.
let (result) = hash_chain{hash_ptr=pedersen_ptr}(data_ptr=data_ptr, length=4);
assert result = 1828757374677754028678056220799392919487521050857166686061558043629802016816;
return ();
}
Prashant Banchhor
answered
8 months ago
How can I use dynamic allocation in Cairo?
How to use get_fp_and_pc in Cairo Lang?
How to write a function in Cairo Lang (StarkNet)?
Cairo Lang / StarkNet: What are Revoked references? What is alloc_locals?
How to divide felt in Cairo Lang using unsigned_div_rem?
How to make recursive function in Cairo Lang?
How to make conditional expressions if..then..else in Cairo lang?
Is anyone experiencing slowness on goerli StarkNet?
Is uint256 math operators like uint256_le safe? Why do I need to use uint256_check?
How to deploy a contract through starknet.py?
What if my solidity contract contains Assembly or special EVM calls ?
How do I run a Pathfinder node?
Cairo OR operator
Why can't mint NFT in starknet system now?