acvm/compiler/
simulator.rs

1use acir::{
2    AcirField,
3    circuit::{
4        Circuit, Opcode,
5        brillig::{BrilligInputs, BrilligOutputs},
6        opcodes::{BlockId, FunctionInput, MemOpKind},
7    },
8    native_types::{Expression, Witness},
9};
10use std::collections::HashSet;
11
12use crate::pwg::arithmetic::ExpressionSolver;
13
14/// Simulate solving a circuit symbolically
15/// Instead of evaluating witness values from the inputs, like the PWG module is doing,
16/// this pass simply marks the witness that can be evaluated, from the known inputs,
17/// and incrementally from the previously marked witnesses.
18/// This avoids any computation on a big field which makes the process efficient.
19/// When all the witness of an opcode are marked as solvable, it means that the
20/// opcode is solvable.
21#[derive(Default)]
22pub struct CircuitSimulator {
23    /// Track the witnesses that can be solved
24    solvable_witnesses: HashSet<Witness>,
25
26    /// Track whether a [`BlockId`] has been initialized
27    initialized_blocks: HashSet<BlockId>,
28}
29
30/// The reason a circuit was deemed unsolvable by the [`CircuitSimulator`].
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum SimulationFailure {
33    /// The opcode at this index cannot be solved from the witnesses known at that point.
34    UnsolvableOpcode(usize),
35    /// All opcodes can be solved, but this circuit return value is never computed by any of them.
36    UnsolvableOutput(Witness),
37}
38
39impl CircuitSimulator {
40    /// Check whether the circuit is solvable in theory.
41    ///
42    /// # Returns
43    ///
44    /// Returns `None` if the circuit is deemed to be solvable
45    /// Otherwise returns `Some(failure)` describing the first unsolvable opcode or return value.
46    pub fn check_circuit<F: AcirField>(circuit: &Circuit<F>) -> Option<SimulationFailure> {
47        Self::default().run_check_circuit(circuit)
48    }
49
50    /// Simulate solving a circuit symbolically by keeping track of the witnesses that can be solved.
51    /// Returns the first opcode that cannot be solved, or a return value that no opcode computes, if any.
52    #[tracing::instrument(level = "trace", skip_all)]
53    fn run_check_circuit<F: AcirField>(
54        &mut self,
55        circuit: &Circuit<F>,
56    ) -> Option<SimulationFailure> {
57        let circuit_inputs = circuit.circuit_arguments();
58        self.solvable_witnesses.extend(circuit_inputs.iter());
59        for (i, op) in circuit.opcodes.iter().enumerate() {
60            if !self.try_solve(op) {
61                return Some(SimulationFailure::UnsolvableOpcode(i));
62            }
63        }
64        // All opcodes can be solved; the declared return values must also be solvable,
65        // otherwise the circuit promises an output it never computes.
66        for ret in &circuit.return_values.0 {
67            if !self.solvable_witnesses.contains(ret) {
68                return Some(SimulationFailure::UnsolvableOutput(*ret));
69            }
70        }
71        None
72    }
73
74    /// Check if the Opcode can be solved, and if yes, add the solved witness to set of solvable witness
75    fn try_solve<F: AcirField>(&mut self, opcode: &Opcode<F>) -> bool {
76        match opcode {
77            Opcode::AssertZero(expr) => {
78                let Some(unresolved) = unresolved_witnesses(expr, &self.solvable_witnesses) else {
79                    return false;
80                };
81                if unresolved.len() == 1 {
82                    self.mark_solvable(*unresolved.iter().next().expect("len == 1"));
83                    return true;
84                }
85                unresolved.is_empty()
86            }
87            Opcode::BlackBoxFuncCall(black_box_func_call) => {
88                let inputs = black_box_func_call.get_inputs_vec();
89                for input in inputs {
90                    if !self.can_solve_function_input(&input) {
91                        return false;
92                    }
93                }
94                let outputs = black_box_func_call.get_outputs_vec();
95                for output in outputs {
96                    self.mark_solvable(output);
97                }
98                true
99            }
100            Opcode::MemoryOp { block_id, op } => {
101                if !self.initialized_blocks.contains(block_id) {
102                    // Memory must be initialized before it can be used.
103                    return false;
104                }
105                if !self.solvable_witnesses.contains(&op.index) {
106                    return false;
107                }
108                match op.operation {
109                    MemOpKind::Read => {
110                        self.mark_solvable(op.value);
111                        true
112                    }
113                    MemOpKind::Write => self.solvable_witnesses.contains(&op.value),
114                }
115            }
116            Opcode::MemoryInit { block_id, init, .. } => {
117                for w in init {
118                    if !self.solvable_witnesses.contains(w) {
119                        return false;
120                    }
121                }
122                self.initialized_blocks.insert(*block_id)
123            }
124            Opcode::BrilligCall { id: _, inputs, outputs, predicate } => {
125                for input in inputs {
126                    if !self.can_solve_brillig_input(input) {
127                        return false;
128                    }
129                }
130                if !self.can_solve_expression(predicate) {
131                    return false;
132                }
133                for output in outputs {
134                    match output {
135                        BrilligOutputs::Simple(w) => self.mark_solvable(*w),
136                        BrilligOutputs::Array(arr) => {
137                            for w in arr {
138                                self.mark_solvable(*w);
139                            }
140                        }
141                    }
142                }
143                true
144            }
145            Opcode::Call { id: _, inputs, outputs, predicate } => {
146                for w in inputs {
147                    if !self.solvable_witnesses.contains(w) {
148                        return false;
149                    }
150                }
151                if !self.can_solve_expression(predicate) {
152                    return false;
153                }
154                for w in outputs {
155                    self.mark_solvable(*w);
156                }
157                true
158            }
159        }
160    }
161
162    /// Adds the witness to set of solvable witness
163    pub(crate) fn mark_solvable(&mut self, witness: Witness) {
164        self.solvable_witnesses.insert(witness);
165    }
166
167    pub fn can_solve_function_input<F: AcirField>(&self, input: &FunctionInput<F>) -> bool {
168        if let FunctionInput::Witness(w) = input {
169            return self.solvable_witnesses.contains(w);
170        }
171        true
172    }
173
174    fn can_solve_expression<F>(&self, expr: &Expression<F>) -> bool {
175        for w in Self::expr_witness(expr) {
176            if !self.solvable_witnesses.contains(&w) {
177                return false;
178            }
179        }
180        true
181    }
182
183    fn can_solve_brillig_input<F>(&self, input: &BrilligInputs<F>) -> bool {
184        match input {
185            BrilligInputs::Single(expr) => self.can_solve_expression(expr),
186            BrilligInputs::Array(exprs) => {
187                for expr in exprs {
188                    if !self.can_solve_expression(expr) {
189                        return false;
190                    }
191                }
192                true
193            }
194
195            BrilligInputs::MemoryArray(block_id) => self.initialized_blocks.contains(block_id),
196        }
197    }
198
199    pub(crate) fn expr_witness<F>(expr: &Expression<F>) -> impl Iterator<Item = Witness> {
200        expr.mul_terms
201            .iter()
202            .flat_map(|i| [i.1, i.2])
203            .chain(expr.linear_combinations.iter().map(|i| i.1))
204    }
205}
206
207/// Returns the deduplicated set of unresolved witnesses in an arithmetic expression,
208/// given a set of already-solvable witnesses.
209///
210/// Returns `None` when the expression has a squaring `w*w` that cannot be solved by the linear PWG.
211///
212/// Otherwise returns `Some(set)`. An expression with `set.len() <= 1` is solvable:
213/// zero unresolved means it is already fully solvable; one unresolved means we
214/// can solve for the remaining witness.
215pub(crate) fn unresolved_witnesses<F: AcirField>(
216    expr: &Expression<F>,
217    solvable: &HashSet<Witness>,
218) -> Option<HashSet<Witness>> {
219    let combined_mul_terms = ExpressionSolver::combine_mul_terms(&expr.mul_terms);
220    let combined_linear_terms = ExpressionSolver::combine_linear_terms(&expr.linear_combinations);
221    let mut unresolved = HashSet::new();
222    for (_, w1, w2) in &combined_mul_terms {
223        if !solvable.contains(w1) {
224            unresolved.insert(*w1);
225        }
226        if !solvable.contains(w2) {
227            if w2 == w1 {
228                // This is a squaring term `w2*w2`, leading to a quadratic equation that cannot be
229                // solved by the linear PWG.
230                return None;
231            }
232            unresolved.insert(*w2);
233        }
234    }
235    for (_, w) in &combined_linear_terms {
236        if !solvable.contains(w) {
237            unresolved.insert(*w);
238        }
239    }
240    Some(unresolved)
241}
242
243#[cfg(test)]
244mod tests {
245    use crate::compiler::{CircuitSimulator, simulator::SimulationFailure};
246    use acir::{circuit::Circuit, native_types::Witness};
247
248    #[test]
249    fn reports_none_for_empty_circuit() {
250        let src = "
251        private parameters: []
252        public parameters: []
253        return values: []
254        ";
255        let empty_circuit = Circuit::from_str(src).unwrap();
256        assert!(CircuitSimulator::check_circuit(&empty_circuit).is_none());
257    }
258
259    #[test]
260    fn reports_none_for_connected_circuit() {
261        let src = "
262        private parameters: [w1]
263        public parameters: []
264        return values: []
265        ASSERT w2 = w1
266        ";
267        let connected_circuit = Circuit::from_str(src).unwrap();
268        assert!(CircuitSimulator::check_circuit(&connected_circuit).is_none());
269    }
270
271    #[test]
272    fn reports_true_for_connected_circuit_with_range() {
273        let src = "
274        private parameters: [w1, w3]
275        public parameters: []
276        return values: []
277        ASSERT w2 = w1
278        BLACKBOX::RANGE input: w3, bits: 8
279        ";
280        let connected_circuit = Circuit::from_str(src).unwrap();
281
282        assert!(CircuitSimulator::check_circuit(&connected_circuit).is_none());
283    }
284
285    #[test]
286    fn reports_false_for_disconnected_circuit() {
287        let src = "
288        private parameters: [w1]
289        public parameters: []
290        return values: []
291        ASSERT w2 = w1
292        ASSERT w4 = w3
293        ";
294        let disconnected_circuit = Circuit::from_str(src).unwrap();
295
296        assert!(CircuitSimulator::check_circuit(&disconnected_circuit).is_some());
297    }
298
299    #[test]
300    fn reports_none_for_blackbox_output() {
301        let src = "
302        private parameters: [w0, w1]
303        public parameters: []
304        return values: []
305        BLACKBOX::AND lhs: w0, rhs: w1, output: w2, bits: 32
306        ASSERT w3 = w2
307        ";
308        let circuit = Circuit::from_str(src).unwrap();
309        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
310    }
311
312    #[test]
313    fn reports_none_for_read_memory() {
314        let src = "
315        private parameters: [w0]
316        public parameters: []
317        return values: []
318        INIT b0 = [w0]
319        READ w1 = b0[w0]
320        ASSERT w2 = w1
321        ";
322        let circuit = Circuit::from_str(src).unwrap();
323        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
324    }
325
326    #[test]
327    fn reports_none_for_call_output() {
328        let src = "
329        private parameters: [w0]
330        public parameters: []
331        return values: []
332        CALL func: 0, predicate: 1, inputs: [w0], outputs: [w1]
333        ASSERT w2 = w1
334        ";
335        let circuit = Circuit::from_str(src).unwrap();
336        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
337    }
338
339    #[test]
340    fn reports_none_for_brillig_call_output() {
341        let src = "
342        private parameters: [w0]
343        public parameters: []
344        return values: []
345        BRILLIG CALL func: 0, predicate: 1, inputs: [w0], outputs: [w1]
346        ASSERT w2 = w1
347        ";
348        let circuit = Circuit::from_str(src).unwrap();
349        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
350    }
351
352    #[test]
353    fn reports_some_for_disconnected_circuit() {
354        let src = "
355        private parameters: [w1]
356        public parameters: []
357        return values: []
358        ASSERT w2 = w1
359        ASSERT w4 = w3
360        ";
361        let disconnected_circuit = Circuit::from_str(src).unwrap();
362        assert_eq!(
363            CircuitSimulator::check_circuit(&disconnected_circuit),
364            Some(SimulationFailure::UnsolvableOpcode(1))
365        );
366    }
367
368    #[test]
369    fn reports_some_when_memory_block_is_passed_an_unknown_witness() {
370        let src = "
371        private parameters: [w1]
372        public parameters: []
373        return values: []
374        ASSERT w1 = 0
375        INIT b0 = [w0]
376        ";
377        let circuit = Circuit::from_str(src).unwrap();
378        assert_eq!(
379            CircuitSimulator::check_circuit(&circuit),
380            Some(SimulationFailure::UnsolvableOpcode(1))
381        );
382    }
383
384    #[test]
385    fn reports_some_when_attempting_to_reinitialize_memory_block() {
386        let src = "
387        private parameters: [w0]
388        public parameters: []
389        return values: []
390        INIT b0 = [w0]
391        INIT b0 = [w0]
392        ";
393        let circuit = Circuit::from_str(src).unwrap();
394        assert_eq!(
395            CircuitSimulator::check_circuit(&circuit),
396            Some(SimulationFailure::UnsolvableOpcode(1))
397        );
398    }
399
400    #[test]
401    fn reports_some_when_unknown_witness_is_multiplied_by_itself() {
402        // If an AssertZero contains just one unknown witness, it might still not possible
403        // to solve if: if that unknown witness is being multiplied by itself.
404        let src = "
405        private parameters: [w0]
406        public parameters: []
407        return values: []
408        ASSERT w0 = w1*w1
409        ";
410        let circuit = Circuit::from_str(src).unwrap();
411        assert_eq!(
412            CircuitSimulator::check_circuit(&circuit),
413            Some(SimulationFailure::UnsolvableOpcode(0))
414        );
415    }
416
417    #[test]
418    fn reports_some_when_write_has_a_single_unknown_witness_in_its_value() {
419        let src = "
420        private parameters: [w0, w1]
421        public parameters: []
422        return values: []
423        INIT b0 = [w0]
424        WRITE b0[w0] = w2
425        ";
426        let circuit = Circuit::from_str(src).unwrap();
427        assert_eq!(
428            CircuitSimulator::check_circuit(&circuit),
429            Some(SimulationFailure::UnsolvableOpcode(1))
430        );
431    }
432
433    #[test]
434    fn reports_none_when_write_has_known_witnesses_in_its_value() {
435        let src = "
436        private parameters: [w0, w1, w2]
437        public parameters: []
438        return values: []
439        INIT b0 = [w0]
440        WRITE b0[w0] = w1 + w2
441        ";
442        let circuit = Circuit::from_str(src).unwrap();
443        assert_eq!(CircuitSimulator::check_circuit(&circuit), None);
444    }
445
446    #[test]
447    fn reports_failure_for_uncomputed_return_value() {
448        let src = "
449        private parameters: [w0]
450        public parameters: []
451        return values: [w2]
452        ASSERT w1 = w0
453        ";
454        let circuit = Circuit::from_str(src).unwrap();
455        assert_eq!(
456            CircuitSimulator::check_circuit(&circuit),
457            Some(SimulationFailure::UnsolvableOutput(Witness(2)))
458        );
459    }
460
461    #[test]
462    fn reports_none_for_computed_return_value() {
463        let src = "
464        private parameters: [w0]
465        public parameters: []
466        return values: [w1]
467        ASSERT w1 = w0
468        ";
469        let circuit = Circuit::from_str(src).unwrap();
470        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
471    }
472
473    #[test]
474    fn reports_none_for_return_value_that_is_also_a_parameter() {
475        let src = "
476        private parameters: [w0]
477        public parameters: []
478        return values: [w0]
479        ";
480        let circuit = Circuit::from_str(src).unwrap();
481        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
482    }
483
484    #[test]
485    fn reports_some_when_expression_can_simplify() {
486        let src = "
487        private parameters: []
488        public parameters: []
489        return values: []
490        ASSERT w1 = w1
491        ASSERT w2 = w1
492        ";
493        let empty_circuit = Circuit::from_str(src).unwrap();
494        assert_eq!(
495            CircuitSimulator::check_circuit(&empty_circuit),
496            Some(SimulationFailure::UnsolvableOpcode(1))
497        );
498    }
499}
acvm/compiler/simulator.rs

acvm/compiler/
simulator.rs
