hekate_sha2/
lib.rs

1// SPDX-FileCopyrightText: 2026 Andrei Kochergin <andrei@oumuamua.dev>
2// SPDX-FileCopyrightText: 2026 Oumuamua Labs <info@oumuamua.dev>
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! SHA-256 compression chiplet for Hekate, the Rust zero-knowledge proof engine.
6//!
7//! [`Sha256Chiplet`] proves the 64 rounds of FIPS 180-4 §6.2.2
8//! at 1, 2, 4, 8 or 16 rounds per row. [`CpuSha256Block`] places
9//! the host's side in the caller's table: the request and the
10//! feed-forward add. [`pad_message`] splits a message into padded
11//! blocks, and [`compress`] computes one compression natively.
12//!
13//! - [SHA-256][sha2]: what the proof states, and padding and chaining
14//!
15//! [sha2]: https://oumuamua.dev/primitives/hashing/sha2
16
17#![cfg_attr(not(feature = "std"), no_std)]
18
19extern crate alloc;
20
21use alloc::vec::Vec;
22use zeroize::Zeroizing;
23
24pub mod cpu;
25pub mod sha256;
26pub mod trace;
27
28pub use cpu::CpuSha256Block;
29pub use sha256::{Sha256Chiplet, Sha256Layout};
30pub use trace::Sha256Call;
31
32pub const STATE_WORDS: usize = 8;
33pub const BLOCK_WORDS: usize = 16;
34pub const ROUNDS: usize = 64;
35
36/// FIPS 180-4 §5.3.3.
37pub const IV: [u32; STATE_WORDS] = [
38    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
39];
40
41/// FIPS 180-4 §4.2.2.
42#[rustfmt::skip]
43pub const K: [u32; ROUNDS] = [
44    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
45    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
46    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
47    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
48    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
49    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
50    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
51    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
52];
53
54pub fn big_sigma0(x: u32) -> u32 {
55    x.rotate_right(2) ^ x.rotate_right(13) ^ x.rotate_right(22)
56}
57
58pub fn big_sigma1(x: u32) -> u32 {
59    x.rotate_right(6) ^ x.rotate_right(11) ^ x.rotate_right(25)
60}
61
62pub fn small_sigma0(x: u32) -> u32 {
63    x.rotate_right(7) ^ x.rotate_right(18) ^ (x >> 3)
64}
65
66pub fn small_sigma1(x: u32) -> u32 {
67    x.rotate_right(17) ^ x.rotate_right(19) ^ (x >> 10)
68}
69
70pub fn ch(e: u32, f: u32, g: u32) -> u32 {
71    g ^ (e & (f ^ g))
72}
73
74pub fn maj(a: u32, b: u32, c: u32) -> u32 {
75    b ^ ((a ^ b) & (b ^ c))
76}
77
78/// `(sum, carries)`: bit `k` of `carries` is
79/// the carry out of bit `k`, bit 31 the overflow.
80pub fn add_with_carries(a: u32, b: u32) -> (u32, u32) {
81    let sum = a.wrapping_add(b);
82    let carry_in = a ^ b ^ sum;
83    let overflow = ((u64::from(a) + u64::from(b)) >> 32) as u32;
84
85    (sum, (carry_in >> 1) | (overflow << 31))
86}
87
88pub fn schedule_word(w: &[u32; BLOCK_WORDS], t: usize) -> u32 {
89    small_sigma1(w[(t + 14) % BLOCK_WORDS])
90        .wrapping_add(w[(t + 9) % BLOCK_WORDS])
91        .wrapping_add(small_sigma0(w[(t + 1) % BLOCK_WORDS]))
92        .wrapping_add(w[t % BLOCK_WORDS])
93}
94
95pub fn round(state: &mut [u32; STATE_WORDS], k: u32, w: u32) {
96    let [a, b, c, d, e, f, g, h] = *state;
97
98    let t1 = h
99        .wrapping_add(big_sigma1(e))
100        .wrapping_add(ch(e, f, g))
101        .wrapping_add(k)
102        .wrapping_add(w);
103
104    let t2 = big_sigma0(a).wrapping_add(maj(a, b, c));
105
106    *state = [t1.wrapping_add(t2), a, b, c, d.wrapping_add(t1), e, f, g];
107}
108
109pub fn rounds(h_in: &[u32; STATE_WORDS], block: &[u32; BLOCK_WORDS]) -> [u32; STATE_WORDS] {
110    let mut w = *block;
111    let mut state = *h_in;
112
113    for t in 0..ROUNDS {
114        if t >= BLOCK_WORDS {
115            w[t % BLOCK_WORDS] = schedule_word(&w, t);
116        }
117
118        round(&mut state, K[t], w[t % BLOCK_WORDS]);
119    }
120
121    state
122}
123
124pub fn feed_forward(h_in: &[u32; STATE_WORDS], state: &[u32; STATE_WORDS]) -> [u32; STATE_WORDS] {
125    let mut h_out = *h_in;
126    for (out, s) in h_out.iter_mut().zip(state) {
127        *out = out.wrapping_add(*s);
128    }
129
130    h_out
131}
132
133/// FIPS 180-4 §6.2.2, big-endian words.
134pub fn compress(h_in: &[u32; STATE_WORDS], block: &[u32; BLOCK_WORDS]) -> [u32; STATE_WORDS] {
135    feed_forward(h_in, &rounds(h_in, block))
136}
137
138/// FIPS 180-4 §5.1.1, big-endian words.
139pub fn pad_message(msg: &[u8]) -> Zeroizing<Vec<[u32; BLOCK_WORDS]>> {
140    let bit_len = (msg.len() as u64) * 8;
141    let padded_len = (msg.len() + 1 + 8).div_ceil(64) * 64;
142
143    let mut bytes = Zeroizing::new(Vec::with_capacity(padded_len));
144    bytes.extend_from_slice(msg);
145    bytes.push(0x80);
146    bytes.resize(padded_len - 8, 0);
147    bytes.extend_from_slice(&bit_len.to_be_bytes());
148
149    let blocks = bytes
150        .as_chunks::<64>()
151        .0
152        .iter()
153        .map(|chunk| {
154            let mut words = [0u32; BLOCK_WORDS];
155            for (word, quad) in words.iter_mut().zip(chunk.as_chunks::<4>().0) {
156                *word = u32::from_be_bytes(*quad);
157            }
158
159            words
160        })
161        .collect();
162
163    Zeroizing::new(blocks)
164}
165
166pub fn sha256_words(msg: &[u8]) -> [u32; STATE_WORDS] {
167    pad_message(msg)
168        .iter()
169        .fold(IV, |h, block| compress(&h, block))
170}
171
172pub fn digest_bytes(words: &[u32; STATE_WORDS]) -> [u8; 32] {
173    let mut out = [0u8; 32];
174    for (quad, word) in out.as_chunks_mut::<4>().0.iter_mut().zip(words) {
175        *quad = word.to_be_bytes();
176    }
177
178    out
179}
180
181#[cfg(test)]
182mod tests {
183    use super::*;
184
185    #[test]
186    fn abc() {
187        assert_eq!(
188            sha256_words(b"abc"),
189            [
190                0xba7816bf, 0x8f01cfea, 0x414140de, 0x5dae2223, 0xb00361a3, 0x96177a9c, 0xb410ff61,
191                0xf20015ad
192            ]
193        );
194    }
195
196    #[test]
197    fn two_blocks() {
198        assert_eq!(
199            sha256_words(b"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"),
200            [
201                0x248d6a61, 0xd20638b8, 0xe5c02693, 0x0c3e6039, 0xa33ce459, 0x64ff2167, 0xf6ecedd4,
202                0x19db06c1
203            ]
204        );
205    }
206
207    #[test]
208    fn empty() {
209        assert_eq!(
210            sha256_words(b""),
211            [
212                0xe3b0c442, 0x98fc1c14, 0x9afbf4c8, 0x996fb924, 0x27ae41e4, 0x649b934c, 0xa495991b,
213                0x7852b855
214            ]
215        );
216    }
217
218    #[test]
219    fn padding_boundaries() {
220        assert_eq!(pad_message(&[0u8; 55]).len(), 1);
221        assert_eq!(pad_message(&[0u8; 56]).len(), 2);
222        assert_eq!(pad_message(&[0u8; 64]).len(), 2);
223        assert_eq!(pad_message(&[0u8; 119]).len(), 2);
224        assert_eq!(pad_message(&[0u8; 120]).len(), 3);
225    }
226
227    #[test]
228    fn carries_reproduce_the_sum() {
229        let pairs = [
230            (0u32, 0u32),
231            (1, 1),
232            (u32::MAX, 1),
233            (u32::MAX, u32::MAX),
234            (0x8000_0000, 0x8000_0000),
235            (0x1234_5678, 0x9abc_def0),
236        ];
237
238        for (a, b) in pairs {
239            let (sum, carries) = add_with_carries(a, b);
240            assert_eq!(sum, a.wrapping_add(b));
241
242            let mut c_prev = 0u32;
243            for k in 0..32 {
244                let a_k = (a >> k) & 1;
245                let b_k = (b >> k) & 1;
246                let expected = (a_k & b_k) | (a_k & c_prev) | (b_k & c_prev);
247                let c_k = (carries >> k) & 1;
248
249                assert_eq!(c_k, expected, "bit {k} of {a:#x} + {b:#x}");
250                assert_eq!((sum >> k) & 1, a_k ^ b_k ^ c_prev);
251
252                c_prev = c_k;
253            }
254        }
255    }
256}
hekate_sha2/lib.rs

hekate_sha2/
lib.rs
