Hashes

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 核心库提供了两种哈希函数：Pedersen 和 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 上最初使用的哈希函数，现在仍用于计算存储中变量的地址（例如，LegacyMap 使用 Pedersen 对 Starknet 上存储映射的键进行哈希）。然而，由于 Poseidon 在处理 STARK 证明系统时比 Pedersen 更便宜，更快，因此现在它已成为 Cairo 程序中推荐使用的哈希函数。

使用哈希

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

要在代码中使用哈希，您必须首先导入相关的trait和函数。在以下示例中，我们将演示如何使用 Pedersen 和 Poseidon 哈希函数对结构体进行哈希处理。

首先，需要根据我们想要使用的哈希函数，使用 PoseidonTrait::new() -> HashState 或 PedersenTrait::new(base: felt252) -> HashState 初始化哈希状态。然后，可以使用 update(self: HashState, value: felt252) -> HashState 或 update_with(self: S, value: T) -> S 函数多次更新哈希状态，具体更新次数取决于需要。最后，使用 finalize(self: HashState) -> felt252 函数完成哈希计算并返回哈希值。

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 is different from Poseidon, as it starts with a base state. This base state must be of felt252 type, which forces us to either hash the struct with an arbitrary base state using the update_with method, or serialize the struct into an array to loop through all of its fields and hash its elements together.

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