fancy_garbling/circuits/
sha.rs

1//! SHA circuits.
2
3use crate::{
4    FancyBinary,
5    circuit::{BinaryCircuit, Circuit, CircuitInputMapper},
6    circuits::binary::BinaryConstant,
7};
8use std::io::Cursor;
9use swanky_channel::Channel;
10use swanky_error::Result;
11
12/// Circuit for the SHA-256 compression function, where the chaining values are
13/// fixed to the SHA-256 IV.
14pub struct Sha256CompressionFunctionFixedIV(BinaryCircuit);
15
16impl Sha256CompressionFunctionFixedIV {
17    /// Create a new [`Sha256CompressionFunctionFixedIV`] circuit.
18    ///
19    /// # Performance Note!
20    /// This involves parsing a Bristol Format file, and thus is not cheap!
21    /// Hence, it is best to reuse this circuit if possible versus calling
22    /// [`Sha256CompressionFunctionFixedIV::new`] every time this circuit is
23    /// needed.
24    pub fn new() -> Self {
25        let circuit = BinaryCircuit::parse_bristol_format(Cursor::<&'static [u8]>::new(
26            include_bytes!("../../circuits/bristol-format/sha-256.txt"),
27        ))
28        .expect("`sha-256.txt` file should always parse correctly");
29        Self(circuit)
30    }
31}
32
33impl Default for Sha256CompressionFunctionFixedIV {
34    fn default() -> Self {
35        Self::new()
36    }
37}
38
39impl<F: FancyBinary> Circuit<F> for Sha256CompressionFunctionFixedIV {
40    type Input = [F::Item; 512];
41    type Output = [F::Item; 256];
42
43    fn execute(
44        &self,
45        backend: &mut F,
46        input: Self::Input,
47        channel: &mut Channel,
48    ) -> Result<Self::Output> {
49        let output = self.0.execute(backend, input.to_vec(), channel)?;
50        Ok(output
51            .try_into()
52            .expect("SHA-256 compression function output should always be 256 elements"))
53    }
54}
55
56impl<F: FancyBinary> CircuitInputMapper<F> for Sha256CompressionFunctionFixedIV {
57    fn map(&self, inputs: Vec<<F as crate::Fancy>::Item>) -> Self::Input {
58        assert_eq!(inputs.len(), 512);
59        inputs.try_into().unwrap()
60    }
61
62    fn ninputs(&self) -> usize {
63        512
64    }
65
66    fn modulus(&self, _: usize) -> u16 {
67        2
68    }
69}
70
71/// Circuit for the SHA-256 compression function.
72pub struct Sha256CompressionFunction(BinaryCircuit);
73
74impl Sha256CompressionFunction {
75    /// Create a new [`Sha256CompressionFunction`] circuit.
76    ///
77    /// # Performance Note!
78    /// This involves parsing a Bristol Fashion file, and thus is not cheap!
79    /// Hence, it is best to reuse this circuit if possible versus calling
80    /// [`Sha256CompressionFunction::new`] every time this circuit is needed.
81    pub fn new() -> Self {
82        let circuit = BinaryCircuit::parse_bristol_fashion(Cursor::<&'static [u8]>::new(
83            include_bytes!("../../circuits/bristol-fashion/sha256.txt"),
84        ))
85        .expect("`sha256.txt` file should always parse correctly");
86        Self(circuit)
87    }
88}
89
90impl Default for Sha256CompressionFunction {
91    fn default() -> Self {
92        Self::new()
93    }
94}
95
96impl<F: FancyBinary> Circuit<F> for Sha256CompressionFunction {
97    type Input = ([F::Item; 512], [F::Item; 256]);
98    type Output = [F::Item; 256];
99
100    fn execute(
101        &self,
102        backend: &mut F,
103        inputs: Self::Input,
104        channel: &mut Channel,
105    ) -> Result<Self::Output> {
106        // Bristol Fashion expects its input in the _reverse_ order of what
107        // would be expected, so we need to reverse everything when building
108        // the vector to pass to [`BinaryCircuit`].
109        let mut combined = inputs.0.iter().rev().cloned().collect::<Vec<_>>();
110        combined.extend(inputs.1.iter().rev().cloned());
111        let output = self.0.execute(backend, combined, channel)?;
112        Ok(output
113            .try_into()
114            .expect("SHA-256 compression function output should always be 256 elements"))
115    }
116}
117
118impl<F: FancyBinary> CircuitInputMapper<F> for Sha256CompressionFunction {
119    fn map(&self, inputs: Vec<<F as crate::Fancy>::Item>) -> Self::Input {
120        assert_eq!(inputs.len(), 768);
121        let (block, chain) = inputs.split_at(512);
122        (
123            block
124                .to_vec()
125                .try_into()
126                .expect("Block should contain 512 elements"),
127            chain
128                .to_vec()
129                .try_into()
130                .expect("Chain should contain 256 elements"),
131        )
132    }
133
134    fn ninputs(&self) -> usize {
135        768
136    }
137
138    fn modulus(&self, _: usize) -> u16 {
139        2
140    }
141}
142
143/// Circuit for SHA-256 hash function supporting arbitrary length messages.
144///
145/// This implementation uses the SHA-256 compression function to process multiple
146/// 512-bit blocks, properly chaining the outputs for multi-block messages.
147pub struct Sha256 {
148    compression: Sha256CompressionFunction,
149}
150
151impl Sha256 {
152    /// Create a new [`Sha256`] circuit.
153    ///
154    /// # Performance Note!
155    /// This involves parsing a Bristol Fashion file, and thus is not cheap!
156    /// Hence, it is best to reuse this circuit if possible versus calling
157    /// [`Sha256::new`] every time this circuit is needed.
158    pub fn new() -> Self {
159        Self {
160            compression: Sha256CompressionFunction::new(),
161        }
162    }
163
164    /// SHA-256 initialization vector (IV).
165    const IV: &'static str = "0110101000001001111001100110011110111011011001111010111010000101\
166                               001111000110111011110011011100101010010101001111111101010011101\
167                               001010001000011100101001001111111100110110000010101101000100011\
168                               000001111110000011110110011010101101011011111000001100110100011001";
169}
170
171impl Default for Sha256 {
172    fn default() -> Self {
173        Self::new()
174    }
175}
176
177impl<F: FancyBinary> Circuit<F> for Sha256 {
178    type Input = Vec<F::Item>;
179    type Output = [F::Item; 256];
180
181    fn execute(
182        &self,
183        backend: &mut F,
184        inputs: Self::Input,
185        channel: &mut Channel,
186    ) -> Result<Self::Output> {
187        let message_len = inputs.len();
188
189        let one = backend.constant(1, 2, channel)?;
190        let zero = backend.constant(0, 2, channel)?;
191
192        // Initialize the hash with SHA-256 IV.
193        let mut chain: [F::Item; 256] = Self::IV
194            .chars()
195            .map(|c| if c == '1' { one.clone() } else { zero.clone() })
196            .collect::<Vec<_>>()
197            .try_into()
198            .unwrap();
199
200        // Pad the input message.
201        let mut padded = inputs.clone();
202        padded.push(one.clone());
203
204        // Calculate padding: we need to reach a length ≡ 448 (mod 512).
205        let current_len = padded.len();
206        let target_len = if current_len <= 448 {
207            448
208        } else {
209            (current_len + 64).div_ceil(512) * 512 - 64
210        };
211        let zeros_needed = target_len - current_len;
212        for _ in 0..zeros_needed {
213            padded.push(zero.clone());
214        }
215
216        // Append the original message length as a 64-bit big-endian integer.
217        let mut length = BinaryConstant::new_with_constants(
218            message_len as u128,
219            64,
220            Some(zero.clone()),
221            Some(one.clone()),
222        )
223        .execute(backend, (), channel)?;
224        // Constants are represented in little-endian, but here we need message
225        // length to be in big-endian. So we reverse the bundle before using it.
226        length.reverse();
227        padded.extend_from_slice(length.wires());
228
229        // Process each 512-bit block.
230        for chunk in padded.chunks(512) {
231            let block: [F::Item; 512] =
232                chunk.to_vec().try_into().expect("Chunk should be 512 bits");
233
234            chain = self.compression.execute(backend, (block, chain), channel)?;
235        }
236
237        Ok(chain)
238    }
239}
240
241#[cfg(test)]
242mod test {
243    use crate::circuits::sha::{
244        Sha256, Sha256CompressionFunction, Sha256CompressionFunctionFixedIV,
245    };
246    use crate::dummy::{Dummy, DummyVal};
247
248    #[cfg(test)]
249    fn string_to_bool_vec(str: &str) -> Vec<DummyVal> {
250        str.chars()
251            .map(|c| match c {
252                '0' => DummyVal::new_bool(false),
253                '1' => DummyVal::new_bool(true),
254                _ => panic!("Unexpected character in boolean string"),
255            })
256            .collect()
257    }
258
259    #[test]
260    fn sha256_compression_function() {
261        // Uses the test vectors found here:
262        // <https://nigelsmart.github.io/MPC-Circuits/sha-256-test.txt>.
263
264        let sha256_fixed_iv = Sha256CompressionFunctionFixedIV::new();
265        let sha256 = Sha256CompressionFunction::new();
266
267        let iv = string_to_bool_vec(
268            "0110101000001001111001100110011110111011011001111010111010000101001111000110111011110011011100101010010101001111111101010011101001010001000011100101001001111111100110110000010101101000100011000001111110000011110110011010101101011011111000001100110100011001",
269        ).try_into().unwrap();
270
271        let block = [DummyVal::new_bool(false); 512];
272        let output = Dummy::eval(&sha256_fixed_iv, block).unwrap();
273        assert_eq!(
274            output
275                .iter()
276                .map(|i| i.val().to_string())
277                .collect::<String>(),
278            "1101101001010110100110001011111000010111101110011011010001101001011000100011001101010111100110010111011110011111101111101100101010001100111001011101010010010001110000001101001001100010010000111011101011111110111110011110101000011000001101111010100111011000"
279        );
280        let output_with_iv = Dummy::eval(&sha256, (block, iv)).unwrap();
281        assert_eq!(output, output_with_iv);
282
283        let block = string_to_bool_vec(
284            "00000000000000010000001000000011000001000000010100000110000001110000100000001001000010100000101100001100000011010000111000001111000100000001000100010010000100110001010000010101000101100001011100011000000110010001101000011011000111000001110100011110000111110010000000100001001000100010001100100100001001010010011000100111001010000010100100101010001010110010110000101101001011100010111100110000001100010011001000110011001101000011010100110110001101110011100000111001001110100011101100111100001111010011111000111111",
285        ).try_into().unwrap();
286        let output = Dummy::eval(&sha256_fixed_iv, block).unwrap();
287        assert_eq!(
288            output
289                .iter()
290                .map(|i| i.val().to_string())
291                .collect::<String>(),
292            "1111110010011001101000101101111110001000111101000010101001111010011110111011100111010001100000000011001111001101110001101010001000000010010101100111010101011111100111010101101110011010010100000100010010101001110011000011000101011010101111101000010010100111"
293        );
294        let output_with_iv = Dummy::eval(&sha256, (block, iv)).unwrap();
295        assert_eq!(output, output_with_iv);
296
297        let block = [DummyVal::new_bool(true); 512];
298        let output = Dummy::eval(&sha256_fixed_iv, block).unwrap();
299        assert_eq!(
300            output
301                .iter()
302                .map(|i| i.val().to_string())
303                .collect::<String>(),
304            "1110111100001100011101001000110111110100110110100101000010101000110101101100010000111100000000010011111011011100001111001110011101101100100111011001111110101001101000010100010110001010110111100101011011101011100001101100000010100110010001001001001011010010"
305        );
306        let output_with_iv = Dummy::eval(&sha256, (block, iv)).unwrap();
307        assert_eq!(output, output_with_iv);
308
309        let block = string_to_bool_vec(
310            "00100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000000011011100000111001101000100101001000000100100111000001000100010100110011111001100011101000000001000001011101111101010011000111011000100111001101100100010010100010100101000001000011110011000111000110100000001001101110111101111100101010001100110110011110011010011101001000011000110110011000000101011000010100110110111110010010111110001010000110111010011111110000100110101011011010110110101010001110000100100010111",
311        ).try_into().unwrap();
312        let output = Dummy::eval(&sha256_fixed_iv, block).unwrap();
313        assert_eq!(
314            output
315                .iter()
316                .map(|i| i.val().to_string())
317                .collect::<String>(),
318            "1100111100001010111001001110101101100111110100111000111111111110101110010100000001101000100110000100101100100010101010111101111001001110100100101011110001010100100011010001010001011000010111100100100011011100101010001000100000101101011110110000100111001110"
319        );
320        let output_with_iv = Dummy::eval(&sha256, (block, iv)).unwrap();
321        assert_eq!(output, output_with_iv);
322    }
323
324    #[test]
325    fn sha256_empty_string() {
326        // Test SHA-256 with empty string input.
327        // Expected output: e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
328
329        let sha256 = Sha256::new();
330        let input = vec![];
331        let output = Dummy::eval(&sha256, input).unwrap();
332        assert_eq!(
333            output
334                .iter()
335                .map(|i| i.val().to_string())
336                .collect::<String>(),
337            "1110001110110000110001000100001010011000111111000001110000010100100110101111101111110100110010001001100101101111101110010010010000100111101011100100000111100100011001001001101110010011010011001010010010010101100110010001101101111000010100101011100001010101"
338        );
339    }
340
341    #[test]
342    fn sha256_abc() {
343        // Test SHA-256 with "abc" input.
344        // Expected output: ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
345
346        let sha256 = Sha256::new();
347
348        // "abc" in binary (ASCII encoding)
349        // 'a' = 0x61 = 01100001
350        // 'b' = 0x62 = 01100010
351        // 'c' = 0x63 = 01100011
352        let input = string_to_bool_vec("011000010110001001100011");
353        let output = Dummy::eval(&sha256, input).unwrap();
354        assert_eq!(
355            output
356                .iter()
357                .map(|i| i.val().to_string())
358                .collect::<String>(),
359            "1011101001111000000101101011111110001111000000011100111111101010010000010100000101000000110111100101110110101110001000100010001110110000000000110110000110100011100101100001011101111010100111001011010000010000111111110110000111110010000000000001010110101101"
360        );
361    }
362
363    #[test]
364    fn sha256_two_blocks() {
365        // Test SHA-256 with a message that requires 2 blocks (> 447 bits).
366        // Message: 448 bits of zeros (requires 2 blocks after padding).
367
368        let sha256 = Sha256::new();
369        let input = vec![DummyVal::new_bool(false); 448];
370        let output = Dummy::eval(&sha256, input).unwrap();
371        assert_eq!(
372            output
373                .iter()
374                .map(|i| i.val().to_string())
375                .collect::<String>(),
376            "1101010010000001011110101010010101001001011101100010100011100111110001110111111001101011011000000110000100000111000001000010101110111011101000110001001100001000100010001100010111110100011110100011011101011110011000010111100110111110011110001001111110111011"
377        );
378    }
379
380    #[test]
381    fn sha256_three_blocks() {
382        // Test SHA-256 with a 3-block message (> 1024 bits).
383        // Message: "abcd" repeated 32 times = 1024 bits = 128 bytes.
384
385        let sha256 = Sha256::new();
386        // "abcd" = 01100001 01100010 01100011 01100100
387        let abcd = string_to_bool_vec("01100001011000100110001101100100");
388        let mut input = Vec::with_capacity(1024);
389        for _ in 0..32 {
390            input.extend_from_slice(&abcd);
391        }
392        let output = Dummy::eval(&sha256, input).unwrap();
393        assert_eq!(
394            output
395                .iter()
396                .map(|i| i.val().to_string())
397                .collect::<String>(),
398            "0100010100110010111011110111001100010001000010011001001010000110000001011001101010111101100001011101010011000000011001110101011111111001011011010010010001001000101100100101100111111001010100011001001000100010101100101010110001101001101101011110101111110011"
399        );
400    }
401
402    #[test]
403    fn sha256_long_message() {
404        let sha256 = Sha256::new();
405
406        let message = "The quick brown fox jumps over the lazy dog";
407        let input: Vec<DummyVal> = message
408            .bytes()
409            .flat_map(|b| {
410                (0..8)
411                    .rev()
412                    .map(move |i| DummyVal::new_bool((b >> i) & 1 == 1))
413            })
414            .collect();
415
416        let output = Dummy::eval(&sha256, input).unwrap();
417        assert_eq!(
418            output
419                .iter()
420                .map(|i| i.val().to_string())
421                .collect::<String>(),
422            "1101011110101000111110111011001100000111110101111000000010010100011010011100101010011010101111001011000000001000001011100100111110001101010101100101000111100100011011010011110011011011011101100010110100000010110100001011111100110111110010011110010110010010"
423        );
424    }
425}
fancy_garbling/circuits/sha.rs

fancy_garbling/circuits/
sha.rs
