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

brillig_vm/
black_box.rs
