w3f_plonk_common/
domain.rs

1use ark_ff::{batch_inversion, FftField, Zero};
2use ark_poly::univariate::DensePolynomial;
3use ark_poly::{
4    DenseUVPolynomial, EvaluationDomain, Evaluations, GeneralEvaluationDomain, Polynomial,
5};
6use ark_std::{vec, vec::Vec};
7
8use crate::FieldColumn;
9
10pub const ZK_ROWS: usize = 3;
11
12// Domains for performing calculations with constraint polynomials of degree up to 4.
13#[derive(Clone)]
14struct Domains<F: FftField> {
15    x1: GeneralEvaluationDomain<F>,
16    x4: GeneralEvaluationDomain<F>,
17}
18
19impl<F: FftField> Domains<F> {
20    fn new(n: usize) -> Self {
21        let x1 = GeneralEvaluationDomain::<F>::new(n)
22            .unwrap_or_else(|| panic!("No domain of size {}", n));
23        let x4 = GeneralEvaluationDomain::<F>::new(4 * n)
24            .unwrap_or_else(|| panic!("No domain of size {}", 4 * n));
25        Self { x1, x4 }
26    }
27
28    fn column_from_evals(&self, evals: Vec<F>, len: usize) -> FieldColumn<F> {
29        assert_eq!(evals.len(), self.x1.size());
30        let evals = Evaluations::from_vec_and_domain(evals, self.x1);
31        let poly = evals.interpolate_by_ref();
32        let evals_4x = poly.evaluate_over_domain_by_ref(self.x4);
33        FieldColumn {
34            len,
35            poly,
36            evals,
37            evals_4x,
38        }
39    }
40
41    fn column_from_poly(&self, poly: DensePolynomial<F>, len: usize) -> FieldColumn<F> {
42        assert!(poly.degree() < self.x1.size());
43        let evals_4x = self.amplify(&poly);
44        let evals = evals_4x.evals.iter().step_by(4).cloned().collect();
45        let evals = Evaluations::from_vec_and_domain(evals, self.x1);
46        FieldColumn {
47            len,
48            poly,
49            evals,
50            evals_4x,
51        }
52    }
53
54    // Amplifies the number of the evaluations of the polynomial so it can be multiplied in linear time.
55    fn amplify(&self, poly: &DensePolynomial<F>) -> Evaluations<F> {
56        poly.evaluate_over_domain_by_ref(self.x4)
57    }
58}
59
60#[derive(Clone)]
61pub struct Domain<F: FftField> {
62    domains: Domains<F>,
63    pub hiding: bool,
64    pub capacity: usize,
65    pub not_last_row: FieldColumn<F>,
66    pub l_first: FieldColumn<F>,
67    pub l_last: FieldColumn<F>,
68    zk_rows_vanishing_poly: Option<DensePolynomial<F>>,
69}
70
71impl<F: FftField> Domain<F> {
72    pub fn new(n: usize, hiding: bool) -> Self {
73        let domains = Domains::new(n);
74        let size = domains.x1.size();
75        let capacity = if hiding { size - ZK_ROWS } else { size };
76        let last_row_index = capacity - 1;
77
78        let l_first = l_i(0, size);
79        let l_first = domains.column_from_evals(l_first, capacity);
80        let l_last = l_i(last_row_index, size);
81        let l_last = domains.column_from_evals(l_last, capacity);
82        let not_last_row = vanishes_on_row(last_row_index, domains.x1);
83        let not_last_row = domains.column_from_poly(not_last_row, capacity);
84
85        let zk_rows_vanishing_poly = hiding.then(|| vanishes_on_last_3_rows(domains.x1));
86
87        Self {
88            domains,
89            hiding,
90            capacity,
91            not_last_row,
92            l_first,
93            l_last,
94            zk_rows_vanishing_poly,
95        }
96    }
97
98    pub(crate) fn divide_by_vanishing_poly(&self, poly: &DensePolynomial<F>) -> DensePolynomial<F> {
99        let (quotient, remainder) = if self.hiding {
100            let exclude_zk_rows = poly * self.zk_rows_vanishing_poly.as_ref().unwrap();
101            exclude_zk_rows.divide_by_vanishing_poly(self.domains.x1)
102        } else {
103            poly.divide_by_vanishing_poly(self.domains.x1)
104        };
105        assert!(remainder.is_zero()); //TODO error-handling
106        quotient
107    }
108
109    pub(crate) fn column(&self, mut evals: Vec<F>, hidden: bool) -> FieldColumn<F> {
110        let len = evals.len();
111        assert!(len <= self.capacity);
112        if self.hiding && hidden && !cfg!(feature = "test-vectors") {
113            evals.resize(self.capacity, F::zero());
114            evals.resize_with(self.domains.x1.size(), || {
115                F::rand(&mut getrandom_or_panic::getrandom_or_panic())
116            });
117        } else {
118            evals.resize(self.domains.x1.size(), F::zero());
119        }
120        self.domains.column_from_evals(evals, len)
121    }
122
123    pub fn private_column(&self, evals: Vec<F>) -> FieldColumn<F> {
124        self.column(evals, true)
125    }
126
127    // public column
128    pub fn public_column(&self, evals: Vec<F>) -> FieldColumn<F> {
129        self.column(evals, false)
130    }
131
132    pub fn omega(&self) -> F {
133        self.domains.x1.group_gen()
134    }
135
136    pub fn domain(&self) -> GeneralEvaluationDomain<F> {
137        self.domains.x1
138    }
139
140    pub fn evaluate(&self, zeta: F) -> EvaluatedDomain<F> {
141        EvaluatedDomain::new(self.domain(), zeta, self.hiding)
142    }
143}
144
145fn l_i<F: FftField>(i: usize, n: usize) -> Vec<F> {
146    let mut l_i = vec![F::zero(); n];
147    l_i[i] = F::one();
148    l_i
149}
150
151// (x - w^i)
152fn vanishes_on_row<F: FftField>(
153    i: usize,
154    domain: GeneralEvaluationDomain<F>,
155) -> DensePolynomial<F> {
156    assert!(i < domain.size());
157    let w = domain.group_gen();
158    let wi = w.pow(&[i as u64]);
159    let wi = DensePolynomial::from_coefficients_slice(&[wi]);
160    let x = DensePolynomial::from_coefficients_slice(&[F::zero(), F::one()]);
161    &x - &wi
162}
163
164// (x - w^{n - 3}) * (x - w^{n - 2}) * (x - w^{n - 1})
165fn vanishes_on_last_3_rows<F: FftField>(domain: GeneralEvaluationDomain<F>) -> DensePolynomial<F> {
166    let w = domain.group_gen();
167    let n3 = (domain.size() - ZK_ROWS) as u64;
168    let w3 = w.pow(&[n3]);
169    let w2 = w3 * w;
170    let w1 = w2 * w;
171    assert_eq!(w1, domain.group_gen_inv());
172    let x = DensePolynomial::from_coefficients_slice(&[F::zero(), F::one()]); // X
173    let c = |a: F| DensePolynomial::from_coefficients_slice(&[a]);
174    &(&(&x - &c(w3)) * &(&x - &c(w2))) * &(&x - &c(w1))
175}
176
177pub struct EvaluatedDomain<F: FftField> {
178    pub domain: GeneralEvaluationDomain<F>,
179    pub not_last_row: F,
180    pub l_first: F,
181    pub l_last: F,
182    pub vanishing_polynomial_inv: F,
183}
184
185impl<F: FftField> EvaluatedDomain<F> {
186    pub fn new(domain: GeneralEvaluationDomain<F>, z: F, hiding: bool) -> Self {
187        let k = if hiding { ZK_ROWS } else { 0 };
188        let mut z_n = z; // z^n, n=2^d - domain size, so squarings only
189        for _ in 0..domain.log_size_of_group() {
190            z_n.square_in_place();
191        }
192        let z_n_minus_one = z_n - F::one(); // vanishing polynomial of the full domain
193
194        // w^{n-1}
195        let mut wi = domain.group_gen_inv();
196        // Vanishing polynomial of zk rows: prod = (z - w^{n-1})...(z - w^{n-k})
197        let mut prod = F::one();
198        for _ in 0..k {
199            prod *= z - wi;
200            wi *= domain.group_gen_inv();
201        }
202        // z - w^{n-(k+1)}}
203        let not_last_row = z - wi;
204
205        // w^{k+1}
206        let wj = domain.group_gen().pow([(k + 1) as u64]);
207
208        let mut inv = [z_n_minus_one, z - F::one(), wj * z - F::one()];
209        batch_inversion(&mut inv);
210
211        let vanishing_polynomial_inv = prod * inv[0];
212        let z_n_minus_one_div_n = z_n_minus_one * domain.size_inv();
213        let l_first = z_n_minus_one_div_n * inv[1];
214        let l_last = z_n_minus_one_div_n * inv[2];
215
216        Self {
217            domain,
218            not_last_row,
219            l_first,
220            l_last,
221            vanishing_polynomial_inv,
222        }
223    }
224
225    pub(crate) fn divide_by_vanishing_poly_in_zeta(&self, poly_in_zeta: F) -> F {
226        poly_in_zeta * self.vanishing_polynomial_inv
227    }
228
229    pub fn omega(&self) -> F {
230        self.domain.group_gen()
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use ark_ed_on_bls12_381_bandersnatch::Fq;
237    use ark_poly::Polynomial;
238    use ark_std::{test_rng, UniformRand};
239
240    use crate::domain::Domain;
241
242    fn _test_evaluated_domain(hiding: bool) {
243        let rng = &mut test_rng();
244
245        // let domain = GeneralEvaluationDomain::new(1024);
246        let n = 1024;
247        let domain = Domain::new(n, hiding);
248        let z = Fq::rand(rng);
249        let domain_eval = domain.evaluate(z);
250        assert_eq!(domain.l_first.poly.evaluate(&z), domain_eval.l_first);
251        assert_eq!(domain.l_last.poly.evaluate(&z), domain_eval.l_last);
252        assert_eq!(
253            domain.not_last_row.poly.evaluate(&z),
254            domain_eval.not_last_row
255        );
256    }
257
258    #[test]
259    fn test_evaluated_domain() {
260        _test_evaluated_domain(false);
261        _test_evaluated_domain(true);
262    }
263}
w3f_plonk_common/domain.rs

w3f_plonk_common/
domain.rs
