1// Copyright (c) 2022 Espresso Systems (espressosys.com)
 2// This file is part of the Jellyfish library.
 3
 4// You should have received a copy of the MIT License
 5// along with the Jellyfish library. If not, see <https://mit-license.org/>.
 6
 7//! Useful utilities for KZG PCS
 8use ark_ff::PrimeField;
 9use ark_poly::DenseMultilinearExtension;
10use ark_std::{end_timer, start_timer, vec::Vec};
11
12use crate::PCSError;
13
14/// Generate eq(t,x), a product of multilinear polynomials with fixed t.
15/// eq(a,b) is takes extensions of a,b in {0,1}^num_vars such that if a and b in
16/// {0,1}^num_vars are equal then this polynomial evaluates to 1.
17pub(crate) fn eq_extension<F: PrimeField>(t: &[F]) -> Vec<DenseMultilinearExtension<F>> {
18    let start = start_timer!(|| "eq extension");
19
20    let dim = t.len();
21    let mut result = Vec::new();
22    for (i, &ti) in t.iter().enumerate().take(dim) {
23        let mut poly = Vec::with_capacity(1 << dim);
24        for x in 0..(1 << dim) {
25            let xi = if x >> i & 1 == 1 { F::one() } else { F::zero() };
26            let ti_xi = ti * xi;
27            poly.push(ti_xi + ti_xi - xi - ti + F::one());
28        }
29        result.push(DenseMultilinearExtension::from_evaluations_vec(dim, poly));
30    }
31
32    end_timer!(start);
33    result
34}
35
36/// Evaluate eq polynomial. use the public one later
37pub(crate) fn eq_eval<F: PrimeField>(x: &[F], y: &[F]) -> Result<F, PCSError> {
38    if x.len() != y.len() {
39        return Err(PCSError::InvalidParameters(
40            "x and y have different length".to_string(),
41        ));
42    }
43    let start = start_timer!(|| "eq_eval");
44    let mut res = F::one();
45    for (&xi, &yi) in x.iter().zip(y.iter()) {
46        let xi_yi = xi * yi;
47        res *= xi_yi + xi_yi - xi - yi + F::one();
48    }
49    end_timer!(start);
50    Ok(res)
51}