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::{errors::HyperPlonkErrors, structs::CustomizedGates};
8
9/// Build MLE from matrix of witnesses.
10///
11/// Given a matrix := [row1, row2, ...] where
12/// row1:= (a1, a2, ...)
13/// row2:= (b1, b2, ...)
14/// row3:= (c1, c2, ...)
15///
16/// output mle(a1,b1,c1, ...), mle(a2,b2,c2, ...), ...
17#[macro_export]
18macro_rules! build_mle {
19 ($rows:expr) => {{
20 let mut res = Vec::with_capacity($rows.len());
21 let num_vars = log2($rows.len()) as usize;
22 let num_mles = $rows[0].0.len();
23
24 for i in 0..num_mles {
25 let mut cur_coeffs = Vec::new();
26 for row in $rows.iter() {
27 cur_coeffs.push(row.0[i])
28 }
29 res.push(Rc::new(DenseMultilinearExtension::from_evaluations_vec(
30 num_vars, cur_coeffs,
31 )))
32 }
33
34 Ok(res)
35 }};
36}
37
38/// build `f(w_0(x),...w_d(x))` where `f` is the constraint polynomial
39/// 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
40/// vanilla plonk
41pub(crate) fn build_f<F: PrimeField>(
42 gates: &CustomizedGates,
43 num_vars: usize,
44 selector_mles: &[Rc<DenseMultilinearExtension<F>>],
45 witness_mles: &[Rc<DenseMultilinearExtension<F>>],
46) -> Result<VirtualPolynomial<F>, HyperPlonkErrors> {
47 // TODO: check that selector and witness lengths match what is in
48 // the gate definition
49
50 for selector_mle in selector_mles.iter() {
51 if selector_mle.num_vars != num_vars {
52 return Err(HyperPlonkErrors::InvalidParameters(format!(
53 "selector has different number of vars: {} vs {}",
54 selector_mle.num_vars, num_vars
55 )));
56 }
57 }
58
59 for witness_mle in witness_mles.iter() {
60 if witness_mle.num_vars != num_vars {
61 return Err(HyperPlonkErrors::InvalidParameters(format!(
62 "selector has different number of vars: {} vs {}",
63 witness_mle.num_vars, num_vars
64 )));
65 }
66 }
67
68 let mut res = VirtualPolynomial::<F>::new(num_vars);
69
70 for (coeff, selector, witnesses) in gates.gates.iter() {
71 let coeff_fr = if *coeff < 0 {
72 -F::from(-*coeff as u64)
73 } else {
74 F::from(*coeff as u64)
75 };
76 let mut mle_list = vec![];
77 match *selector {
78 Some(s) => mle_list.push(selector_mles[s].clone()),
79 None => (),
80 };
81 for &witness in witnesses.iter() {
82 mle_list.push(witness_mles[witness].clone())
83 }
84 res.add_mle_list(mle_list, coeff_fr)?;
85 }
86
87 Ok(res)
88}
89
90#[allow(dead_code)]
91pub(crate) fn eval_f<F: PrimeField>(
92 gates: &CustomizedGates,
93 selector_evals: &[F],
94 witness_evals: &[F],
95) -> Result<F, HyperPlonkErrors> {
96 let mut res = F::zero();
97 for (coeff, selector, witnesses) in gates.gates.iter() {
98 let mut cur_value = if *coeff < 0 {
99 -F::from(-*coeff as u64)
100 } else {
101 F::from(*coeff as u64)
102 };
103 cur_value *= match selector {
104 Some(s) => selector_evals[*s],
105 None => F::one(),
106 };
107 for &witness in witnesses.iter() {
108 cur_value *= witness_evals[witness]
109 }
110 res += cur_value;
111 }
112 Ok(res)
113}
114
115#[cfg(test)]
116mod test {
117 use super::*;
118 use ark_bls12_381::Fr;
119 use ark_ff::PrimeField;
120 use ark_poly::MultilinearExtension;
121 #[test]
122 fn test_build_gate() -> Result<(), HyperPlonkErrors> {
123 test_build_gate_helper::<Fr>()
124 }
125
126 fn test_build_gate_helper<F: PrimeField>() -> Result<(), HyperPlonkErrors> {
127 let num_vars = 2;
128
129 // ql = 3x1x2 + 2x2 whose evaluations are
130 // 0, 0 |-> 0
131 // 0, 1 |-> 2
132 // 1, 0 |-> 0
133 // 1, 1 |-> 5
134 let ql_eval = vec![F::zero(), F::from(2u64), F::zero(), F::from(5u64)];
135 let ql = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, ql_eval));
136
137 // W1 = x1x2 + x1 whose evaluations are
138 // 0, 0 |-> 0
139 // 0, 1 |-> 0
140 // 1, 0 |-> 1
141 // 1, 1 |-> 2
142 let w_eval = vec![F::zero(), F::zero(), F::from(1u64), F::from(2u64)];
143 let w1 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
144
145 // W2 = x1 + x2 whose evaluations are
146 // 0, 0 |-> 0
147 // 0, 1 |-> 1
148 // 1, 0 |-> 1
149 // 1, 1 |-> 2
150 let w_eval = vec![F::zero(), F::one(), F::from(1u64), F::from(2u64)];
151 let w2 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
152
153 // Example:
154 // q_L(X) * W_1(X)^5 - W_2(X)
155 // is represented as
156 // vec![
157 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
158 // (-1, None, vec![id_W2])
159 // ]
160 let gates = CustomizedGates {
161 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
162 };
163 let f = build_f(&gates, num_vars, &[ql.clone()], &[w1.clone(), w2.clone()])?;
164
165 // Sanity check on build_f
166 // f(0, 0) = 0
167 assert_eq!(f.evaluate(&[F::zero(), F::zero()])?, F::zero());
168 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
169 assert_eq!(f.evaluate(&[F::zero(), F::one()])?, -F::one());
170 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
171 assert_eq!(f.evaluate(&[F::one(), F::zero()])?, -F::one());
172 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
173 assert_eq!(f.evaluate(&[F::one(), F::one()])?, F::from(158u64));
174
175 // test eval_f
176 {
177 let point = [F::zero(), F::zero()];
178 let selector_evals = ql.evaluate(&point).unwrap();
179 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
180 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
181 // f(0, 0) = 0
182 assert_eq!(eval_f, F::zero());
183 }
184 {
185 let point = [F::zero(), F::one()];
186 let selector_evals = ql.evaluate(&point).unwrap();
187 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
188 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
189 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
190 assert_eq!(eval_f, -F::one());
191 }
192 {
193 let point = [F::one(), F::zero()];
194 let selector_evals = ql.evaluate(&point).unwrap();
195 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
196 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
197 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
198 assert_eq!(eval_f, -F::one());
199 }
200 {
201 let point = [F::one(), F::one()];
202 let selector_evals = ql.evaluate(&point).unwrap();
203 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
204 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
205 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
206 assert_eq!(eval_f, F::from(158u64));
207 }
208 Ok(())
209 }
210}