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> 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 is_one(&self) -> bool

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.

impl Expression<FieldElement>

pub fn from_str(src: &str) -> Result<Self, AcirParserErrorWithSource>

Creates a Expression object from the given string.

pub fn from_str_impl(src: &str) -> Result<Self, AcirParserErrorWithSource>

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: AcirField> 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 FromStr for Expression<FieldElement>

type Err = AcirParserErrorWithSource

The associated error which can be returned from parsing.

fn from_str(src: &str) -> Result<Self, Self::Err>

Parses a string s to return a value of this type.

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: 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: 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> 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>