hyperplonk/hyperplonk/src/utils.rs
hyperplonk/src/utils.rsRaw
1use crate::{
2 custom_gate::CustomizedGates, errors::HyperPlonkErrors, structs::HyperPlonkParams,
3 witness::WitnessColumn,
4};
5use arithmetic::{evaluate_opt, VirtualPolynomial};
6use ark_ec::PairingEngine;
7use ark_ff::PrimeField;
8use ark_poly::DenseMultilinearExtension;
9use std::{borrow::Borrow, rc::Rc};
10use subroutines::pcs::{prelude::Commitment, PolynomialCommitmentScheme};
11use transcript::IOPTranscript;
12
13/// An accumulator structure that holds a polynomial and
14/// its opening points
15#[derive(Debug)]
16pub(super) struct PcsAccumulator<E: PairingEngine, PCS: PolynomialCommitmentScheme<E>> {
17 // sequence:
18 // - prod(x) at 5 points
19 // - w_merged at perm check point
20 // - w_merged at zero check points (#witness points)
21 // - selector_merged at zero check points (#selector points)
22 // - w[0] at r_pi
23 pub(crate) num_var: usize,
24 pub(crate) polynomials: Vec<PCS::Polynomial>,
25 pub(crate) commitments: Vec<PCS::Commitment>,
26 pub(crate) points: Vec<PCS::Point>,
27 pub(crate) evals: Vec<PCS::Evaluation>,
28}
29
30impl<E, PCS> PcsAccumulator<E, PCS>
31where
32 E: PairingEngine,
33 PCS: PolynomialCommitmentScheme<
34 E,
35 Polynomial = Rc<DenseMultilinearExtension<E::Fr>>,
36 Point = Vec<E::Fr>,
37 Evaluation = E::Fr,
38 Commitment = Commitment<E>,
39 >,
40{
41 /// Create an empty accumulator.
42 pub(super) fn new(num_var: usize) -> Self {
43 Self {
44 num_var,
45 polynomials: vec![],
46 commitments: vec![],
47 points: vec![],
48 evals: vec![],
49 }
50 }
51
52 /// Push a new evaluation point into the accumulator
53 pub(super) fn insert_poly_and_points(
54 &mut self,
55 poly: &PCS::Polynomial,
56 commit: &PCS::Commitment,
57 point: &PCS::Point,
58 ) {
59 assert!(poly.num_vars == point.len());
60 assert!(poly.num_vars == self.num_var);
61
62 let eval = evaluate_opt(poly, point);
63
64 self.evals.push(eval);
65 self.polynomials.push(poly.clone());
66 self.points.push(point.clone());
67 self.commitments.push(*commit);
68 }
69
70 /// Batch open all the points over a merged polynomial.
71 /// A simple wrapper of PCS::multi_open
72 pub(super) fn multi_open(
73 &self,
74 prover_param: impl Borrow<PCS::ProverParam>,
75 transcript: &mut IOPTranscript<E::Fr>,
76 ) -> Result<PCS::BatchProof, HyperPlonkErrors> {
77 Ok(PCS::multi_open(
78 prover_param.borrow(),
79 self.polynomials.as_ref(),
80 self.points.as_ref(),
81 self.evals.as_ref(),
82 transcript,
83 )?)
84 }
85}
86
87/// Build MLE from matrix of witnesses.
88///
89/// Given a matrix := [row1, row2, ...] where
90/// row1:= (a1, a2, ...)
91/// row2:= (b1, b2, ...)
92/// row3:= (c1, c2, ...)
93///
94/// output mle(a1,b1,c1, ...), mle(a2,b2,c2, ...), ...
95#[macro_export]
96macro_rules! build_mle {
97 ($rows:expr) => {{
98 let mut res = Vec::with_capacity($rows.len());
99 let num_vars = log2($rows.len()) as usize;
100 let num_mles = $rows[0].0.len();
101
102 for i in 0..num_mles {
103 let mut cur_coeffs = Vec::new();
104 for row in $rows.iter() {
105 cur_coeffs.push(row.0[i])
106 }
107 res.push(Rc::new(DenseMultilinearExtension::from_evaluations_vec(
108 num_vars, cur_coeffs,
109 )))
110 }
111
112 Ok(res)
113 }};
114}
115
116/// Sanity-check for HyperPlonk SNARK proving
117pub(crate) fn prover_sanity_check<F: PrimeField>(
118 params: &HyperPlonkParams,
119 pub_input: &[F],
120 witnesses: &[WitnessColumn<F>],
121) -> Result<(), HyperPlonkErrors> {
122 // public input length must be no greater than num_constraints
123
124 if pub_input.len() > params.num_constraints {
125 return Err(HyperPlonkErrors::InvalidProver(format!(
126 "Public input length {} is greater than num constraits {}",
127 pub_input.len(),
128 params.num_pub_input
129 )));
130 }
131
132 // public input length
133 if pub_input.len() != params.num_pub_input {
134 return Err(HyperPlonkErrors::InvalidProver(format!(
135 "Public input length is not correct: got {}, expect {}",
136 pub_input.len(),
137 params.num_pub_input
138 )));
139 }
140 if !pub_input.len().is_power_of_two() {
141 return Err(HyperPlonkErrors::InvalidProver(format!(
142 "Public input length is not power of two: got {}",
143 pub_input.len(),
144 )));
145 }
146
147 // witnesses length
148 for (i, w) in witnesses.iter().enumerate() {
149 if w.0.len() != params.num_constraints {
150 return Err(HyperPlonkErrors::InvalidProver(format!(
151 "{}-th witness length is not correct: got {}, expect {}",
152 i,
153 w.0.len(),
154 params.num_constraints
155 )));
156 }
157 }
158 // check public input matches witness[0]'s first 2^ell elements
159 for (i, (&pi, &w)) in pub_input
160 .iter()
161 .zip(witnesses[0].0.iter().take(pub_input.len()))
162 .enumerate()
163 {
164 if pi != w {
165 return Err(HyperPlonkErrors::InvalidProver(format!(
166 "The {:?}-th public input {:?} does not match witness[0] {:?}",
167 i, pi, w
168 )));
169 }
170 }
171
172 Ok(())
173}
174
175/// build `f(w_0(x),...w_d(x))` where `f` is the constraint polynomial
176/// i.e., `f(a, b, c) = q_l a(x) + q_r b(x) + q_m a(x)b(x) - q_o c(x)` in
177/// vanilla plonk
178pub(crate) fn build_f<F: PrimeField>(
179 gates: &CustomizedGates,
180 num_vars: usize,
181 selector_mles: &[Rc<DenseMultilinearExtension<F>>],
182 witness_mles: &[Rc<DenseMultilinearExtension<F>>],
183) -> Result<VirtualPolynomial<F>, HyperPlonkErrors> {
184 // TODO: check that selector and witness lengths match what is in
185 // the gate definition
186
187 for selector_mle in selector_mles.iter() {
188 if selector_mle.num_vars != num_vars {
189 return Err(HyperPlonkErrors::InvalidParameters(format!(
190 "selector has different number of vars: {} vs {}",
191 selector_mle.num_vars, num_vars
192 )));
193 }
194 }
195
196 for witness_mle in witness_mles.iter() {
197 if witness_mle.num_vars != num_vars {
198 return Err(HyperPlonkErrors::InvalidParameters(format!(
199 "selector has different number of vars: {} vs {}",
200 witness_mle.num_vars, num_vars
201 )));
202 }
203 }
204
205 let mut res = VirtualPolynomial::<F>::new(num_vars);
206
207 for (coeff, selector, witnesses) in gates.gates.iter() {
208 let coeff_fr = if *coeff < 0 {
209 -F::from(-*coeff as u64)
210 } else {
211 F::from(*coeff as u64)
212 };
213 let mut mle_list = vec![];
214 if let Some(s) = *selector {
215 mle_list.push(selector_mles[s].clone())
216 }
217 for &witness in witnesses.iter() {
218 mle_list.push(witness_mles[witness].clone())
219 }
220 res.add_mle_list(mle_list, coeff_fr)?;
221 }
222
223 Ok(res)
224}
225
226pub(crate) fn eval_f<F: PrimeField>(
227 gates: &CustomizedGates,
228 selector_evals: &[F],
229 witness_evals: &[F],
230) -> Result<F, HyperPlonkErrors> {
231 let mut res = F::zero();
232 for (coeff, selector, witnesses) in gates.gates.iter() {
233 let mut cur_value = if *coeff < 0 {
234 -F::from(-*coeff as u64)
235 } else {
236 F::from(*coeff as u64)
237 };
238 cur_value *= match selector {
239 Some(s) => selector_evals[*s],
240 None => F::one(),
241 };
242 for &witness in witnesses.iter() {
243 cur_value *= witness_evals[witness]
244 }
245 res += cur_value;
246 }
247 Ok(res)
248}
249
250// check perm check subclaim:
251// proof.witness_perm_check_eval ?= perm_check_sub_claim.expected_eval
252// Q(x) := prod(x) - p1(x) * p2(x)
253// + alpha * frac(x) * g1(x) * ... * gk(x)
254// - alpha * f1(x) * ... * fk(x)
255//
256// where p1(x) = (1-x1) * frac(x2, ..., xn, 0)
257// + x1 * prod(x2, ..., xn, 0),
258// and p2(x) = (1-x1) * frac(x2, ..., xn, 1)
259// + x1 * prod(x2, ..., xn, 1)
260// and gi(x) = (wi(x) + beta * perms_i(x) + gamma)
261// and fi(x) = (wi(x) + beta * s_id_i(x) + gamma)
262#[allow(clippy::too_many_arguments)]
263pub(crate) fn eval_perm_gate<F: PrimeField>(
264 prod_evals: &[F],
265 frac_evals: &[F],
266 witness_perm_evals: &[F],
267 id_evals: &[F],
268 perm_evals: &[F],
269 alpha: F,
270 beta: F,
271 gamma: F,
272 x1: F,
273) -> Result<F, HyperPlonkErrors> {
274 let p1_eval = frac_evals[1] + x1 * (prod_evals[1] - frac_evals[1]);
275 let p2_eval = frac_evals[2] + x1 * (prod_evals[2] - frac_evals[2]);
276 let mut f_prod_eval = F::one();
277 for (&w_eval, &id_eval) in witness_perm_evals.iter().zip(id_evals.iter()) {
278 f_prod_eval *= w_eval + beta * id_eval + gamma;
279 }
280 let mut g_prod_eval = F::one();
281 for (&w_eval, &p_eval) in witness_perm_evals.iter().zip(perm_evals.iter()) {
282 g_prod_eval *= w_eval + beta * p_eval + gamma;
283 }
284 let res =
285 prod_evals[0] - p1_eval * p2_eval + alpha * (frac_evals[0] * g_prod_eval - f_prod_eval);
286 Ok(res)
287}
288
289#[cfg(test)]
290mod test {
291 use super::*;
292 use ark_bls12_381::Fr;
293 use ark_ff::PrimeField;
294 use ark_poly::MultilinearExtension;
295 #[test]
296 fn test_build_gate() -> Result<(), HyperPlonkErrors> {
297 test_build_gate_helper::<Fr>()
298 }
299
300 fn test_build_gate_helper<F: PrimeField>() -> Result<(), HyperPlonkErrors> {
301 let num_vars = 2;
302
303 // ql = 3x1x2 + 2x2 whose evaluations are
304 // 0, 0 |-> 0
305 // 0, 1 |-> 2
306 // 1, 0 |-> 0
307 // 1, 1 |-> 5
308 let ql_eval = vec![F::zero(), F::from(2u64), F::zero(), F::from(5u64)];
309 let ql = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, ql_eval));
310
311 // W1 = x1x2 + x1 whose evaluations are
312 // 0, 0 |-> 0
313 // 0, 1 |-> 0
314 // 1, 0 |-> 1
315 // 1, 1 |-> 2
316 let w_eval = vec![F::zero(), F::zero(), F::from(1u64), F::from(2u64)];
317 let w1 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
318
319 // W2 = x1 + x2 whose evaluations are
320 // 0, 0 |-> 0
321 // 0, 1 |-> 1
322 // 1, 0 |-> 1
323 // 1, 1 |-> 2
324 let w_eval = vec![F::zero(), F::one(), F::from(1u64), F::from(2u64)];
325 let w2 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
326
327 // Example:
328 // q_L(X) * W_1(X)^5 - W_2(X)
329 // is represented as
330 // vec![
331 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
332 // (-1, None, vec![id_W2])
333 // ]
334 let gates = CustomizedGates {
335 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
336 };
337 let f = build_f(&gates, num_vars, &[ql.clone()], &[w1.clone(), w2.clone()])?;
338
339 // Sanity check on build_f
340 // f(0, 0) = 0
341 assert_eq!(f.evaluate(&[F::zero(), F::zero()])?, F::zero());
342 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
343 assert_eq!(f.evaluate(&[F::zero(), F::one()])?, -F::one());
344 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
345 assert_eq!(f.evaluate(&[F::one(), F::zero()])?, -F::one());
346 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
347 assert_eq!(f.evaluate(&[F::one(), F::one()])?, F::from(158u64));
348
349 // test eval_f
350 {
351 let point = [F::zero(), F::zero()];
352 let selector_evals = ql.evaluate(&point).unwrap();
353 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
354 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
355 // f(0, 0) = 0
356 assert_eq!(eval_f, F::zero());
357 }
358 {
359 let point = [F::zero(), F::one()];
360 let selector_evals = ql.evaluate(&point).unwrap();
361 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
362 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
363 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
364 assert_eq!(eval_f, -F::one());
365 }
366 {
367 let point = [F::one(), F::zero()];
368 let selector_evals = ql.evaluate(&point).unwrap();
369 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
370 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
371 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
372 assert_eq!(eval_f, -F::one());
373 }
374 {
375 let point = [F::one(), F::one()];
376 let selector_evals = ql.evaluate(&point).unwrap();
377 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
378 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
379 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
380 assert_eq!(eval_f, F::from(158u64));
381 }
382 Ok(())
383 }
384}