sonobe-primitives 0.1.0-alpha.1

Cryptographic primitives, utilities, and abstractions for the Sonobe library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

//! This module provides helpers for working with polynomials inside circuits.

use ark_ff::{Field, PrimeField, Zero};
use ark_poly::{DenseMultilinearExtension, EvaluationDomain, GeneralEvaluationDomain};
use ark_r1cs_std::fields::{FieldVar, fp::FpVar};
use ark_relations::gr1cs::SynthesisError;
use ark_std::log2;

use super::pow::Pow;

/// [`MLEHelper`] provides functionality for multilinear extensions.
pub trait MLEHelper<F> {
    /// [`MLEHelper::from_evaluations`] builds a multilinear extension from a
    /// (possibly non-power-of-two) vector of evaluations, padding with zeros
    /// up to the next power of two.
    fn from_evaluations(evaluations: &[F]) -> Self;
}

impl<F: Field> MLEHelper<F> for DenseMultilinearExtension<F> {
    fn from_evaluations(evaluations: &[F]) -> Self {
        let l = evaluations.len();
        let pad = vec![Zero::zero(); l.next_power_of_two() - l];
        Self::from_evaluations_vec(log2(l) as usize, [evaluations, &pad].concat())
    }
}

/// [`EvaluationDomainGadget`] provides a subset of evaluation domain operations
/// in [`EvaluationDomain`] for in-circuit field variables.
pub trait EvaluationDomainGadget<F: PrimeField> {
    /// [`EvaluationDomainGadget::evaluate_all_lagrange_coefficients_var`]
    /// computes all Lagrange basis polynomials evaluated at `tau`.
    ///
    /// It is the in-circuit counterpart of [`EvaluationDomain::evaluate_all_lagrange_coefficients`].
    fn evaluate_all_lagrange_coefficients_var(
        &self,
        tau: &FpVar<F>,
    ) -> Result<Vec<FpVar<F>>, SynthesisError>;

    /// [`EvaluationDomainGadget::evaluate_vanishing_polynomial_var`] evaluates
    /// the vanishing polynomial of the domain at `tau`.
    ///
    /// It is the in-circuit counterpart of [`EvaluationDomain::evaluate_vanishing_polynomial`].
    fn evaluate_vanishing_polynomial_var(&self, tau: &FpVar<F>)
    -> Result<FpVar<F>, SynthesisError>;
}

impl<F: PrimeField> EvaluationDomainGadget<F> for GeneralEvaluationDomain<F> {
    fn evaluate_all_lagrange_coefficients_var(
        &self,
        tau: &FpVar<F>,
    ) -> Result<Vec<FpVar<F>>, SynthesisError> {
        let size = self.size() as u64;
        let size_inv = self.size_inv();
        let offset = self.coset_offset();
        let offset_inv = self.coset_offset_inv();
        let group_gen = self.group_gen();

        // We assume that the evaluation of vanishing polynomial at tau is non-0

        let l_i = (tau.pow_by_constant([size])? * offset_inv.pow([size - 1]) - offset) * size_inv;

        group_gen
            .powers(size as usize)
            .into_iter()
            .map(|g| (&l_i * g).mul_by_inverse(&(tau - offset * g)))
            .collect()
    }

    fn evaluate_vanishing_polynomial_var(
        &self,
        tau: &FpVar<F>,
    ) -> Result<FpVar<F>, SynthesisError> {
        Ok(tau.pow_by_constant([self.size() as u64])? - self.coset_offset_pow_size())
    }
}