acir/circuit/
brillig.rs

1//! This module contains [Brillig][brillig] structures for integration within an ACIR circuit.
2//!
3//! [Brillig][brillig] is used in ACIR as a hint for the solver when executing the circuit.
4//! Executing Brillig does not generate any constraints and is the result of the compilation of an unconstrained function.
5//!
6//! Let's see an example with euclidean division.
7//! The normal way to compute `a/b`, where `a` and `b` are 8-bits integers, is to
8//! implement the Euclidean algorithm which computes in a loop (or recursively)
9//! modulus of the kind 'a mod b'. Doing this computation requires a lot of steps to
10//! be properly implemented in ACIR, especially the loop with a condition. However,
11//! euclidean division can be easily constrained with one assert-zero opcode:
12//! `a = bq+r`, assuming `q` is 8 bits and `r<b`. Since these assumptions can easily
13//! written with a few range opcodes, euclidean division can in fact be implemented
14//! with a small number of opcodes.
15//!
16//! However, in order to write these opcodes we need the result of the division
17//! which are the witness `q` and `r`. But from the constraint `a=bq+r`, how can the
18//! solver figure out how to solve `q` and `r` with only one equation? This is where
19//! brillig/unconstrained function come into action. We simply define a function that
20//! performs the usual Euclidean algorithm to compute `q` and `r` from `a` and `b`.
21//! Since executing Brillig does not generate constraints, it is not meaningful to the
22//! proving system but simply used by the solver to compute the values of `q` and
23//! `r`. The output witnesses `q` and `r` are then expected to be used by the proving system.
24//!
25//! In summary, executing Brillig will perform the computation defined by its
26//! bytecode, on the provided inputs, and assign the result to the output witnesses,
27//! without adding any constraints.
28
29use super::opcodes::BlockId;
30use crate::native_types::{Expression, Witness};
31use acir_field::AcirField;
32use brillig::Opcode as BrilligOpcode;
33use msgpack_tagged::MsgpackTagged;
34use serde::{Deserialize, Serialize};
35
36/// Inputs for the Brillig VM. These are the initial inputs
37/// that the Brillig VM will use to start.
38#[derive(Clone, PartialEq, Eq, Debug, Hash)]
39#[derive(Serialize, Deserialize, MsgpackTagged)]
40#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
41pub enum BrilligInputs<F> {
42    #[tag(0)]
43    Single(Expression<F>),
44    #[tag(1)]
45    Array(Vec<Expression<F>>),
46    #[tag(2)]
47    MemoryArray(BlockId),
48}
49
50impl<F: AcirField> std::fmt::Display for BrilligInputs<F> {
51    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
52        match self {
53            BrilligInputs::Single(expr) => expr.fmt(f),
54            BrilligInputs::Array(exprs) => {
55                let joined = exprs.iter().map(|e| format!("{e}")).collect::<Vec<_>>().join(", ");
56                write!(f, "[{joined}]")
57            }
58            BrilligInputs::MemoryArray(block_id) => block_id.fmt(f),
59        }
60    }
61}
62
63/// Outputs for the Brillig VM. Once the VM has completed
64/// execution, this will be the object that is returned.
65#[derive(Clone, PartialEq, Eq, Debug, Hash)]
66#[derive(Serialize, Deserialize, MsgpackTagged)]
67#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
68pub enum BrilligOutputs {
69    #[tag(0)]
70    Simple(Witness),
71    #[tag(1)]
72    Array(Vec<Witness>),
73}
74
75impl std::fmt::Display for BrilligOutputs {
76    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
77        match self {
78            BrilligOutputs::Simple(witness) => write!(f, "{witness}"),
79            BrilligOutputs::Array(witnesses) => {
80                let joined =
81                    witnesses.iter().map(|w| format!("{w}")).collect::<Vec<_>>().join(", ");
82                write!(f, "[{joined}]")
83            }
84        }
85    }
86}
87
88/// This is purely a wrapper struct around a list of Brillig opcode's which represents
89/// a full Brillig function to be executed by the Brillig VM.
90/// This is stored separately on a program and accessed through a [BrilligFunctionId].
91#[derive(Clone, PartialEq, Eq, Default, Debug, Hash)]
92#[derive(Serialize, Deserialize, MsgpackTagged)]
93#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
94#[tagged(allow_unknown_tags)]
95pub struct BrilligBytecode<F> {
96    #[serde(default)] // For backwards compatibility
97    #[tag(0)]
98    pub function_name: String,
99    #[tag(1)]
100    pub bytecode: Vec<BrilligOpcode<F>>,
101}
102
103/// Id for the function being called.
104/// Indexes into the table of Brillig function's specified in a [program][super::Program]
105#[derive(Clone, Debug, PartialEq, Eq, Hash, Copy, Default, PartialOrd, Ord)]
106#[derive(Serialize, Deserialize, MsgpackTagged)]
107#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
108#[serde(transparent)]
109pub struct BrilligFunctionId(pub u32);
110
111impl BrilligFunctionId {
112    pub fn as_usize(&self) -> usize {
113        self.0 as usize
114    }
115}
116
117impl std::fmt::Display for BrilligFunctionId {
118    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
119        write!(f, "{}", self.0)
120    }
121}
acir/circuit/brillig.rs

acir/circuit/
brillig.rs
