hyperplonk/poly-iop/src/virtual_poly.rs
poly-iop/src/virtual_poly.rsRaw
1use crate::{errors::PolyIOPErrors, structs::DomainInfo};
2use ark_ff::PrimeField;
3use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
4use ark_std::{end_timer, start_timer};
5use std::{cmp::max, collections::HashMap, marker::PhantomData, rc::Rc};
6
7/// A virtual polynomial is a list of multilinear polynomials
8#[derive(Clone, Debug, Default, PartialEq)]
9pub struct VirtualPolynomial<F: PrimeField> {
10 /// Aux information about the multilinear polynomial
11 pub domain_info: DomainInfo<F>,
12 /// list of reference to products (as usize) of multilinear extension
13 pub products: Vec<(F, Vec<usize>)>,
14 /// Stores multilinear extensions in which product multiplicand can refer
15 /// to.
16 pub flattened_ml_extensions: Vec<Rc<DenseMultilinearExtension<F>>>,
17 /// Pointers to the above poly extensions
18 raw_pointers_lookup_table: HashMap<*const DenseMultilinearExtension<F>, usize>,
19}
20
21impl<F: PrimeField> VirtualPolynomial<F> {
22 /// Returns an empty polynomial
23 pub fn new(num_variables: usize) -> Self {
24 VirtualPolynomial {
25 domain_info: DomainInfo {
26 max_degree: 0,
27 num_variables,
28 phantom: PhantomData::default(),
29 },
30 products: Vec::new(),
31 flattened_ml_extensions: Vec::new(),
32 raw_pointers_lookup_table: HashMap::new(),
33 }
34 }
35
36 /// Add a list of multilinear extensions that is meant to be multiplied
37 /// together. The resulting polynomial will be multiplied by the scalar
38 /// `coefficient`.
39 pub fn add_product(
40 &mut self,
41 product: impl IntoIterator<Item = Rc<DenseMultilinearExtension<F>>>,
42 coefficient: F,
43 ) -> Result<(), PolyIOPErrors> {
44 let product: Vec<Rc<DenseMultilinearExtension<F>>> = product.into_iter().collect();
45 let mut indexed_product = Vec::with_capacity(product.len());
46 assert!(!product.is_empty());
47 self.domain_info.max_degree = max(self.domain_info.max_degree, product.len());
48 for m in product {
49 if m.num_vars != self.domain_info.num_variables {
50 return Err(PolyIOPErrors::InvalidParameters(format!(
51 "product has a multiplicand with wrong number of variables {} vs {}",
52 m.num_vars, self.domain_info.num_variables
53 )));
54 }
55
56 let m_ptr: *const DenseMultilinearExtension<F> = Rc::as_ptr(&m);
57 if let Some(index) = self.raw_pointers_lookup_table.get(&m_ptr) {
58 indexed_product.push(*index)
59 } else {
60 let curr_index = self.flattened_ml_extensions.len();
61 self.flattened_ml_extensions.push(m.clone());
62 self.raw_pointers_lookup_table.insert(m_ptr, curr_index);
63 indexed_product.push(curr_index);
64 }
65 }
66 self.products.push((coefficient, indexed_product));
67 Ok(())
68 }
69
70 /// Evaluate the polynomial at point `point`
71 pub fn evaluate(&self, point: &[F]) -> Result<F, PolyIOPErrors> {
72 let start = start_timer!(|| "begin evaluation");
73
74 if self.domain_info.num_variables != point.len() {
75 return Err(PolyIOPErrors::InvalidParameters(format!(
76 "wrong number of variables {} vs {}",
77 self.domain_info.num_variables,
78 point.len()
79 )));
80 }
81
82 let evals: Vec<F> = self
83 .flattened_ml_extensions
84 .iter()
85 .map(|x| {
86 x.evaluate(point).unwrap() // safe unwrap here since we have
87 // already checked that num_var
88 // matches
89 })
90 .collect();
91
92 let res = self
93 .products
94 .iter()
95 .map(|(c, p)| *c * p.iter().map(|&i| evals[i]).product::<F>())
96 .sum();
97
98 end_timer!(start);
99 Ok(res)
100 }
101}
102
103#[cfg(test)]
104pub(crate) mod test {
105 use super::*;
106 use ark_std::rand::{Rng, RngCore};
107
108 pub fn random_product<F: PrimeField, R: RngCore>(
109 nv: usize,
110 num_multiplicands: usize,
111 rng: &mut R,
112 ) -> (Vec<Rc<DenseMultilinearExtension<F>>>, F) {
113 let mut multiplicands = Vec::with_capacity(num_multiplicands);
114 for _ in 0..num_multiplicands {
115 multiplicands.push(Vec::with_capacity(1 << nv))
116 }
117 let mut sum = F::zero();
118
119 for _ in 0..(1 << nv) {
120 let mut product = F::one();
121 for i in 0..num_multiplicands {
122 let val = F::rand(rng);
123 multiplicands[i].push(val);
124 product *= val;
125 }
126 sum += product;
127 }
128
129 (
130 multiplicands
131 .into_iter()
132 .map(|x| Rc::new(DenseMultilinearExtension::from_evaluations_vec(nv, x)))
133 .collect(),
134 sum,
135 )
136 }
137
138 pub(crate) fn random_list_of_products<F: PrimeField, R: RngCore>(
139 nv: usize,
140 num_multiplicands_range: (usize, usize),
141 num_products: usize,
142 rng: &mut R,
143 ) -> (VirtualPolynomial<F>, F) {
144 let mut sum = F::zero();
145 let mut poly = VirtualPolynomial::new(nv);
146 for _ in 0..num_products {
147 let num_multiplicands =
148 rng.gen_range(num_multiplicands_range.0..num_multiplicands_range.1);
149 let (product, product_sum) = random_product(nv, num_multiplicands, rng);
150 let coefficient = F::rand(rng);
151 poly.add_product(product.into_iter(), coefficient).unwrap();
152 sum += product_sum * coefficient;
153 }
154
155 (poly, sum)
156 }
157
158 // pub fn random_zero_product<F: PrimeField, R: RngCore>(
159 // nv: usize,
160 // num_multiplicands: usize,
161 // rng: &mut R,
162 // ) -> Vec<Rc<DenseMultilinearExtension<F>>> {
163 // let degree = 2;
164 // let mut multiplicands = Vec::with_capacity(degree);
165 // for _ in 0..degree {
166 // multiplicands.push(Vec::with_capacity(1 << nv))
167 // }
168 // let mut sum = F::zero();
169
170 // for _ in 0..(1 << nv) {
171 // let mut product = F::one();
172 // for i in 0..degree {
173 // let val = F::zero(); // F::rand(rng);
174 // multiplicands[i].push(val);
175 // product *= val;
176 // }
177 // sum += product;
178 // }
179
180 // // // last nv offsets the poly to 0
181 // // for i in 0..num_multiplicands - 1 {
182 // // multiplicands[i].push(F::one());
183 // // }
184 // // multiplicands[num_multiplicands - 1].push(-sum);
185
186 // multiplicands
187 // .into_iter()
188 // .map(|x|
189 // Rc::new(DenseMultilinearExtension::from_evaluations_vec(nv, x)))
190 // .collect()
191 // }
192
193 // pub(crate) fn random_zero_list_of_products<F: PrimeField, R: RngCore>(
194 // nv: usize,
195 // num_multiplicands_range: (usize, usize),
196 // num_products: usize,
197 // rng: &mut R,
198 // ) -> VirtualPolynomial<F> {
199 // let mut poly = VirtualPolynomial::new(nv);
200 // for _ in 0..num_products {
201 // let num_multiplicands =
202 //
203 // rng.gen_range(num_multiplicands_range.0..num_multiplicands_range.1);
204 // let product = random_zero_product(nv, num_multiplicands, rng);
205 // let coefficient = F::rand(rng);
206 // poly.add_product(product.into_iter(), coefficient);
207 // }
208
209 // poly
210 // }
211}