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 ) -> (CCCS<C>, Witness<C::ScalarField>) {
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 (
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 assert_eq!(self.C, Pedersen::commit(pedersen_params, &w.w, &w.r_w));
113
114 // check CCCS relation
115 let z: Vec<C::ScalarField> =
116 [vec![C::ScalarField::one()], self.x.clone(), w.w.to_vec()].concat();
117
118 // A CCCS relation is satisfied if the q(x) multivariate polynomial evaluates to zero in the hypercube
119 let q_x = ccs.compute_q(&z);
120 for x in BooleanHypercube::new(ccs.s) {
121 if !q_x.evaluate(&x).unwrap().is_zero() {
122 return Err(Error::NotSatisfied);
123 }
124 }
125
126 Ok(())
127 }
128}
129
130#[cfg(test)]
131pub mod tests {
132 use super::*;
133 use crate::ccs::tests::{get_test_ccs, get_test_z};
134 use ark_std::test_rng;
135 use ark_std::UniformRand;
136
137 use ark_pallas::{Fr, Projective};
138
139 /// Do some sanity checks on q(x). It's a multivariable polynomial and it should evaluate to zero inside the
140 /// hypercube, but to not-zero outside the hypercube.
141 #[test]
142 fn test_compute_q() {
143 let mut rng = test_rng();
144
145 let ccs = get_test_ccs::<Projective>();
146 let z = get_test_z(3);
147
148 let q = ccs.compute_q(&z);
149
150 // Evaluate inside the hypercube
151 for x in BooleanHypercube::new(ccs.s) {
152 assert_eq!(Fr::zero(), q.evaluate(&x).unwrap());
153 }
154
155 // Evaluate outside the hypercube
156 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
157 assert_ne!(Fr::zero(), q.evaluate(&beta).unwrap());
158 }
159
160 /// Perform some sanity checks on Q(x).
161 #[test]
162 fn test_compute_Q() {
163 let mut rng = test_rng();
164
165 let ccs: CCS<Projective> = get_test_ccs();
166 let z = get_test_z(3);
167 ccs.check_relation(&z).unwrap();
168
169 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
170
171 // Compute Q(x) = eq(beta, x) * q(x).
172 let Q = ccs.compute_Q(&z, &beta);
173
174 // Let's consider the multilinear polynomial G(x) = \sum_{y \in {0, 1}^s} eq(x, y) q(y)
175 // which interpolates the multivariate polynomial q(x) inside the hypercube.
176 //
177 // Observe that summing Q(x) inside the hypercube, directly computes G(\beta).
178 //
179 // Now, G(x) is multilinear and agrees with q(x) inside the hypercube. Since q(x) vanishes inside the
180 // hypercube, this means that G(x) also vanishes in the hypercube. Since G(x) is multilinear and vanishes
181 // inside the hypercube, this makes it the zero polynomial.
182 //
183 // Hence, evaluating G(x) at a random beta should give zero.
184
185 // Now sum Q(x) evaluations in the hypercube and expect it to be 0
186 let r = BooleanHypercube::new(ccs.s)
187 .map(|x| Q.evaluate(&x).unwrap())
188 .fold(Fr::zero(), |acc, result| acc + result);
189 assert_eq!(r, Fr::zero());
190 }
191
192 /// The polynomial G(x) (see above) interpolates q(x) inside the hypercube.
193 /// Summing Q(x) over the hypercube is equivalent to evaluating G(x) at some point.
194 /// This test makes sure that G(x) agrees with q(x) inside the hypercube, but not outside
195 #[test]
196 fn test_Q_against_q() {
197 let mut rng = test_rng();
198
199 let ccs: CCS<Projective> = get_test_ccs();
200 let z = get_test_z(3);
201 ccs.check_relation(&z).unwrap();
202
203 // 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
204 // should be equal to q(d), since G(x) interpolates q(x) inside the hypercube
205 let q = ccs.compute_q(&z);
206 for d in BooleanHypercube::new(ccs.s) {
207 let Q_at_d = ccs.compute_Q(&z, &d);
208
209 // Get G(d) by summing over Q_d(x) over the hypercube
210 let G_at_d = BooleanHypercube::new(ccs.s)
211 .map(|x| Q_at_d.evaluate(&x).unwrap())
212 .fold(Fr::zero(), |acc, result| acc + result);
213 assert_eq!(G_at_d, q.evaluate(&d).unwrap());
214 }
215
216 // Now test that they should disagree outside of the hypercube
217 let r: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
218 let Q_at_r = ccs.compute_Q(&z, &r);
219
220 // Get G(d) by summing over Q_d(x) over the hypercube
221 let G_at_r = BooleanHypercube::new(ccs.s)
222 .map(|x| Q_at_r.evaluate(&x).unwrap())
223 .fold(Fr::zero(), |acc, result| acc + result);
224 assert_ne!(G_at_r, q.evaluate(&r).unwrap());
225 }
226}