acir/circuit/
opcodes.rs

1//! ACIR opcodes
2//!
3//! This module defines the core set opcodes used in ACIR.
4use super::brillig::{BrilligFunctionId, BrilligInputs, BrilligOutputs};
5
6pub mod function_id;
7pub use function_id::AcirFunctionId;
8
9use crate::{
10    circuit::PublicInputs,
11    native_types::{Expression, Witness, display_expression},
12};
13use acir_field::AcirField;
14use serde::{Deserialize, Serialize};
15
16mod black_box_function_call;
17mod memory_operation;
18
19pub use black_box_function_call::{BlackBoxFuncCall, FunctionInput, InvalidInputBitSize};
20pub use memory_operation::{BlockId, MemOp};
21
22/// Type for a memory block
23#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize, Hash)]
24#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
25pub enum BlockType {
26    /// The default type of memory block.
27    /// Virtually all user memory blocks are expected to be of this type
28    /// unless the backend wishes to expose special handling for call/return data.
29    Memory,
30    /// Indicate to the backend that this memory comes from a circuit's inputs.
31    ///
32    /// This is most useful for schemes which require passing a lot of circuit inputs
33    /// through multiple circuits (such as in a recursive proof scheme).
34    /// Stores a constant identifier to distinguish between multiple calldata inputs.
35    CallData(u32),
36    /// Similar to calldata except it states that this memory is returned in the circuit outputs.
37    ReturnData,
38}
39
40impl BlockType {
41    pub fn is_databus(&self) -> bool {
42        matches!(self, BlockType::CallData(_) | BlockType::ReturnData)
43    }
44}
45
46/// Defines an operation within an ACIR circuit
47///
48/// Expects a type parameter `F` which implements [AcirField].
49#[allow(clippy::large_enum_variant)]
50#[derive(Clone, PartialEq, Eq, Serialize, Deserialize, Hash)]
51#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
52pub enum Opcode<F: AcirField> {
53    /// An `AssertZero` opcode adds the constraint that `P(w) = 0`, where
54    /// `w=(w_1,..w_n)` is a tuple of `n` witnesses, and `P` is a multi-variate
55    /// polynomial of total degree at most `2`.
56    ///
57    /// The coefficients `{q_M}_{i,j}, q_i,q_c` of the polynomial are known
58    /// values which define the opcode.
59    ///
60    /// A general expression of assert-zero opcode is the following:
61    /// ```text
62    /// \sum_{i,j} {q_M}_{i,j}w_iw_j + \sum_i q_iw_i +q_c = 0
63    /// ```
64    ///
65    /// An assert-zero opcode can be used to:
66    /// - **express a constraint** on witnesses; for instance to express that a
67    ///   witness `w` is a boolean, you can add the opcode: `w*w-w=0`
68    /// - or, to **compute the value** of an arithmetic operation of some inputs.
69    ///
70    /// For instance, to multiply two witnesses `x` and `y`, you would use the
71    /// opcode `z-x*y=0`, which would constrain `z` to be `x*y`.
72    ///
73    /// The solver expects that at most one witness is not known when executing the opcode.
74    AssertZero(Expression<F>),
75
76    /// Calls to "gadgets" which rely on backends implementing support for
77    /// specialized constraints.
78    ///
79    /// Often used for exposing more efficient implementations of
80    /// SNARK-unfriendly computations.
81    ///
82    /// All black box function inputs are specified as [FunctionInput],
83    /// and they have one or several witnesses as output.
84    ///
85    /// Some more advanced computations assume that the proving system has an
86    /// 'embedded curve'. It is a curve that cycles with the main curve of the
87    /// proving system, i.e the scalar field of the embedded curve is the base
88    /// field of the main one, and vice-versa.
89    /// e.g. Aztec's Barretenberg uses BN254 as the main curve and Grumpkin as the
90    /// embedded curve.
91    BlackBoxFuncCall(BlackBoxFuncCall<F>),
92
93    /// Atomic operation on a block of memory
94    ///
95    /// ACIR is able to address any array of witnesses. Each array is assigned
96    /// an id ([BlockId]) and needs to be initialized with the [Opcode::MemoryInit] opcode.
97    /// Then it is possible to read and write from/to an array by providing the
98    /// index and the value we read/write as arithmetic expressions. Note that
99    /// ACIR arrays all have a known fixed length (given in the [Opcode::MemoryInit]
100    /// opcode below)
101    MemoryOp {
102        /// Identifier of the array
103        block_id: BlockId,
104        /// Describe the memory operation to perform
105        op: MemOp<F>,
106    },
107
108    /// Initialize an ACIR array from a vector of witnesses.
109    ///
110    /// There must be only one MemoryInit per block_id, and MemoryOp opcodes must
111    /// come after the MemoryInit.
112    MemoryInit {
113        /// Identifier of the array
114        block_id: BlockId,
115        /// Vector of witnesses specifying the initial value of the array
116        init: Vec<Witness>,
117        /// Specify what type of memory we should initialize
118        block_type: BlockType,
119    },
120
121    /// Calls to unconstrained functions. Unconstrained functions are constructed with [Brillig][super::brillig].
122    BrilligCall {
123        /// Id for the function being called. It is the responsibility of the executor
124        /// to fetch the appropriate Brillig bytecode from this id.
125        id: BrilligFunctionId,
126        /// Inputs to the function call
127        inputs: Vec<BrilligInputs<F>>,
128        /// Outputs to the function call
129        outputs: Vec<BrilligOutputs>,
130        /// Predicate of the Brillig execution - when the predicate evaluates to 0, execution is skipped.
131        /// When the predicate evaluates to 1, execution proceeds.
132        predicate: Expression<F>,
133    },
134
135    /// Calls to functions represented as a separate circuit. A call opcode allows us
136    /// to build a call stack when executing the outer-most circuit.
137    Call {
138        /// Id for the function being called. It is the responsibility of the executor
139        /// to fetch the appropriate circuit from this id.
140        id: AcirFunctionId,
141        /// Inputs to the function call
142        inputs: Vec<Witness>,
143        /// Outputs of the function call
144        outputs: Vec<Witness>,
145        /// Predicate of the circuit execution - when the predicate evaluates to 0, execution is skipped.
146        /// When the predicate evaluates to 1, execution proceeds.
147        predicate: Expression<F>,
148    },
149}
150
151impl<F: AcirField> std::fmt::Display for Opcode<F> {
152    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
153        display_opcode(self, None, f)
154    }
155}
156
157impl<F: AcirField> std::fmt::Debug for Opcode<F> {
158    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
159        std::fmt::Display::fmt(self, f)
160    }
161}
162
163/// Displays an opcode, optionally using the provided return values to prefer displaying
164/// `ASSERT return_value = ...` when possible.
165pub(super) fn display_opcode<F: AcirField>(
166    opcode: &Opcode<F>,
167    return_values: Option<&PublicInputs>,
168    f: &mut std::fmt::Formatter<'_>,
169) -> std::fmt::Result {
170    match opcode {
171        Opcode::AssertZero(expr) => {
172            write!(f, "ASSERT ")?;
173            display_expression(expr, true, return_values, f)
174        }
175        Opcode::BlackBoxFuncCall(g) => std::fmt::Display::fmt(&g, f),
176        Opcode::MemoryOp { block_id, op } => {
177            let is_read = op.operation.is_zero();
178            if is_read {
179                write!(f, "READ {} = b{}[{}]", op.value, block_id.0, op.index)
180            } else {
181                write!(f, "WRITE b{}[{}] = {}", block_id.0, op.index, op.value)
182            }
183        }
184        Opcode::MemoryInit { block_id, init, block_type: databus } => {
185            match databus {
186                BlockType::Memory => write!(f, "INIT ")?,
187                BlockType::CallData(id) => write!(f, "INIT CALLDATA {id} ")?,
188                BlockType::ReturnData => write!(f, "INIT RETURNDATA ")?,
189            }
190            let witnesses = init.iter().map(|w| format!("{w}")).collect::<Vec<String>>().join(", ");
191            write!(f, "b{} = [{witnesses}]", block_id.0)
192        }
193        // We keep the display for a BrilligCall and circuit Call separate as they
194        // are distinct in their functionality and we should maintain this separation for debugging.
195        Opcode::BrilligCall { id, inputs, outputs, predicate } => {
196            write!(f, "BRILLIG CALL func: {id}, ")?;
197            write!(f, "predicate: {predicate}, ")?;
198
199            let inputs =
200                inputs.iter().map(|input| format!("{input}")).collect::<Vec<String>>().join(", ");
201            let outputs = outputs
202                .iter()
203                .map(|output| format!("{output}"))
204                .collect::<Vec<String>>()
205                .join(", ");
206
207            write!(f, "inputs: [{inputs}], ")?;
208            write!(f, "outputs: [{outputs}]")
209        }
210        Opcode::Call { id, inputs, outputs, predicate } => {
211            write!(f, "CALL func: {id}, ")?;
212            write!(f, "predicate: {predicate}, ")?;
213            let inputs = inputs.iter().map(|w| format!("{w}")).collect::<Vec<String>>().join(", ");
214            let outputs =
215                outputs.iter().map(|w| format!("{w}")).collect::<Vec<String>>().join(", ");
216
217            write!(f, "inputs: [{inputs}], ")?;
218            write!(f, "outputs: [{outputs}]")
219        }
220    }
221}
222
223#[cfg(test)]
224mod tests {
225    use acir_field::FieldElement;
226
227    use crate::{
228        circuit::opcodes::{BlackBoxFuncCall, BlockId, BlockType, FunctionInput},
229        native_types::{Expression, Witness},
230    };
231
232    use super::Opcode;
233
234    #[test]
235    fn mem_init_display_snapshot() {
236        let mem_init: Opcode<FieldElement> = Opcode::MemoryInit {
237            block_id: BlockId(42),
238            init: (0..10u32).map(Witness).collect(),
239            block_type: BlockType::Memory,
240        };
241
242        insta::assert_snapshot!(
243            mem_init.to_string(),
244            @"INIT b42 = [w0, w1, w2, w3, w4, w5, w6, w7, w8, w9]"
245        );
246    }
247
248    #[test]
249    fn blackbox_snapshot() {
250        let xor: Opcode<FieldElement> = Opcode::BlackBoxFuncCall(BlackBoxFuncCall::XOR {
251            lhs: FunctionInput::Witness(0.into()),
252            rhs: FunctionInput::Witness(1.into()),
253            num_bits: 32,
254            output: Witness(3),
255        });
256
257        insta::assert_snapshot!(
258            xor.to_string(),
259            @"BLACKBOX::XOR lhs: w0, rhs: w1, output: w3, bits: 32"
260        );
261    }
262
263    #[test]
264    fn range_display_snapshot() {
265        let range: Opcode<FieldElement> = Opcode::BlackBoxFuncCall(BlackBoxFuncCall::RANGE {
266            input: FunctionInput::Witness(0.into()),
267            num_bits: 32,
268        });
269
270        insta::assert_snapshot!(
271            range.to_string(),
272            @"BLACKBOX::RANGE input: w0, bits: 32"
273        );
274    }
275
276    #[test]
277    fn display_zero() {
278        let zero = Opcode::AssertZero(Expression::<FieldElement>::default());
279        assert_eq!(zero.to_string(), "ASSERT 0 = 0");
280    }
281}
acir/circuit/opcodes.rs

acir/circuit/
opcodes.rs
