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

acir/circuit/
opcodes.rs
