hyperplonk/hyperplonk/src/utils.rs
hyperplonk/src/utils.rsRaw
1use std::rc::Rc;
2
3use arithmetic::VirtualPolynomial;
4use ark_ff::PrimeField;
5use ark_poly::DenseMultilinearExtension;
6
7use crate::{
8 errors::HyperPlonkErrors,
9 structs::{CustomizedGates, HyperPlonkParams},
10 witness::WitnessColumn,
11};
12
13use poly_iop::prelude::bit_decompose;
14
15/// Build MLE from matrix of witnesses.
16///
17/// Given a matrix := [row1, row2, ...] where
18/// row1:= (a1, a2, ...)
19/// row2:= (b1, b2, ...)
20/// row3:= (c1, c2, ...)
21///
22/// output mle(a1,b1,c1, ...), mle(a2,b2,c2, ...), ...
23#[macro_export]
24macro_rules! build_mle {
25 ($rows:expr) => {{
26 let mut res = Vec::with_capacity($rows.len());
27 let num_vars = log2($rows.len()) as usize;
28 let num_mles = $rows[0].0.len();
29
30 for i in 0..num_mles {
31 let mut cur_coeffs = Vec::new();
32 for row in $rows.iter() {
33 cur_coeffs.push(row.0[i])
34 }
35 res.push(Rc::new(DenseMultilinearExtension::from_evaluations_vec(
36 num_vars, cur_coeffs,
37 )))
38 }
39
40 Ok(res)
41 }};
42}
43
44/// Sanity-check for HyperPlonk SNARK proving
45pub(crate) fn prove_sanity_check<F: PrimeField>(
46 params: &HyperPlonkParams,
47 pub_input: &[F],
48 witnesses: &[WitnessColumn<F>],
49) -> Result<(), HyperPlonkErrors> {
50 let num_vars = params.nv;
51 let ell = params.log_pub_input_len;
52
53 // public input length
54 if pub_input.len() != 1 << ell {
55 return Err(HyperPlonkErrors::InvalidProver(format!(
56 "Public input length is not correct: got {}, expect {}",
57 pub_input.len(),
58 1 << ell
59 )));
60 }
61 // witnesses length
62 for (i, w) in witnesses.iter().enumerate() {
63 if w.0.len() != 1 << num_vars {
64 return Err(HyperPlonkErrors::InvalidProver(format!(
65 "{}-th witness length is not correct: got {}, expect {}",
66 i,
67 pub_input.len(),
68 1 << ell
69 )));
70 }
71 }
72 // check public input matches witness[0]'s first 2^ell elements
73 for (i, (&pi, &w)) in pub_input
74 .iter()
75 .zip(witnesses[0].0.iter().take(pub_input.len()))
76 .enumerate()
77 {
78 if pi != w {
79 return Err(HyperPlonkErrors::InvalidProver(format!(
80 "The {:?}-th public input {:?} does not match witness[0] {:?}",
81 i, pi, w
82 )));
83 }
84 }
85
86 Ok(())
87}
88
89/// build `f(w_0(x),...w_d(x))` where `f` is the constraint polynomial
90/// 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
91/// vanilla plonk
92pub(crate) fn build_f<F: PrimeField>(
93 gates: &CustomizedGates,
94 num_vars: usize,
95 selector_mles: &[Rc<DenseMultilinearExtension<F>>],
96 witness_mles: &[Rc<DenseMultilinearExtension<F>>],
97) -> Result<VirtualPolynomial<F>, HyperPlonkErrors> {
98 // TODO: check that selector and witness lengths match what is in
99 // the gate definition
100
101 for selector_mle in selector_mles.iter() {
102 if selector_mle.num_vars != num_vars {
103 return Err(HyperPlonkErrors::InvalidParameters(format!(
104 "selector has different number of vars: {} vs {}",
105 selector_mle.num_vars, num_vars
106 )));
107 }
108 }
109
110 for witness_mle in witness_mles.iter() {
111 if witness_mle.num_vars != num_vars {
112 return Err(HyperPlonkErrors::InvalidParameters(format!(
113 "selector has different number of vars: {} vs {}",
114 witness_mle.num_vars, num_vars
115 )));
116 }
117 }
118
119 let mut res = VirtualPolynomial::<F>::new(num_vars);
120
121 for (coeff, selector, witnesses) in gates.gates.iter() {
122 let coeff_fr = if *coeff < 0 {
123 -F::from(-*coeff as u64)
124 } else {
125 F::from(*coeff as u64)
126 };
127 let mut mle_list = vec![];
128 if let Some(s) = *selector {
129 mle_list.push(selector_mles[s].clone())
130 }
131 for &witness in witnesses.iter() {
132 mle_list.push(witness_mles[witness].clone())
133 }
134 res.add_mle_list(mle_list, coeff_fr)?;
135 }
136
137 Ok(res)
138}
139
140pub(crate) fn eval_f<F: PrimeField>(
141 gates: &CustomizedGates,
142 selector_evals: &[F],
143 witness_evals: &[F],
144) -> Result<F, HyperPlonkErrors> {
145 let mut res = F::zero();
146 for (coeff, selector, witnesses) in gates.gates.iter() {
147 let mut cur_value = if *coeff < 0 {
148 -F::from(-*coeff as u64)
149 } else {
150 F::from(*coeff as u64)
151 };
152 cur_value *= match selector {
153 Some(s) => selector_evals[*s],
154 None => F::one(),
155 };
156 for &witness in witnesses.iter() {
157 cur_value *= witness_evals[witness]
158 }
159 res += cur_value;
160 }
161 Ok(res)
162}
163
164/// given the evaluation input `point` of the `index`-th polynomial,
165/// obtain the evaluation point in the merged polynomial
166pub(crate) fn gen_eval_point<F: PrimeField>(index: usize, index_len: usize, point: &[F]) -> Vec<F> {
167 let mut index_vec: Vec<F> = bit_decompose(index as u64, index_len)
168 .into_iter()
169 .map(|x| F::from(x))
170 .collect();
171 index_vec.reverse();
172 [point, &index_vec].concat()
173}
174
175#[cfg(test)]
176mod test {
177 use super::*;
178 use ark_bls12_381::Fr;
179 use ark_ff::PrimeField;
180 use ark_poly::MultilinearExtension;
181 #[test]
182 fn test_build_gate() -> Result<(), HyperPlonkErrors> {
183 test_build_gate_helper::<Fr>()
184 }
185
186 fn test_build_gate_helper<F: PrimeField>() -> Result<(), HyperPlonkErrors> {
187 let num_vars = 2;
188
189 // ql = 3x1x2 + 2x2 whose evaluations are
190 // 0, 0 |-> 0
191 // 0, 1 |-> 2
192 // 1, 0 |-> 0
193 // 1, 1 |-> 5
194 let ql_eval = vec![F::zero(), F::from(2u64), F::zero(), F::from(5u64)];
195 let ql = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, ql_eval));
196
197 // W1 = x1x2 + x1 whose evaluations are
198 // 0, 0 |-> 0
199 // 0, 1 |-> 0
200 // 1, 0 |-> 1
201 // 1, 1 |-> 2
202 let w_eval = vec![F::zero(), F::zero(), F::from(1u64), F::from(2u64)];
203 let w1 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
204
205 // W2 = x1 + x2 whose evaluations are
206 // 0, 0 |-> 0
207 // 0, 1 |-> 1
208 // 1, 0 |-> 1
209 // 1, 1 |-> 2
210 let w_eval = vec![F::zero(), F::one(), F::from(1u64), F::from(2u64)];
211 let w2 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
212
213 // Example:
214 // q_L(X) * W_1(X)^5 - W_2(X)
215 // is represented as
216 // vec![
217 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
218 // (-1, None, vec![id_W2])
219 // ]
220 let gates = CustomizedGates {
221 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
222 };
223 let f = build_f(&gates, num_vars, &[ql.clone()], &[w1.clone(), w2.clone()])?;
224
225 // Sanity check on build_f
226 // f(0, 0) = 0
227 assert_eq!(f.evaluate(&[F::zero(), F::zero()])?, F::zero());
228 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
229 assert_eq!(f.evaluate(&[F::zero(), F::one()])?, -F::one());
230 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
231 assert_eq!(f.evaluate(&[F::one(), F::zero()])?, -F::one());
232 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
233 assert_eq!(f.evaluate(&[F::one(), F::one()])?, F::from(158u64));
234
235 // test eval_f
236 {
237 let point = [F::zero(), F::zero()];
238 let selector_evals = ql.evaluate(&point).unwrap();
239 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
240 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
241 // f(0, 0) = 0
242 assert_eq!(eval_f, F::zero());
243 }
244 {
245 let point = [F::zero(), F::one()];
246 let selector_evals = ql.evaluate(&point).unwrap();
247 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
248 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
249 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
250 assert_eq!(eval_f, -F::one());
251 }
252 {
253 let point = [F::one(), F::zero()];
254 let selector_evals = ql.evaluate(&point).unwrap();
255 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
256 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
257 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
258 assert_eq!(eval_f, -F::one());
259 }
260 {
261 let point = [F::one(), F::one()];
262 let selector_evals = ql.evaluate(&point).unwrap();
263 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
264 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
265 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
266 assert_eq!(eval_f, F::from(158u64));
267 }
268 Ok(())
269 }
270}