hyperplonk/poly-iop/src/perm_check/mod.rs
poly-iop/src/perm_check/mod.rsRaw
1//! This module implements the permutation check protocol.
2
3use crate::{utils::get_index, PolyIOPErrors};
4use ark_ff::PrimeField;
5use ark_poly::DenseMultilinearExtension;
6use ark_std::{end_timer, start_timer};
7
8/// Compute `prod(0,x) := prod(0, x1, …, xn)` which is the MLE over the
9/// evaluations of the following polynomial on the boolean hypercube {0,1}^n:
10///
11/// (w(x) + \beta s_id(x) + \gamma)/(w(x) + \beta s_perm(x) + \gamma)
12///
13/// where
14/// - beta and gamma are challenges
15/// - w(x), s_id(x), s_perm(x) are mle-s
16///
17/// The caller needs to check num_vars matches in w/s_id/s_perm
18/// Cost: linear in N.
19#[allow(dead_code)]
20// TODO: remove
21fn compute_prod_0<F: PrimeField>(
22 beta: &F,
23 gamma: &F,
24 w: &DenseMultilinearExtension<F>,
25 s_id: &DenseMultilinearExtension<F>,
26 s_perm: &DenseMultilinearExtension<F>,
27) -> Result<DenseMultilinearExtension<F>, PolyIOPErrors> {
28 let start = start_timer!(|| "compute prod(1,x)");
29 let num_vars = w.num_vars;
30 let eval: Vec<F> = w
31 .iter()
32 .zip(s_id.iter().zip(s_perm.iter()))
33 .map(|(wi, (s_id_i, s_perm_i))| {
34 let tmp = *wi + *gamma;
35 (tmp + *beta * *s_id_i) / (tmp + *beta * *s_perm_i)
36 })
37 .collect();
38
39 let res = DenseMultilinearExtension::from_evaluations_vec(num_vars, eval);
40 end_timer!(start);
41 Ok(res)
42}
43
44/// Compute the following 5 polynomials
45/// - prod(x)
46/// - prod(0, x)
47/// - prod(1, x)
48/// - prod(x, 0)
49/// - prod(x, 1)
50///
51/// where
52/// - `prod(0,x) := prod(0, x0, x1, …, xn)` which is the MLE over the
53/// evaluations of the following polynomial on the boolean hypercube {0,1}^n:
54///
55/// (w(x) + \beta s_id(x) + \gamma)/(w(x) + \beta s_perm(x) + \gamma)
56///
57/// where
58/// - beta and gamma are challenges
59/// - w(x), s_id(x), s_perm(x) are mle-s
60///
61/// - `prod(1,x) := prod(x, 0) * prod(x, 1)`
62///
63/// Returns an error when the num_vars in w/s_id/s_perm does not match
64/// Cost: linear in N.
65#[allow(dead_code)]
66// TODO: remove
67fn compute_products<F: PrimeField>(
68 beta: &F,
69 gamma: &F,
70 w: &DenseMultilinearExtension<F>,
71 s_id: &DenseMultilinearExtension<F>,
72 s_perm: &DenseMultilinearExtension<F>,
73) -> Result<[DenseMultilinearExtension<F>; 5], PolyIOPErrors> {
74 let start = start_timer!(|| "compute all prod polynomial");
75
76 let num_vars = w.num_vars;
77
78 if num_vars != s_id.num_vars || num_vars != s_perm.num_vars {
79 return Err(PolyIOPErrors::InvalidParameters(
80 "num of variables do not match".to_string(),
81 ));
82 }
83 // ===================================
84 // prod(0, x)
85 // ===================================
86 let prod_0x = compute_prod_0(beta, gamma, w, s_id, s_perm)?;
87
88 // ===================================
89 // prod(1, x)
90 // ===================================
91 //
92 // `prod(1, x)` can be computed via recursing the following formula for 2^n-1
93 // times
94 //
95 // `prod(1, x_1, ..., x_n) :=
96 // prod(x_1, x_2, ..., x_n, 0) * prod(x_1, x_2, ..., x_n, 1)`
97 //
98 // At any given step, the right hand side of the equation
99 // is available via either eval_0x or the current view of eval_1x
100 let eval_0x = &prod_0x.evaluations;
101 let mut eval_1x = vec![];
102 for x in 0..(1 << num_vars) - 1 {
103 // sign will decide if the evaluation should be looked up from eval_0x or
104 // eval_1x; x_zero_index is the index for the evaluation (x_2, ..., x_n,
105 // 0); x_one_index is the index for the evaluation (x_2, ..., x_n, 1);
106 let (x_zero_index, x_one_index, sign) = get_index(x, num_vars);
107 if !sign {
108 eval_1x.push(eval_0x[x_zero_index] * eval_0x[x_one_index]);
109 } else {
110 // sanity check: if we are trying to look up from the eval_1x table,
111 // then the target index must already exist
112 if x_zero_index >= eval_1x.len() || x_one_index >= eval_1x.len() {
113 return Err(PolyIOPErrors::ShouldNotArrive);
114 }
115 eval_1x.push(eval_1x[x_zero_index] * eval_1x[x_one_index]);
116 }
117 }
118 // prod(1, 1, ..., 1) := 0
119 eval_1x.push(F::zero());
120
121 // ===================================
122 // prod(x)
123 // ===================================
124 // prod(x)'s evaluation is indeed `e := [eval_0x[..], eval_1x[..]].concat()`
125 let eval = [eval_0x.as_slice(), eval_1x.as_slice()].concat();
126
127 // ===================================
128 // prod(x, 0) and prod(x, 1)
129 // ===================================
130 //
131 // now we compute eval_x0 and eval_x1
132 // eval_0x will be the odd coefficients of eval
133 // and eval_1x will be the even coefficients of eval
134 let mut eval_x0 = vec![];
135 let mut eval_x1 = vec![];
136 for (x, &prod_x) in eval.iter().enumerate() {
137 if x & 1 == 0 {
138 eval_x0.push(prod_x);
139 } else {
140 eval_x1.push(prod_x);
141 }
142 }
143
144 let prod_1x = DenseMultilinearExtension::from_evaluations_vec(num_vars, eval_1x);
145 let prod_x0 = DenseMultilinearExtension::from_evaluations_vec(num_vars, eval_x0);
146 let prod_x1 = DenseMultilinearExtension::from_evaluations_vec(num_vars, eval_x1);
147 let prod = DenseMultilinearExtension::from_evaluations_vec(num_vars + 1, eval);
148
149 end_timer!(start);
150 Ok([prod, prod_0x, prod_1x, prod_x0, prod_x1])
151}
152
153#[cfg(test)]
154mod test {
155 use super::*;
156 use crate::utils::bit_decompose;
157 use ark_bls12_381::Fr;
158 use ark_ff::UniformRand;
159 use ark_poly::MultilinearExtension;
160 use ark_std::test_rng;
161
162 /// An MLE that represent an identity permutation: `f(index) \mapto index`
163 fn identity_permutation_mle<F: PrimeField>(num_vars: usize) -> DenseMultilinearExtension<F> {
164 let s_id_vec = (0..1u64 << num_vars).map(|index| F::from(index)).collect();
165 DenseMultilinearExtension::from_evaluations_vec(num_vars, s_id_vec)
166 }
167
168 #[test]
169 fn test_compute_prod_0() -> Result<(), PolyIOPErrors> {
170 let mut rng = test_rng();
171
172 for num_vars in 2..6 {
173 let w_vec: Vec<Fr> = (0..(1 << num_vars)).map(|_| Fr::rand(&mut rng)).collect();
174 let w = DenseMultilinearExtension::from_evaluations_vec(num_vars, w_vec);
175
176 let s_id = identity_permutation_mle::<Fr>(num_vars);
177
178 let s_perm_vec: Vec<Fr> = (0..(1 << num_vars)).map(|_| Fr::rand(&mut rng)).collect();
179 let s_perm = DenseMultilinearExtension::from_evaluations_vec(num_vars, s_perm_vec);
180
181 let beta = Fr::rand(&mut rng);
182 let gamma = Fr::rand(&mut rng);
183
184 let prod_0 = compute_prod_0(&beta, &gamma, &w, &s_id, &s_perm)?;
185
186 for i in 0..1 << num_vars {
187 let r: Vec<Fr> = bit_decompose(i, num_vars)
188 .iter()
189 .map(|&x| Fr::from(x))
190 .collect();
191
192 let eval = prod_0.evaluate(&r).unwrap();
193
194 let w_eval = w.evaluate(&r).unwrap();
195 let s_id_eval = s_id.evaluate(&r).unwrap();
196 let s_perm_eval = s_perm.evaluate(&r).unwrap();
197 let eval_rec =
198 (w_eval + beta * s_id_eval + gamma) / (w_eval + beta * s_perm_eval + gamma);
199
200 assert_eq!(eval, eval_rec);
201 }
202 }
203 Ok(())
204 }
205
206 #[test]
207 fn test_compute_prod() -> Result<(), PolyIOPErrors> {
208 let mut rng = test_rng();
209
210 for num_vars in 2..6 {
211 let w_vec: Vec<Fr> = (0..(1 << num_vars)).map(|_| Fr::rand(&mut rng)).collect();
212 let w = DenseMultilinearExtension::from_evaluations_vec(num_vars, w_vec);
213
214 let s_id = identity_permutation_mle::<Fr>(num_vars);
215
216 let s_perm_vec: Vec<Fr> = (0..(1 << num_vars)).map(|_| Fr::rand(&mut rng)).collect();
217 let s_perm = DenseMultilinearExtension::from_evaluations_vec(num_vars, s_perm_vec);
218
219 let beta = Fr::rand(&mut rng);
220 let gamma = Fr::rand(&mut rng);
221
222 // TODO: also test other 4 polynomials
223 let res = compute_products(&beta, &gamma, &w, &s_id, &s_perm)?;
224
225 for i in 0..1 << num_vars {
226 let r: Vec<Fr> = bit_decompose(i, num_vars)
227 .iter()
228 .map(|&x| Fr::from(x))
229 .collect();
230
231 let eval = res[1].evaluate(&r).unwrap();
232
233 let w_eval = w.evaluate(&r).unwrap();
234 let s_id_eval = s_id.evaluate(&r).unwrap();
235 let s_perm_eval = s_perm.evaluate(&r).unwrap();
236 let eval_rec =
237 (w_eval + beta * s_id_eval + gamma) / (w_eval + beta * s_perm_eval + gamma);
238
239 assert_eq!(eval, eval_rec);
240 }
241 }
242 Ok(())
243 }
244}