NEWTON

NEWTON

# How to use Pedersen Hash in StarkNet / Cairo Language?

3 months ago

73

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

#17daysOfCairocairo-beginnerscairoplayground

Newton

3 months ago

0

## 1. Input

• A felt array

``````example: [1 ,2 ,3 ,4 ,5]
``````

## 2. Output

• Pedersen hash of input

``````example: hash(hash(hash(hash(1, 2), 3), 4), 5).
``````

## 3. Requirement

• Define the `hash_chain` function to calculate the output.

## 4. Solution

• 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)
``````

• If array's `length == 2` :
• If `temp == 0`: our array has two elements, return `hash(array, array)`
• If `temp != 0`: this is the end of the array, return `hash(hash(temp, array), array)`

• If array's `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), array)
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)
data_ptr = data_ptr + 1
length = length - 1
``````

## 5. Source code

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

3 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

3 months ago