w3f_plonk_common/
domain.rs

1use crate::FieldColumn;
2use ark_ff::{batch_inversion, FftField, Zero};
3use ark_poly::univariate::DensePolynomial;
4use ark_poly::{
5    DenseUVPolynomial, EvaluationDomain, Evaluations, GeneralEvaluationDomain, Polynomial,
6};
7use ark_std::{vec, vec::Vec};
8use getrandom_or_panic::getrandom_or_panic;
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, padded_evals: Vec<F>, payload_len: usize) -> FieldColumn<F> {
29        debug_assert_eq!(padded_evals.len(), self.x1.size());
30        let evals = Evaluations::from_vec_and_domain(padded_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            poly,
35            evals,
36            evals_4x,
37            payload_len,
38        }
39    }
40
41    fn column_from_poly(&self, poly: DensePolynomial<F>) -> FieldColumn<F> {
42        debug_assert!(poly.degree() + 1 <= 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            poly,
48            evals,
49            evals_4x,
50            payload_len: self.x1.size(),
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 domain_size = domains.x1.size();
75        let domain_capacity = if hiding {
76            domain_size - ZK_ROWS
77        } else {
78            domain_size
79        };
80        let last_row_index = domain_capacity - 1;
81
82        let l_first = l_i(0, domain_size);
83        let l_first = domains.column_from_evals(l_first, 0);
84        let l_last = l_i(last_row_index, domain_size);
85        let l_last = domains.column_from_evals(l_last, 0);
86        let not_last_row = vanishes_on_row(last_row_index, domains.x1);
87        let not_last_row = domains.column_from_poly(not_last_row);
88
89        let zk_rows_vanishing_poly = hiding.then(|| vanishes_on_last_3_rows(domains.x1));
90
91        Self {
92            domains,
93            hiding,
94            capacity: domain_capacity,
95            not_last_row,
96            l_first,
97            l_last,
98            zk_rows_vanishing_poly,
99        }
100    }
101
102    pub(crate) fn divide_by_vanishing_poly(&self, poly: &DensePolynomial<F>) -> DensePolynomial<F> {
103        let (quotient, remainder) = if self.hiding {
104            let exclude_zk_rows = poly * self.zk_rows_vanishing_poly.as_ref().unwrap();
105            exclude_zk_rows.divide_by_vanishing_poly(self.domains.x1)
106        } else {
107            poly.divide_by_vanishing_poly(self.domains.x1)
108        };
109        assert!(remainder.is_zero()); //TODO error-handling
110        quotient
111    }
112
113    pub(crate) fn column(&self, mut values: Vec<F>, hidden: bool) -> FieldColumn<F> {
114        let payload_len = values.len();
115        debug_assert!(payload_len <= self.capacity);
116        values.resize(self.capacity, F::zero());
117        if self.hiding && hidden && !cfg!(feature = "test-vectors") {
118            values.resize_with(
119                self.domains.x1.size(),
120                || F::rand(&mut getrandom_or_panic()),
121            );
122        } else {
123            values.resize(self.domains.x1.size(), F::zero());
124        }
125        self.domains.column_from_evals(values, payload_len)
126    }
127
128    pub fn private_column(&self, values: Vec<F>) -> FieldColumn<F> {
129        self.column(values, true)
130    }
131
132    // public column
133    pub fn public_column(&self, evals: Vec<F>) -> FieldColumn<F> {
134        self.column(evals, false)
135    }
136
137    pub fn omega(&self) -> F {
138        self.domains.x1.group_gen()
139    }
140
141    pub fn domain(&self) -> GeneralEvaluationDomain<F> {
142        self.domains.x1
143    }
144
145    pub fn evaluate(&self, zeta: F) -> EvaluatedDomain<F> {
146        EvaluatedDomain::new(self.domain(), zeta, self.hiding)
147    }
148}
149
150fn l_i<F: FftField>(i: usize, n: usize) -> Vec<F> {
151    let mut l_i = vec![F::zero(); n];
152    l_i[i] = F::one();
153    l_i
154}
155
156// (x - w^i)
157fn vanishes_on_row<F: FftField>(
158    i: usize,
159    domain: GeneralEvaluationDomain<F>,
160) -> DensePolynomial<F> {
161    assert!(i < domain.size());
162    let w = domain.group_gen();
163    let wi = w.pow(&[i as u64]);
164    let wi = DensePolynomial::from_coefficients_slice(&[wi]);
165    let x = DensePolynomial::from_coefficients_slice(&[F::zero(), F::one()]);
166    &x - &wi
167}
168
169// (x - w^{n - 3}) * (x - w^{n - 2}) * (x - w^{n - 1})
170fn vanishes_on_last_3_rows<F: FftField>(domain: GeneralEvaluationDomain<F>) -> DensePolynomial<F> {
171    let w = domain.group_gen();
172    let n3 = (domain.size() - ZK_ROWS) as u64;
173    let w3 = w.pow(&[n3]);
174    let w2 = w3 * w;
175    let w1 = w2 * w;
176    assert_eq!(w1, domain.group_gen_inv());
177    let x = DensePolynomial::from_coefficients_slice(&[F::zero(), F::one()]); // X
178    let c = |a: F| DensePolynomial::from_coefficients_slice(&[a]);
179    &(&(&x - &c(w3)) * &(&x - &c(w2))) * &(&x - &c(w1))
180}
181
182pub struct EvaluatedDomain<F: FftField> {
183    pub domain: GeneralEvaluationDomain<F>,
184    pub not_last_row: F,
185    pub l_first: F,
186    pub l_last: F,
187    pub vanishing_polynomial_inv: F,
188}
189
190impl<F: FftField> EvaluatedDomain<F> {
191    pub fn new(domain: GeneralEvaluationDomain<F>, z: F, hiding: bool) -> Self {
192        let k = if hiding { ZK_ROWS } else { 0 };
193        let mut z_n = z; // z^n, n=2^d - domain size, so squarings only
194        for _ in 0..domain.log_size_of_group() {
195            z_n.square_in_place();
196        }
197        let z_n_minus_one = z_n - F::one(); // vanishing polynomial of the full domain
198
199        // w^{n-1}
200        let mut wi = domain.group_gen_inv();
201        // Vanishing polynomial of zk rows: prod = (z - w^{n-1})...(z - w^{n-k})
202        let mut prod = F::one();
203        for _ in 0..k {
204            prod *= z - wi;
205            wi *= domain.group_gen_inv();
206        }
207        // z - w^{n-(k+1)}}
208        let not_last_row = z - wi;
209
210        // w^{k+1}
211        let wj = domain.group_gen().pow([(k + 1) as u64]);
212
213        let mut inv = [z_n_minus_one, z - F::one(), wj * z - F::one()];
214        batch_inversion(&mut inv);
215
216        let vanishing_polynomial_inv = prod * inv[0];
217        let z_n_minus_one_div_n = z_n_minus_one * domain.size_inv();
218        let l_first = z_n_minus_one_div_n * inv[1];
219        let l_last = z_n_minus_one_div_n * inv[2];
220
221        Self {
222            domain,
223            not_last_row,
224            l_first,
225            l_last,
226            vanishing_polynomial_inv,
227        }
228    }
229
230    pub(crate) fn divide_by_vanishing_poly_in_zeta(&self, poly_in_zeta: F) -> F {
231        poly_in_zeta * self.vanishing_polynomial_inv
232    }
233
234    pub fn omega(&self) -> F {
235        self.domain.group_gen()
236    }
237}
238
239#[cfg(test)]
240mod tests {
241    use ark_ed_on_bls12_381_bandersnatch::Fq;
242    use ark_poly::Polynomial;
243    use ark_std::{test_rng, UniformRand};
244
245    use crate::domain::Domain;
246
247    fn _test_evaluated_domain(hiding: bool) {
248        let rng = &mut test_rng();
249
250        // let domain = GeneralEvaluationDomain::new(1024);
251        let n = 1024;
252        let domain = Domain::new(n, hiding);
253        let z = Fq::rand(rng);
254        let domain_eval = domain.evaluate(z);
255        assert_eq!(domain.l_first.poly.evaluate(&z), domain_eval.l_first);
256        assert_eq!(domain.l_last.poly.evaluate(&z), domain_eval.l_last);
257        assert_eq!(
258            domain.not_last_row.poly.evaluate(&z),
259            domain_eval.not_last_row
260        );
261    }
262
263    #[test]
264    fn test_evaluated_domain() {
265        _test_evaluated_domain(false);
266        _test_evaluated_domain(true);
267    }
268}
w3f_plonk_common/domain.rs

w3f_plonk_common/
domain.rs
