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 based on known witness values in a single pass.

For expressions with 0 or 1 multiplication terms (the common case), this avoids allocating an intermediate Expression and eliminates redundant witness map lookups. Falls back to the general evaluate-based approach for 2+ mul terms or when linear term combining is needed.

fn verify_satisfied<F: AcirField>( sum: F, ) -> Result<(), OpcodeResolutionError<F>>

Verify that the fully-evaluated expression equals zero.

fn solve_single_unknown<F: AcirField>( sum: F, coeff: F, witness: Witness, initial_witness: &mut WitnessMap<F>, ) -> Result<(), OpcodeResolutionError<F>>

Solve sum + coeff * witness = 0 for the witness.

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

General solver that allocates an intermediate evaluated Expression. Used as a fallback when the single-pass approach cannot handle the expression (2+ mul terms, or linear terms that need combining).

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

Indicates the ‘solved’ status of the mul term, after partial evaluation.

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 fan_in_status<F: AcirField>( linear_combinations: &[(F, Witness)], ) -> OpcodeStatus<F>

Indicate the ‘solved’ status of the linear terms after partial evaluation.

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.