sonobe/folding-schemes/src/commitment/ipa.rs
folding-schemes/src/commitment/ipa.rsRaw
1/// IPA implements the modified Inner Product Argument described in
2/// [Halo](https://eprint.iacr.org/2019/1021.pdf). The variable names used follow the paper
3/// notation in order to make it more readable.
4///
5/// The implementation does the following optimizations in order to reduce the amount of
6/// constraints in the circuit:
7/// i. <s, b> computation is done in log time following a modification of the equation 3 in section
8/// 3.2 from the paper.
9/// ii. s computation is done in 2^{k+1}-2 instead of k*2^k.
10use ark_ec::{AffineRepr, CurveGroup};
11use ark_ff::{Field, PrimeField};
12use ark_r1cs_std::{
13 alloc::{AllocVar, AllocationMode},
14 boolean::Boolean,
15 fields::{nonnative::NonNativeFieldVar, FieldVar},
16 groups::GroupOpsBounds,
17 prelude::CurveVar,
18 ToBitsGadget,
19};
20use ark_relations::r1cs::{Namespace, SynthesisError};
21use ark_std::{cfg_iter, rand::RngCore, UniformRand, Zero};
22use core::{borrow::Borrow, marker::PhantomData};
23use rayon::iter::{IndexedParallelIterator, IntoParallelRefIterator, ParallelIterator};
24
25use super::{pedersen::Params as PedersenParams, CommitmentScheme};
26use crate::transcript::Transcript;
27use crate::utils::{
28 powers_of,
29 vec::{vec_add, vec_scalar_mul},
30};
31use crate::Error;
32
33#[derive(Debug, Clone, Eq, PartialEq)]
34pub struct Proof<C: CurveGroup> {
35 a: C::ScalarField,
36 l: Vec<C::ScalarField>,
37 r: Vec<C::ScalarField>,
38 L: Vec<C>,
39 R: Vec<C>,
40}
41
42/// IPA implements the Inner Product Argument protocol following the CommitmentScheme trait. The
43/// `H` parameter indicates if to use the commitment in hiding mode or not.
44#[derive(Debug, Clone, Eq, PartialEq)]
45pub struct IPA<C: CurveGroup, const H: bool = false> {
46 _c: PhantomData<C>,
47}
48
49/// Implements the CommitmentScheme trait for IPA
50impl<C: CurveGroup, const H: bool> CommitmentScheme<C, H> for IPA<C, H> {
51 type ProverParams = PedersenParams<C>;
52 type VerifierParams = PedersenParams<C>;
53 type Proof = (Proof<C>, C::ScalarField, C::ScalarField); // (proof, v=p(x), r=blinding factor)
54 type ProverChallenge = (C::ScalarField, C, Vec<C::ScalarField>);
55 type Challenge = (C::ScalarField, C, Vec<C::ScalarField>);
56
57 fn setup(
58 mut rng: impl RngCore,
59 len: usize,
60 ) -> Result<(Self::ProverParams, Self::VerifierParams), Error> {
61 let generators: Vec<C::Affine> = std::iter::repeat_with(|| C::Affine::rand(&mut rng))
62 .take(len.next_power_of_two())
63 .collect();
64 let p = PedersenParams::<C> {
65 h: C::rand(&mut rng),
66 generators,
67 };
68 Ok((p.clone(), p))
69 }
70
71 fn commit(
72 params: &PedersenParams<C>,
73 a: &[C::ScalarField],
74 r: &C::ScalarField, // blinding factor
75 ) -> Result<C, Error> {
76 if params.generators.len() < a.len() {
77 return Err(Error::PedersenParamsLen(params.generators.len(), a.len()));
78 }
79 if !H && (!r.is_zero()) {
80 return Err(Error::BlindingNotZero);
81 }
82
83 // h⋅r + <g, a>
84 // use msm_unchecked because we already ensured at the if that lengths match
85 if !H {
86 return Ok(C::msm_unchecked(¶ms.generators[..a.len()], a));
87 }
88 Ok(params.h.mul(r) + C::msm_unchecked(¶ms.generators[..a.len()], a))
89 }
90
91 fn prove(
92 params: &Self::ProverParams,
93 transcript: &mut impl Transcript<C>,
94 P: &C, // commitment
95 a: &[C::ScalarField], // vector
96 blind: &C::ScalarField,
97 rng: Option<&mut dyn RngCore>,
98 ) -> Result<Self::Proof, Error> {
99 if !a.len().is_power_of_two() {
100 return Err(Error::NotPowerOfTwo("a".to_string(), a.len()));
101 }
102 if !H && (!blind.is_zero()) {
103 return Err(Error::BlindingNotZero);
104 }
105 let d = a.len();
106 let k = (f64::from(d as u32).log2()) as usize;
107
108 if params.generators.len() < a.len() {
109 return Err(Error::PedersenParamsLen(params.generators.len(), a.len()));
110 }
111 // blinding factors
112 let l: Vec<C::ScalarField>;
113 let r: Vec<C::ScalarField>;
114 if H {
115 let rng = rng.ok_or(Error::MissingRandomness)?;
116 l = std::iter::repeat_with(|| C::ScalarField::rand(rng))
117 .take(k)
118 .collect();
119 r = std::iter::repeat_with(|| C::ScalarField::rand(rng))
120 .take(k)
121 .collect();
122 } else {
123 l = vec![];
124 r = vec![];
125 }
126
127 transcript.absorb_point(P)?;
128 let x = transcript.get_challenge(); // challenge value at which we evaluate
129 let s = transcript.get_challenge();
130 let U = C::generator().mul(s);
131
132 let mut a = a.to_owned();
133 let mut b = powers_of(x, d);
134 let v = inner_prod(&a, &b)?;
135
136 let mut G = params.generators.clone();
137
138 let mut L: Vec<C> = vec![C::zero(); k];
139 let mut R: Vec<C> = vec![C::zero(); k];
140
141 // u challenges
142 let mut u: Vec<C::ScalarField> = vec![C::ScalarField::zero(); k];
143 for j in (0..k).rev() {
144 let m = a.len() / 2;
145
146 if H {
147 L[j] = C::msm_unchecked(&G[m..], &a[..m])
148 + params.h.mul(l[j])
149 + U.mul(inner_prod(&a[..m], &b[m..])?);
150 R[j] = C::msm_unchecked(&G[..m], &a[m..])
151 + params.h.mul(r[j])
152 + U.mul(inner_prod(&a[m..], &b[..m])?);
153 } else {
154 L[j] = C::msm_unchecked(&G[m..], &a[..m]) + U.mul(inner_prod(&a[..m], &b[m..])?);
155 R[j] = C::msm_unchecked(&G[..m], &a[m..]) + U.mul(inner_prod(&a[m..], &b[..m])?);
156 }
157 // get challenge for the j-th round
158 transcript.absorb_point(&L[j])?;
159 transcript.absorb_point(&R[j])?;
160 u[j] = transcript.get_challenge();
161
162 let uj = u[j];
163 let uj_inv = u[j]
164 .inverse()
165 .ok_or(Error::Other("error on computing inverse".to_string()))?;
166
167 // a_hi * uj^-1 + a_lo * uj
168 a = vec_add(
169 &vec_scalar_mul(&a[..m], &uj),
170 &vec_scalar_mul(&a[m..], &uj_inv),
171 )?;
172 // b_lo * uj^-1 + b_hi * uj
173 b = vec_add(
174 &vec_scalar_mul(&b[..m], &uj_inv),
175 &vec_scalar_mul(&b[m..], &uj),
176 )?;
177 // G_lo * uj^-1 + G_hi * uj
178 G = cfg_iter!(G[..m])
179 .map(|e| e.into_group().mul(uj_inv))
180 .zip(cfg_iter!(G[m..]).map(|e| e.into_group().mul(uj)))
181 .map(|(a, b)| (a + b).into_affine())
182 .collect::<Vec<C::Affine>>();
183 }
184
185 if a.len() != 1 {
186 return Err(Error::NotExpectedLength(a.len(), 1));
187 }
188 if b.len() != 1 {
189 return Err(Error::NotExpectedLength(b.len(), 1));
190 }
191 if G.len() != 1 {
192 return Err(Error::NotExpectedLength(G.len(), 1));
193 }
194
195 Ok((
196 Proof {
197 a: a[0],
198 l: l.clone(),
199 r: r.clone(),
200 L,
201 R,
202 },
203 v, // evaluation at challenge, v=p(x)
204 *blind, // blind factor
205 ))
206 }
207
208 fn prove_with_challenge(
209 _params: &Self::ProverParams,
210 _challenge: Self::ProverChallenge,
211 _a: &[C::ScalarField], // vector
212 _blind: &C::ScalarField,
213 _rng: Option<&mut dyn RngCore>,
214 ) -> Result<Self::Proof, Error> {
215 // not supported because the prover logic computes challenges as it advances on the logic
216 Err(Error::NotSupported("IPA::prove_with_challenge".to_string()))
217 }
218
219 fn verify(
220 params: &Self::VerifierParams,
221 transcript: &mut impl Transcript<C>,
222 P: &C, // commitment
223 proof: &Self::Proof,
224 ) -> Result<(), Error> {
225 let (p, _r) = (proof.0.clone(), proof.1);
226 let k = p.L.len();
227
228 transcript.absorb_point(P)?;
229 let x = transcript.get_challenge(); // challenge value at which we evaluate
230 let s = transcript.get_challenge();
231 let U = C::generator().mul(s);
232 let mut u: Vec<C::ScalarField> = vec![C::ScalarField::zero(); k];
233 for i in (0..k).rev() {
234 transcript.absorb_point(&p.L[i])?;
235 transcript.absorb_point(&p.R[i])?;
236 u[i] = transcript.get_challenge();
237 }
238 let challenge = (x, U, u);
239
240 Self::verify_with_challenge(params, challenge, P, proof)
241 }
242
243 fn verify_with_challenge(
244 params: &Self::VerifierParams,
245 challenge: Self::Challenge,
246 P: &C, // commitment
247 proof: &Self::Proof,
248 ) -> Result<(), Error> {
249 let (p, v, r) = (proof.0.clone(), proof.1, proof.2);
250 let (x, U, u) = challenge;
251
252 let k = p.L.len();
253 if p.R.len() != k {
254 return Err(Error::CommitmentVerificationFail);
255 }
256 if !H && (!r.is_zero()) {
257 return Err(Error::BlindingNotZero);
258 }
259 if !H && (!p.l.is_empty() || !p.r.is_empty()) {
260 return Err(Error::CommitmentVerificationFail);
261 }
262 if H && (p.l.len() != k || p.r.len() != k) {
263 return Err(Error::CommitmentVerificationFail);
264 }
265
266 let P = *P + U.mul(v); // where v=p(x)
267
268 let mut q_0 = P;
269 let mut r = r;
270
271 // compute u[i]^-1 once
272 let mut u_invs = vec![C::ScalarField::zero(); u.len()];
273 for (j, u_j) in u.iter().enumerate() {
274 u_invs[j] = u_j
275 .inverse()
276 .ok_or(Error::Other("error on computing inverse".to_string()))?;
277 }
278
279 // compute b & G from s
280 let s = build_s(&u, &u_invs, k)?;
281 // b = <s, b_vec> = <s, [1, x, x^2, ..., x^d-1]>
282 let b = s_b_inner(&u, &x)?;
283 let d: usize = 2_u64.pow(k as u32) as usize;
284 if params.generators.len() < d {
285 return Err(Error::PedersenParamsLen(params.generators.len(), d));
286 }
287 let G = C::msm_unchecked(¶ms.generators, &s);
288
289 for (j, u_j) in u.iter().enumerate() {
290 let uj2 = u_j.square();
291 let uj_inv2 = u_invs[j].square();
292
293 q_0 = q_0 + p.L[j].mul(uj2) + p.R[j].mul(uj_inv2);
294 if H {
295 r = r + p.l[j] * uj2 + p.r[j] * uj_inv2;
296 }
297 }
298
299 let q_1 = if H {
300 G.mul(p.a) + params.h.mul(r) + U.mul(p.a * b)
301 } else {
302 G.mul(p.a) + U.mul(p.a * b)
303 };
304
305 if q_0 != q_1 {
306 return Err(Error::CommitmentVerificationFail);
307 }
308 Ok(())
309 }
310}
311
312/// Computes s such that
313/// s = (
314/// u₁⁻¹ u₂⁻¹ … uₖ⁻¹,
315/// u₁ u₂⁻¹ … uₖ⁻¹,
316/// u₁⁻¹ u₂ … uₖ⁻¹,
317/// u₁ u₂ … uₖ⁻¹,
318/// ⋮ ⋮ ⋮
319/// u₁ u₂ … uₖ
320/// )
321/// Uses Halo2 approach computing $g(X) = \prod\limits_{i=0}^{k-1} (1 + u_{k - 1 - i} X^{2^i})$,
322/// taking 2^{k+1}-2.
323/// src: https://github.com/zcash/halo2/blob/81729eca91ba4755e247f49c3a72a4232864ec9e/halo2_proofs/src/poly/commitment/verifier.rs#L156
324fn build_s<F: PrimeField>(u: &[F], u_invs: &[F], k: usize) -> Result<Vec<F>, Error> {
325 let d: usize = 2_u64.pow(k as u32) as usize;
326 let mut s: Vec<F> = vec![F::one(); d];
327 for (len, (u_j, u_j_inv)) in u
328 .iter()
329 .zip(u_invs)
330 .enumerate()
331 .map(|(i, u_j)| (1 << i, u_j))
332 {
333 let (left, right) = s.split_at_mut(len);
334 let right = &mut right[0..len];
335 right.copy_from_slice(left);
336 for s in left {
337 *s *= u_j_inv;
338 }
339 for s in right {
340 *s *= u_j;
341 }
342 }
343 Ok(s)
344}
345
346/// Computes (in-circuit) s such that
347/// s = (
348/// u₁⁻¹ u₂⁻¹ … uₖ⁻¹,
349/// u₁ u₂⁻¹ … uₖ⁻¹,
350/// u₁⁻¹ u₂ … uₖ⁻¹,
351/// u₁ u₂ … uₖ⁻¹,
352/// ⋮ ⋮ ⋮
353/// u₁ u₂ … uₖ
354/// )
355/// Uses Halo2 approach computing $g(X) = \prod\limits_{i=0}^{k-1} (1 + u_{k - 1 - i} X^{2^i})$,
356/// taking 2^{k+1}-2.
357/// src: https://github.com/zcash/halo2/blob/81729eca91ba4755e247f49c3a72a4232864ec9e/halo2_proofs/src/poly/commitment/verifier.rs#L156
358fn build_s_gadget<F: PrimeField, CF: PrimeField>(
359 u: &[NonNativeFieldVar<F, CF>],
360 u_invs: &[NonNativeFieldVar<F, CF>],
361 k: usize,
362) -> Result<Vec<NonNativeFieldVar<F, CF>>, SynthesisError> {
363 let d: usize = 2_u64.pow(k as u32) as usize;
364 let mut s: Vec<NonNativeFieldVar<F, CF>> = vec![NonNativeFieldVar::one(); d];
365 for (len, (u_j, u_j_inv)) in u
366 .iter()
367 .zip(u_invs)
368 .enumerate()
369 .map(|(i, u_j)| (1 << i, u_j))
370 {
371 let (left, right) = s.split_at_mut(len);
372 let right = &mut right[0..len];
373 right.clone_from_slice(left);
374 for s in left {
375 *s *= u_j_inv;
376 }
377 for s in right {
378 *s *= u_j;
379 }
380 }
381 Ok(s)
382}
383
384fn inner_prod<F: PrimeField>(a: &[F], b: &[F]) -> Result<F, Error> {
385 if a.len() != b.len() {
386 return Err(Error::NotSameLength(
387 "a".to_string(),
388 a.len(),
389 "b".to_string(),
390 b.len(),
391 ));
392 }
393 let c = cfg_iter!(a)
394 .zip(cfg_iter!(b))
395 .map(|(a_i, b_i)| *a_i * b_i)
396 .sum();
397 Ok(c)
398}
399
400// g(x, u_1, u_2, ..., u_k) = <s, b>, naively takes linear, but can compute in log time through
401// g(x, u_1, u_2, ..., u_k) = \Prod u_i x^{2^i} + u_i^-1
402fn s_b_inner<F: PrimeField>(u: &[F], x: &F) -> Result<F, Error> {
403 let mut c: F = F::one();
404 let mut x_2_i = *x; // x_2_i is x^{2^i}, starting from x^{2^0}=x
405 for u_i in u.iter() {
406 c *= (*u_i * x_2_i)
407 + u_i
408 .inverse()
409 .ok_or(Error::Other("error on computing inverse".to_string()))?;
410 x_2_i *= x_2_i;
411 }
412 Ok(c)
413}
414
415// g(x, u_1, u_2, ..., u_k) = <s, b>, naively takes linear, but can compute in log time through
416// g(x, u_1, u_2, ..., u_k) = \Prod u_i x^{2^i} + u_i^-1
417fn s_b_inner_gadget<F: PrimeField, CF: PrimeField>(
418 u: &[NonNativeFieldVar<F, CF>],
419 x: &NonNativeFieldVar<F, CF>,
420) -> Result<NonNativeFieldVar<F, CF>, SynthesisError> {
421 let mut c: NonNativeFieldVar<F, CF> = NonNativeFieldVar::<F, CF>::one();
422 let mut x_2_i = x.clone(); // x_2_i is x^{2^i}, starting from x^{2^0}=x
423 for u_i in u.iter() {
424 c *= u_i.clone() * x_2_i.clone() + u_i.inverse()?;
425 x_2_i *= x_2_i.clone();
426 }
427 Ok(c)
428}
429
430pub type CF<C> = <<C as CurveGroup>::BaseField as Field>::BasePrimeField;
431
432pub struct ProofVar<C: CurveGroup, GC: CurveVar<C, CF<C>>> {
433 a: NonNativeFieldVar<C::ScalarField, CF<C>>,
434 l: Vec<NonNativeFieldVar<C::ScalarField, CF<C>>>,
435 r: Vec<NonNativeFieldVar<C::ScalarField, CF<C>>>,
436 L: Vec<GC>,
437 R: Vec<GC>,
438}
439impl<C, GC> AllocVar<Proof<C>, CF<C>> for ProofVar<C, GC>
440where
441 C: CurveGroup,
442 GC: CurveVar<C, CF<C>>,
443 <C as ark_ec::CurveGroup>::BaseField: PrimeField,
444{
445 fn new_variable<T: Borrow<Proof<C>>>(
446 cs: impl Into<Namespace<CF<C>>>,
447 f: impl FnOnce() -> Result<T, SynthesisError>,
448 mode: AllocationMode,
449 ) -> Result<Self, SynthesisError> {
450 f().and_then(|val| {
451 let cs = cs.into();
452
453 let a = NonNativeFieldVar::<C::ScalarField, CF<C>>::new_variable(
454 cs.clone(),
455 || Ok(val.borrow().a),
456 mode,
457 )?;
458 let l: Vec<NonNativeFieldVar<C::ScalarField, CF<C>>> =
459 Vec::new_variable(cs.clone(), || Ok(val.borrow().l.clone()), mode)?;
460 let r: Vec<NonNativeFieldVar<C::ScalarField, CF<C>>> =
461 Vec::new_variable(cs.clone(), || Ok(val.borrow().r.clone()), mode)?;
462 let L: Vec<GC> = Vec::new_variable(cs.clone(), || Ok(val.borrow().L.clone()), mode)?;
463 let R: Vec<GC> = Vec::new_variable(cs.clone(), || Ok(val.borrow().R.clone()), mode)?;
464
465 Ok(Self { a, l, r, L, R })
466 })
467 }
468}
469
470/// IPAGadget implements the circuit that verifies an IPA Proof. The `H` parameter indicates if to
471/// use the commitment in hiding mode or not, reducing a bit the number of constraints needed in
472/// the later case.
473pub struct IPAGadget<C, GC, const H: bool = false>
474where
475 C: CurveGroup,
476 GC: CurveVar<C, CF<C>>,
477{
478 _cf: PhantomData<CF<C>>,
479 _c: PhantomData<C>,
480 _gc: PhantomData<GC>,
481}
482
483impl<C, GC, const H: bool> IPAGadget<C, GC, H>
484where
485 C: CurveGroup,
486 GC: CurveVar<C, CF<C>>,
487
488 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
489 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
490{
491 /// Verify the IPA opening proof, K=log2(d), where d is the degree of the committed polynomial,
492 /// and H indicates if the commitment is in hiding mode and thus uses blinding factors, if not,
493 /// there are some constraints saved.
494 #[allow(clippy::too_many_arguments)]
495 pub fn verify<const K: usize>(
496 g: &Vec<GC>, // params.generators
497 h: &GC, // params.h
498 x: &NonNativeFieldVar<C::ScalarField, CF<C>>, // evaluation point, challenge
499 v: &NonNativeFieldVar<C::ScalarField, CF<C>>, // value at evaluation point
500 P: &GC, // commitment
501 p: &ProofVar<C, GC>,
502 r: &NonNativeFieldVar<C::ScalarField, CF<C>>, // blinding factor
503 u: &[NonNativeFieldVar<C::ScalarField, CF<C>>; K], // challenges
504 U: &GC, // challenge
505 ) -> Result<Boolean<CF<C>>, SynthesisError> {
506 if p.L.len() != K || p.R.len() != K {
507 return Err(SynthesisError::Unsatisfiable);
508 }
509
510 let P_ = P + U.scalar_mul_le(v.to_bits_le()?.iter())?;
511 let mut q_0 = P_;
512 let mut r = r.clone();
513
514 // compute u[i]^-1 once
515 let mut u_invs = vec![NonNativeFieldVar::<C::ScalarField, CF<C>>::zero(); u.len()];
516 for (j, u_j) in u.iter().enumerate() {
517 u_invs[j] = u_j.inverse()?;
518 }
519
520 // compute b & G from s
521 let s = build_s_gadget(u, &u_invs, K)?;
522 // b = <s, b_vec> = <s, [1, x, x^2, ..., x^K-1]>
523 let b = s_b_inner_gadget(u, x)?;
524 // ensure that generators.len() === s.len():
525 if g.len() < K {
526 return Err(SynthesisError::Unsatisfiable);
527 }
528
529 // msm: G=<G, s>
530 let mut G = GC::zero();
531 for (i, s_i) in s.iter().enumerate() {
532 G += g[i].scalar_mul_le(s_i.to_bits_le()?.iter())?;
533 }
534
535 for (j, u_j) in u.iter().enumerate() {
536 let uj2 = u_j.square()?;
537 let uj_inv2 = u_invs[j].square()?; // cheaper square than inversing the uj2
538
539 q_0 = q_0
540 + p.L[j].scalar_mul_le(uj2.to_bits_le()?.iter())?
541 + p.R[j].scalar_mul_le(uj_inv2.to_bits_le()?.iter())?;
542 if H {
543 r = r + &p.l[j] * &uj2 + &p.r[j] * &uj_inv2;
544 }
545 }
546
547 let q_1 = if H {
548 G.scalar_mul_le(p.a.to_bits_le()?.iter())?
549 + h.scalar_mul_le(r.to_bits_le()?.iter())?
550 + U.scalar_mul_le((p.a.clone() * b).to_bits_le()?.iter())?
551 } else {
552 G.scalar_mul_le(p.a.to_bits_le()?.iter())?
553 + U.scalar_mul_le((p.a.clone() * b).to_bits_le()?.iter())?
554 };
555 // q_0 == q_1
556 q_0.is_eq(&q_1)
557 }
558}
559
560#[cfg(test)]
561mod tests {
562 use ark_ec::Group;
563 use ark_pallas::{constraints::GVar, Fq, Fr, Projective};
564 use ark_r1cs_std::{alloc::AllocVar, bits::boolean::Boolean, eq::EqGadget};
565 use ark_relations::r1cs::ConstraintSystem;
566 use ark_std::UniformRand;
567 use std::ops::Mul;
568
569 use super::*;
570 use crate::transcript::poseidon::{poseidon_test_config, PoseidonTranscript};
571
572 #[test]
573 fn test_ipa() {
574 test_ipa_opt::<false>();
575 test_ipa_opt::<true>();
576 }
577 fn test_ipa_opt<const hiding: bool>() {
578 let mut rng = ark_std::test_rng();
579
580 const k: usize = 4;
581 const d: usize = 2_u64.pow(k as u32) as usize;
582
583 // setup params
584 let (params, _) = IPA::<Projective, hiding>::setup(&mut rng, d).unwrap();
585
586 let poseidon_config = poseidon_test_config::<Fr>();
587 // init Prover's transcript
588 let mut transcript_p = PoseidonTranscript::<Projective>::new(&poseidon_config);
589 // init Verifier's transcript
590 let mut transcript_v = PoseidonTranscript::<Projective>::new(&poseidon_config);
591
592 // a is the vector that we're committing
593 let a: Vec<Fr> = std::iter::repeat_with(|| Fr::rand(&mut rng))
594 .take(d)
595 .collect();
596 let r_blind: Fr = if hiding {
597 Fr::rand(&mut rng)
598 } else {
599 Fr::zero()
600 };
601 let cm = IPA::<Projective, hiding>::commit(¶ms, &a, &r_blind).unwrap();
602
603 let proof = IPA::<Projective, hiding>::prove(
604 ¶ms,
605 &mut transcript_p,
606 &cm,
607 &a,
608 &r_blind,
609 Some(&mut rng),
610 )
611 .unwrap();
612
613 IPA::<Projective, hiding>::verify(¶ms, &mut transcript_v, &cm, &proof).unwrap();
614 }
615
616 #[test]
617 fn test_ipa_gadget() {
618 test_ipa_gadget_opt::<false>();
619 test_ipa_gadget_opt::<true>();
620 }
621 fn test_ipa_gadget_opt<const hiding: bool>() {
622 let mut rng = ark_std::test_rng();
623
624 const k: usize = 3;
625 const d: usize = 2_u64.pow(k as u32) as usize;
626
627 // setup params
628 let (params, _) = IPA::<Projective, hiding>::setup(&mut rng, d).unwrap();
629
630 let poseidon_config = poseidon_test_config::<Fr>();
631 // init Prover's transcript
632 let mut transcript_p = PoseidonTranscript::<Projective>::new(&poseidon_config);
633 // init Verifier's transcript
634 let mut transcript_v = PoseidonTranscript::<Projective>::new(&poseidon_config);
635
636 let mut a: Vec<Fr> = std::iter::repeat_with(|| Fr::rand(&mut rng))
637 .take(d / 2)
638 .collect();
639 a.extend(vec![Fr::zero(); d / 2]);
640 let r_blind: Fr = if hiding {
641 Fr::rand(&mut rng)
642 } else {
643 Fr::zero()
644 };
645 let cm = IPA::<Projective, hiding>::commit(¶ms, &a, &r_blind).unwrap();
646
647 let proof = IPA::<Projective, hiding>::prove(
648 ¶ms,
649 &mut transcript_p,
650 &cm,
651 &a,
652 &r_blind,
653 Some(&mut rng),
654 )
655 .unwrap();
656
657 IPA::<Projective, hiding>::verify(¶ms, &mut transcript_v, &cm, &proof).unwrap();
658
659 // circuit
660 let cs = ConstraintSystem::<Fq>::new_ref();
661
662 let mut transcript_v = PoseidonTranscript::<Projective>::new(&poseidon_config);
663 transcript_v.absorb_point(&cm).unwrap();
664 let challenge = transcript_v.get_challenge(); // challenge value at which we evaluate
665 let s = transcript_v.get_challenge();
666 let U = Projective::generator().mul(s);
667 let mut u: Vec<Fr> = vec![Fr::zero(); k];
668 for i in (0..k).rev() {
669 transcript_v.absorb_point(&proof.0.L[i]).unwrap();
670 transcript_v.absorb_point(&proof.0.R[i]).unwrap();
671 u[i] = transcript_v.get_challenge();
672 }
673
674 // prepare inputs
675 let gVar = Vec::<GVar>::new_constant(cs.clone(), params.generators).unwrap();
676 let hVar = GVar::new_constant(cs.clone(), params.h).unwrap();
677 let challengeVar =
678 NonNativeFieldVar::<Fr, Fq>::new_witness(cs.clone(), || Ok(challenge)).unwrap();
679 let vVar = NonNativeFieldVar::<Fr, Fq>::new_witness(cs.clone(), || Ok(proof.1)).unwrap();
680 let cmVar = GVar::new_witness(cs.clone(), || Ok(cm)).unwrap();
681 let proofVar =
682 ProofVar::<Projective, GVar>::new_witness(cs.clone(), || Ok(proof.0)).unwrap();
683 let r_blindVar =
684 NonNativeFieldVar::<Fr, Fq>::new_witness(cs.clone(), || Ok(r_blind)).unwrap();
685 let uVar_vec = Vec::<NonNativeFieldVar<Fr, Fq>>::new_witness(cs.clone(), || Ok(u)).unwrap();
686 let uVar: [NonNativeFieldVar<Fr, Fq>; k] = uVar_vec.try_into().unwrap();
687 let UVar = GVar::new_witness(cs.clone(), || Ok(U)).unwrap();
688
689 let v = IPAGadget::<Projective, GVar, hiding>::verify::<k>(
690 &gVar,
691 &hVar,
692 &challengeVar,
693 &vVar,
694 &cmVar,
695 &proofVar,
696 &r_blindVar,
697 &uVar,
698 &UVar,
699 )
700 .unwrap();
701 v.enforce_equal(&Boolean::TRUE).unwrap();
702 assert!(cs.is_satisfied().unwrap());
703 }
704}