//! Keccak-256 cryptographic hash function implementation.
//!
//! # Main Functions
//!
//! - [`keccak_u256s_le_inputs`] - Hash multiple `u256` values in little-endian format
//! - [`keccak_u256s_be_inputs`] - Hash multiple `u256` values in big-endian format
//! - [`cairo_keccak`] - Hash u64 words with a final partial word. Closest to the syscall input.
//! - [`compute_keccak_byte_array`] - Hash a `ByteArray` directly
//!
//! # Examples
//!
//! ```
//! use core::keccak::*;
//!
//! // Hash u256 values
//! let input = array![1_u256, 2_u256].span();
//! assert!(keccak_u256s_le_inputs(input) ==
//! 0x234a9e12e9b063b60f7e3289ee9b86a731de8e7e41bd4987f10982d6a753444d);
//! assert!(keccak_u256s_be_inputs(input) ==
//! 0xe0c2a7d2cc99d544061ac0ccbb083ac8976e54eed878fb1854dfe7b6ce7b0be9);
//!
//! // Hash a `Bytearray`
//! let text: ByteArray = "Hello, Keccak!";
//! assert!(compute_keccak_byte_array(@text) ==
//! 0x85c9aab73219c1e95c5b5966a4ecc8db4418c3500072a830cfb5a2d13d2c2249);
//! ```
use starknet::SyscallResultTrait;
use crate::array::{ArrayTrait, Span, SpanTrait};
#[feature("byte-span")]
use crate::byte_array::ToByteSpanTrait;
#[feature("bounded-int-utils")]
use crate::internal::bounded_int::upcast;
use crate::num::traits::Split;
const KECCAK_FULL_RATE_IN_U64S: NonZero<usize> = 17;
fn keccak_add_u256_le(ref keccak_input: Array<u64>, v: u256) {
let (high, low) = v.low.split();
keccak_input.append(low);
keccak_input.append(high);
let (high, low) = v.high.split();
keccak_input.append(low);
keccak_input.append(high);
}
/// Computes the Keccak-256 hash of multiple `u256` values in little-endian format.
///
/// # Arguments
///
/// * `input` - A span of little-endian `u256` values to be hashed
///
/// # Returns
///
/// The 32-byte Keccak-256 hash as a little-endian `u256`
///
/// # Examples
///
/// ```
/// use core::keccak::keccak_u256s_le_inputs;
///
/// let input: Span<u256> = array![0, 1, 2].span();
/// assert!(keccak_u256s_le_inputs(input) ==
/// 0xf005473605efc7d8ff67d9f23fe2e4a4f23454c12b49b38822ed362e0a92a0a6);
/// ```
pub fn keccak_u256s_le_inputs(mut input: Span<u256>) -> u256 {
let mut keccak_input: Array<u64> = Default::default();
loop {
match input.pop_front() {
Some(v) => { keccak_add_u256_le(ref keccak_input, *v); },
None => { break (); },
}
}
add_padding(ref keccak_input, 0, 0);
starknet::syscalls::keccak_syscall(keccak_input.span()).unwrap_syscall()
}
fn keccak_add_u256_be(ref keccak_input: Array<u64>, v: u256) {
let (high, low) = crate::integer::u128_byte_reverse(v.high).split();
keccak_input.append(low);
keccak_input.append(high);
let (high, low) = crate::integer::u128_byte_reverse(v.low).split();
keccak_input.append(low);
keccak_input.append(high);
}
/// Computes the Keccak-256 hash of multiple `u256` values in big-endian format.
///
/// # Arguments
///
/// * `input` - A span of big-endian `u256` values to be hashed
///
/// # Returns
///
/// The 32-byte Keccak-256 hash as a little-endian `u256`
///
/// # Examples
///
/// ```
/// use core::keccak::keccak_u256s_be_inputs;
///
/// let input = array![0x1234_u256, 0x5678_u256].span();
/// let hash = assert!(keccak_u256s_be_inputs(input) ==
/// 0xfa31cb2326ed629f79d2da5beb78e2bd8ac7a1b8b86cae09eeb6a89a908b12a);
/// ```
pub fn keccak_u256s_be_inputs(mut input: Span<u256>) -> u256 {
let mut keccak_input: Array<u64> = Default::default();
loop {
match input.pop_front() {
Some(v) => { keccak_add_u256_be(ref keccak_input, *v); },
None => { break (); },
}
}
add_padding(ref keccak_input, 0, 0);
starknet::syscalls::keccak_syscall(keccak_input.span()).unwrap_syscall()
}
/// Computes the Keccak-256 hash of a byte sequence with custom padding.
///
/// This function allows hashing arbitrary byte sequences by providing the input as
/// 64-bit words in little-endian format and a final partial word.
///
/// # Arguments
///
/// * `input` - Array of complete 64-bit words in little-endian format
/// * `last_input_word` - Final partial word (if any)
/// * `last_input_num_bytes` - Number of valid bytes in the final word (0-7)
///
/// # Returns
///
/// The 32-byte Keccak-256 hash as a little-endian `u256`
///
/// # Panics
///
/// Panics if `last_input_num_bytes` is greater than 7.
///
/// # Examples
///
/// ```
/// use core::keccak::cairo_keccak;
///
/// // Hash "Hello world!" by splitting into 64-bit words in little-endian
/// let mut input = array![0x6f77206f6c6c6548]; // a full 8-byte word
/// let hash = cairo_keccak(ref input, 0x21646c72, 4); // 4 bytes of the last word
/// assert!(hash == 0xabea1f2503529a21734e2077c8b584d7bee3f45550c2d2f12a198ea908e1d0ec);
/// ```
pub fn cairo_keccak(
ref input: Array<u64>, last_input_word: u64, last_input_num_bytes: usize,
) -> u256 {
add_padding(ref input, last_input_word, last_input_num_bytes);
starknet::syscalls::keccak_syscall(input.span()).unwrap_syscall()
}
/// Adds Keccak-256 padding according to the "1 0* 1" rule.
///
/// # Arguments
///
/// * `input` - The buffer to pad
/// * `last_input_word` - Final partial word to include before padding
/// * `last_input_num_bytes` - Number of valid bytes in the final word (0-7)
///
/// # Panics
///
/// Panics if `last_input_num_bytes` is greater than 7.
fn add_padding(ref input: Array<u64>, last_input_word: u64, last_input_num_bytes: usize) {
// `last_block_num_full_words` is in range [0, KECCAK_FULL_RATE_IN_U64S - 1]
let (_, last_block_num_full_words) = crate::integer::u32_safe_divmod(
input.len(), KECCAK_FULL_RATE_IN_U64S,
);
// The first word to append would be of the form
// 0x1<`last_input_num_bytes` LSB bytes of `last_input_word`>.
// For example, for `last_input_num_bytes == 4`:
// 0x1000000 + (last_input_word & 0xffffff)
let first_word_to_append = if last_input_num_bytes == 0 {
// This case is handled separately to avoid unnecessary computations.
1
} else {
let first_padding_byte_part: NonZero<u64> = if last_input_num_bytes == 1 {
0x100
} else if last_input_num_bytes == 2 {
0x10000
} else if last_input_num_bytes == 3 {
0x1000000
} else if last_input_num_bytes == 4 {
0x100000000
} else if last_input_num_bytes == 5 {
0x10000000000
} else if last_input_num_bytes == 6 {
0x1000000000000
} else if last_input_num_bytes == 7 {
0x100000000000000
} else {
crate::panic_with_felt252('Keccak last input word >7b')
};
let (_, r) = crate::integer::u64_safe_divmod(last_input_word, first_padding_byte_part);
first_padding_byte_part.into() + r
};
const LAST_FULL_COUNT: usize = KECCAK_FULL_RATE_IN_U64S.into() - 1;
if last_block_num_full_words == LAST_FULL_COUNT {
input.append(0x8000000000000000 + first_word_to_append);
return;
}
// last_block_num_full_words < LAST_FULL_COUNT
input.append(first_word_to_append);
finalize_padding(ref input, LAST_FULL_COUNT - last_block_num_full_words);
}
/// Finalizes the padding by appending "0* 1".
fn finalize_padding(ref input: Array<u64>, num_padding_words: u32) {
if (num_padding_words == 1) {
input.append(0x8000000000000000);
return;
}
input.append(0);
finalize_padding(ref input, num_padding_words - 1);
}
/// Computes the Keccak-256 hash of a `ByteArray`.
///
/// # Arguments
///
/// * `arr` - The input bytes to hash
///
/// # Returns
///
/// The 32-byte Keccak-256 hash as a little-endian `u256`
///
/// # Examples
///
/// ```
/// use core::keccak::compute_keccak_byte_array;
///
/// let text: ByteArray = "Hello world!";
/// let hash = compute_keccak_byte_array(@text);
/// assert!(hash == 0xabea1f2503529a21734e2077c8b584d7bee3f45550c2d2f12a198ea908e1d0ec);
/// ```
pub fn compute_keccak_byte_array(arr: @ByteArray) -> u256 {
let mut iter = arr.span().into_iter();
let mut word_arr = array![];
let (last_word, last_word_len) = loop {
let Some(curr_word) = iter.next() else {
break (0, 0);
};
let Some(next_byte) = iter.next() else {
break (upcast(curr_word), 1);
};
let curr_word = conversions::prepend_byte(curr_word, next_byte, 0x100);
let Some(next_byte) = iter.next() else {
break (upcast(curr_word), 2);
};
let curr_word = conversions::prepend_byte(curr_word, next_byte, 0x10000);
let Some(next_byte) = iter.next() else {
break (upcast(curr_word), 3);
};
let curr_word = conversions::prepend_byte(curr_word, next_byte, 0x1000000);
let Some(next_byte) = iter.next() else {
break (upcast(curr_word), 4);
};
let curr_word = conversions::prepend_byte(curr_word, next_byte, 0x100000000);
let Some(next_byte) = iter.next() else {
break (upcast(curr_word), 5);
};
let curr_word = conversions::prepend_byte(curr_word, next_byte, 0x10000000000);
let Some(next_byte) = iter.next() else {
break (upcast(curr_word), 6);
};
let curr_word = conversions::prepend_byte(curr_word, next_byte, 0x1000000000000);
let Some(next_byte) = iter.next() else {
break (upcast(curr_word), 7);
};
let curr_word = conversions::prepend_byte(curr_word, next_byte, 0x100000000000000);
word_arr.append(upcast(curr_word));
};
add_padding(ref word_arr, last_word, last_word_len);
starknet::syscalls::keccak_syscall(word_arr.span()).unwrap_syscall()
}
mod conversions {
#[feature("bounded-int-utils")]
use core::internal::bounded_int::{self, AddHelper, BoundedInt, MulHelper, UnitInt};
impl U8Shift8 of MulHelper<u8, UnitInt<0x100>> {
type Result = BoundedInt<0, 0xFF00>;
}
impl U8Shift16 of MulHelper<u8, UnitInt<0x10000>> {
type Result = BoundedInt<0, 0xFF0000>;
}
impl U8Shift24 of MulHelper<u8, UnitInt<0x1000000>> {
type Result = BoundedInt<0, 0xFF000000>;
}
impl U8Shift32 of MulHelper<u8, UnitInt<0x100000000>> {
type Result = BoundedInt<0, 0xFF00000000>;
}
impl U8Shift40 of MulHelper<u8, UnitInt<0x10000000000>> {
type Result = BoundedInt<0, 0xFF0000000000>;
}
impl U8Shift48 of MulHelper<u8, UnitInt<0x1000000000000>> {
type Result = BoundedInt<0, 0xFF000000000000>;
}
impl U8Shift56 of MulHelper<u8, UnitInt<0x100000000000000>> {
type Result = BoundedInt<0, 0xFF00000000000000>;
}
impl U8ShiftAddU8 of AddHelper<u8, U8Shift8::Result> {
type Result = BoundedInt<0, 0xFFFF>;
}
impl U8ShiftAddU16 of AddHelper<U8ShiftAddU8::Result, U8Shift16::Result> {
type Result = BoundedInt<0, 0xFFFFFF>;
}
impl U8ShiftAddU24 of AddHelper<U8ShiftAddU16::Result, U8Shift24::Result> {
type Result = BoundedInt<0, 0xFFFFFFFF>;
}
impl U8ShiftAddU32 of AddHelper<U8ShiftAddU24::Result, U8Shift32::Result> {
type Result = BoundedInt<0, 0xFFFFFFFFFF>;
}
impl U8ShiftAddU40 of AddHelper<U8ShiftAddU32::Result, U8Shift40::Result> {
type Result = BoundedInt<0, 0xFFFFFFFFFFFF>;
}
impl U8ShiftAddU48 of AddHelper<U8ShiftAddU40::Result, U8Shift48::Result> {
type Result = BoundedInt<0, 0xFFFFFFFFFFFFFF>;
}
impl U8ShiftAddU56 of AddHelper<U8ShiftAddU48::Result, U8Shift56::Result> {
type Result = BoundedInt<0, 0xFFFFFFFFFFFFFFFF>;
}
trait PrependByte<T, const C: felt252, MulResult> {
impl Mul: MulHelper<u8, UnitInt<C>>;
impl Add: AddHelper<T, MulResult>;
}
// Blanket implementation for any type with appropriate helpers.
impl PrependByteImpl<
T, const C: felt252, impl MH: MulHelper<u8, UnitInt<C>>, impl AH: AddHelper<T, MH::Result>,
> of PrependByte<T, C, MH::Result> {}
/// Shifts a byte to be the next byte of the word.
pub fn prepend_byte<
T,
const C: felt252,
MulResult,
impl PB: PrependByte<T, C, MulResult>,
+core::metaprogramming::TypeEqual<MulResult, PB::Mul::Result>,
>(
word: T, byte: u8, shift: UnitInt<C>,
) -> PB::Add::Result {
bounded_int::add::<_, _, PB::Add>(word, bounded_int::mul::<_, _, PB::Mul>(byte, shift))
}
}