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