sonobe/src/folding/hypernova/cccs.rs
src/folding/hypernova/cccs.rsRaw
1use ark_ec::CurveGroup;
2use ark_ff::PrimeField;
3use ark_std::One;
4use ark_std::Zero;
5use std::ops::Add;
6use std::sync::Arc;
7
8use ark_std::{rand::Rng, UniformRand};
9
10use super::utils::compute_sum_Mz;
11use crate::ccs::CCS;
12use crate::pedersen::{Params as PedersenParams, Pedersen};
13use crate::utils::hypercube::BooleanHypercube;
14use crate::utils::mle::matrix_to_mle;
15use crate::utils::mle::vec_to_mle;
16use crate::utils::virtual_polynomial::VirtualPolynomial;
17use crate::Error;
18
19/// Witness for the LCCCS & CCCS, containing the w vector, and the r_w used as randomness in the Pedersen commitment.
20#[derive(Debug, Clone)]
21pub struct Witness<F: PrimeField> {
22 pub w: Vec<F>,
23 pub r_w: F, // randomness used in the Pedersen commitment of w
24}
25
26/// Committed CCS instance
27#[derive(Debug, Clone)]
28pub struct CCCS<C: CurveGroup> {
29 // Commitment to witness
30 pub C: C,
31 // Public input/output
32 pub x: Vec<C::ScalarField>,
33}
34
35impl<C: CurveGroup> CCS<C> {
36 pub fn to_cccs<R: Rng>(
37 &self,
38 rng: &mut R,
39 pedersen_params: &PedersenParams<C>,
40 z: &[C::ScalarField],
41 ) -> Result<(CCCS<C>, Witness<C::ScalarField>), Error> {
42 let w: Vec<C::ScalarField> = z[(1 + self.l)..].to_vec();
43 let r_w = C::ScalarField::rand(rng);
44 let C = Pedersen::<C>::commit(pedersen_params, &w, &r_w)?;
45
46 Ok((
47 CCCS::<C> {
48 C,
49 x: z[1..(1 + self.l)].to_vec(),
50 },
51 Witness::<C::ScalarField> { w, r_w },
52 ))
53 }
54
55 /// Computes q(x) = \sum^q c_i * \prod_{j \in S_i} ( \sum_{y \in {0,1}^s'} M_j(x, y) * z(y) )
56 /// polynomial over x
57 pub fn compute_q(&self, z: &Vec<C::ScalarField>) -> VirtualPolynomial<C::ScalarField> {
58 let z_mle = vec_to_mle(self.s_prime, z);
59 let mut q = VirtualPolynomial::<C::ScalarField>::new(self.s);
60
61 for i in 0..self.q {
62 let mut prod: VirtualPolynomial<C::ScalarField> =
63 VirtualPolynomial::<C::ScalarField>::new(self.s);
64 for j in self.S[i].clone() {
65 let M_j = matrix_to_mle(self.M[j].clone());
66
67 let sum_Mz = compute_sum_Mz(M_j, &z_mle, self.s_prime);
68
69 // Fold this sum into the running product
70 if prod.products.is_empty() {
71 // If this is the first time we are adding something to this virtual polynomial, we need to
72 // explicitly add the products using add_mle_list()
73 // XXX is this true? improve API
74 prod.add_mle_list([Arc::new(sum_Mz)], C::ScalarField::one())
75 .unwrap();
76 } else {
77 prod.mul_by_mle(Arc::new(sum_Mz), C::ScalarField::one())
78 .unwrap();
79 }
80 }
81 // Multiply by the product by the coefficient c_i
82 prod.scalar_mul(&self.c[i]);
83 // Add it to the running sum
84 q = q.add(&prod);
85 }
86 q
87 }
88
89 /// Computes Q(x) = eq(beta, x) * q(x)
90 /// = eq(beta, x) * \sum^q c_i * \prod_{j \in S_i} ( \sum_{y \in {0,1}^s'} M_j(x, y) * z(y) )
91 /// polynomial over x
92 pub fn compute_Q(
93 &self,
94 z: &Vec<C::ScalarField>,
95 beta: &[C::ScalarField],
96 ) -> VirtualPolynomial<C::ScalarField> {
97 let q = self.compute_q(z);
98 q.build_f_hat(beta).unwrap()
99 }
100}
101
102impl<C: CurveGroup> CCCS<C> {
103 /// Perform the check of the CCCS instance described at section 4.1
104 pub fn check_relation(
105 &self,
106 pedersen_params: &PedersenParams<C>,
107 ccs: &CCS<C>,
108 w: &Witness<C::ScalarField>,
109 ) -> Result<(), Error> {
110 // check that C is the commitment of w. Notice that this is not verifying a Pedersen
111 // opening, but checking that the Commmitment comes from committing to the witness.
112 if self.C != Pedersen::commit(pedersen_params, &w.w, &w.r_w)? {
113 return Err(Error::NotSatisfied);
114 }
115
116 // check CCCS relation
117 let z: Vec<C::ScalarField> =
118 [vec![C::ScalarField::one()], self.x.clone(), w.w.to_vec()].concat();
119
120 // A CCCS relation is satisfied if the q(x) multivariate polynomial evaluates to zero in the hypercube
121 let q_x = ccs.compute_q(&z);
122 for x in BooleanHypercube::new(ccs.s) {
123 if !q_x.evaluate(&x).unwrap().is_zero() {
124 return Err(Error::NotSatisfied);
125 }
126 }
127
128 Ok(())
129 }
130}
131
132#[cfg(test)]
133pub mod tests {
134 use super::*;
135 use crate::ccs::tests::{get_test_ccs, get_test_z};
136 use ark_std::test_rng;
137 use ark_std::UniformRand;
138
139 use ark_pallas::{Fr, Projective};
140
141 /// Do some sanity checks on q(x). It's a multivariable polynomial and it should evaluate to zero inside the
142 /// hypercube, but to not-zero outside the hypercube.
143 #[test]
144 fn test_compute_q() {
145 let mut rng = test_rng();
146
147 let ccs = get_test_ccs::<Projective>();
148 let z = get_test_z(3);
149
150 let q = ccs.compute_q(&z);
151
152 // Evaluate inside the hypercube
153 for x in BooleanHypercube::new(ccs.s) {
154 assert_eq!(Fr::zero(), q.evaluate(&x).unwrap());
155 }
156
157 // Evaluate outside the hypercube
158 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
159 assert_ne!(Fr::zero(), q.evaluate(&beta).unwrap());
160 }
161
162 /// Perform some sanity checks on Q(x).
163 #[test]
164 fn test_compute_Q() {
165 let mut rng = test_rng();
166
167 let ccs: CCS<Projective> = get_test_ccs();
168 let z = get_test_z(3);
169 ccs.check_relation(&z).unwrap();
170
171 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
172
173 // Compute Q(x) = eq(beta, x) * q(x).
174 let Q = ccs.compute_Q(&z, &beta);
175
176 // Let's consider the multilinear polynomial G(x) = \sum_{y \in {0, 1}^s} eq(x, y) q(y)
177 // which interpolates the multivariate polynomial q(x) inside the hypercube.
178 //
179 // Observe that summing Q(x) inside the hypercube, directly computes G(\beta).
180 //
181 // Now, G(x) is multilinear and agrees with q(x) inside the hypercube. Since q(x) vanishes inside the
182 // hypercube, this means that G(x) also vanishes in the hypercube. Since G(x) is multilinear and vanishes
183 // inside the hypercube, this makes it the zero polynomial.
184 //
185 // Hence, evaluating G(x) at a random beta should give zero.
186
187 // Now sum Q(x) evaluations in the hypercube and expect it to be 0
188 let r = BooleanHypercube::new(ccs.s)
189 .map(|x| Q.evaluate(&x).unwrap())
190 .fold(Fr::zero(), |acc, result| acc + result);
191 assert_eq!(r, Fr::zero());
192 }
193
194 /// The polynomial G(x) (see above) interpolates q(x) inside the hypercube.
195 /// Summing Q(x) over the hypercube is equivalent to evaluating G(x) at some point.
196 /// This test makes sure that G(x) agrees with q(x) inside the hypercube, but not outside
197 #[test]
198 fn test_Q_against_q() {
199 let mut rng = test_rng();
200
201 let ccs: CCS<Projective> = get_test_ccs();
202 let z = get_test_z(3);
203 ccs.check_relation(&z).unwrap();
204
205 // Now test that if we create Q(x) with eq(d,y) where d is inside the hypercube, \sum Q(x) should be G(d) which
206 // should be equal to q(d), since G(x) interpolates q(x) inside the hypercube
207 let q = ccs.compute_q(&z);
208 for d in BooleanHypercube::new(ccs.s) {
209 let Q_at_d = ccs.compute_Q(&z, &d);
210
211 // Get G(d) by summing over Q_d(x) over the hypercube
212 let G_at_d = BooleanHypercube::new(ccs.s)
213 .map(|x| Q_at_d.evaluate(&x).unwrap())
214 .fold(Fr::zero(), |acc, result| acc + result);
215 assert_eq!(G_at_d, q.evaluate(&d).unwrap());
216 }
217
218 // Now test that they should disagree outside of the hypercube
219 let r: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
220 let Q_at_r = ccs.compute_Q(&z, &r);
221
222 // Get G(d) by summing over Q_d(x) over the hypercube
223 let G_at_r = BooleanHypercube::new(ccs.s)
224 .map(|x| Q_at_r.evaluate(&x).unwrap())
225 .fold(Fr::zero(), |acc, result| acc + result);
226 assert_ne!(G_at_r, q.evaluate(&r).unwrap());
227 }
228}