acvm/pwg/
brillig.rs

1use std::collections::HashMap;
2
3use acir::{
4    AcirField,
5    brillig::{ForeignCallParam, ForeignCallResult, Opcode as BrilligOpcode},
6    circuit::{
7        OpcodeLocation,
8        brillig::{BrilligFunctionId, BrilligInputs, BrilligOutputs},
9        opcodes::BlockId,
10    },
11    native_types::WitnessMap,
12};
13use acvm_blackbox_solver::BlackBoxFunctionSolver;
14use brillig_vm::{
15    BranchToFeatureMap, BrilligProfilingSamples, FailureReason, MemoryValue, VM, VMStatus,
16};
17use serde::{Deserialize, Serialize};
18
19use crate::{OpcodeResolutionError, pwg::OpcodeNotSolvable};
20
21use super::{
22    ErrorSelector, RawAssertionPayload, ResolvedAssertionPayload, get_value, insert_value,
23    memory_op::MemoryOpSolver,
24};
25
26#[derive(Debug)]
27pub enum BrilligSolverStatus<F> {
28    Finished,
29    InProgress,
30    ForeignCallWait(ForeignCallWaitInfo<F>),
31}
32
33/// Specific solver for Brillig opcodes
34/// It maintains a Brillig VM that can execute the bytecode of the called brillig function
35pub struct BrilligSolver<'b, F, B: BlackBoxFunctionSolver<F>> {
36    vm: VM<'b, F, B>,
37    acir_index: usize,
38    /// This id references which Brillig function within the main ACIR program we are solving.
39    /// This is used for appropriately resolving errors as the ACIR program artifacts
40    /// set up their Brillig debug metadata by function id.
41    pub function_id: BrilligFunctionId,
42}
43
44impl<'b, B: BlackBoxFunctionSolver<F>, F: AcirField> BrilligSolver<'b, F, B> {
45    /// Assigns the zero value to all outputs of a given [brillig call][acir::circuit::opcodes::Opcode::BrilligCall].
46    pub(super) fn zero_out_brillig_outputs(
47        initial_witness: &mut WitnessMap<F>,
48        outputs: &[BrilligOutputs],
49    ) -> Result<(), OpcodeResolutionError<F>> {
50        for output in outputs {
51            match output {
52                BrilligOutputs::Simple(witness) => {
53                    insert_value(witness, F::zero(), initial_witness)?;
54                }
55                BrilligOutputs::Array(witness_arr) => {
56                    for witness in witness_arr {
57                        insert_value(witness, F::zero(), initial_witness)?;
58                    }
59                }
60            }
61        }
62        Ok(())
63    }
64
65    /// Constructs a solver for a Brillig block given the bytecode and initial
66    /// witness.
67    #[allow(clippy::too_many_arguments)]
68    pub(crate) fn new_call(
69        initial_witness: &WitnessMap<F>,
70        memory: &HashMap<BlockId, MemoryOpSolver<F>>,
71        inputs: &'b [BrilligInputs<F>],
72        brillig_bytecode: &'b [BrilligOpcode<F>],
73        bb_solver: &'b B,
74        acir_index: usize,
75        brillig_function_id: BrilligFunctionId,
76        profiling_active: bool,
77        with_branch_to_feature_map: Option<&BranchToFeatureMap>,
78    ) -> Result<Self, OpcodeResolutionError<F>> {
79        let vm = Self::setup_brillig_vm(
80            initial_witness,
81            memory,
82            inputs,
83            brillig_bytecode,
84            bb_solver,
85            profiling_active,
86            with_branch_to_feature_map,
87        )?;
88        Ok(Self { vm, acir_index, function_id: brillig_function_id })
89    }
90
91    /// Get a `BrilligVM` for executing the provided bytecode
92    /// 1. Reduce the input expressions into a known value, or error if they do not reduce to a value.
93    /// 2. Instantiate the Brillig VM with the bytecode and the reduced inputs.
94    fn setup_brillig_vm(
95        initial_witness: &WitnessMap<F>,
96        memory: &HashMap<BlockId, MemoryOpSolver<F>>,
97        inputs: &[BrilligInputs<F>],
98        brillig_bytecode: &'b [BrilligOpcode<F>],
99        bb_solver: &'b B,
100        profiling_active: bool,
101        with_branch_to_feature_map: Option<&BranchToFeatureMap>,
102    ) -> Result<VM<'b, F, B>, OpcodeResolutionError<F>> {
103        // Set input values
104        let mut calldata: Vec<F> = Vec::new();
105        // Each input represents an expression or array of expressions to evaluate.
106        // Iterate over each input and evaluate the expression(s) associated with it.
107        // Push the results into memory.
108        // If a certain expression is not solvable, we stall the ACVM and do not proceed with Brillig VM execution.
109        for input in inputs {
110            match input {
111                BrilligInputs::Single(expr) => match get_value(expr, initial_witness) {
112                    Ok(value) => calldata.push(value),
113                    Err(_) => {
114                        return Err(OpcodeResolutionError::OpcodeNotSolvable(
115                            OpcodeNotSolvable::ExpressionHasTooManyUnknowns(expr.clone()),
116                        ));
117                    }
118                },
119                BrilligInputs::Array(expr_arr) => {
120                    // Attempt to fetch all array input values
121                    for expr in expr_arr {
122                        match get_value(expr, initial_witness) {
123                            Ok(value) => calldata.push(value),
124                            Err(_) => {
125                                return Err(OpcodeResolutionError::OpcodeNotSolvable(
126                                    OpcodeNotSolvable::ExpressionHasTooManyUnknowns(expr.clone()),
127                                ));
128                            }
129                        }
130                    }
131                }
132                BrilligInputs::MemoryArray(block_id) => {
133                    let memory_block = memory
134                        .get(block_id)
135                        .ok_or(OpcodeNotSolvable::MissingMemoryBlock(block_id.as_u32()))?;
136                    calldata.extend(&memory_block.block_value);
137                }
138            }
139        }
140
141        // Instantiate a Brillig VM given the solved calldata
142        // along with the Brillig bytecode.
143        let vm = VM::new(
144            calldata,
145            brillig_bytecode,
146            bb_solver,
147            profiling_active,
148            with_branch_to_feature_map,
149        );
150        Ok(vm)
151    }
152
153    pub fn get_memory(&self) -> &[MemoryValue<F>] {
154        self.vm.get_memory()
155    }
156
157    pub fn write_memory_at(&mut self, ptr: u32, value: MemoryValue<F>) {
158        self.vm.write_memory_at(ptr, value);
159    }
160
161    pub fn get_call_stack(&self) -> Vec<usize> {
162        self.vm.get_call_stack()
163    }
164
165    pub fn get_fuzzing_trace(&self) -> Vec<u32> {
166        self.vm.get_fuzzing_trace()
167    }
168
169    pub(crate) fn solve(&mut self) -> Result<BrilligSolverStatus<F>, OpcodeResolutionError<F>> {
170        let status = self.vm.process_opcodes();
171        self.handle_vm_status(status)
172    }
173
174    pub fn step(&mut self) -> Result<BrilligSolverStatus<F>, OpcodeResolutionError<F>> {
175        let status = self.vm.process_opcode().clone();
176        self.handle_vm_status(status)
177    }
178
179    pub fn program_counter(&self) -> usize {
180        self.vm.program_counter()
181    }
182
183    /// Returns the status of the Brillig VM as a '`BrilligSolverStatus`' resolution.
184    /// It may be finished, in-progress, failed, or may be waiting for results of a foreign call.
185    /// Return the "resolution" to the caller who may choose to make subsequent calls
186    /// (when it gets foreign call results for example).
187    fn handle_vm_status(
188        &self,
189        vm_status: VMStatus<F>,
190    ) -> Result<BrilligSolverStatus<F>, OpcodeResolutionError<F>> {
191        match vm_status {
192            VMStatus::Finished { .. } => Ok(BrilligSolverStatus::Finished),
193            VMStatus::InProgress => Ok(BrilligSolverStatus::InProgress),
194            VMStatus::Failure { reason, call_stack } => {
195                let call_stack = call_stack
196                    .iter()
197                    .map(|brillig_index| OpcodeLocation::Brillig {
198                        acir_index: self.acir_index,
199                        brillig_index: *brillig_index,
200                    })
201                    .collect();
202                let payload = match reason {
203                    FailureReason::RuntimeError { message } => {
204                        Some(ResolvedAssertionPayload::String(message))
205                    }
206                    FailureReason::Trap { revert_data_offset, revert_data_size } => {
207                        extract_failure_payload_from_memory(
208                            self.vm.get_memory(),
209                            revert_data_offset
210                                .try_into()
211                                .expect("Failed conversion from u32 to usize"),
212                            revert_data_size
213                                .try_into()
214                                .expect("Failed conversion from u32 to usize"),
215                        )
216                    }
217                };
218
219                Err(OpcodeResolutionError::BrilligFunctionFailed {
220                    function_id: self.function_id,
221                    payload,
222                    call_stack,
223                })
224            }
225            VMStatus::ForeignCallWait { function, inputs } => {
226                Ok(BrilligSolverStatus::ForeignCallWait(ForeignCallWaitInfo { function, inputs }))
227            }
228        }
229    }
230
231    pub(crate) fn finalize(
232        self,
233        witness: &mut WitnessMap<F>,
234        outputs: &[BrilligOutputs],
235    ) -> Result<(), OpcodeResolutionError<F>> {
236        assert!(!self.vm.is_profiling_active(), "Expected VM profiling to not be active");
237        self.finalize_inner(witness, outputs)
238    }
239
240    /// Finalize the VM and return the profiling samples.
241    pub(crate) fn finalize_with_profiling(
242        mut self,
243        witness: &mut WitnessMap<F>,
244        outputs: &[BrilligOutputs],
245    ) -> Result<BrilligProfilingSamples, OpcodeResolutionError<F>> {
246        assert!(self.vm.is_profiling_active(), "Expected VM profiling to be active");
247        self.finalize_inner(witness, outputs)?;
248        Ok(self.vm.take_profiling_samples())
249    }
250
251    /// Finalize the VM execution and write the outputs to the provided witness map.
252    fn finalize_inner(
253        &self,
254        witness: &mut WitnessMap<F>,
255        outputs: &[BrilligOutputs],
256    ) -> Result<(), OpcodeResolutionError<F>> {
257        // Finish the Brillig execution by writing the outputs to the witness map
258        let vm_status = self.vm.get_status();
259        match vm_status {
260            VMStatus::Finished { return_data_offset, return_data_size } => {
261                self.write_brillig_outputs(
262                    witness,
263                    return_data_offset.try_into().expect("Failed conversion from u32 to usize"),
264                    return_data_size.try_into().expect("Failed conversion from u32 to usize"),
265                    outputs,
266                )?;
267                Ok(())
268            }
269            _ => panic!("Brillig VM has not completed execution"),
270        }
271    }
272
273    /// Write VM execution results into the witness map
274    fn write_brillig_outputs(
275        &self,
276        witness_map: &mut WitnessMap<F>,
277        return_data_offset: usize,
278        return_data_size: usize,
279        outputs: &[BrilligOutputs],
280    ) -> Result<(), OpcodeResolutionError<F>> {
281        let memory = self.vm.get_memory();
282        let mut current_ret_data_idx = return_data_offset;
283        for output in outputs {
284            match output {
285                BrilligOutputs::Simple(witness) => {
286                    let value =
287                        memory.get(current_ret_data_idx).ok_or_else(|| self.outputs_mismatch())?;
288                    insert_value(witness, value.to_field(), witness_map)?;
289                    current_ret_data_idx = current_ret_data_idx
290                        .checked_add(1)
291                        .ok_or_else(|| self.outputs_mismatch())?;
292                }
293                BrilligOutputs::Array(witness_arr) => {
294                    for witness in witness_arr {
295                        let value = memory
296                            .get(current_ret_data_idx)
297                            .ok_or_else(|| self.outputs_mismatch())?;
298                        insert_value(witness, value.to_field(), witness_map)?;
299                        current_ret_data_idx = current_ret_data_idx
300                            .checked_add(1)
301                            .ok_or_else(|| self.outputs_mismatch())?;
302                    }
303                }
304            }
305        }
306
307        let expected_end = return_data_offset
308            .checked_add(return_data_size)
309            .ok_or_else(|| self.outputs_mismatch())?;
310        if current_ret_data_idx != expected_end {
311            return Err(self.outputs_mismatch());
312        }
313        Ok(())
314    }
315
316    /// Error raised when the brillig return data described by the `Stop` opcode is
317    /// inconsistent with the expected call outputs (out of bounds, or a different count).
318    fn outputs_mismatch(&self) -> OpcodeResolutionError<F> {
319        OpcodeResolutionError::BrilligOutputsMismatch { function_id: self.function_id }
320    }
321
322    pub fn resolve_pending_foreign_call(&mut self, foreign_call_result: ForeignCallResult<F>) {
323        match self.vm.get_status() {
324            VMStatus::ForeignCallWait { .. } => self.vm.resolve_foreign_call(foreign_call_result),
325            _ => unreachable!("Brillig VM is not waiting for a foreign call"),
326        }
327    }
328}
329
330/// Extracts a `ResolvedAssertionPayload` from a block of memory of a Brillig VM instance.
331///
332/// Returns `None` if the amount of memory requested is zero.
333fn extract_failure_payload_from_memory<F: AcirField>(
334    memory: &[MemoryValue<F>],
335    revert_data_offset: usize,
336    revert_data_size: usize,
337) -> Option<ResolvedAssertionPayload<F>> {
338    // Since noir can only revert with strings currently, we can parse return data as a string
339    if revert_data_size == 0 {
340        None
341    } else {
342        let end = revert_data_offset
343            .checked_add(revert_data_size)
344            .expect("Revert data offset and size overflow");
345        let mut revert_values_iter = memory
346            .get(revert_data_offset..end)
347            .expect("Revert data offset and size exceed memory bounds")
348            .iter();
349        let error_selector = ErrorSelector::new(
350            revert_values_iter
351                .next()
352                .copied()
353                .expect("Incorrect revert data size")
354                .try_into()
355                .expect("Error selector is not u64"),
356        );
357
358        Some(ResolvedAssertionPayload::Raw(RawAssertionPayload {
359            selector: error_selector,
360            data: revert_values_iter.map(|value| value.to_field()).collect(),
361        }))
362    }
363}
364
365/// Encapsulates a request from a Brillig VM process that encounters a [foreign call opcode][brillig_vm::brillig::Opcode::ForeignCall]
366/// where the result of the foreign call has not yet been provided.
367///
368/// The caller must resolve this opcode externally based upon the information in the request.
369#[derive(Debug, PartialEq, Clone, Serialize, Deserialize)]
370pub struct ForeignCallWaitInfo<F> {
371    /// An identifier interpreted by the caller process
372    pub function: String,
373    /// Resolved inputs to a foreign call computed in the previous steps of a Brillig VM process
374    pub inputs: Vec<ForeignCallParam<F>>,
375}
376
377#[cfg(test)]
378mod tests {
379    use crate::pwg::{BrilligSolver, OpcodeResolutionError};
380    use acir::{
381        FieldElement,
382        brillig::{BinaryFieldOp, BitSize, HeapVector, IntegerBitSize, MemoryAddress, Opcode},
383        circuit::brillig::{BrilligFunctionId, BrilligInputs, BrilligOutputs},
384        native_types::{Expression, Witness, WitnessMap},
385    };
386    use std::collections::{BTreeMap, HashMap};
387
388    #[test]
389    fn test_solver() {
390        let mut initial_witness = WitnessMap::from(BTreeMap::from_iter([
391            (Witness(1), FieldElement::from(1u128)),
392            (Witness(2), FieldElement::from(1u128)),
393            (Witness(3), FieldElement::from(2u128)),
394        ]));
395        let w1 = Expression::from(Witness(1));
396        let w2 = Expression::from(Witness(2));
397        let w3 = Expression::from(Witness(3));
398        let inputs =
399            vec![BrilligInputs::Single(w1), BrilligInputs::Single(w2), BrilligInputs::Single(w3)];
400
401        let backend = acvm_blackbox_solver::StubbedBlackBoxSolver;
402        let bytecode = vec![
403            Opcode::Const {
404                destination: MemoryAddress::Direct(21),
405                bit_size: BitSize::Integer(IntegerBitSize::U32),
406                value: FieldElement::from(1_u128),
407            },
408            Opcode::Const {
409                destination: MemoryAddress::Direct(20),
410                bit_size: BitSize::Integer(IntegerBitSize::U32),
411                value: FieldElement::from(0_u128),
412            },
413            Opcode::CalldataCopy {
414                destination_address: MemoryAddress::Direct(0),
415                size_address: MemoryAddress::Direct(21),
416                offset_address: MemoryAddress::Direct(20),
417            },
418            Opcode::Const {
419                destination: MemoryAddress::Direct(2),
420                bit_size: BitSize::Field,
421                value: FieldElement::from(0_u128),
422            },
423            Opcode::BinaryFieldOp {
424                destination: MemoryAddress::Direct(3),
425                op: BinaryFieldOp::Equals,
426                lhs: MemoryAddress::Direct(0),
427                rhs: MemoryAddress::Direct(2),
428            },
429            Opcode::JumpIf { condition: MemoryAddress::Direct(3), location: 8 },
430            Opcode::Const {
431                destination: MemoryAddress::Direct(1),
432                bit_size: BitSize::Field,
433                value: FieldElement::from(1_u128),
434            },
435            Opcode::BinaryFieldOp {
436                destination: MemoryAddress::Direct(0),
437                op: BinaryFieldOp::Add,
438                lhs: MemoryAddress::Direct(1),
439                rhs: MemoryAddress::Direct(0),
440            },
441            Opcode::Stop {
442                return_data: HeapVector {
443                    pointer: MemoryAddress::Direct(20),
444                    size: MemoryAddress::Direct(21),
445                },
446            },
447        ];
448        let mut solver = BrilligSolver::new_call(
449            &initial_witness,
450            &HashMap::new(),
451            &inputs,
452            &bytecode,
453            &backend,
454            0,
455            BrilligFunctionId::default(),
456            false,
457            None,
458        )
459        .unwrap();
460        solver.solve().unwrap();
461        let outputs = vec![BrilligOutputs::Simple(Witness(4))];
462        solver.finalize(&mut initial_witness, &outputs).unwrap();
463
464        assert_eq!(initial_witness[&Witness(4)], FieldElement::from(2u128));
465    }
466
467    /// A `Stop` opcode having return-data pointer outside of
468    /// the VM's allocated memory
469    #[test]
470    fn out_of_bounds_return_data_offset_errors_instead_of_panicking() {
471        let mut initial_witness = WitnessMap::from(BTreeMap::<Witness, FieldElement>::new());
472        let inputs: Vec<BrilligInputs<FieldElement>> = vec![];
473
474        let backend = acvm_blackbox_solver::StubbedBlackBoxSolver;
475        let bytecode = vec![
476            // The value stored here is dereferenced as the return-data offset; point it
477            // far beyond any memory the program actually wrote to.
478            Opcode::Const {
479                destination: MemoryAddress::Direct(10),
480                bit_size: BitSize::Integer(IntegerBitSize::U32),
481                value: FieldElement::from(1_000_000_u128),
482            },
483            Opcode::Const {
484                destination: MemoryAddress::Direct(11),
485                bit_size: BitSize::Integer(IntegerBitSize::U32),
486                value: FieldElement::from(1_u128),
487            },
488            Opcode::Stop {
489                return_data: HeapVector {
490                    pointer: MemoryAddress::Direct(10),
491                    size: MemoryAddress::Direct(11),
492                },
493            },
494        ];
495        let mut solver = BrilligSolver::new_call(
496            &initial_witness,
497            &HashMap::new(),
498            &inputs,
499            &bytecode,
500            &backend,
501            0,
502            BrilligFunctionId::default(),
503            false,
504            None,
505        )
506        .unwrap();
507        solver.solve().unwrap();
508
509        let outputs = vec![BrilligOutputs::Simple(Witness(4))];
510        let result = solver.finalize(&mut initial_witness, &outputs);
511        assert!(
512            matches!(result, Err(OpcodeResolutionError::BrilligOutputsMismatch { .. })),
513            "expected a BrilligOutputsMismatch error, got {result:?}"
514        );
515    }
516
517    /// A `Stop` opcode whose declared return-data size does not match the number of
518    /// `outputs`.
519    #[test]
520    fn return_data_size_mismatch_errors_instead_of_asserting() {
521        let mut initial_witness = WitnessMap::from(BTreeMap::<Witness, FieldElement>::new());
522        let inputs: Vec<BrilligInputs<FieldElement>> = vec![];
523
524        let backend = acvm_blackbox_solver::StubbedBlackBoxSolver;
525        let bytecode = vec![
526            // Dereferenced as the (in-bounds) return-data offset.
527            Opcode::Const {
528                destination: MemoryAddress::Direct(0),
529                bit_size: BitSize::Integer(IntegerBitSize::U32),
530                value: FieldElement::from(0_u128),
531            },
532            // Claim five return values while only a single output witness is provided.
533            Opcode::Const {
534                destination: MemoryAddress::Direct(5),
535                bit_size: BitSize::Integer(IntegerBitSize::U32),
536                value: FieldElement::from(5_u128),
537            },
538            Opcode::Stop {
539                return_data: HeapVector {
540                    pointer: MemoryAddress::Direct(0),
541                    size: MemoryAddress::Direct(5),
542                },
543            },
544        ];
545        let mut solver = BrilligSolver::new_call(
546            &initial_witness,
547            &HashMap::new(),
548            &inputs,
549            &bytecode,
550            &backend,
551            0,
552            BrilligFunctionId::default(),
553            false,
554            None,
555        )
556        .unwrap();
557        solver.solve().unwrap();
558
559        let outputs = vec![BrilligOutputs::Simple(Witness(4))];
560        let result = solver.finalize(&mut initial_witness, &outputs);
561        assert!(
562            matches!(result, Err(OpcodeResolutionError::BrilligOutputsMismatch { .. })),
563            "expected a BrilligOutputsMismatch error, got {result:?}"
564        );
565    }
566}
acvm/pwg/brillig.rs

acvm/pwg/
brillig.rs
