miden_air/trace/chiplets/
hasher.rs

1//! Hasher chiplet trace constants and types.
2//!
3//! This module defines the structure of the hasher chiplet's execution trace, including:
4//! - Trace selectors that determine which hash operation is being performed
5//! - State layout for the Poseidon2 permutation (12 field elements: 8 rate + 4 capacity)
6//! - Column ranges and indices for accessing trace data
7//!
8//! The hasher chiplet supports several operations:
9//! - Linear hashing (absorbing arbitrary-length inputs)
10//! - 2-to-1 hashing (Merkle tree node computation)
11//! - Merkle path verification
12//! - Merkle root updates (for authenticated data structure modifications)
13
14use core::ops::Range;
15
16pub use miden_core::{Word, crypto::hash::Poseidon2 as Hasher};
17
18use super::{Felt, HASH_KERNEL_VTABLE_AUX_TRACE_OFFSET, ONE, ZERO, create_range};
19
20// TYPES ALIASES
21// ================================================================================================
22
23/// Type for Hasher trace selector. These selectors are used to define which transition function
24/// is to be applied at a specific row of the hasher execution trace.
25pub type Selectors = [Felt; NUM_SELECTORS];
26
27/// Type for the Hasher's state.
28pub type HasherState = [Felt; STATE_WIDTH];
29
30// CONSTANTS
31// ================================================================================================
32
33/// Number of field element needed to represent the sponge state for the hash function.
34///
35/// This value is set to 12: 8 elements are reserved for rate and the remaining 4 elements are
36/// reserved for capacity. This configuration enables computation of 2-to-1 hash in a single
37/// permutation.
38/// The sponge state is `[RATE0(4), RATE1(4), CAPACITY(4)]`.
39pub const STATE_WIDTH: usize = Hasher::STATE_WIDTH;
40
41/// The hasher state portion of the execution trace, located in columns 3..15.
42pub const STATE_COL_RANGE: Range<usize> = create_range(NUM_SELECTORS, STATE_WIDTH);
43
44/// Number of field elements in the capacity portion of the hasher's state.
45pub const CAPACITY_LEN: usize = STATE_WIDTH - RATE_LEN;
46
47/// The index in the hasher state where the domain is set when initializing the hasher.
48///
49/// The domain is stored in the second element of the capacity word.
50/// With LE sponge state layout [RATE0, RATE1, CAP], this is at index 9 (= CAPACITY_RANGE.start +
51/// 1).
52pub const CAPACITY_DOMAIN_IDX: usize = 9;
53
54/// Number of field elements in the rate portion of the hasher's state.
55pub const RATE_LEN: usize = 8;
56
57/// The rate portion of the hasher state in the execution trace, located in columns 3..11.
58/// With LE sponge state layout [RATE0, RATE1, CAP], rate comes first.
59pub const RATE_COL_RANGE: Range<usize> = Range {
60    start: STATE_COL_RANGE.start,
61    end: STATE_COL_RANGE.start + RATE_LEN,
62};
63
64/// The capacity portion of the hasher state in the execution trace, located in columns 11..15.
65/// With LE sponge state layout [RATE0, RATE1, CAP], capacity comes last.
66pub const CAPACITY_COL_RANGE: Range<usize> = Range {
67    start: RATE_COL_RANGE.end,
68    end: RATE_COL_RANGE.end + CAPACITY_LEN,
69};
70
71// The length of the output portion of the hash state.
72pub const DIGEST_LEN: usize = 4;
73
74/// The output portion of the hash state, located in the first rate word (RATE0).
75pub const DIGEST_RANGE: Range<usize> = Hasher::DIGEST_RANGE;
76
77/// Number of round steps used to complete a single permutation.
78///
79/// For Poseidon2, we model a permutation as 31 step transitions, resulting in a 32-row cycle.
80pub const NUM_ROUNDS: usize = miden_core::chiplets::hasher::NUM_ROUNDS;
81
82/// Index of the last row in a permutation cycle (0-based).
83pub const LAST_CYCLE_ROW: usize = NUM_ROUNDS;
84pub const LAST_CYCLE_ROW_FELT: Felt = Felt::new(LAST_CYCLE_ROW as u64);
85
86/// Number of selector columns in the trace.
87pub const NUM_SELECTORS: usize = 3;
88
89/// The number of rows in the execution trace required to compute a permutation of Poseidon2.
90/// This is equal to 32.
91pub const HASH_CYCLE_LEN: usize = NUM_ROUNDS.next_power_of_two();
92pub const HASH_CYCLE_LEN_FELT: Felt = Felt::new(HASH_CYCLE_LEN as u64);
93
94/// Number of columns in Hasher execution trace. There is one additional column for the node index.
95pub const TRACE_WIDTH: usize = NUM_SELECTORS + STATE_WIDTH + 1;
96
97// --- Transition selectors -----------------------------------------------------------------------
98
99/// Specifies a start of a new linear hash computation or absorption of new elements into an
100/// executing linear hash computation. These selectors can also be used for a simple 2-to-1 hash
101/// computation.
102pub const LINEAR_HASH: Selectors = [ONE, ZERO, ZERO];
103/// Unique label computed as 1 plus the full chiplet selector with the bits reversed.
104/// `selector = [0 | 1, 0, 0]`, `flag = rev(selector) + 1 = [0, 0, 1 | 0] + 1 = 3`
105pub const LINEAR_HASH_LABEL: u8 = 0b0010 + 1;
106
107/// Specifies a start of Merkle path verification computation or absorption of a new path node
108/// into the hasher state.
109pub const MP_VERIFY: Selectors = [ONE, ZERO, ONE];
110/// Unique label computed as 1 plus the full chiplet selector with the bits reversed.
111/// `selector = [0 | 1, 0, 1]`, `flag = rev(selector) + 1 = [1, 0, 1 | 0] + 1 = 11`
112pub const MP_VERIFY_LABEL: u8 = 0b1010 + 1;
113
114/// Specifies a start of Merkle path verification or absorption of a new path node into the hasher
115/// state for the "old" node value during Merkle root update computation.
116pub const MR_UPDATE_OLD: Selectors = [ONE, ONE, ZERO];
117/// Unique label computed as 1 plus the full chiplet selector with the bits reversed.
118/// `selector = [0 | 1, 1, 0]`, `flag = rev(selector) + 1 = [0, 1, 1 | 0] + 1 = 7`
119pub const MR_UPDATE_OLD_LABEL: u8 = 0b0110 + 1;
120
121/// Specifies a start of Merkle path verification or absorption of a new path node into the hasher
122/// state for the "new" node value during Merkle root update computation.
123pub const MR_UPDATE_NEW: Selectors = [ONE, ONE, ONE];
124/// Unique label computed as 1 plus the full chiplet selector with the bits reversed.
125/// `selector = [0 | 1, 1, 1]`, `flag = rev(selector) + 1 = [1, 1, 1 | 0] + 1 = 15`
126pub const MR_UPDATE_NEW_LABEL: u8 = 0b1110 + 1;
127
128/// Specifies a completion of a computation such that only the hash result (values in h0, h1, h2
129/// h3) is returned.
130pub const RETURN_HASH: Selectors = [ZERO, ZERO, ZERO];
131/// Unique label computed as 1 plus the full chiplet selector with the bits reversed.
132/// `selector = [0 | 0, 0, 0]`, `flag = rev(selector) + 1 = [0, 0, 0 | 0] + 1 = 1`
133#[expect(clippy::identity_op)]
134pub const RETURN_HASH_LABEL: u8 = 0b0000 + 1;
135
136/// Specifies a completion of a computation such that the entire hasher state (values in h0 through
137/// h11) is returned.
138pub const RETURN_STATE: Selectors = [ZERO, ZERO, ONE];
139/// Unique label computed as 1 plus the full chiplet selector with the bits reversed.
140/// `selector = [0 | 0, 0, 1]`, `flag = rev(selector) + 1 = [1, 0, 0 | 0] + 1 = 9`
141pub const RETURN_STATE_LABEL: u8 = 0b1000 + 1;
142
143// --- Column accessors in the auxiliary trace ----------------------------------------------------
144
145/// Index of the auxiliary trace column tracking the state of the sibling table.
146pub const P1_COL_IDX: usize = HASH_KERNEL_VTABLE_AUX_TRACE_OFFSET;
miden_air/trace/chiplets/hasher.rs

miden_air/trace/chiplets/
hasher.rs
