Struct Expression

pub struct Expression<F> {
    pub mul_terms: Vec<(F, Witness, Witness)>,
    pub linear_combinations: Vec<(F, Witness)>,
    pub q_c: F,
}

An expression representing a quadratic polynomial.

This struct is primarily used to express arithmetic relations between variables. It includes multiplication terms, linear combinations, and a constant term.

Addition polynomial

• Unlike standard plonk constraints with fixed wire assignments (wL, wR, wO), we allow arbitrary fan-in and fan-out. This means we need a more flexible representation and we need more than wL, wR, and wO.
• When looking at the quotient polynomial for the assert-zero opcode in standard plonk, you can interpret the structure in two ways:
  1. Fan-in 2 and fan-out 1
  2. Fan-in 1 and fan-out 2

Multiplication polynomial

• If we were allow the degree of the quotient polynomial to be arbitrary, then we will need a vector of wire values.

Fields

mul_terms: Vec<(F, Witness, Witness)>

Collection of multiplication terms.

To avoid having to create intermediate variables pre-optimization We collect all of the multiplication terms in the assert-zero opcode A multiplication term is of the form q_M * wL * wR Hence this vector represents the following sum: q_M1 * wL1 * wR1 + q_M2 * wL2 * wR2 + .. +

linear_combinations: Vec<(F, Witness)>

Collection of linear terms in the expression.

Each term follows the form: q_L * w, where q_L is a coefficient and w is a witness.

q_c: F

A constant term in the expression

Implementations

impl<F: Ord> Expression<F>

fn get_max_idx(&self) -> WitnessIdx

fn get_max_term(&self, idx: &mut WitnessIdx) -> Option<Witness>

Returns the maximum witness at the provided position, and decrement the position.

This function assumes the gate is sorted

fn cmp_max(m1: Option<Witness>, m2: Option<Witness>) -> Ordering

impl<F> Expression<F>

pub fn num_mul_terms(&self) -> usize

Returns the number of multiplication terms

pub fn push_addition_term(&mut self, coefficient: F, variable: Witness)

Adds a new linear term to the Expression.

pub fn push_multiplication_term( &mut self, coefficient: F, lhs: Witness, rhs: Witness, )

Adds a new quadratic term to the Expression.

pub fn is_const(&self) -> bool

Returns true if the expression represents a constant polynomial.

Examples:

• f(x,y) = x + y would return false
• f(x,y) = xy would return false, the degree here is 2
• f(x,y) = 5 would return true, the degree is 0

pub fn to_const(&self) -> Option<&F>

Returns a FieldElement if the expression represents a constant polynomial. Otherwise returns None.

Examples:

• f(x,y) = x would return None
• f(x,y) = x + 6 would return None
• f(x,y) = 2*y + 6 would return None
• f(x,y) = x + y would return None
• f(x,y) = 5 would return FieldElement(5)

pub fn is_linear(&self) -> bool

Returns true if highest degree term in the expression is one or less.

• mul_term in an expression contains degree-2 terms
• linear_combinations contains degree-1 terms

Hence, it is sufficient to check that there are no mul_terms

Examples:

• f(x,y) = x + y would return true
• f(x,y) = xy would return false, the degree here is 2
• f(x,y) = 0 would return true, the degree is 0

pub fn is_degree_one_univariate(&self) -> bool

Returns true if the expression can be seen as a degree-1 univariate polynomial

• mul_terms in an expression can be univariate, however unless the coefficient is zero, it is always degree-2.
• linear_combinations contains the sum of degree-1 terms, these terms do not need to contain the same variable and so it can be multivariate. However, we have thus far only checked if linear_combinations contains one term, so this method will return false, if the Expression has not been simplified.

Hence, we check in the simplest case if an expression is a degree-1 univariate, by checking if it contains no mul_terms and it contains one linear_combination term.

Examples:

• f(x,y) = x would return true
• f(x,y) = x + 6 would return true
• f(x,y) = 2*y + 6 would return true
• f(x,y) = x + y would return false
• f(x,y) = x + x should return true, but we return false *** (we do not simplify)
• f(x,y) = 5 would return false

pub fn sort(&mut self)

Sorts opcode in a deterministic order XXX: We can probably make this more efficient by sorting on each phase. We only care if it is deterministic

impl<F: AcirField> Expression<F>

pub fn from_field(q_c: F) -> Self

pub fn zero() -> Self

pub fn is_zero(&self) -> bool

pub fn one() -> Self

pub fn to_witness(&self) -> Option<Witness>

Returns a Witness if the Expression can be represented as a degree-1 univariate polynomial. Otherwise returns None.

Note that Witness is only capable of expressing polynomials of the form f(x) = x and not polynomials of the form f(x) = mx+c , so this method has extra checks to ensure that m=1 and c=0

pub fn add_mul(&self, k: F, b: &Self) -> Self

Returns self + k*b

pub fn width(&self) -> usize

Determine the width of this expression. The width meaning the number of unique witnesses needed for this expression.

Trait Implementations

impl<F: AcirField> Add<&Expression<F>> for &Expression<F>

type Output = Expression<F>

The resulting type after applying the + operator.

fn add(self, rhs: &Expression<F>) -> Self::Output

Performs the + operation.

impl<F: AcirField> Add<&Expression<F>> for Witness

type Output = Expression<F>

The resulting type after applying the + operator.

fn add(self, rhs: &Expression<F>) -> Self::Output

Performs the + operation.

impl<F: AcirField> Add<F> for Expression<F>

type Output = Expression<F>

The resulting type after applying the + operator.

fn add(self, rhs: F) -> Self::Output

Performs the + operation.

impl<F: AcirField> Add<Witness> for &Expression<F>

type Output = Expression<F>

The resulting type after applying the + operator.

fn add(self, rhs: Witness) -> Self::Output

Performs the + operation.

impl<F: Clone> Clone for Expression<F>

fn clone(&self) -> Expression<F>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F: Debug> Debug for Expression<F>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F: AcirField> Default for Expression<F>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, F> Deserialize<'de> for Expression<F>

where F: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<F: Display> Display for Expression<F>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F: AcirField> From<F> for Expression<F>

fn from(constant: F) -> Self

Converts to this type from the input type.

impl<F: AcirField> From<Witness> for Expression<F>

fn from(wit: Witness) -> Self

Creates an Expression from a Witness.

This is infallible since an Expression is a multi-variate polynomial and a Witness can be seen as a univariate polynomial

impl<F: Hash> Hash for Expression<F>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<F: AcirField> Mul<&Expression<F>> for &Expression<F>

type Output = Option<Expression<F>>

The resulting type after applying the * operator.

fn mul(self, rhs: &Expression<F>) -> Self::Output

Performs the * operation.

impl<F: AcirField> Mul<F> for &Expression<F>

type Output = Expression<F>

The resulting type after applying the * operator.

fn mul(self, rhs: F) -> Self::Output

Performs the * operation.

impl<F: AcirField> Neg for &Expression<F>

type Output = Expression<F>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<F: Ord> Ord for Expression<F>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<F: PartialEq> PartialEq for Expression<F>

fn eq(&self, other: &Expression<F>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<F: Ord> PartialOrd for Expression<F>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<F> ProtoCodec<Expression<F>, Expression> for ProtoSchema<F>

where F: AcirField,

fn encode(value: &Expression<F>) -> Expression

Convert domain type T to protobuf representation R.

fn decode(value: &Expression) -> Result<Expression<F>>

Try to convert protobuf representation R to domain type T.

fn encode_some(value: &T) -> Option<R>

Encode a field as Some.

fn encode_vec<'a, I>(values: I) -> Vec<R>

where I: IntoIterator<Item = &'a T>, T: 'a,

Encode multiple values as a vector.

fn decode_wrap(value: &R, msg: &'static str) -> Result<T, Report>

Decode a field and attach the name of the field if it fails.

fn decode_vec(values: &[R]) -> Result<Vec<T>, Report>

Decode multiple values into a vector.

fn decode_vec_wrap(values: &[R], msg: &'static str) -> Result<Vec<T>, Report>

Decode multiple values into a vector, attaching a field name to any errors.

fn decode_arr<const N: usize>(values: &[R]) -> Result<[T; N], Report>

Decode a fixed size array.

fn decode_arr_wrap<const N: usize>( values: &[R], msg: &'static str, ) -> Result<[T; N], Report>

Decode a fixed size array, attaching a field name to any errors

fn decode_box_arr<const N: usize>(values: &[R]) -> Result<Box<[T; N]>, Report>

Decode a boxed fixed size array.

fn decode_box_arr_wrap<const N: usize>( values: &[R], msg: &'static str, ) -> Result<Box<[T; N]>, Report>

Decode a boxed fixed size array, attaching a field name to any errors

fn decode_some(value: &Option<R>) -> Result<T, Report>

Decode an optional field as a required one; fails if it’s None.

fn decode_some_wrap(value: &Option<R>, msg: &'static str) -> Result<T, Report>

Decode an optional field as a required one, attaching a field name to any errors. Returns error if the field is missing.

fn decode_opt_wrap( value: &Option<R>, msg: &'static str, ) -> Result<Option<T>, Report>

Decode an optional field, attaching a field name to any errors. Return None if the field is missing.

fn serialize_to_vec(value: &T) -> Vec<u8>

where R: Message,

Encode a domain type to protobuf and serialize it to bytes.

fn deserialize_from_slice(buf: &[u8]) -> Result<T, Report>

where R: Message + Default,

Deserialize a buffer into protobuf and then decode into the domain type.

impl<F> Serialize for Expression<F>

where F: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<F: AcirField> Sub<&Expression<F>> for &Expression<F>

type Output = Expression<F>

The resulting type after applying the - operator.

fn sub(self, rhs: &Expression<F>) -> Self::Output

Performs the - operation.

impl<F: AcirField> Sub<&Expression<F>> for Witness

type Output = Expression<F>

The resulting type after applying the - operator.

fn sub(self, rhs: &Expression<F>) -> Self::Output

Performs the - operation.

impl<F: AcirField> Sub<F> for Expression<F>

type Output = Expression<F>

The resulting type after applying the - operator.

fn sub(self, rhs: F) -> Self::Output

Performs the - operation.

impl<F: AcirField> Sub<Witness> for &Expression<F>

type Output = Expression<F>

The resulting type after applying the - operator.

fn sub(self, rhs: Witness) -> Self::Output

Performs the - operation.

impl<F: Eq> Eq for Expression<F>

impl<F> StructuralPartialEq for Expression<F>