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