kimchi/circuits/
domain_constant_evaluation.rs

1//! This contains the [DomainConstantEvaluations] which is used to provide precomputations to a [ConstraintSystem](super::constraints::ConstraintSystem).
2
3use crate::circuits::domains::EvaluationDomains;
4use alloc::{vec, vec::Vec};
5use ark_ff::FftField;
6use ark_poly::{
7    univariate::DensePolynomial as DP, EvaluationDomain, Evaluations as E, Polynomial,
8    Radix2EvaluationDomain as D,
9};
10#[cfg(feature = "parallel")]
11use rayon::prelude::*;
12use serde::{Deserialize, Serialize};
13use serde_with::serde_as;
14
15use super::polynomials::permutation::permutation_vanishing_polynomial;
16
17/// The points of `domain` (`g^0, g^1, …`), computed in parallel. Each chunk
18/// seeds its first power with a single exponentiation and then walks a running
19/// product, so the work is `O(n)` multiplications spread across the cores with
20/// only one `pow` per chunk of overhead. For domains smaller than the chunk
21/// size this is a single sequential chunk, so the parallelism never dominates.
22fn domain_points<F: FftField>(domain: D<F>) -> Vec<F> {
23    const CHUNK: usize = 1 << 14;
24    let gen = domain.group_gen;
25    let mut points = vec![F::one(); domain.size()];
26    o1_utils::cfg_chunks_mut!(points, CHUNK)
27        .enumerate()
28        .for_each(|(chunk_idx, chunk)| {
29            let mut x = gen.pow([(chunk_idx * CHUNK) as u64]);
30            for slot in chunk.iter_mut() {
31                *slot = x;
32                x *= gen;
33            }
34        });
35    points
36}
37
38/// Evaluate the polynomial `Π (x - root)` (given by its roots) at every point of
39/// `d8`, where `x_d8` holds the d8 domain points. For the low-degree vanishing
40/// polynomials this is far cheaper than padding to 8n coefficients and running
41/// an FFT, and it parallelises trivially over the points.
42fn eval_from_roots_over_d8<F: FftField>(x_d8: &[F], roots: &[F], d8: D<F>) -> E<F, D<F>> {
43    let evals: Vec<F> = o1_utils::cfg_iter!(x_d8)
44        .map(|z| roots.iter().map(|root| *z - *root).product())
45        .collect();
46    E::from_vec_and_domain(evals, d8)
47}
48
49#[serde_as]
50#[derive(Clone, Serialize, Deserialize, Debug)]
51/// pre-computed polynomials that depend only on the chosen field and domain
52pub struct DomainConstantEvaluations<F: FftField> {
53    /// the polynomial `x` evaluated over domain.d8 (i.e. the d8 domain points)
54    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
55    pub poly_x_d1: E<F, D<F>>,
56    /// the polynomial that vanishes on the zero-knowledge rows and the row before
57    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
58    pub vanishes_on_zero_knowledge_and_previous_rows: E<F, D<F>>,
59    /// zero-knowledge polynomial over domain.d8
60    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
61    pub permutation_vanishing_polynomial_l: E<F, D<F>>,
62    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
63    pub permutation_vanishing_polynomial_m: DP<F>,
64}
65
66impl<F: FftField> DomainConstantEvaluations<F> {
67    pub fn create(domain: EvaluationDomains<F>, zk_rows: u64) -> Option<Self> {
68        assert!(domain.d1.size > zk_rows);
69
70        let omega = domain.d1.group_gen;
71        let n = domain.d1.size;
72
73        // `x` over d8 is just the d8 domain points (g8^row); recover them from
74        // the domain rather than through an FFT.
75        let x_d8 = domain_points(domain.d8);
76
77        // Vanishes on the last (zk_rows + 1) rows: roots omega^{n-(zk_rows+1)} ..
78        // omega^{n-1}.
79        let zk_roots: Vec<F> = ((n - (zk_rows + 1))..n).map(|i| omega.pow([i])).collect();
80        let vanishes_on_zero_knowledge_and_previous_rows =
81            eval_from_roots_over_d8(&x_d8, &zk_roots, domain.d8);
82
83        // x^3 - x^2(w1+w2+w3) + x(w1w2+w1w3+w2w3) - w1w2w3, with the three roots
84        // omega^{n-zk_rows}, omega^{n-zk_rows+1}, omega^{n-1}.
85        let permutation_vanishing_polynomial_m =
86            permutation_vanishing_polynomial(domain.d1, zk_rows);
87        let permutation_vanishing_polynomial_l = {
88            let evals: Vec<F> = o1_utils::cfg_iter!(x_d8)
89                .map(|z| permutation_vanishing_polynomial_m.evaluate(z))
90                .collect();
91            E::from_vec_and_domain(evals, domain.d8)
92        };
93
94        let poly_x_d1 = E::from_vec_and_domain(x_d8, domain.d8);
95
96        Some(DomainConstantEvaluations {
97            poly_x_d1,
98            vanishes_on_zero_knowledge_and_previous_rows,
99            permutation_vanishing_polynomial_l,
100            permutation_vanishing_polynomial_m,
101        })
102    }
103}
kimchi/circuits/domain_constant_evaluation.rs

kimchi/circuits/
domain_constant_evaluation.rs
