brillig_vm/
black_box.rs

1//! Implementations for VM native [black box functions][acir::brillig::Opcode::BlackBox].
2use acir::brillig::{BlackBoxOp, HeapArray};
3use acir::{AcirField, BlackBoxFunc};
4use acvm_blackbox_solver::{
5    BlackBoxFunctionSolver, BlackBoxResolutionError, aes128_encrypt, blake2s, blake3,
6    ecdsa_secp256k1_verify, ecdsa_secp256r1_verify, keccakf1600, sha256_compression,
7};
8use num_bigint::BigUint;
9use num_traits::Zero;
10
11use crate::Memory;
12use crate::assert_usize;
13use crate::memory::MemoryValue;
14
15/// Reads a fixed-size [array][HeapArray] from memory.
16///
17/// The data is not expected to contain pointers to nested arrays or vector.
18fn read_heap_array<'a, F: AcirField>(
19    memory: &'a Memory<F>,
20    array: &HeapArray,
21) -> &'a [MemoryValue<F>] {
22    let items_start = memory.read_ref(array.pointer);
23    memory.read_slice(items_start, assert_usize(array.size.0))
24}
25
26/// Write values to a [array][HeapArray] in memory.
27fn write_heap_array<F: AcirField>(
28    memory: &mut Memory<F>,
29    array: &HeapArray,
30    values: &[MemoryValue<F>],
31) {
32    let items_start = memory.read_ref(array.pointer);
33    memory.write_slice(items_start, values);
34}
35
36/// Extracts the last byte of every value
37fn to_u8_vec<F: AcirField>(inputs: &[MemoryValue<F>]) -> Vec<u8> {
38    let mut result = Vec::with_capacity(inputs.len());
39    for &input in inputs {
40        result.push(input.expect_u8().unwrap());
41    }
42    result
43}
44
45/// Converts a slice of u8 values into a Vec<[`MemoryValue<F>`]>,
46/// wrapping each byte as a [`MemoryValue::U8`].
47fn to_value_vec<F: AcirField>(input: &[u8]) -> Vec<MemoryValue<F>> {
48    input.iter().map(|&x| x.into()).collect()
49}
50
51/// Evaluates a black box function inside the VM, performing the actual native computation.
52///
53/// Delegates the execution to the corresponding cryptographic or arithmetic
54/// function, depending on the [`BlackBoxOp`] variant.
55/// Handles input conversion, writing the result to memory, and error propagation.
56///
57/// # Arguments
58/// - op: The black box operation to evaluate.
59/// - solver: An implementation of [`BlackBoxFunctionSolver`] providing external function behavior.
60/// - memory: The VM memory from which inputs are read and to which results are written.
61/// - `bigint_solver`: A solver used for big integer operations.
62///
63/// # Returns
64/// - Ok(()) if evaluation succeeds.
65/// - Err([`BlackBoxResolutionError`]) if an error occurs during execution or input is invalid.
66///
67/// # Panics
68/// If any required memory value cannot be converted to the expected type (e.g., [`expect_u8`][MemoryValue::expect_u8])
69/// or if the [radix decomposition][BlackBoxOp::ToRadix] constraints are violated internally, such as an invalid radix range (e.g., radix of 1).
70pub(crate) fn evaluate_black_box<F: AcirField, Solver: BlackBoxFunctionSolver<F>>(
71    op: &BlackBoxOp,
72    solver: &Solver,
73    memory: &mut Memory<F>,
74) -> Result<(), BlackBoxResolutionError> {
75    match op {
76        BlackBoxOp::AES128Encrypt { inputs, iv, key, outputs } => {
77            let bb_func = black_box_function_from_op(op);
78
79            let inputs = to_u8_vec(read_heap_array(memory, inputs));
80
81            let iv: [u8; 16] = to_u8_vec(read_heap_array(memory, iv)).try_into().map_err(|_| {
82                BlackBoxResolutionError::Failed(bb_func, "Invalid iv length".to_string())
83            })?;
84            let key: [u8; 16] =
85                to_u8_vec(read_heap_array(memory, key)).try_into().map_err(|_| {
86                    BlackBoxResolutionError::Failed(bb_func, "Invalid key length".to_string())
87                })?;
88            let ciphertext = aes128_encrypt(&inputs, iv, key)?;
89
90            write_heap_array(memory, outputs, &to_value_vec(&ciphertext));
91
92            Ok(())
93        }
94        BlackBoxOp::Blake2s { message, output } => {
95            let message = to_u8_vec(read_heap_array(memory, message));
96            let bytes = blake2s(message.as_slice())?;
97            write_heap_array(memory, output, &to_value_vec(&bytes));
98            Ok(())
99        }
100        BlackBoxOp::Blake3 { message, output } => {
101            let message = to_u8_vec(read_heap_array(memory, message));
102            let bytes = blake3(message.as_slice())?;
103            write_heap_array(memory, output, &to_value_vec(&bytes));
104            Ok(())
105        }
106        BlackBoxOp::Keccakf1600 { input, output } => {
107            let state_vec: Vec<u64> = read_heap_array(memory, input)
108                .iter()
109                .map(|&memory_value| memory_value.expect_u64().unwrap())
110                .collect();
111            let state: [u64; 25] = state_vec.try_into().unwrap();
112
113            let new_state = keccakf1600(state)?;
114
115            let new_state: Vec<MemoryValue<F>> = new_state.into_iter().map(|x| x.into()).collect();
116            write_heap_array(memory, output, &new_state);
117            Ok(())
118        }
119        BlackBoxOp::EcdsaSecp256k1 {
120            hashed_msg,
121            public_key_x,
122            public_key_y,
123            signature,
124            result: result_address,
125        }
126        | BlackBoxOp::EcdsaSecp256r1 {
127            hashed_msg,
128            public_key_x,
129            public_key_y,
130            signature,
131            result: result_address,
132        } => {
133            let bb_func = black_box_function_from_op(op);
134
135            let public_key_x: [u8; 32] =
136                to_u8_vec(read_heap_array(memory, public_key_x)).try_into().map_err(|_| {
137                    BlackBoxResolutionError::Failed(
138                        bb_func,
139                        "Invalid public key x length".to_string(),
140                    )
141                })?;
142            let public_key_y: [u8; 32] =
143                to_u8_vec(read_heap_array(memory, public_key_y)).try_into().map_err(|_| {
144                    BlackBoxResolutionError::Failed(
145                        bb_func,
146                        "Invalid public key y length".to_string(),
147                    )
148                })?;
149            let signature: [u8; 64] =
150                to_u8_vec(read_heap_array(memory, signature)).try_into().map_err(|_| {
151                    BlackBoxResolutionError::Failed(bb_func, "Invalid signature length".to_string())
152                })?;
153
154            let hashed_msg: [u8; 32] =
155                to_u8_vec(read_heap_array(memory, hashed_msg)).try_into().map_err(|_| {
156                    BlackBoxResolutionError::Failed(
157                        bb_func,
158                        "Invalid hashed message length".to_string(),
159                    )
160                })?;
161
162            let result = match op {
163                BlackBoxOp::EcdsaSecp256k1 { .. } => {
164                    ecdsa_secp256k1_verify(&hashed_msg, &public_key_x, &public_key_y, &signature)?
165                }
166                BlackBoxOp::EcdsaSecp256r1 { .. } => {
167                    ecdsa_secp256r1_verify(&hashed_msg, &public_key_x, &public_key_y, &signature)?
168                }
169                _ => unreachable!("`BlackBoxOp` is guarded against being a non-ecdsa operation"),
170            };
171
172            memory.write(*result_address, result.into());
173            Ok(())
174        }
175        BlackBoxOp::MultiScalarMul { points, scalars, outputs: result } => {
176            let points: Vec<F> =
177                read_heap_array(memory, points).iter().map(|x| x.expect_field().unwrap()).collect();
178            let scalars: Vec<F> = read_heap_array(memory, scalars)
179                .iter()
180                .map(|x| x.expect_field().unwrap())
181                .collect();
182            let mut scalars_lo = Vec::with_capacity(scalars.len() / 2);
183            let mut scalars_hi = Vec::with_capacity(scalars.len() / 2);
184            for (i, scalar) in scalars.iter().enumerate() {
185                if i % 2 == 0 {
186                    scalars_lo.push(*scalar);
187                } else {
188                    scalars_hi.push(*scalar);
189                }
190            }
191            let (x, y) = solver.multi_scalar_mul(
192                &points,
193                &scalars_lo,
194                &scalars_hi,
195                true, // Predicate is always true as brillig has control flow to handle false case
196            )?;
197            write_heap_array(
198                memory,
199                result,
200                &[MemoryValue::new_field(x), MemoryValue::new_field(y)],
201            );
202            Ok(())
203        }
204        BlackBoxOp::EmbeddedCurveAdd { input1_x, input1_y, input2_x, input2_y, result } => {
205            let input1_x = memory.read(*input1_x).expect_field().unwrap();
206            let input1_y = memory.read(*input1_y).expect_field().unwrap();
207            let input2_x = memory.read(*input2_x).expect_field().unwrap();
208            let input2_y = memory.read(*input2_y).expect_field().unwrap();
209            let (x, y) = solver.ec_add(
210                &input1_x, &input1_y, &input2_x, &input2_y,
211                true, // Predicate is always true as brillig has control flow to handle false case
212            )?;
213
214            write_heap_array(
215                memory,
216                result,
217                &[MemoryValue::new_field(x), MemoryValue::new_field(y)],
218            );
219            Ok(())
220        }
221        BlackBoxOp::Poseidon2Permutation { message, output } => {
222            let input = read_heap_array(memory, message);
223            let input: Vec<F> = input.iter().map(|x| x.expect_field().unwrap()).collect();
224            let result = solver.poseidon2_permutation(&input)?;
225            let mut values = Vec::new();
226            for i in result {
227                values.push(MemoryValue::new_field(i));
228            }
229            write_heap_array(memory, output, &values);
230            Ok(())
231        }
232        BlackBoxOp::Sha256Compression { input, hash_values, output } => {
233            let mut message = [0; 16];
234            let inputs = read_heap_array(memory, input);
235            if inputs.len() != 16 {
236                return Err(BlackBoxResolutionError::Failed(
237                    BlackBoxFunc::Sha256Compression,
238                    format!("Expected 16 inputs but encountered {}", inputs.len()),
239                ));
240            }
241            for (i, &input) in inputs.iter().enumerate() {
242                message[i] = input.expect_u32().unwrap();
243            }
244            let mut state = [0; 8];
245            let values = read_heap_array(memory, hash_values);
246            if values.len() != 8 {
247                return Err(BlackBoxResolutionError::Failed(
248                    BlackBoxFunc::Sha256Compression,
249                    format!("Expected 8 values but encountered {}", values.len()),
250                ));
251            }
252            for (i, &value) in values.iter().enumerate() {
253                state[i] = value.expect_u32().unwrap();
254            }
255
256            sha256_compression(&mut state, &message);
257            let state = state.map(|x| x.into());
258
259            write_heap_array(memory, output, &state);
260            Ok(())
261        }
262        BlackBoxOp::ToRadix { input, radix, output_pointer, num_limbs, output_bits } => {
263            let input: F = memory.read(*input).expect_field().expect("ToRadix input not a field");
264            let MemoryValue::U32(radix) = memory.read(*radix) else {
265                panic!("ToRadix opcode's radix bit size does not match expected bit size 32")
266            };
267            let num_limbs = memory.read(*num_limbs).to_u32();
268            let MemoryValue::U1(output_bits) = memory.read(*output_bits) else {
269                panic!("ToRadix opcode's output_bits size does not match expected bit size 1")
270            };
271
272            let output = to_be_radix(input, radix, assert_usize(num_limbs), output_bits)?;
273
274            memory.write_slice(memory.read_ref(*output_pointer), &output);
275
276            Ok(())
277        }
278    }
279}
280
281/// Maps a [`BlackBoxOp`] variant to its corresponding [`BlackBoxFunc`].
282/// Used primarily for error reporting and resolution purposes.
283///
284/// # Panics
285/// If called with a [`BlackBoxOp::ToRadix`] operation, which is not part of the [`BlackBoxFunc`] enum.
286fn black_box_function_from_op(op: &BlackBoxOp) -> BlackBoxFunc {
287    match op {
288        BlackBoxOp::AES128Encrypt { .. } => BlackBoxFunc::AES128Encrypt,
289        BlackBoxOp::Blake2s { .. } => BlackBoxFunc::Blake2s,
290        BlackBoxOp::Blake3 { .. } => BlackBoxFunc::Blake3,
291        BlackBoxOp::Keccakf1600 { .. } => BlackBoxFunc::Keccakf1600,
292        BlackBoxOp::EcdsaSecp256k1 { .. } => BlackBoxFunc::EcdsaSecp256k1,
293        BlackBoxOp::EcdsaSecp256r1 { .. } => BlackBoxFunc::EcdsaSecp256r1,
294        BlackBoxOp::MultiScalarMul { .. } => BlackBoxFunc::MultiScalarMul,
295        BlackBoxOp::EmbeddedCurveAdd { .. } => BlackBoxFunc::EmbeddedCurveAdd,
296        BlackBoxOp::Poseidon2Permutation { .. } => BlackBoxFunc::Poseidon2Permutation,
297        BlackBoxOp::Sha256Compression { .. } => BlackBoxFunc::Sha256Compression,
298        BlackBoxOp::ToRadix { .. } => unreachable!("ToRadix is not an ACIR BlackBoxFunc"),
299    }
300}
301
302fn to_be_radix<F: AcirField>(
303    input: F,
304    radix: u32,
305    num_limbs: usize,
306    output_bits: bool,
307) -> Result<Vec<MemoryValue<F>>, BlackBoxResolutionError> {
308    assert!(
309        (2u32..=256u32).contains(&radix),
310        "Radix out of the valid range [2,256]. Value: {radix}"
311    );
312
313    assert!(
314        !output_bits || radix == 2u32,
315        "Radix {radix} is not equal to 2 and bit mode is activated."
316    );
317
318    let mut input = BigUint::from_bytes_be(&input.to_be_bytes());
319    let radix = BigUint::from(radix);
320
321    let mut limbs: Vec<MemoryValue<F>> = vec![MemoryValue::default(); num_limbs];
322    for i in (0..num_limbs).rev() {
323        let limb = &input % &radix;
324        limbs[i] = if output_bits {
325            MemoryValue::U1(!limb.is_zero())
326        } else {
327            let limb: u8 = limb.try_into().unwrap();
328            MemoryValue::U8(limb)
329        };
330        input /= &radix;
331    }
332
333    // In order for a successful decomposition, we require that after `num_limbs` divisions by `radix` then `input` should be zero.
334    // If `input` is non-zero then that implies that we have additional limbs which are not handled.
335    if !input.is_zero() {
336        return Err(BlackBoxResolutionError::AssertFailed(format!(
337            "Field failed to decompose into specified {num_limbs} limbs"
338        )));
339    }
340
341    Ok(limbs)
342}
343
344#[cfg(test)]
345mod ecdsa_tests {
346    use acir::brillig::lengths::SemiFlattenedLength;
347    use acir::brillig::{BlackBoxOp, HeapArray, MemoryAddress};
348    use acvm_blackbox_solver::{BlackBoxResolutionError, StubbedBlackBoxSolver};
349
350    use crate::Memory;
351    use crate::black_box::evaluate_black_box;
352    use crate::memory::MemoryValue;
353
354    use acir::FieldElement;
355
356    /// Writes a byte array into memory and returns a [`HeapArray`] pointing at it.
357    ///
358    /// `pointer_addr` holds the address of the items, `items_addr` is where the
359    /// bytes are stored. `len` is the size advertised by the heap array, which is
360    /// allowed to differ from `bytes.len()` so tests can exercise mismatched sizes.
361    fn write_heap_array(
362        memory: &mut Memory<FieldElement>,
363        pointer_addr: u32,
364        items_addr: u32,
365        bytes: &[u8],
366        len: u32,
367    ) -> HeapArray {
368        let pointer = MemoryAddress::direct(pointer_addr);
369        memory.write_ref(pointer, MemoryAddress::direct(items_addr));
370        let values: Vec<MemoryValue<FieldElement>> = bytes.iter().map(|&b| b.into()).collect();
371        memory.write_slice(MemoryAddress::direct(items_addr), &values);
372        HeapArray { pointer, size: SemiFlattenedLength(len) }
373    }
374
375    /// A `hashed_msg` of the wrong length must surface a recoverable
376    /// [`BlackBoxResolutionError`], not panic the VM.
377    #[test]
378    fn ecdsa_secp256k1_rejects_wrong_hashed_msg_length() {
379        let mut memory = Memory::default();
380
381        // Valid lengths for the keys and signature so evaluation reaches the
382        // `hashed_msg` length check.
383        let public_key_x = write_heap_array(&mut memory, 0, 1000, &[0u8; 32], 32);
384        let public_key_y = write_heap_array(&mut memory, 1, 2000, &[0u8; 32], 32);
385        let signature = write_heap_array(&mut memory, 2, 3000, &[0u8; 64], 64);
386        // A 31-byte hashed message: one short of the expected 32.
387        let hashed_msg = write_heap_array(&mut memory, 3, 4000, &[0u8; 31], 31);
388
389        let op = BlackBoxOp::EcdsaSecp256k1 {
390            hashed_msg,
391            public_key_x,
392            public_key_y,
393            signature,
394            result: MemoryAddress::direct(5),
395        };
396
397        let result = evaluate_black_box(&op, &StubbedBlackBoxSolver, &mut memory);
398        assert!(
399            matches!(result, Err(BlackBoxResolutionError::Failed(..))),
400            "expected a recoverable error, got {result:?}"
401        );
402    }
403
404    #[test]
405    fn ecdsa_secp256r1_rejects_wrong_hashed_msg_length() {
406        let mut memory = Memory::default();
407
408        let public_key_x = write_heap_array(&mut memory, 0, 1000, &[0u8; 32], 32);
409        let public_key_y = write_heap_array(&mut memory, 1, 2000, &[0u8; 32], 32);
410        let signature = write_heap_array(&mut memory, 2, 3000, &[0u8; 64], 64);
411        let hashed_msg = write_heap_array(&mut memory, 3, 4000, &[0u8; 31], 31);
412
413        let op = BlackBoxOp::EcdsaSecp256r1 {
414            hashed_msg,
415            public_key_x,
416            public_key_y,
417            signature,
418            result: MemoryAddress::direct(5),
419        };
420
421        let result = evaluate_black_box(&op, &StubbedBlackBoxSolver, &mut memory);
422        assert!(
423            matches!(result, Err(BlackBoxResolutionError::Failed(..))),
424            "expected a recoverable error, got {result:?}"
425        );
426    }
427}
428
429#[cfg(test)]
430mod to_be_radix_tests {
431    use crate::black_box::to_be_radix;
432
433    use acir::{AcirField, FieldElement};
434
435    use proptest::prelude::*;
436
437    // Define a wrapper around field so we can implement `Arbitrary`.
438    // NB there are other methods like `arbitrary_field_elements` around the codebase,
439    // but for `proptest_derive::Arbitrary` we need `F: AcirField + Arbitrary`.
440    acir::acir_field::field_wrapper!(TestField, FieldElement);
441
442    impl Arbitrary for TestField {
443        type Parameters = ();
444        type Strategy = BoxedStrategy<Self>;
445
446        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
447            any::<u128>().prop_map(|v| Self(FieldElement::from(v))).boxed()
448        }
449    }
450
451    proptest! {
452        #[test]
453        fn matches_byte_decomposition(param: TestField) {
454            let bytes: Vec<u8> = to_be_radix(param.0, 256, 32, false).unwrap().into_iter().map(|byte| byte.expect_u8().unwrap()).collect();
455            let expected_bytes = param.0.to_be_bytes();
456            prop_assert_eq!(bytes, expected_bytes);
457        }
458    }
459
460    #[test]
461    fn correctly_handles_unusual_radices() {
462        let value = FieldElement::from(65024u128);
463        let expected_limbs = vec![254, 254];
464
465        let limbs: Vec<u8> = to_be_radix(value, 255, 2, false)
466            .unwrap()
467            .into_iter()
468            .map(|byte| byte.expect_u8().unwrap())
469            .collect();
470        assert_eq!(limbs, expected_limbs);
471    }
472
473    #[test]
474    fn matches_decimal_decomposition() {
475        let value = FieldElement::from(123456789u128);
476        let expected_limbs = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
477
478        let limbs: Vec<u8> = to_be_radix(value, 10, 9, false)
479            .unwrap()
480            .into_iter()
481            .map(|byte| byte.expect_u8().unwrap())
482            .collect();
483        assert_eq!(limbs, expected_limbs);
484    }
485
486    #[test]
487    fn rejects_non_zero_field_with_zero_limbs() {
488        let value = FieldElement::from(1u128);
489
490        let error = to_be_radix(value, 256, 0, false).unwrap_err();
491        assert_eq!(
492            error,
493            acvm_blackbox_solver::BlackBoxResolutionError::AssertFailed(
494                "Field failed to decompose into specified 0 limbs".to_string()
495            )
496        );
497    }
498}
brillig_vm/black_box.rs

brillig_vm/
black_box.rs
