Struct ExpressionSolver

pub(crate) struct ExpressionSolver;

An Expression solver will take a Circuit’s assert-zero opcodes with witness assignments and create the other witness variables

Implementations

impl ExpressionSolver

pub(crate) fn solve<F: AcirField>( initial_witness: &mut WitnessMap<F>, opcode: &Expression<F>, ) -> Result<(), OpcodeResolutionError<F>>

Derives the rest of the witness in the provided expression based on the known witness values

1. First we simplify the expression based on the known values and try to reduce the multiplication and linear terms
2. If we end up with only the constant term;
   • if it is 0 then the opcode is solved, if not,
   • the assert_zero opcode is not satisfied and we return an error
3. If we end up with only linear terms on the same witness ‘w’, we can regroup them and solve ‘a*w+c = 0’:
   • If ‘a’ is zero in the above expression;
     • if c is also 0 then the opcode is solved
     • if not that means the assert_zero opcode is not satisfied and we return an error
   • If ‘a’ is not zero, we can solve it by setting the value of w: ‘w = -c/a’

fn solve_mul_term<F: AcirField>( mul_terms: &[(F, Witness, Witness)], witness_assignments: &WitnessMap<F>, ) -> Result<MulTerm<F>, OpcodeStatus<F>>

Try to reduce the multiplication terms of the given expression’s mul terms to a known value or to a linear term, using the provided witness mapping. If there are 2 or more multiplication terms it returns the OpcodeUnsolvable error. If no witnesses value is in the provided ‘witness_assignments’ map, it returns MulTerm::TooManyUnknowns

fn solve_mul_term_helper<F: AcirField>( term: &(F, Witness, Witness), witness_assignments: &WitnessMap<F>, ) -> MulTerm<F>

Try to solve a multiplication term of the form qab, where q is a constant and a,b are witnesses If both a and b have known values (in the provided map), it returns the value qab If only one of a or b has a known value, it returns the linear term c*w where c is a constant and w is the unknown witness If both a and b are unknown, it returns MulTerm::TooManyUnknowns

fn solve_fan_in_term_helper<F: AcirField>( term: &(F, Witness), witness_assignments: &WitnessMap<F>, ) -> Option<F>

Reduce a linear term to its value if the witness assignment is known If the witness value is not known in the provided map, it returns None.

pub(super) fn solve_fan_in_term<F: AcirField>( linear_combinations: &[(F, Witness)], witness_assignments: &WitnessMap<F>, ) -> OpcodeStatus<F>

Returns the summation of all of the variables, plus the unknown variable Returns OpcodeStatus::OpcodeUnsolvable, if there is more than one unknown variable

pub(crate) fn evaluate<F: AcirField>( expr: &Expression<F>, initial_witness: &WitnessMap<F>, ) -> Expression<F>

pub(crate) fn combine_linear_terms<F: AcirField>( linear_combinations: &[(F, Witness)], ) -> Vec<(F, Witness)>

Combines linear terms with the same witness by summing their coefficients. For example w1 + 2*w1 becomes 3*w1.

pub(crate) fn combine_mul_terms<F: AcirField>( mul_terms: &[(F, Witness, Witness)], ) -> Vec<(F, Witness, Witness)>

Combines multiplication terms with the same witnesses by summing their coefficients. For example w1*w2 + 2*w2*w1 becomes 3*w1*w2. If a coefficient ends up being zero, the term is removed.