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#[cfg(test)]
244mod test {
245 use super::*;
246 use ark_bls12_381::Fr;
247 use ark_ff::PrimeField;
248 use ark_poly::MultilinearExtension;
249 #[test]
250 fn test_build_gate() -> Result<(), HyperPlonkErrors> {
251 test_build_gate_helper::<Fr>()
252 }
253
254 fn test_build_gate_helper<F: PrimeField>() -> Result<(), HyperPlonkErrors> {
255 let num_vars = 2;
256
257 // ql = 3x1x2 + 2x2 whose evaluations are
258 // 0, 0 |-> 0
259 // 0, 1 |-> 2
260 // 1, 0 |-> 0
261 // 1, 1 |-> 5
262 let ql_eval = vec![F::zero(), F::from(2u64), F::zero(), F::from(5u64)];
263 let ql = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, ql_eval));
264
265 // W1 = x1x2 + x1 whose evaluations are
266 // 0, 0 |-> 0
267 // 0, 1 |-> 0
268 // 1, 0 |-> 1
269 // 1, 1 |-> 2
270 let w_eval = vec![F::zero(), F::zero(), F::from(1u64), F::from(2u64)];
271 let w1 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
272
273 // W2 = x1 + x2 whose evaluations are
274 // 0, 0 |-> 0
275 // 0, 1 |-> 1
276 // 1, 0 |-> 1
277 // 1, 1 |-> 2
278 let w_eval = vec![F::zero(), F::one(), F::from(1u64), F::from(2u64)];
279 let w2 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
280
281 // Example:
282 // q_L(X) * W_1(X)^5 - W_2(X)
283 // is represented as
284 // vec![
285 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
286 // (-1, None, vec![id_W2])
287 // ]
288 let gates = CustomizedGates {
289 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
290 };
291 let f = build_f(&gates, num_vars, &[ql.clone()], &[w1.clone(), w2.clone()])?;
292
293 // Sanity check on build_f
294 // f(0, 0) = 0
295 assert_eq!(f.evaluate(&[F::zero(), F::zero()])?, F::zero());
296 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
297 assert_eq!(f.evaluate(&[F::zero(), F::one()])?, -F::one());
298 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
299 assert_eq!(f.evaluate(&[F::one(), F::zero()])?, -F::one());
300 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
301 assert_eq!(f.evaluate(&[F::one(), F::one()])?, F::from(158u64));
302
303 // test eval_f
304 {
305 let point = [F::zero(), F::zero()];
306 let selector_evals = ql.evaluate(&point).unwrap();
307 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
308 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
309 // f(0, 0) = 0
310 assert_eq!(eval_f, F::zero());
311 }
312 {
313 let point = [F::zero(), F::one()];
314 let selector_evals = ql.evaluate(&point).unwrap();
315 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
316 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
317 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
318 assert_eq!(eval_f, -F::one());
319 }
320 {
321 let point = [F::one(), F::zero()];
322 let selector_evals = ql.evaluate(&point).unwrap();
323 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
324 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
325 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
326 assert_eq!(eval_f, -F::one());
327 }
328 {
329 let point = [F::one(), F::one()];
330 let selector_evals = ql.evaluate(&point).unwrap();
331 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
332 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
333 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
334 assert_eq!(eval_f, F::from(158u64));
335 }
336 Ok(())
337 }
338}