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 if let Some(s) = *selector {
78 mle_list.push(selector_mles[s].clone())
79 }
80 for &witness in witnesses.iter() {
81 mle_list.push(witness_mles[witness].clone())
82 }
83 res.add_mle_list(mle_list, coeff_fr)?;
84 }
85
86 Ok(res)
87}
88
89#[allow(dead_code)]
90pub(crate) fn eval_f<F: PrimeField>(
91 gates: &CustomizedGates,
92 selector_evals: &[F],
93 witness_evals: &[F],
94) -> Result<F, HyperPlonkErrors> {
95 let mut res = F::zero();
96 for (coeff, selector, witnesses) in gates.gates.iter() {
97 let mut cur_value = if *coeff < 0 {
98 -F::from(-*coeff as u64)
99 } else {
100 F::from(*coeff as u64)
101 };
102 cur_value *= match selector {
103 Some(s) => selector_evals[*s],
104 None => F::one(),
105 };
106 for &witness in witnesses.iter() {
107 cur_value *= witness_evals[witness]
108 }
109 res += cur_value;
110 }
111 Ok(res)
112}
113
114#[cfg(test)]
115mod test {
116 use super::*;
117 use ark_bls12_381::Fr;
118 use ark_ff::PrimeField;
119 use ark_poly::MultilinearExtension;
120 #[test]
121 fn test_build_gate() -> Result<(), HyperPlonkErrors> {
122 test_build_gate_helper::<Fr>()
123 }
124
125 fn test_build_gate_helper<F: PrimeField>() -> Result<(), HyperPlonkErrors> {
126 let num_vars = 2;
127
128 // ql = 3x1x2 + 2x2 whose evaluations are
129 // 0, 0 |-> 0
130 // 0, 1 |-> 2
131 // 1, 0 |-> 0
132 // 1, 1 |-> 5
133 let ql_eval = vec![F::zero(), F::from(2u64), F::zero(), F::from(5u64)];
134 let ql = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, ql_eval));
135
136 // W1 = x1x2 + x1 whose evaluations are
137 // 0, 0 |-> 0
138 // 0, 1 |-> 0
139 // 1, 0 |-> 1
140 // 1, 1 |-> 2
141 let w_eval = vec![F::zero(), F::zero(), F::from(1u64), F::from(2u64)];
142 let w1 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
143
144 // W2 = x1 + x2 whose evaluations are
145 // 0, 0 |-> 0
146 // 0, 1 |-> 1
147 // 1, 0 |-> 1
148 // 1, 1 |-> 2
149 let w_eval = vec![F::zero(), F::one(), F::from(1u64), F::from(2u64)];
150 let w2 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
151
152 // Example:
153 // q_L(X) * W_1(X)^5 - W_2(X)
154 // is represented as
155 // vec![
156 // ( 1, Some(id_qL), vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
157 // (-1, None, vec![id_W2])
158 // ]
159 let gates = CustomizedGates {
160 gates: vec![(1, Some(0), vec![0, 0, 0, 0, 0]), (-1, None, vec![1])],
161 };
162 let f = build_f(&gates, num_vars, &[ql.clone()], &[w1.clone(), w2.clone()])?;
163
164 // Sanity check on build_f
165 // f(0, 0) = 0
166 assert_eq!(f.evaluate(&[F::zero(), F::zero()])?, F::zero());
167 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
168 assert_eq!(f.evaluate(&[F::zero(), F::one()])?, -F::one());
169 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
170 assert_eq!(f.evaluate(&[F::one(), F::zero()])?, -F::one());
171 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
172 assert_eq!(f.evaluate(&[F::one(), F::one()])?, F::from(158u64));
173
174 // test eval_f
175 {
176 let point = [F::zero(), F::zero()];
177 let selector_evals = ql.evaluate(&point).unwrap();
178 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
179 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
180 // f(0, 0) = 0
181 assert_eq!(eval_f, F::zero());
182 }
183 {
184 let point = [F::zero(), F::one()];
185 let selector_evals = ql.evaluate(&point).unwrap();
186 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
187 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
188 // f(0, 1) = 2 * 0^5 + (-1) * 1 = -1
189 assert_eq!(eval_f, -F::one());
190 }
191 {
192 let point = [F::one(), F::zero()];
193 let selector_evals = ql.evaluate(&point).unwrap();
194 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
195 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
196 // f(1, 0) = 0 * 1^5 + (-1) * 1 = -1
197 assert_eq!(eval_f, -F::one());
198 }
199 {
200 let point = [F::one(), F::one()];
201 let selector_evals = ql.evaluate(&point).unwrap();
202 let witness_evals = [w1.evaluate(&point).unwrap(), w2.evaluate(&point).unwrap()];
203 let eval_f = eval_f(&gates, &[selector_evals], &witness_evals)?;
204 // f(1, 1) = 5 * 2^5 + (-1) * 2 = 158
205 assert_eq!(eval_f, F::from(158u64));
206 }
207 Ok(())
208 }
209}