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 // witnesses length
141 for (i, w) in witnesses.iter().enumerate() {
142 if w.0.len() != params.num_constraints {
143 return Err(HyperPlonkErrors::InvalidProver(format!(
144 "{}-th witness length is not correct: got {}, expect {}",
145 i,
146 w.0.len(),
147 params.num_constraints
148 )));
149 }
150 }
151 // check public input matches witness[0]'s first 2^ell elements
152 for (i, (&pi, &w)) in pub_input
153 .iter()
154 .zip(witnesses[0].0.iter().take(pub_input.len()))
155 .enumerate()
156 {
157 if pi != w {
158 return Err(HyperPlonkErrors::InvalidProver(format!(
159 "The {:?}-th public input {:?} does not match witness[0] {:?}",
160 i, pi, w
161 )));
162 }
163 }
164
165 Ok(())
166}
167
168/// build `f(w_0(x),...w_d(x))` where `f` is the constraint polynomial
169/// 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
170/// vanilla plonk
171pub(crate) fn build_f<F: PrimeField>(
172 gates: &CustomizedGates,
173 num_vars: usize,
174 selector_mles: &[Rc<DenseMultilinearExtension<F>>],
175 witness_mles: &[Rc<DenseMultilinearExtension<F>>],
176) -> Result<VirtualPolynomial<F>, HyperPlonkErrors> {
177 // TODO: check that selector and witness lengths match what is in
178 // the gate definition
179
180 for selector_mle in selector_mles.iter() {
181 if selector_mle.num_vars != num_vars {
182 return Err(HyperPlonkErrors::InvalidParameters(format!(
183 "selector has different number of vars: {} vs {}",
184 selector_mle.num_vars, num_vars
185 )));
186 }
187 }
188
189 for witness_mle in witness_mles.iter() {
190 if witness_mle.num_vars != num_vars {
191 return Err(HyperPlonkErrors::InvalidParameters(format!(
192 "selector has different number of vars: {} vs {}",
193 witness_mle.num_vars, num_vars
194 )));
195 }
196 }
197
198 let mut res = VirtualPolynomial::<F>::new(num_vars);
199
200 for (coeff, selector, witnesses) in gates.gates.iter() {
201 let coeff_fr = if *coeff < 0 {
202 -F::from(-*coeff as u64)
203 } else {
204 F::from(*coeff as u64)
205 };
206 let mut mle_list = vec![];
207 if let Some(s) = *selector {
208 mle_list.push(selector_mles[s].clone())
209 }
210 for &witness in witnesses.iter() {
211 mle_list.push(witness_mles[witness].clone())
212 }
213 res.add_mle_list(mle_list, coeff_fr)?;
214 }
215
216 Ok(res)
217}
218
219pub(crate) fn eval_f<F: PrimeField>(
220 gates: &CustomizedGates,
221 selector_evals: &[F],
222 witness_evals: &[F],
223) -> Result<F, HyperPlonkErrors> {
224 let mut res = F::zero();
225 for (coeff, selector, witnesses) in gates.gates.iter() {
226 let mut cur_value = if *coeff < 0 {
227 -F::from(-*coeff as u64)
228 } else {
229 F::from(*coeff as u64)
230 };
231 cur_value *= match selector {
232 Some(s) => selector_evals[*s],
233 None => F::one(),
234 };
235 for &witness in witnesses.iter() {
236 cur_value *= witness_evals[witness]
237 }
238 res += cur_value;
239 }
240 Ok(res)
241}
242
243// check perm check subclaim:
244// proof.witness_perm_check_eval ?= perm_check_sub_claim.expected_eval
245// Q(x) := prod(x) - p1(x) * p2(x)
246// + alpha * frac(x) * g1(x) * ... * gk(x)
247// - alpha * f1(x) * ... * fk(x)
248//
249// where p1(x) = (1-x1) * frac(x2, ..., xn, 0)
250// + x1 * prod(x2, ..., xn, 0),
251// and p2(x) = (1-x1) * frac(x2, ..., xn, 1)
252// + x1 * prod(x2, ..., xn, 1)
253// and gi(x) = (wi(x) + beta * perms_i(x) + gamma)
254// and fi(x) = (wi(x) + beta * s_id_i(x) + gamma)
255#[allow(clippy::too_many_arguments)]
256pub(crate) fn eval_perm_gate<F: PrimeField>(
257 prod_evals: &[F],
258 frac_evals: &[F],
259 witness_perm_evals: &[F],
260 id_evals: &[F],
261 perm_evals: &[F],
262 alpha: F,
263 beta: F,
264 gamma: F,
265 x1: F,
266) -> Result<F, HyperPlonkErrors> {
267 let p1_eval = frac_evals[1] + x1 * (prod_evals[1] - frac_evals[1]);
268 let p2_eval = frac_evals[2] + x1 * (prod_evals[2] - frac_evals[2]);
269 let mut f_prod_eval = F::one();
270 for (&w_eval, &id_eval) in witness_perm_evals.iter().zip(id_evals.iter()) {
271 f_prod_eval *= w_eval + beta * id_eval + gamma;
272 }
273 let mut g_prod_eval = F::one();
274 for (&w_eval, &p_eval) in witness_perm_evals.iter().zip(perm_evals.iter()) {
275 g_prod_eval *= w_eval + beta * p_eval + gamma;
276 }
277 let res =
278 prod_evals[0] - p1_eval * p2_eval + alpha * (frac_evals[0] * g_prod_eval - f_prod_eval);
279 Ok(res)
280}
281
282#[cfg(test)]
283mod test {
284 use super::*;
285 use ark_bls12_381::Fr;
286 use ark_ff::PrimeField;
287 use ark_poly::MultilinearExtension;
288 #[test]
289 fn test_build_gate() -> Result<(), HyperPlonkErrors> {
290 test_build_gate_helper::<Fr>()
291 }
292
293 fn test_build_gate_helper<F: PrimeField>() -> Result<(), HyperPlonkErrors> {
294 let num_vars = 2;
295
296 // ql = 3x1x2 + 2x2 whose evaluations are
297 // 0, 0 |-> 0
298 // 0, 1 |-> 2
299 // 1, 0 |-> 0
300 // 1, 1 |-> 5
301 let ql_eval = vec![F::zero(), F::from(2u64), F::zero(), F::from(5u64)];
302 let ql = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, ql_eval));
303
304 // W1 = x1x2 + x1 whose evaluations are
305 // 0, 0 |-> 0
306 // 0, 1 |-> 0
307 // 1, 0 |-> 1
308 // 1, 1 |-> 2
309 let w_eval = vec![F::zero(), F::zero(), F::from(1u64), F::from(2u64)];
310 let w1 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
311
312 // W2 = x1 + x2 whose evaluations are
313 // 0, 0 |-> 0
314 // 0, 1 |-> 1
315 // 1, 0 |-> 1
316 // 1, 1 |-> 2
317 let w_eval = vec![F::zero(), F::one(), F::from(1u64), F::from(2u64)];
318 let w2 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
319
320 // Example:
321 // q_L(X) * W_1(X)^5 - W_2(X)
322 // is represented as
323 // vec![
324 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
325 // (-1, None, vec![id_W2])
326 // ]
327 let gates = CustomizedGates {
328 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
329 };
330 let f = build_f(&gates, num_vars, &[ql.clone()], &[w1.clone(), w2.clone()])?;
331
332 // Sanity check on build_f
333 // f(0, 0) = 0
334 assert_eq!(f.evaluate(&[F::zero(), F::zero()])?, F::zero());
335 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
336 assert_eq!(f.evaluate(&[F::zero(), F::one()])?, -F::one());
337 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
338 assert_eq!(f.evaluate(&[F::one(), F::zero()])?, -F::one());
339 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
340 assert_eq!(f.evaluate(&[F::one(), F::one()])?, F::from(158u64));
341
342 // test eval_f
343 {
344 let point = [F::zero(), F::zero()];
345 let selector_evals = ql.evaluate(&point).unwrap();
346 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
347 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
348 // f(0, 0) = 0
349 assert_eq!(eval_f, F::zero());
350 }
351 {
352 let point = [F::zero(), F::one()];
353 let selector_evals = ql.evaluate(&point).unwrap();
354 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
355 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
356 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
357 assert_eq!(eval_f, -F::one());
358 }
359 {
360 let point = [F::one(), F::zero()];
361 let selector_evals = ql.evaluate(&point).unwrap();
362 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
363 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
364 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
365 assert_eq!(eval_f, -F::one());
366 }
367 {
368 let point = [F::one(), F::one()];
369 let selector_evals = ql.evaluate(&point).unwrap();
370 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
371 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
372 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
373 assert_eq!(eval_f, F::from(158u64));
374 }
375 Ok(())
376 }
377}