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