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
141fn l_i<F: FftField>(i: usize, n: usize) -> Vec<F> {
142    let mut l_i = vec![F::zero(); n];
143    l_i[i] = F::one();
144    l_i
145}
146
147// (x - w^i)
148fn vanishes_on_row<F: FftField>(
149    i: usize,
150    domain: GeneralEvaluationDomain<F>,
151) -> DensePolynomial<F> {
152    assert!(i < domain.size());
153    let w = domain.group_gen();
154    let wi = w.pow(&[i as u64]);
155    let wi = DensePolynomial::from_coefficients_slice(&[wi]);
156    let x = DensePolynomial::from_coefficients_slice(&[F::zero(), F::one()]);
157    &x - &wi
158}
159
160// (x - w^{n - 3}) * (x - w^{n - 2}) * (x - w^{n - 1})
161fn vanishes_on_last_3_rows<F: FftField>(domain: GeneralEvaluationDomain<F>) -> DensePolynomial<F> {
162    let w = domain.group_gen();
163    let n3 = (domain.size() - ZK_ROWS) as u64;
164    let w3 = w.pow(&[n3]);
165    let w2 = w3 * w;
166    let w1 = w2 * w;
167    assert_eq!(w1, domain.group_gen_inv());
168    let x = DensePolynomial::from_coefficients_slice(&[F::zero(), F::one()]); // X
169    let c = |a: F| DensePolynomial::from_coefficients_slice(&[a]);
170    &(&(&x - &c(w3)) * &(&x - &c(w2))) * &(&x - &c(w1))
171}
172
173pub struct EvaluatedDomain<F: FftField> {
174    pub domain: GeneralEvaluationDomain<F>,
175    pub not_last_row: F,
176    pub l_first: F,
177    pub l_last: F,
178    pub vanishing_polynomial_inv: F,
179}
180
181impl<F: FftField> EvaluatedDomain<F> {
182    pub fn new(domain: GeneralEvaluationDomain<F>, z: F, hiding: bool) -> Self {
183        let k = if hiding { ZK_ROWS } else { 0 };
184        let mut z_n = z; // z^n, n=2^d - domain size, so squarings only
185        for _ in 0..domain.log_size_of_group() {
186            z_n.square_in_place();
187        }
188        let z_n_minus_one = z_n - F::one(); // vanishing polynomial of the full domain
189
190        // w^{n-1}
191        let mut wi = domain.group_gen_inv();
192        // Vanishing polynomial of zk rows: prod = (z - w^{n-1})...(z - w^{n-k})
193        let mut prod = F::one();
194        for _ in 0..k {
195            prod *= z - wi;
196            wi *= domain.group_gen_inv();
197        }
198        // z - w^{n-(k+1)}}
199        let not_last_row = z - wi;
200
201        // w^{k+1}
202        let wj = domain.group_gen().pow([(k + 1) as u64]);
203
204        let mut inv = [z_n_minus_one, z - F::one(), wj * z - F::one()];
205        batch_inversion(&mut inv);
206
207        let vanishing_polynomial_inv = prod * inv[0];
208        let z_n_minus_one_div_n = z_n_minus_one * domain.size_inv();
209        let l_first = z_n_minus_one_div_n * inv[1];
210        let l_last = z_n_minus_one_div_n * inv[2];
211
212        Self {
213            domain,
214            not_last_row,
215            l_first,
216            l_last,
217            vanishing_polynomial_inv,
218        }
219    }
220
221    pub(crate) fn divide_by_vanishing_poly_in_zeta(&self, poly_in_zeta: F) -> F {
222        poly_in_zeta * self.vanishing_polynomial_inv
223    }
224
225    pub fn omega(&self) -> F {
226        self.domain.group_gen()
227    }
228}
229
230#[cfg(test)]
231mod tests {
232    use ark_ed_on_bls12_381_bandersnatch::Fq;
233    use ark_poly::Polynomial;
234    use ark_std::{test_rng, UniformRand};
235
236    use crate::domain::{Domain, EvaluatedDomain};
237
238    fn _test_evaluated_domain(hiding: bool) {
239        let rng = &mut test_rng();
240
241        // let domain = GeneralEvaluationDomain::new(1024);
242        let n = 1024;
243        let domain = Domain::new(n, hiding);
244        let z = Fq::rand(rng);
245        let domain_eval = EvaluatedDomain::new(domain.domain(), z, hiding);
246        assert_eq!(domain.l_first.poly.evaluate(&z), domain_eval.l_first);
247        assert_eq!(domain.l_last.poly.evaluate(&z), domain_eval.l_last);
248        assert_eq!(
249            domain.not_last_row.poly.evaluate(&z),
250            domain_eval.not_last_row
251        );
252    }
253
254    #[test]
255    fn test_evaluated_domain() {
256        _test_evaluated_domain(false);
257        _test_evaluated_domain(true);
258    }
259}
w3f_plonk_common/domain.rs

w3f_plonk_common/
domain.rs
