sonobe/folding-schemes/src/folding/hypernova/cccs.rs
folding-schemes/src/folding/hypernova/cccs.rsRaw
1use ark_crypto_primitives::sponge::Absorb;
2use ark_ec::CurveGroup;
3use ark_ff::PrimeField;
4use ark_serialize::CanonicalDeserialize;
5use ark_serialize::CanonicalSerialize;
6use ark_std::One;
7use ark_std::Zero;
8use std::sync::Arc;
9
10use ark_std::rand::Rng;
11
12use super::Witness;
13use crate::arith::{ccs::CCS, Arith};
14use crate::commitment::CommitmentScheme;
15use crate::transcript::AbsorbNonNative;
16use crate::utils::mle::dense_vec_to_dense_mle;
17use crate::utils::vec::mat_vec_mul;
18use crate::utils::virtual_polynomial::{build_eq_x_r_vec, VirtualPolynomial};
19use crate::Error;
20
21/// Committed CCS instance
22#[derive(Debug, Clone, CanonicalSerialize, CanonicalDeserialize)]
23pub struct CCCS<C: CurveGroup> {
24 // Commitment to witness
25 pub C: C,
26 // Public input/output
27 pub x: Vec<C::ScalarField>,
28}
29
30impl<F: PrimeField> CCS<F> {
31 pub fn to_cccs<R: Rng, C, CS: CommitmentScheme<C, H>, const H: bool>(
32 &self,
33 rng: &mut R,
34 cs_params: &CS::ProverParams,
35 z: &[C::ScalarField],
36 ) -> Result<(CCCS<C>, Witness<C::ScalarField>), Error>
37 where
38 // enforce that CCS's F is the C::ScalarField
39 C: CurveGroup<ScalarField = F>,
40 {
41 let w: Vec<C::ScalarField> = z[(1 + self.l)..].to_vec();
42
43 // if the commitment scheme is set to be hiding, set the random blinding parameter
44 let r_w = if CS::is_hiding() {
45 C::ScalarField::rand(rng)
46 } else {
47 C::ScalarField::zero()
48 };
49 let C = CS::commit(cs_params, &w, &r_w)?;
50
51 Ok((
52 CCCS::<C> {
53 C,
54 x: z[1..(1 + self.l)].to_vec(),
55 },
56 Witness::<C::ScalarField> { w, r_w },
57 ))
58 }
59
60 /// Computes q(x) = \sum^q c_i * \prod_{j \in S_i} ( \sum_{y \in {0,1}^s'} M_j(x, y) * z(y) )
61 /// polynomial over x
62 pub fn compute_q(&self, z: &[F]) -> Result<VirtualPolynomial<F>, Error> {
63 let mut q_x = VirtualPolynomial::<F>::new(self.s);
64 for i in 0..self.q {
65 let mut Q_k = vec![];
66 for &j in self.S[i].iter() {
67 Q_k.push(dense_vec_to_dense_mle(self.s, &mat_vec_mul(&self.M[j], z)?));
68 }
69 q_x.add_mle_list(Q_k.iter().map(|v| Arc::new(v.clone())), self.c[i])?;
70 }
71 Ok(q_x)
72 }
73
74 /// Computes Q(x) = eq(beta, x) * q(x)
75 /// = eq(beta, x) * \sum^q c_i * \prod_{j \in S_i} ( \sum_{y \in {0,1}^s'} M_j(x, y) * z(y) )
76 /// polynomial over x
77 pub fn compute_Q(&self, z: &[F], beta: &[F]) -> Result<VirtualPolynomial<F>, Error> {
78 let eq_beta = build_eq_x_r_vec(beta)?;
79 let eq_beta_mle = dense_vec_to_dense_mle(self.s, &eq_beta);
80
81 let mut Q = VirtualPolynomial::<F>::new(self.s);
82 for i in 0..self.q {
83 let mut Q_k = vec![];
84 for &j in self.S[i].iter() {
85 Q_k.push(dense_vec_to_dense_mle(self.s, &mat_vec_mul(&self.M[j], z)?));
86 }
87 Q_k.push(eq_beta_mle.clone());
88 Q.add_mle_list(Q_k.iter().map(|v| Arc::new(v.clone())), self.c[i])?;
89 }
90 Ok(Q)
91 }
92}
93
94impl<C: CurveGroup> CCCS<C> {
95 pub fn dummy(l: usize) -> CCCS<C>
96 where
97 C::ScalarField: PrimeField,
98 {
99 CCCS::<C> {
100 C: C::zero(),
101 x: vec![C::ScalarField::zero(); l],
102 }
103 }
104
105 /// Perform the check of the CCCS instance described at section 4.1,
106 /// notice that this method does not check the commitment correctness
107 pub fn check_relation(
108 &self,
109 ccs: &CCS<C::ScalarField>,
110 w: &Witness<C::ScalarField>,
111 ) -> Result<(), Error> {
112 // check CCCS relation
113 let z: Vec<C::ScalarField> =
114 [vec![C::ScalarField::one()], self.x.clone(), w.w.to_vec()].concat();
115
116 // A CCCS relation is satisfied if the q(x) multivariate polynomial evaluates to zero in
117 // the hypercube, evaluating over the whole boolean hypercube for a normal-sized instance
118 // would take too much, this checks the CCS relation of the CCCS.
119 ccs.check_relation(&z)?;
120
121 Ok(())
122 }
123}
124
125impl<C: CurveGroup> Absorb for CCCS<C>
126where
127 C::ScalarField: Absorb,
128{
129 fn to_sponge_bytes(&self, _dest: &mut Vec<u8>) {
130 // This is never called
131 unimplemented!()
132 }
133
134 fn to_sponge_field_elements<F: PrimeField>(&self, dest: &mut Vec<F>) {
135 // We cannot call `to_native_sponge_field_elements(dest)` directly, as
136 // `to_native_sponge_field_elements` needs `F` to be `C::ScalarField`,
137 // but here `F` is a generic `PrimeField`.
138 self.C
139 .to_native_sponge_field_elements_as_vec()
140 .to_sponge_field_elements(dest);
141 self.x.to_sponge_field_elements(dest);
142 }
143}
144
145#[cfg(test)]
146pub mod tests {
147 use ark_pallas::Fr;
148 use ark_std::test_rng;
149 use ark_std::UniformRand;
150
151 use super::*;
152 use crate::arith::ccs::tests::{get_test_ccs, get_test_z};
153 use crate::utils::hypercube::BooleanHypercube;
154
155 /// Do some sanity checks on q(x). It's a multivariable polynomial and it should evaluate to zero inside the
156 /// hypercube, but to not-zero outside the hypercube.
157 #[test]
158 fn test_compute_q() {
159 let mut rng = test_rng();
160
161 let ccs = get_test_ccs::<Fr>();
162 let z = get_test_z(3);
163
164 let q = ccs.compute_q(&z).unwrap();
165
166 // Evaluate inside the hypercube
167 for x in BooleanHypercube::new(ccs.s) {
168 assert_eq!(Fr::zero(), q.evaluate(&x).unwrap());
169 }
170
171 // Evaluate outside the hypercube
172 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
173 assert_ne!(Fr::zero(), q.evaluate(&beta).unwrap());
174 }
175
176 /// Perform some sanity checks on Q(x).
177 #[test]
178 fn test_compute_Q() {
179 let mut rng = test_rng();
180
181 let ccs: CCS<Fr> = get_test_ccs();
182 let z = get_test_z(3);
183 ccs.check_relation(&z).unwrap();
184
185 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
186
187 // Compute Q(x) = eq(beta, x) * q(x).
188 let Q = ccs.compute_Q(&z, &beta).unwrap();
189
190 // Let's consider the multilinear polynomial G(x) = \sum_{y \in {0, 1}^s} eq(x, y) q(y)
191 // which interpolates the multivariate polynomial q(x) inside the hypercube.
192 //
193 // Observe that summing Q(x) inside the hypercube, directly computes G(\beta).
194 //
195 // Now, G(x) is multilinear and agrees with q(x) inside the hypercube. Since q(x) vanishes inside the
196 // hypercube, this means that G(x) also vanishes in the hypercube. Since G(x) is multilinear and vanishes
197 // inside the hypercube, this makes it the zero polynomial.
198 //
199 // Hence, evaluating G(x) at a random beta should give zero.
200
201 // Now sum Q(x) evaluations in the hypercube and expect it to be 0
202 let r = BooleanHypercube::new(ccs.s)
203 .map(|x| Q.evaluate(&x).unwrap())
204 .fold(Fr::zero(), |acc, result| acc + result);
205 assert_eq!(r, Fr::zero());
206 }
207
208 /// The polynomial G(x) (see above) interpolates q(x) inside the hypercube.
209 /// Summing Q(x) over the hypercube is equivalent to evaluating G(x) at some point.
210 /// This test makes sure that G(x) agrees with q(x) inside the hypercube, but not outside
211 #[test]
212 fn test_Q_against_q() {
213 let mut rng = test_rng();
214
215 let ccs: CCS<Fr> = get_test_ccs();
216 let z = get_test_z(3);
217 ccs.check_relation(&z).unwrap();
218
219 // 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
220 // should be equal to q(d), since G(x) interpolates q(x) inside the hypercube
221 let q = ccs.compute_q(&z).unwrap();
222 for d in BooleanHypercube::new(ccs.s) {
223 let Q_at_d = ccs.compute_Q(&z, &d).unwrap();
224
225 // Get G(d) by summing over Q_d(x) over the hypercube
226 let G_at_d = BooleanHypercube::new(ccs.s)
227 .map(|x| Q_at_d.evaluate(&x).unwrap())
228 .fold(Fr::zero(), |acc, result| acc + result);
229 assert_eq!(G_at_d, q.evaluate(&d).unwrap());
230 }
231
232 // Now test that they should disagree outside of the hypercube
233 let r: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
234 let Q_at_r = ccs.compute_Q(&z, &r).unwrap();
235
236 // Get G(d) by summing over Q_d(x) over the hypercube
237 let G_at_r = BooleanHypercube::new(ccs.s)
238 .map(|x| Q_at_r.evaluate(&x).unwrap())
239 .fold(Fr::zero(), |acc, result| acc + result);
240 assert_ne!(G_at_r, q.evaluate(&r).unwrap());
241 }
242}