hash_chain.cairo

# cairo programming exercise

%builtins output pedersen

from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.cairo_builtins import HashBuiltin

# compute H(x, y)
func compute_hash(hash_ptr : HashBuiltin*, x, y) -> (
        hash_ptr : HashBuiltin*, z):
    let hash = cast(hash_ptr, HashBuiltin*)
    hash.x = x
    hash.y = y
    [ap] = hash_ptr + HashBuiltin.SIZE; ap++
    [ap] = hash.result; ap++
    ret
end

# compute H(...H(H(arr[0], arr[1]), arr[2]),...arr[size - 1])
func compute_hash_chain(hash_ptr : HashBuiltin*, arr, size) -> (hash_ptr: HashBuiltin*, hash):
    if size == 2:
        let (hash_ptr, hash) = compute_hash(hash_ptr, [arr], [arr + 1])
        return (hash_ptr=hash_ptr, hash=hash)
    end

    let (hash_ptr, hash) = compute_hash_chain(hash_ptr, arr=arr, size=size - 1)
    let (hash_ptr, hash) = compute_hash(hash_ptr, hash, [arr + size - 1])
    return (hash_ptr=hash_ptr, hash=hash)
end

func main(output_ptr, pedersen_ptr: HashBuiltin*) -> (output_ptr, pedersen_ptr):
    const ARRAY_SIZE = 3
    let (ptr) = alloc()
    assert [ptr] = 3
    assert [ptr + 1] = 5
    assert [ptr + 2] = 8

    let (pedersen_ptr, z) = compute_hash_chain(pedersen_ptr, ptr, ARRAY_SIZE)
    [output_ptr] = z
    [ap] = output_ptr + 1; ap++
    [ap] = pedersen_ptr; ap++

    ret
end