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