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