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