miden_precompiles/hash/
mod.rs

1//! Shared base for hash precompiles.
2//!
3//! [`HashPrecompile<H>`] implements the generic hash assertion protocol. A hash assertion is one
4//! precompile-owned join node tagged `[hash_id, ASSERT_DISC, n_bytes, 0]` over two framework-owned
5//! [`Tag::CHUNKS`](miden_core::deferred::Tag::CHUNKS) children: the preimage bytes and the expected
6//! digest bytes.
7
8use alloc::vec::Vec;
9use core::marker::PhantomData;
10
11use miden_core::{
12    Felt, ZERO,
13    deferred::{
14        DeferredContext, Digest, Node, NodeType, Payload, Precompile, PrecompileError, Tag,
15        precompile_id,
16    },
17};
18
19use crate::codec::{chunks_to_bytes_exact, n_chunks};
20
21pub mod keccak256;
22
23// HASH FUNCTION
24// ================================================================================================
25
26/// The byte-level hash backing a [`HashPrecompile`].
27pub trait HashFunction: Default + Send + Sync + 'static {
28    /// Stable name hashed into the precompile id; renaming changes every tag it owns.
29    const NAME: &'static str;
30    /// u32-packed-LE felts in the digest (8 for a 256-bit hash, 16 for 512-bit).
31    const DIGEST_FELTS: usize;
32    /// Hashes `input`, returning the digest as `DIGEST_FELTS * 4` bytes.
33    fn hash(input: &[u8]) -> Vec<u8>;
34}
35
36// HASH PRECOMPILE
37// ================================================================================================
38
39const ASSERT_DISC: u32 = 0;
40
41/// A structural view of a hash assertion node owned by [`HashPrecompile`].
42///
43/// This exposes only the assertion tag immediate and join child digests; it does not evaluate the
44/// preimage or expected digest children.
45#[derive(Debug, Clone, Copy, PartialEq, Eq)]
46pub struct HashAssertNode {
47    /// Declared preimage length in bytes.
48    pub n_bytes: u32,
49    /// Structural digest of the preimage chunk-list child.
50    pub preimage_digest: Digest,
51    /// Structural digest of the expected-digest chunk-list child.
52    pub expected_digest: Digest,
53}
54
55/// A hash assertion precompile parameterized by its [`HashFunction`].
56pub struct HashPrecompile<H>(PhantomData<H>);
57
58impl<H> Default for HashPrecompile<H> {
59    fn default() -> Self {
60        Self(PhantomData)
61    }
62}
63
64impl<H: HashFunction> HashPrecompile<H> {
65    /// Local discriminant of the assertion tag.
66    pub const ASSERT_TAG_ID: u32 = ASSERT_DISC;
67
68    /// Derives this precompile's id from its [`HashFunction::NAME`].
69    pub fn id() -> Felt {
70        precompile_id(H::NAME)
71    }
72
73    /// Tag for a hash assertion node carrying the preimage byte length.
74    pub fn assert_tag(n_bytes: u32) -> Tag {
75        Self::tag([Felt::from_u32(ASSERT_DISC), Felt::from_u32(n_bytes), ZERO])
76    }
77
78    /// Builds a hash assertion predicate over generic chunk-list children.
79    pub fn assert_node(n_bytes: u32, preimage_digest: Digest, expected_digest: Digest) -> Node {
80        Node::join(Self::assert_tag(n_bytes), preimage_digest, expected_digest)
81            .expect("assert tag is precompile-owned")
82    }
83
84    /// Decodes a hash assertion tag owned by this precompile.
85    ///
86    /// Returns `Ok(None)` when `tag` belongs to another precompile. Tags with this precompile's id
87    /// but invalid assertion arguments return [`PrecompileError::InvalidNode`].
88    pub fn decode_assert_tag(tag: Tag) -> Result<Option<u32>, PrecompileError> {
89        if tag.id() != Self::id() {
90            return Ok(None);
91        }
92
93        let args = tag.args();
94        let disc =
95            u32::try_from(args[0].as_canonical_u64()).map_err(|_| PrecompileError::InvalidNode)?;
96        let n_bytes =
97            u32::try_from(args[1].as_canonical_u64()).map_err(|_| PrecompileError::InvalidNode)?;
98        if disc != ASSERT_DISC || args[2] != ZERO {
99            return Err(PrecompileError::InvalidNode);
100        }
101
102        Ok(Some(n_bytes))
103    }
104
105    /// Decodes a hash assertion node without evaluating its children.
106    ///
107    /// Returns `Ok(None)` when `node` belongs to another precompile. Owned nodes return their
108    /// structural join child digests directly from the payload.
109    pub fn decode_assert_node(node: &Node) -> Result<Option<HashAssertNode>, PrecompileError> {
110        let Some(n_bytes) = Self::decode_assert_tag(node.tag())? else {
111            return Ok(None);
112        };
113        let (preimage_digest, expected_digest) = node.payload().as_join()?;
114        Ok(Some(HashAssertNode {
115            n_bytes,
116            preimage_digest,
117            expected_digest,
118        }))
119    }
120
121    fn tag(args: [Felt; 3]) -> Tag {
122        Tag::precompile(Self::id(), args).expect("hash precompile id is not framework-reserved")
123    }
124
125    fn digest_chunks() -> usize {
126        H::DIGEST_FELTS.div_ceil(8)
127    }
128}
129
130impl<H: HashFunction> Precompile for HashPrecompile<H> {
131    fn name(&self) -> &'static str {
132        H::NAME
133    }
134
135    fn id(&self) -> Felt {
136        Self::id()
137    }
138
139    fn decode(&self, args: [Felt; 3]) -> Option<NodeType> {
140        let disc = u32::try_from(args[0].as_canonical_u64()).ok()?;
141        if disc != ASSERT_DISC || args[2] != ZERO {
142            return None;
143        }
144        u32::try_from(args[1].as_canonical_u64()).ok()?;
145        Some(NodeType::Join)
146    }
147
148    fn evaluate(
149        &self,
150        args: [Felt; 3],
151        payload: &Payload,
152        context: &mut DeferredContext<'_>,
153    ) -> Result<Node, PrecompileError> {
154        let disc =
155            u32::try_from(args[0].as_canonical_u64()).map_err(|_| PrecompileError::InvalidNode)?;
156        let n_bytes =
157            u32::try_from(args[1].as_canonical_u64()).map_err(|_| PrecompileError::InvalidNode)?;
158        if disc != ASSERT_DISC || args[2] != ZERO {
159            return Err(PrecompileError::InvalidNode);
160        }
161
162        let (preimage_digest, expected_digest) = payload.as_join()?;
163        let preimage = chunks_child_to_bytes(
164            context,
165            preimage_digest,
166            n_chunks(n_bytes).get() as usize,
167            n_bytes as usize,
168        )?;
169        let expected = chunks_child_to_bytes(
170            context,
171            expected_digest,
172            Self::digest_chunks(),
173            H::DIGEST_FELTS * size_of::<u32>(),
174        )?;
175
176        if expected != H::hash(&preimage) {
177            return Err(PrecompileError::AssertionFailed);
178        }
179        Ok(Node::TRUE)
180    }
181}
182
183fn chunks_child_to_bytes(
184    context: &mut DeferredContext<'_>,
185    digest: Digest,
186    expected_chunks: usize,
187    n_bytes: usize,
188) -> Result<Vec<u8>, PrecompileError> {
189    let canonical_digest = context.evaluate_digest(digest)?;
190    let canonical_node = context.get_node(&canonical_digest).ok_or(PrecompileError::InvalidNode)?;
191    if canonical_node.tag() != Tag::CHUNKS {
192        return Err(PrecompileError::InvalidNode);
193    }
194    let chunks = canonical_node.payload().as_data()?;
195    chunks_to_bytes_exact(chunks, expected_chunks, n_bytes)
196}
197
198// TEST SUPPORT
199// ================================================================================================
200
201/// Exercises the shared hash assertion protocol for `H`.
202#[cfg(test)]
203pub(crate) fn assert_hash_precompile<H: HashFunction>() {
204    use alloc::{sync::Arc, vec, vec::Vec};
205
206    use miden_core::{
207        deferred::{DeferredState, PrecompileRegistry, TRUE_DIGEST, Tag},
208        utils::bytes_to_packed_u32_elements,
209    };
210
211    fn chunks_from_bytes(bytes: &[u8]) -> Vec<[Felt; 8]> {
212        Node::chunks_from_bytes(bytes)
213            .payload()
214            .as_data()
215            .expect("chunks_from_bytes creates data payload")
216            .to_vec()
217    }
218
219    fn digest_chunks<H: HashFunction>(input: &[u8]) -> Vec<[Felt; 8]> {
220        let mut felts = bytes_to_packed_u32_elements(&H::hash(input));
221        felts.resize(HashPrecompile::<H>::digest_chunks() * 8, ZERO);
222        felts
223            .as_chunks::<8>()
224            .0
225            .iter()
226            .map(|c| core::array::from_fn(|i| c[i]))
227            .collect()
228    }
229
230    let fresh = || {
231        DeferredState::new(Arc::new(
232            PrecompileRegistry::new().with_precompile(HashPrecompile::<H>::default()),
233        ))
234        .expect("hash precompile initialization should fit the test budget")
235    };
236    let assert_registers = |state: &mut DeferredState,
237                            n_bytes: u32,
238                            preimage_chunks: Vec<[Felt; 8]>,
239                            expected_chunks: Vec<[Felt; 8]>|
240     -> Result<Digest, PrecompileError> {
241        let preimage = state.register(Node::chunks(preimage_chunks).expect("preimage chunks"))?;
242        let expected = state.register(Node::chunks(expected_chunks).expect("expected chunks"))?;
243        state.register(HashPrecompile::<H>::assert_node(n_bytes, preimage, expected))
244    };
245    let assert_error = |err: PrecompileError, expected: PrecompileError| {
246        assert!(
247            matches!(
248                (err.root(), &expected),
249                (PrecompileError::InvalidNode, PrecompileError::InvalidNode)
250                    | (PrecompileError::AssertionFailed, PrecompileError::AssertionFailed)
251            ),
252            "unexpected error root: {err:?}"
253        );
254    };
255
256    let pc = HashPrecompile::<H>::default();
257    assert_eq!(
258        pc.decode([Felt::from_u32(HashPrecompile::<H>::ASSERT_TAG_ID), Felt::from_u32(65), ZERO]),
259        Some(NodeType::Join),
260    );
261    assert!(pc.decode([Felt::from_u32(1), ZERO, ZERO]).is_none());
262    assert!(
263        pc.decode([
264            Felt::from_u32(HashPrecompile::<H>::ASSERT_TAG_ID),
265            Felt::from_u32(65),
266            Felt::from_u32(1),
267        ])
268        .is_none()
269    );
270    let non_u32 = Felt::new_unchecked(u64::from(u32::MAX) + 1);
271    assert!(pc.decode([non_u32, ZERO, ZERO]).is_none());
272    assert!(
273        pc.decode([Felt::from_u32(HashPrecompile::<H>::ASSERT_TAG_ID), non_u32, ZERO])
274            .is_none()
275    );
276
277    let assert_tag = HashPrecompile::<H>::assert_tag(65);
278    assert_eq!(HashPrecompile::<H>::decode_assert_tag(assert_tag).unwrap(), Some(65));
279    assert_eq!(HashPrecompile::<H>::decode_assert_tag(Tag::CHUNKS).unwrap(), None);
280    let invalid_assert_tag =
281        HashPrecompile::<H>::tag([Felt::from_u32(1), Felt::from_u32(65), ZERO]);
282    assert!(matches!(
283        HashPrecompile::<H>::decode_assert_tag(invalid_assert_tag),
284        Err(PrecompileError::InvalidNode)
285    ));
286
287    let assert_node = HashPrecompile::<H>::assert_node(65, TRUE_DIGEST, TRUE_DIGEST);
288    assert_eq!(HashPrecompile::<H>::decode_assert_node(&Node::TRUE).unwrap(), None);
289    assert_eq!(
290        HashPrecompile::<H>::decode_assert_node(&assert_node).unwrap(),
291        Some(HashAssertNode {
292            n_bytes: 65,
293            preimage_digest: TRUE_DIGEST,
294            expected_digest: TRUE_DIGEST,
295        })
296    );
297    let invalid_node = Node::join(invalid_assert_tag, TRUE_DIGEST, TRUE_DIGEST).unwrap();
298    assert!(matches!(
299        HashPrecompile::<H>::decode_assert_node(&invalid_node),
300        Err(PrecompileError::InvalidNode)
301    ));
302    let invalid_shape = Node::value(assert_tag, [ZERO; 8]).unwrap();
303    assert!(HashPrecompile::<H>::decode_assert_node(&invalid_shape).is_err());
304
305    let input = b"hash assertions consume generic chunks";
306    let mut state = fresh();
307    let assertion = assert_registers(
308        &mut state,
309        input.len() as u32,
310        chunks_from_bytes(input),
311        digest_chunks::<H>(input),
312    )
313    .expect("matching hash assertion should register");
314    assert_eq!(state.evaluate_digest(assertion).unwrap(), TRUE_DIGEST);
315    state.log_statement(assertion).expect("true assertion should log");
316
317    let mut wrong = digest_chunks::<H>(input);
318    wrong[0][0] = if wrong[0][0] == ZERO { Felt::from_u32(1) } else { ZERO };
319    let mut state = fresh();
320    let err = assert_registers(&mut state, input.len() as u32, chunks_from_bytes(input), wrong)
321        .unwrap_err();
322    assert_error(err, PrecompileError::AssertionFailed);
323
324    let too_long: Vec<u8> = (0u8..33).collect();
325    let mut state = fresh();
326    let err = assert_registers(
327        &mut state,
328        too_long.len() as u32,
329        vec![chunks_from_bytes(&too_long)[0]],
330        digest_chunks::<H>(&too_long),
331    )
332    .unwrap_err();
333    assert_error(err, PrecompileError::InvalidNode);
334
335    let mut padded = chunks_from_bytes(&[1, 2, 3]);
336    padded[0][0] = Felt::from_u32(u32::from_le_bytes([1, 2, 3, 0xaa]));
337    let mut state = fresh();
338    let err = assert_registers(&mut state, 3, padded, digest_chunks::<H>(&[1, 2, 3])).unwrap_err();
339    assert_error(err, PrecompileError::InvalidNode);
340
341    let non_u32 = Felt::new_unchecked(u64::from(u32::MAX) + 1);
342    let mut preimage = chunks_from_bytes(input);
343    preimage[0][0] = non_u32;
344    let mut state = fresh();
345    let err = assert_registers(&mut state, input.len() as u32, preimage, digest_chunks::<H>(input))
346        .unwrap_err();
347    assert_error(err, PrecompileError::InvalidNode);
348
349    let mut expected = digest_chunks::<H>(input);
350    expected[0][0] = non_u32;
351    let mut state = fresh();
352    let err = assert_registers(&mut state, input.len() as u32, chunks_from_bytes(input), expected)
353        .unwrap_err();
354    assert_error(err, PrecompileError::InvalidNode);
355
356    let precompile_owned_data = Node::try_data(
357        HashPrecompile::<H>::assert_tag(input.len() as u32),
358        chunks_from_bytes(input),
359    )
360    .expect("data node is syntactically constructible");
361    let mut state = fresh();
362    let preimage = state.register(precompile_owned_data).unwrap_err();
363    assert_error(preimage, PrecompileError::InvalidNode);
364
365    let mut state = fresh();
366    let zero = assert_registers(&mut state, 0, vec![[ZERO; 8]], digest_chunks::<H>(&[]))
367        .expect("zero-byte hash assertion should register");
368    assert_eq!(state.evaluate_digest(zero).unwrap(), TRUE_DIGEST);
369
370    let mut state = fresh();
371    let preimage_chunks = chunks_from_bytes(input);
372    let expected_chunks = digest_chunks::<H>(input);
373    let preimage = state.register(Node::chunks(preimage_chunks).unwrap()).unwrap();
374    let expected = state.register(Node::chunks(expected_chunks).unwrap()).unwrap();
375    let assertion_node = HashPrecompile::<H>::assert_node(input.len() as u32, preimage, expected);
376    let assertion = state.register(assertion_node).unwrap();
377    state.log_statement(assertion).unwrap();
378    let wire = state.to_wire().expect("hash assertion state should encode");
379    let mut rehydrated = DeferredState::from_wire(
380        Arc::new(PrecompileRegistry::new().with_precompile(HashPrecompile::<H>::default())),
381        &wire,
382    )
383    .expect("wire should rehydrate under the hash registry");
384    assert_eq!(rehydrated.evaluate_digest(rehydrated.root()).unwrap(), TRUE_DIGEST);
385}
miden_precompiles/hash/mod.rs

miden_precompiles/hash/
mod.rs
