1// Copyright (c) 2023 Espresso Systems (espressosys.com)
 2// This file is part of the HyperPlonk library.
 3
 4// You should have received a copy of the MIT License
 5// along with the HyperPlonk library. If not, see <https://mit-license.org/>.
 6
 7//! This module implements useful functions for the permutation check protocol.
 8
 9use crate::poly_iop::errors::PolyIOPErrors;
10use arithmetic::identity_permutation_mles;
11use ark_ff::PrimeField;
12use ark_poly::DenseMultilinearExtension;
13use ark_std::{end_timer, start_timer};
14use std::sync::Arc;
15
16/// Returns the evaluations of two list of MLEs:
17/// - numerators = (a1, ..., ak)
18/// - denominators = (b1, ..., bk)
19///
20///  where
21///  - beta and gamma are challenges
22///  - (f1, ..., fk), (g1, ..., gk),
23///  - (s_id1, ..., s_idk), (perm1, ..., permk) are mle-s
24///
25/// - ai(x) is the MLE for `fi(x) + \beta s_id_i(x) + \gamma`
26/// - bi(x) is the MLE for `gi(x) + \beta perm_i(x) + \gamma`
27///
28/// The caller is responsible for sanity-check
29#[allow(clippy::type_complexity)]
30pub(super) fn computer_nums_and_denoms<F: PrimeField>(
31    beta: &F,
32    gamma: &F,
33    fxs: &[Arc<DenseMultilinearExtension<F>>],
34    gxs: &[Arc<DenseMultilinearExtension<F>>],
35    perms: &[Arc<DenseMultilinearExtension<F>>],
36) -> Result<
37    (
38        Vec<Arc<DenseMultilinearExtension<F>>>,
39        Vec<Arc<DenseMultilinearExtension<F>>>,
40    ),
41    PolyIOPErrors,
42> {
43    let start = start_timer!(|| "compute numerators and denominators");
44
45    let num_vars = fxs[0].num_vars;
46    let mut numerators = vec![];
47    let mut denominators = vec![];
48    let s_ids = identity_permutation_mles::<F>(num_vars, fxs.len());
49    for l in 0..fxs.len() {
50        let mut numerator_evals = vec![];
51        let mut denominator_evals = vec![];
52
53        for (&f_ev, (&g_ev, (&s_id_ev, &perm_ev))) in fxs[l]
54            .iter()
55            .zip(gxs[l].iter().zip(s_ids[l].iter().zip(perms[l].iter())))
56        {
57            let numerator = f_ev + *beta * s_id_ev + gamma;
58            let denominator = g_ev + *beta * perm_ev + gamma;
59
60            numerator_evals.push(numerator);
61            denominator_evals.push(denominator);
62        }
63        numerators.push(Arc::new(DenseMultilinearExtension::from_evaluations_vec(
64            num_vars,
65            numerator_evals,
66        )));
67        denominators.push(Arc::new(DenseMultilinearExtension::from_evaluations_vec(
68            num_vars,
69            denominator_evals,
70        )));
71    }
72
73    end_timer!(start);
74    Ok((numerators, denominators))
75}