fullcodec_plonk/proof_system/widget/permutation/
proverkey.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4//
5// Copyright (c) DUSK NETWORK. All rights reserved.
6
7use crate::fft::{EvaluationDomain, Evaluations, Polynomial};
8use crate::permutation::constants::{K1, K2, K3};
9use dusk_bls12_381::BlsScalar;
10
11#[derive(Debug, Eq, PartialEq, Clone)]
12pub(crate) struct ProverKey {
13    pub(crate) left_sigma: (Polynomial, Evaluations),
14    pub(crate) right_sigma: (Polynomial, Evaluations),
15    pub(crate) out_sigma: (Polynomial, Evaluations),
16    pub(crate) fourth_sigma: (Polynomial, Evaluations),
17    pub(crate) linear_evaluations: Evaluations,
18    /* Evaluations of f(x) = X
19     * [XXX: Remove this and
20     * benchmark if it makes a
21     * considerable difference
22     * -- These are just the
23     * domain elements] */
24}
25
26impl ProverKey {
27    pub(crate) fn compute_quotient_i(
28        &self,
29        index: usize,
30        w_l_i: &BlsScalar,
31        w_r_i: &BlsScalar,
32        w_o_i: &BlsScalar,
33        w_4_i: &BlsScalar,
34        z_i: &BlsScalar,
35        z_i_next: &BlsScalar,
36        alpha: &BlsScalar,
37        l1_alpha_sq: &BlsScalar,
38        beta: &BlsScalar,
39        gamma: &BlsScalar,
40    ) -> BlsScalar {
41        let a = self.compute_quotient_identity_range_check_i(
42            index, w_l_i, w_r_i, w_o_i, w_4_i, z_i, alpha, beta, gamma,
43        );
44        let b = self.compute_quotient_copy_range_check_i(
45            index, w_l_i, w_r_i, w_o_i, w_4_i, z_i_next, alpha, beta, gamma,
46        );
47        let c = self.compute_quotient_term_check_one_i(z_i, l1_alpha_sq);
48        a + b + c
49    }
50    // (a(x) + beta * X + gamma) (b(X) + beta * k1 * X + gamma) (c(X) + beta *
51    // k2 * X + gamma)(d(X) + beta * k3 * X + gamma)z(X) * alpha
52    fn compute_quotient_identity_range_check_i(
53        &self,
54        index: usize,
55        w_l_i: &BlsScalar,
56        w_r_i: &BlsScalar,
57        w_o_i: &BlsScalar,
58        w_4_i: &BlsScalar,
59        z_i: &BlsScalar,
60        alpha: &BlsScalar,
61        beta: &BlsScalar,
62        gamma: &BlsScalar,
63    ) -> BlsScalar {
64        let x = self.linear_evaluations[index];
65
66        (w_l_i + (beta * x) + gamma)
67            * (w_r_i + (beta * K1 * x) + gamma)
68            * (w_o_i + (beta * K2 * x) + gamma)
69            * (w_4_i + (beta * K3 * x) + gamma)
70            * z_i
71            * alpha
72    }
73    // (a(x) + beta* Sigma1(X) + gamma) (b(X) + beta * Sigma2(X) + gamma) (c(X)
74    // + beta * Sigma3(X) + gamma)(d(X) + beta * Sigma4(X) + gamma) Z(X.omega) *
75    // alpha
76    fn compute_quotient_copy_range_check_i(
77        &self,
78        index: usize,
79        w_l_i: &BlsScalar,
80        w_r_i: &BlsScalar,
81        w_o_i: &BlsScalar,
82        w_4_i: &BlsScalar,
83        z_i_next: &BlsScalar,
84        alpha: &BlsScalar,
85        beta: &BlsScalar,
86        gamma: &BlsScalar,
87    ) -> BlsScalar {
88        let left_sigma_eval = self.left_sigma.1[index];
89        let right_sigma_eval = self.right_sigma.1[index];
90        let out_sigma_eval = self.out_sigma.1[index];
91        let fourth_sigma_eval = self.fourth_sigma.1[index];
92
93        let product = (w_l_i + (beta * left_sigma_eval) + gamma)
94            * (w_r_i + (beta * right_sigma_eval) + gamma)
95            * (w_o_i + (beta * out_sigma_eval) + gamma)
96            * (w_4_i + (beta * fourth_sigma_eval) + gamma)
97            * z_i_next
98            * alpha;
99
100        -product
101    }
102    // L_1(X)[Z(X) - 1]
103    fn compute_quotient_term_check_one_i(
104        &self,
105        z_i: &BlsScalar,
106        l1_alpha_sq: &BlsScalar,
107    ) -> BlsScalar {
108        (z_i - BlsScalar::one()) * l1_alpha_sq
109    }
110
111    pub(crate) fn compute_linearisation(
112        &self,
113        z_challenge: &BlsScalar,
114        (alpha, beta, gamma): (&BlsScalar, &BlsScalar, &BlsScalar),
115        (a_eval, b_eval, c_eval, d_eval): (
116            &BlsScalar,
117            &BlsScalar,
118            &BlsScalar,
119            &BlsScalar,
120        ),
121        (sigma_1_eval, sigma_2_eval, sigma_3_eval): (
122            &BlsScalar,
123            &BlsScalar,
124            &BlsScalar,
125        ),
126        z_eval: &BlsScalar,
127        z_poly: &Polynomial,
128    ) -> Polynomial {
129        let a = self.compute_lineariser_identity_range_check(
130            (a_eval, b_eval, c_eval, d_eval),
131            z_challenge,
132            (alpha, beta, gamma),
133            z_poly,
134        );
135        let b = self.compute_lineariser_copy_range_check(
136            (a_eval, b_eval, c_eval),
137            z_eval,
138            sigma_1_eval,
139            sigma_2_eval,
140            sigma_3_eval,
141            (alpha, beta, gamma),
142            &self.fourth_sigma.0,
143        );
144
145        let domain = EvaluationDomain::new(z_poly.degree()).unwrap();
146        let c = self.compute_lineariser_check_is_one(
147            &domain,
148            z_challenge,
149            &alpha.square(),
150            z_poly,
151        );
152        &(&a + &b) + &c
153    }
154    // (a_eval + beta * z_challenge + gamma)(b_eval + beta * K1 * z_challenge +
155    // gamma)(c_eval + beta * K2 * z_challenge + gamma) * alpha z(X)
156    fn compute_lineariser_identity_range_check(
157        &self,
158        (a_eval, b_eval, c_eval, d_eval): (
159            &BlsScalar,
160            &BlsScalar,
161            &BlsScalar,
162            &BlsScalar,
163        ),
164        z_challenge: &BlsScalar,
165        (alpha, beta, gamma): (&BlsScalar, &BlsScalar, &BlsScalar),
166        z_poly: &Polynomial,
167    ) -> Polynomial {
168        let beta_z = beta * z_challenge;
169
170        // a_eval + beta * z_challenge + gamma
171        let mut a_0 = a_eval + beta_z;
172        a_0 += gamma;
173
174        // b_eval + beta * K1 * z_challenge + gamma
175        let beta_z_k1 = K1 * beta_z;
176        let mut a_1 = b_eval + beta_z_k1;
177        a_1 += gamma;
178
179        // c_eval + beta * K2 * z_challenge + gamma
180        let beta_z_k2 = K2 * beta_z;
181        let mut a_2 = c_eval + beta_z_k2;
182        a_2 += gamma;
183
184        // d_eval + beta * K3 * z_challenge + gamma
185        let beta_z_k3 = K3 * beta_z;
186        let mut a_3 = d_eval + beta_z_k3;
187        a_3 += gamma;
188
189        let mut a = a_0 * a_1;
190        a *= a_2;
191        a *= a_3;
192        a *= alpha; // (a_eval + beta * z_challenge + gamma)(b_eval + beta * K1 *
193                    // z_challenge + gamma)(c_eval + beta * K2 * z_challenge + gamma)(d_eval
194                    // + beta * K3 * z_challenge + gamma) * alpha
195        z_poly * &a // (a_eval + beta * z_challenge + gamma)(b_eval + beta * K1
196                    // * z_challenge + gamma)(c_eval + beta * K2 * z_challenge +
197                    // gamma) * alpha z(X)
198    }
199    // -(a_eval + beta * sigma_1 + gamma)(b_eval + beta * sigma_2 + gamma)
200    // (c_eval + beta * sigma_3 + gamma) * beta *z_eval * alpha^2 * Sigma_4(X)
201    fn compute_lineariser_copy_range_check(
202        &self,
203        (a_eval, b_eval, c_eval): (&BlsScalar, &BlsScalar, &BlsScalar),
204        z_eval: &BlsScalar,
205        sigma_1_eval: &BlsScalar,
206        sigma_2_eval: &BlsScalar,
207        sigma_3_eval: &BlsScalar,
208        (alpha, beta, gamma): (&BlsScalar, &BlsScalar, &BlsScalar),
209        fourth_sigma_poly: &Polynomial,
210    ) -> Polynomial {
211        // a_eval + beta * sigma_1 + gamma
212        let beta_sigma_1 = beta * sigma_1_eval;
213        let mut a_0 = a_eval + beta_sigma_1;
214        a_0 += gamma;
215
216        // b_eval + beta * sigma_2 + gamma
217        let beta_sigma_2 = beta * sigma_2_eval;
218        let mut a_1 = b_eval + beta_sigma_2;
219        a_1 += gamma;
220
221        // c_eval + beta * sigma_3 + gamma
222        let beta_sigma_3 = beta * sigma_3_eval;
223        let mut a_2 = c_eval + beta_sigma_3;
224        a_2 += gamma;
225
226        let beta_z_eval = beta * z_eval;
227
228        let mut a = a_0 * a_1 * a_2;
229        a *= beta_z_eval;
230        a *= alpha; // (a_eval + beta * sigma_1 + gamma)(b_eval + beta * sigma_2 +
231                    // gamma)(c_eval + beta * sigma_3 + gamma) * beta * z_eval * alpha
232
233        fourth_sigma_poly * &-a // -(a_eval + beta * sigma_1 + gamma)(b_eval +
234                                // beta * sigma_2 + gamma) (c_eval + beta *
235                                // sigma_3 + gamma) * beta * z_eval * alpha^2 *
236                                // Sigma_4(X)
237    }
238
239    fn compute_lineariser_check_is_one(
240        &self,
241        domain: &EvaluationDomain,
242        z_challenge: &BlsScalar,
243        alpha_sq: &BlsScalar,
244        z_coeffs: &Polynomial,
245    ) -> Polynomial {
246        // Evaluate l_1(z)
247        let l_1_z = domain.evaluate_all_lagrange_coefficients(*z_challenge)[0];
248
249        z_coeffs * &(l_1_z * alpha_sq)
250    }
251}
fullcodec_plonk/proof_system/widget/permutation/proverkey.rs

fullcodec_plonk/proof_system/widget/permutation/
proverkey.rs
