I. Task

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[0], array[1])
  • If temp != 0: this is the end of the array, return hash(hash(temp, array[0]), array[1])

---

---

• 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[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    
    

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

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