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        #[tag(3)]
152        predicate: Expression<F>,
153    },
154
155    /// Calls to functions represented as a separate circuit. A call opcode allows us
156    /// to build a call stack when executing the outer-most circuit.
157    #[tag(5)]
158    Call {
159        /// Id for the function being called. It is the responsibility of the executor
160        /// to fetch the appropriate circuit from this id.
161        #[tag(0)]
162        id: AcirFunctionId,
163        /// Inputs to the function call
164        #[tag(1)]
165        inputs: Vec<Witness>,
166        /// Outputs of the function call
167        #[tag(2)]
168        outputs: Vec<Witness>,
169        /// Predicate of the circuit execution - when the predicate evaluates to 0, execution is skipped.
170        /// When the predicate evaluates to 1, execution proceeds.
171        #[tag(3)]
172        predicate: Expression<F>,
173    },
174}
175
176impl<F: AcirField> std::fmt::Display for Opcode<F> {
177    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
178        display_opcode(self, None, f)
179    }
180}
181
182impl<F: AcirField> std::fmt::Debug for Opcode<F> {
183    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
184        std::fmt::Display::fmt(self, f)
185    }
186}
187
188/// Displays an opcode, optionally using the provided return values to prefer displaying
189/// `ASSERT return_value = ...` when possible.
190pub(super) fn display_opcode<F: AcirField>(
191    opcode: &Opcode<F>,
192    return_values: Option<&PublicInputs>,
193    f: &mut std::fmt::Formatter<'_>,
194) -> std::fmt::Result {
195    match opcode {
196        Opcode::AssertZero(expr) => {
197            write!(f, "ASSERT ")?;
198            display_expression(expr, true, return_values, f)
199        }
200        Opcode::BlackBoxFuncCall(g) => std::fmt::Display::fmt(&g, f),
201        Opcode::MemoryOp { block_id, op } => match op.operation {
202            MemOpKind::Read => {
203                write!(f, "READ {} = b{}[{}]", op.value, block_id.0, op.index)
204            }
205            MemOpKind::Write => {
206                write!(f, "WRITE b{}[{}] = {}", block_id.0, op.index, op.value)
207            }
208        },
209        Opcode::MemoryInit { block_id, init, block_type: databus } => {
210            match databus {
211                BlockType::Memory => write!(f, "INIT ")?,
212                BlockType::CallData(id) => write!(f, "INIT CALLDATA {id} ")?,
213                BlockType::ReturnData => write!(f, "INIT RETURNDATA ")?,
214            }
215            let witnesses = init.iter().map(|w| format!("{w}")).collect::<Vec<String>>().join(", ");
216            write!(f, "b{} = [{witnesses}]", block_id.0)
217        }
218        // We keep the display for a BrilligCall and circuit Call separate as they
219        // are distinct in their functionality and we should maintain this separation for debugging.
220        Opcode::BrilligCall { id, inputs, outputs, predicate } => {
221            write!(f, "BRILLIG CALL func: {id}, ")?;
222            write!(f, "predicate: {predicate}, ")?;
223
224            let inputs =
225                inputs.iter().map(|input| format!("{input}")).collect::<Vec<String>>().join(", ");
226            let outputs = outputs
227                .iter()
228                .map(|output| format!("{output}"))
229                .collect::<Vec<String>>()
230                .join(", ");
231
232            write!(f, "inputs: [{inputs}], ")?;
233            write!(f, "outputs: [{outputs}]")
234        }
235        Opcode::Call { id, inputs, outputs, predicate } => {
236            write!(f, "CALL func: {id}, ")?;
237            write!(f, "predicate: {predicate}, ")?;
238            let inputs = inputs.iter().map(|w| format!("{w}")).collect::<Vec<String>>().join(", ");
239            let outputs =
240                outputs.iter().map(|w| format!("{w}")).collect::<Vec<String>>().join(", ");
241
242            write!(f, "inputs: [{inputs}], ")?;
243            write!(f, "outputs: [{outputs}]")
244        }
245    }
246}
247
248#[cfg(test)]
249mod tests {
250    use acir_field::FieldElement;
251
252    use crate::{
253        circuit::opcodes::{BlackBoxFuncCall, BlockId, BlockType, FunctionInput},
254        native_types::{Expression, Witness},
255    };
256
257    use super::Opcode;
258
259    #[test]
260    fn mem_init_display_snapshot() {
261        let mem_init: Opcode<FieldElement> = Opcode::MemoryInit {
262            block_id: BlockId(42),
263            init: (0..10u32).map(Witness).collect(),
264            block_type: BlockType::Memory,
265        };
266
267        insta::assert_snapshot!(
268            mem_init.to_string(),
269            @"INIT b42 = [w0, w1, w2, w3, w4, w5, w6, w7, w8, w9]"
270        );
271    }
272
273    #[test]
274    fn blackbox_snapshot() {
275        let xor: Opcode<FieldElement> = Opcode::BlackBoxFuncCall(BlackBoxFuncCall::XOR {
276            lhs: FunctionInput::Witness(0.into()),
277            rhs: FunctionInput::Witness(1.into()),
278            num_bits: 32,
279            output: Witness(3),
280        });
281
282        insta::assert_snapshot!(
283            xor.to_string(),
284            @"BLACKBOX::XOR lhs: w0, rhs: w1, output: w3, bits: 32"
285        );
286    }
287
288    #[test]
289    fn range_display_snapshot() {
290        let range: Opcode<FieldElement> = Opcode::BlackBoxFuncCall(BlackBoxFuncCall::RANGE {
291            input: FunctionInput::Witness(0.into()),
292            num_bits: 32,
293        });
294
295        insta::assert_snapshot!(
296            range.to_string(),
297            @"BLACKBOX::RANGE input: w0, bits: 32"
298        );
299    }
300
301    #[test]
302    fn display_zero() {
303        let zero = Opcode::AssertZero(Expression::<FieldElement>::default());
304        assert_eq!(zero.to_string(), "ASSERT 0 = 0");
305    }
306}
acir/circuit/opcodes.rs

acir/circuit/
opcodes.rs
