Hashler

At its essence, hashing is a process of converting input data (often called a message) of any length into a fixed-size value, typically referred to as a "hash." This transformation is deterministic, meaning that the same input will always produce the same hash value. Hash functions are a fundamental component in various fields, including data storage, cryptography and data integrity verification. They are very often used when developing smart contracts, especially when working with Merkle trees.

In this chapter, we will present the two hash functions implemented natively in the Cairo core library: Poseidon and Pedersen. We will discuss when and how to use them, and see examples with Cairo programs.

Hash Functions in Cairo

Cairo çekirdek kitaplığı iki hash fonksiyonu sağlar: Pedersen ve Poseidon.

Pedersen hash functions are cryptographic algorithms that rely on elliptic curve cryptography. These functions perform operations on points along an elliptic curve — essentially, doing math with the locations of these points — which are easy to do in one direction and hard to undo. This one-way difficulty is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP), which is a problem so hard to solve that it ensures the security of the hash function. The difficulty of reversing these operations is what makes the Pedersen hash function secure and reliable for cryptographic purposes.

Poseidon is a family of hash functions designed to be very efficient as algebraic circuits. Its design is particularly efficient for Zero-Knowledge proof systems, including STARKs (so, Cairo). Poseidon uses a method called a 'sponge construction,' which soaks up data and transforms it securely using a process known as the Hades permutation. Cairo's version of Poseidon is based on a three-element state permutation with specific parameters.

When to Use Them?

Pedersen, Starknet'te kullanılan ilk hash fonksiyonuydu ve hala depolama alanındaki değişkenlerin adreslerini hesaplamak için kullanılmaktadır (örneğin, LegacyMap Starknet'te bir depolama eşlemesinin anahtarlarını hashlemek için Pedersen kullanır). Ancak, Poseidon STARK kanıt sistemiyle çalışırken Pedersen'den daha ucuz ve daha hızlı olduğundan, şimdi Kahire programlarında kullanılması önerilen hash fonksiyonudur.

Hash'lerle Çalışma

The core library makes it easy to work with hashes. The Hash trait is implemented for all types that can be converted to felt252, including felt252 itself. For more complex types like structs, deriving Hash allows them to be hashed easily using the hash function of your choice - given that all of the struct's fields are themselves hashable. You cannot derive the Hash trait on a struct that contains un-hashable values, such as Array<T> or Felt252Dict<T>, even if T itself is hashable.

The Hash trait is accompanied by the HashStateTrait and HashStateExTrait that define the basic methods to work with hashes. They allow you to initialize a hash state that will contain the temporary values of the hash after each application of the hash function, update the hash state and finalize it when the computation is completed. HashStateTrait and HashStateExTrait are defined as follows:

/// A trait for hash state accumulators.
trait HashStateTrait<S> {
    fn update(self: S, value: felt252) -> S;
    fn finalize(self: S) -> felt252;
}

/// Extension trait for hash state accumulators.
trait HashStateExTrait<S, T> {
    /// Updates the hash state with the given value.
    fn update_with(self: S, value: T) -> S;
}

/// A trait for values that can be hashed.
trait Hash<T, S, +HashStateTrait<S>> {
    /// Updates the hash state with the given value.
    fn update_state(state: S, value: T) -> S;
}

Kodunuzda hash'leri kullanmak için, ilgili özellikleri ve fonksiyonları önce içe aktarmanız gerekir. Aşağıdaki örnekte, hem Pedersen hem de Poseidon hash fonksiyonlarını kullanarak bir yapıyı nasıl hashleyeceğimizi göstereceğiz.

İlk adım, hangi hash fonksiyonuyla çalışmak istediğimize bağlı olarak ya PoseidonTrait::new() -> HashState ya da PedersenTrait::new(base: felt252) -> HashState ile hash'i başlatmaktır. Daha sonra hash durumu, gerektiği kadar update(self: HashState, value: felt252) -> HashState veya update_with(self: S, value: T) -> S fonksiyonları ile güncellenebilir. Sonra finalize(self: HashState) -> felt252 fonksiyonu hash durumu üzerinde çağrılır ve hash değeri bir felt252 olarak döndürülür.

use core::poseidon::PoseidonTrait;
use core::hash::{HashStateTrait, HashStateExTrait};

#[derive(Drop, Hash)]
struct StructForHash {
    first: felt252,
    second: felt252,
    third: (u32, u32),
    last: bool,
}

fn main() -> felt252 {
    let struct_to_hash = StructForHash { first: 0, second: 1, third: (1, 2), last: false };

    let hash = PoseidonTrait::new().update_with(struct_to_hash).finalize();
    hash
}

Pedersen, bir temel durumla başladığı için Poseidon'dan farklıdır. Bu temel durum felt252 türünde olmalıdır, bu da bizi ya update_with metodunu kullanarak yapıyı keyfi bir temel durumla hashlemeye ya da yapıyı bir diziye seri hale getirip tüm alanlarını döngüye alıp elemanlarını birlikte hashlemeye zorlar.

Here is a short example of Pedersen hashing:

use core::pedersen::PedersenTrait;
use core::hash::{HashStateTrait, HashStateExTrait};

#[derive(Drop, Hash, Serde, Copy)]
struct StructForHash {
    first: felt252,
    second: felt252,
    third: (u32, u32),
    last: bool,
}

fn main() -> (felt252, felt252) {
    let struct_to_hash = StructForHash { first: 0, second: 1, third: (1, 2), last: false };

    // hash1 is the result of hashing a struct with a base state of 0
    let hash1 = PedersenTrait::new(0).update_with(struct_to_hash).finalize();

    let mut serialized_struct: Array<felt252> = ArrayTrait::new();
    Serde::serialize(@struct_to_hash, ref serialized_struct);
    let first_element = serialized_struct.pop_front().unwrap();
    let mut state = PedersenTrait::new(first_element);

    while let Option::Some(value) = serialized_struct.pop_front() {
        state = state.update(value);
    };

    // hash2 is the result of hashing only the fields of the struct
    let hash2 = state.finalize();

    (hash1, hash2)
}

Advanced Hashing: Hashing Arrays with Poseidon

Let us look at an example of hashing a struct that contains a Span<felt252>. To hash a Span<felt252> or a struct that contains a Span<felt252> you can use the built-in function poseidon_hash_span(mut span: Span<felt252>) -> felt252. Similarly, you can hash Array<felt252> by calling poseidon_hash_span on its span.

First, let us import the following traits and function:

use core::poseidon::PoseidonTrait;
use core::poseidon::poseidon_hash_span;
use core::hash::{HashStateTrait, HashStateExTrait};

Now we define the struct. As you might have noticed, we didn't derive the Hash trait. If you attempt to derive the Hash trait for this struct, it will result in an error because the structure contains a field that is not hashable.

#[derive(Drop)]
struct StructForHashArray {
    first: felt252,
    second: felt252,
    third: Array<felt252>,
}

In this example, we initialized a HashState (hash), updated it and then called the function finalize() on the HashState to get the computed hash hash_felt252. We used poseidon_hash_span on the Span of the Array<felt252> to compute its hash.

use core::poseidon::PoseidonTrait;
use core::poseidon::poseidon_hash_span;
use core::hash::{HashStateTrait, HashStateExTrait};

#[derive(Drop)]
struct StructForHashArray {
    first: felt252,
    second: felt252,
    third: Array<felt252>,
}

fn main() {
    let struct_to_hash = StructForHashArray { first: 0, second: 1, third: array![1, 2, 3, 4, 5] };

    let mut hash = PoseidonTrait::new().update(struct_to_hash.first).update(struct_to_hash.second);
    let hash_felt252 = hash.update(poseidon_hash_span(struct_to_hash.third.span())).finalize();
}