acvm/pwg/blackbox/
hash.rs

1use acir::{
2    AcirField,
3    circuit::opcodes::FunctionInput,
4    native_types::{Witness, WitnessMap},
5};
6use acvm_blackbox_solver::{BlackBoxFunctionSolver, BlackBoxResolutionError, sha256_compression};
7use itertools::Itertools;
8
9use crate::OpcodeResolutionError;
10use crate::pwg::{input_to_value, insert_value};
11
12/// Attempts to solve a 256 bit hash function opcode.
13/// If successful, `initial_witness` will be mutated to contain the new witness assignment.
14pub(super) fn solve_generic_256_hash_opcode<F: AcirField>(
15    initial_witness: &mut WitnessMap<F>,
16    inputs: &[FunctionInput<F>],
17    var_message_size: Option<&FunctionInput<F>>,
18    outputs: &[Witness; 32],
19    hash_function: fn(data: &[u8]) -> Result<[u8; 32], BlackBoxResolutionError>,
20) -> Result<(), OpcodeResolutionError<F>> {
21    let message_input = get_hash_input(initial_witness, inputs, var_message_size, 8)?;
22    let digest: [u8; 32] = hash_function(&message_input)?;
23
24    write_digest_to_outputs(initial_witness, outputs, digest)
25}
26
27/// Reads the hash function input from a [`WitnessMap`].
28pub(crate) fn get_hash_input<F: AcirField>(
29    initial_witness: &WitnessMap<F>,
30    inputs: &[FunctionInput<F>],
31    message_size: Option<&FunctionInput<F>>,
32    num_bits: usize,
33) -> Result<Vec<u8>, OpcodeResolutionError<F>> {
34    // Read witness assignments.
35    let mut message_input = Vec::new();
36    for input in inputs {
37        let witness_assignment = input_to_value(initial_witness, *input)?;
38        let bytes = witness_assignment.fetch_nearest_bytes(num_bits);
39        message_input.extend(bytes);
40    }
41
42    // Truncate the message if there is a `message_size` parameter given
43    match message_size {
44        Some(input) => {
45            let num_bytes_to_take = input_to_value(initial_witness, *input)?
46                .try_into_u128()
47                .map(|num_bytes_to_take| num_bytes_to_take as usize)
48                .expect("expected a 'num_bytes_to_take' that fit into a u128");
49
50            // If the number of bytes to take is more than the amount of bytes available
51            // in the message, then we error.
52            if num_bytes_to_take > message_input.len() {
53                return Err(OpcodeResolutionError::BlackBoxFunctionFailed(
54                    acir::BlackBoxFunc::Blake2s,
55                    format!(
56                        "the number of bytes to take from the message is more than the number of bytes in the message. {} > {}",
57                        num_bytes_to_take,
58                        message_input.len()
59                    ),
60                ));
61            }
62            let truncated_message = message_input[0..num_bytes_to_take].to_vec();
63            Ok(truncated_message)
64        }
65        None => Ok(message_input),
66    }
67}
68
69/// Writes a `digest` to the [`WitnessMap`] at witness indices `outputs`.
70fn write_digest_to_outputs<F: AcirField>(
71    initial_witness: &mut WitnessMap<F>,
72    outputs: &[Witness; 32],
73    digest: [u8; 32],
74) -> Result<(), OpcodeResolutionError<F>> {
75    for (output_witness, value) in outputs.iter().zip_eq(digest) {
76        insert_value(output_witness, F::from_be_bytes_reduce(&[value]), initial_witness)?;
77    }
78
79    Ok(())
80}
81
82fn to_u32_array<const N: usize, F: AcirField>(
83    initial_witness: &WitnessMap<F>,
84    inputs: &[FunctionInput<F>; N],
85) -> Result<[u32; N], OpcodeResolutionError<F>> {
86    let mut result = [0; N];
87    for (it, input) in result.iter_mut().zip_eq(inputs) {
88        let witness_value = input_to_value(initial_witness, *input)?;
89        *it = witness_value
90            .try_into_u128()
91            .expect("expected the 'witness_value' to fit into a u128")
92            .try_into()
93            .expect("expected the 'witness_value' to fit into a u32");
94    }
95    Ok(result)
96}
97
98pub(crate) fn solve_sha_256_permutation_opcode<F: AcirField>(
99    initial_witness: &mut WitnessMap<F>,
100    inputs: &[FunctionInput<F>; 16],
101    hash_values: &[FunctionInput<F>; 8],
102    outputs: &[Witness; 8],
103) -> Result<(), OpcodeResolutionError<F>> {
104    let state = execute_sha_256_permutation_opcode(initial_witness, inputs, hash_values)?;
105
106    for (output_witness, value) in outputs.iter().zip_eq(state) {
107        insert_value(output_witness, F::from(u128::from(value)), initial_witness)?;
108    }
109
110    Ok(())
111}
112
113pub(crate) fn execute_sha_256_permutation_opcode<F: AcirField>(
114    initial_witness: &WitnessMap<F>,
115    inputs: &[FunctionInput<F>; 16],
116    hash_values: &[FunctionInput<F>; 8],
117) -> Result<[u32; 8], OpcodeResolutionError<F>> {
118    let message = to_u32_array(initial_witness, inputs)?;
119    let mut state = to_u32_array(initial_witness, hash_values)?;
120
121    sha256_compression(&mut state, &message);
122
123    Ok(state)
124}
125
126pub(crate) fn solve_poseidon2_permutation_opcode<F: AcirField>(
127    backend: &impl BlackBoxFunctionSolver<F>,
128    initial_witness: &mut WitnessMap<F>,
129    inputs: &[FunctionInput<F>],
130    outputs: &[Witness],
131) -> Result<(), OpcodeResolutionError<F>> {
132    if inputs.len() != outputs.len() {
133        return Err(OpcodeResolutionError::BlackBoxFunctionFailed(
134            acir::BlackBoxFunc::Poseidon2Permutation,
135            format!(
136                "the input and output sizes are not consistent. {} != {}",
137                inputs.len(),
138                outputs.len()
139            ),
140        ));
141    }
142
143    let state = execute_poseidon2_permutation_opcode(backend, initial_witness, inputs)?;
144
145    // Write witness assignments
146    for (output_witness, value) in outputs.iter().zip_eq(state) {
147        insert_value(output_witness, value, initial_witness)?;
148    }
149    Ok(())
150}
151
152pub(crate) fn execute_poseidon2_permutation_opcode<F: AcirField>(
153    backend: &impl BlackBoxFunctionSolver<F>,
154    initial_witness: &WitnessMap<F>,
155    inputs: &[FunctionInput<F>],
156) -> Result<Vec<F>, OpcodeResolutionError<F>> {
157    // Read witness assignments
158    let state: Vec<F> = inputs
159        .iter()
160        .map(|input| input_to_value(initial_witness, *input))
161        .collect::<Result<_, _>>()?;
162
163    let state = backend.poseidon2_permutation(&state)?;
164    Ok(state)
165}
166
167#[cfg(test)]
168mod tests {
169    use crate::pwg::blackbox::solve_generic_256_hash_opcode;
170    use acir::{
171        FieldElement,
172        circuit::opcodes::FunctionInput,
173        native_types::{Witness, WitnessMap},
174    };
175    use acvm_blackbox_solver::{blake2s, blake3};
176    use std::collections::BTreeMap;
177
178    #[test]
179    fn test_blake2s() {
180        // Test vector is coming from Barretenberg (cf. blake2s.test.cpp)
181        let mut inputs = Vec::new();
182        for i in 0..3 {
183            inputs.push(FunctionInput::Witness(Witness(1 + i)));
184        }
185        let mut outputs = [Witness(0); 32];
186        #[allow(clippy::needless_range_loop)]
187        for i in 0..32 {
188            outputs[i] = Witness(4 + i as u32);
189        }
190
191        let mut initial_witness = WitnessMap::from(BTreeMap::from_iter([
192            (Witness(1), FieldElement::from('a' as u128)),
193            (Witness(2), FieldElement::from('b' as u128)),
194            (Witness(3), FieldElement::from('c' as u128)),
195        ]));
196
197        solve_generic_256_hash_opcode(&mut initial_witness, &inputs, None, &outputs, blake2s)
198            .unwrap();
199
200        let expected_output: [u128; 32] = [
201            0x50, 0x8C, 0x5E, 0x8C, 0x32, 0x7C, 0x14, 0xE2, 0xE1, 0xA7, 0x2B, 0xA3, 0x4E, 0xEB,
202            0x45, 0x2F, 0x37, 0x45, 0x8B, 0x20, 0x9E, 0xD6, 0x3A, 0x29, 0x4D, 0x99, 0x9B, 0x4C,
203            0x86, 0x67, 0x59, 0x82,
204        ];
205        let expected_output = expected_output.map(FieldElement::from);
206        let expected_output: Vec<&FieldElement> = expected_output.iter().collect();
207        for i in 0..32 {
208            assert_eq!(initial_witness[&Witness(4 + i as u32)], *expected_output[i]);
209        }
210    }
211
212    #[test]
213    fn test_blake3s() {
214        // Test vector is coming from Barretenberg (cf. blake3s.test.cpp)
215        let mut inputs = Vec::new();
216        for i in 0..3 {
217            inputs.push(FunctionInput::Witness(Witness(1 + i)));
218        }
219        let mut outputs = [Witness(0); 32];
220        #[allow(clippy::needless_range_loop)]
221        for i in 0..32 {
222            outputs[i] = Witness(4 + i as u32);
223        }
224
225        let mut initial_witness = WitnessMap::from(BTreeMap::from_iter([
226            (Witness(1), FieldElement::from('a' as u128)),
227            (Witness(2), FieldElement::from('b' as u128)),
228            (Witness(3), FieldElement::from('c' as u128)),
229        ]));
230
231        solve_generic_256_hash_opcode(&mut initial_witness, &inputs, None, &outputs, blake3)
232            .unwrap();
233
234        let expected_output: [u128; 32] = [
235            0x64, 0x37, 0xB3, 0xAC, 0x38, 0x46, 0x51, 0x33, 0xFF, 0xB6, 0x3B, 0x75, 0x27, 0x3A,
236            0x8D, 0xB5, 0x48, 0xC5, 0x58, 0x46, 0x5D, 0x79, 0xDB, 0x03, 0xFD, 0x35, 0x9C, 0x6C,
237            0xD5, 0xBD, 0x9D, 0x85,
238        ];
239        let expected_output = expected_output.map(FieldElement::from);
240        let expected_output: Vec<&FieldElement> = expected_output.iter().collect();
241        for i in 0..32 {
242            assert_eq!(initial_witness[&Witness(4 + i as u32)], *expected_output[i]);
243        }
244    }
245}
acvm/pwg/blackbox/hash.rs

acvm/pwg/blackbox/
hash.rs
