sonobe_primitives/algebra/ops/
poly.rs

1//! This module provides helpers for working with polynomials inside circuits.
2
3use ark_ff::{Field, PrimeField, Zero};
4use ark_poly::{DenseMultilinearExtension, EvaluationDomain, GeneralEvaluationDomain};
5use ark_r1cs_std::fields::{FieldVar, fp::FpVar};
6use ark_relations::gr1cs::SynthesisError;
7use ark_std::log2;
8
9use super::pow::Pow;
10
11/// [`MLEHelper`] provides functionality for multilinear extensions.
12pub trait MLEHelper<F> {
13    /// [`MLEHelper::from_evaluations`] builds a multilinear extension from a
14    /// (possibly non-power-of-two) vector of evaluations, padding with zeros
15    /// up to the next power of two.
16    fn from_evaluations(evaluations: &[F]) -> Self;
17}
18
19impl<F: Field> MLEHelper<F> for DenseMultilinearExtension<F> {
20    fn from_evaluations(evaluations: &[F]) -> Self {
21        let l = evaluations.len();
22        let pad = vec![Zero::zero(); l.next_power_of_two() - l];
23        Self::from_evaluations_vec(log2(l) as usize, [evaluations, &pad].concat())
24    }
25}
26
27/// [`EvaluationDomainGadget`] provides a subset of evaluation domain operations
28/// in [`EvaluationDomain`] for in-circuit field variables.
29pub trait EvaluationDomainGadget<F: PrimeField> {
30    /// [`EvaluationDomainGadget::evaluate_all_lagrange_coefficients_var`]
31    /// computes all Lagrange basis polynomials evaluated at `tau`.
32    ///
33    /// It is the in-circuit counterpart of [`EvaluationDomain::evaluate_all_lagrange_coefficients`].
34    fn evaluate_all_lagrange_coefficients_var(
35        &self,
36        tau: &FpVar<F>,
37    ) -> Result<Vec<FpVar<F>>, SynthesisError>;
38
39    /// [`EvaluationDomainGadget::evaluate_vanishing_polynomial_var`] evaluates
40    /// the vanishing polynomial of the domain at `tau`.
41    ///
42    /// It is the in-circuit counterpart of [`EvaluationDomain::evaluate_vanishing_polynomial`].
43    fn evaluate_vanishing_polynomial_var(&self, tau: &FpVar<F>)
44    -> Result<FpVar<F>, SynthesisError>;
45}
46
47impl<F: PrimeField> EvaluationDomainGadget<F> for GeneralEvaluationDomain<F> {
48    fn evaluate_all_lagrange_coefficients_var(
49        &self,
50        tau: &FpVar<F>,
51    ) -> Result<Vec<FpVar<F>>, SynthesisError> {
52        let size = self.size() as u64;
53        let size_inv = self.size_inv();
54        let offset = self.coset_offset();
55        let offset_inv = self.coset_offset_inv();
56        let group_gen = self.group_gen();
57
58        // We assume that the evaluation of vanishing polynomial at tau is non-0
59
60        let l_i = (tau.pow_by_constant([size])? * offset_inv.pow([size - 1]) - offset) * size_inv;
61
62        group_gen
63            .powers(size as usize)
64            .into_iter()
65            .map(|g| (&l_i * g).mul_by_inverse(&(tau - offset * g)))
66            .collect()
67    }
68
69    fn evaluate_vanishing_polynomial_var(
70        &self,
71        tau: &FpVar<F>,
72    ) -> Result<FpVar<F>, SynthesisError> {
73        Ok(tau.pow_by_constant([self.size() as u64])? - self.coset_offset_pow_size())
74    }
75}
sonobe_primitives/algebra/ops/poly.rs

sonobe_primitives/algebra/ops/
poly.rs
