ipa-rs/src/lib.rs
src/lib.rsRaw
1extern crate ark_ed_on_bn254;
2use ark_ec::ProjectiveCurve;
3use ark_ed_on_bn254::{EdwardsProjective, Fr};
4use ark_ff::{fields::PrimeField, Field};
5use ark_std::{One, UniformRand, Zero};
6
7#[allow(non_snake_case)]
8pub struct IPA {
9 d: u32,
10 H: EdwardsProjective,
11 Gs: Vec<EdwardsProjective>,
12 rng: rand::rngs::ThreadRng,
13}
14
15#[allow(non_snake_case)]
16pub struct Proof {
17 a: Fr,
18 l: Vec<Fr>,
19 r: Vec<Fr>,
20 L: Vec<EdwardsProjective>,
21 R: Vec<EdwardsProjective>,
22}
23
24#[allow(non_snake_case)]
25#[allow(clippy::many_single_char_names)]
26impl IPA {
27 pub fn new(d: u32) -> IPA {
28 let mut rng = ark_std::rand::thread_rng();
29
30 let mut gs: Vec<EdwardsProjective> = Vec::new();
31 for _ in 0..d {
32 gs.push(EdwardsProjective::rand(&mut rng));
33 }
34
35 IPA {
36 d,
37 H: EdwardsProjective::rand(&mut rng),
38 Gs: gs,
39 rng,
40 }
41 }
42
43 pub fn commit(&self, a: &[Fr], r: Fr) -> Result<EdwardsProjective, String> {
44 Ok(inner_product_point(a, &self.Gs)? + self.H.mul(r.into_repr()))
45 }
46
47 pub fn prove(
48 &mut self,
49 a: &[Fr],
50 b: &[Fr],
51 u: &[Fr],
52 U: &EdwardsProjective,
53 ) -> Result<Proof, String> {
54 let mut a = a.to_owned();
55 let mut b = b.to_owned();
56 let mut G = self.Gs.clone();
57
58 let k = (f64::from(self.d as u32).log2()) as usize;
59 let mut l: Vec<Fr> = vec![Fr::zero(); k];
60 let mut r: Vec<Fr> = vec![Fr::zero(); k];
61 let mut L: Vec<EdwardsProjective> = vec![EdwardsProjective::zero(); k];
62 let mut R: Vec<EdwardsProjective> = vec![EdwardsProjective::zero(); k];
63
64 for j in (0..k).rev() {
65 let m = a.len() / 2;
66 let a_lo = a[..m].to_vec();
67 let a_hi = a[m..].to_vec();
68 let b_lo = b[..m].to_vec();
69 let b_hi = b[m..].to_vec();
70 let G_lo = G[..m].to_vec();
71 let G_hi = G[m..].to_vec();
72
73 l[j] = Fr::rand(&mut self.rng);
74 r[j] = Fr::rand(&mut self.rng);
75
76 L[j] = inner_product_point(&a_lo, &G_hi)?
77 + self.H.mul(l[j].into_repr())
78 + U.mul(inner_product_field(&a_lo, &b_hi)?.into_repr());
79 R[j] = inner_product_point(&a_hi, &G_lo)?
80 + self.H.mul(r[j].into_repr())
81 + U.mul(inner_product_field(&a_hi, &b_lo)?.into_repr());
82
83 let uj = u[j];
84 let uj_inv = u[j].inverse().unwrap();
85
86 a = vec_add(
87 &vec_scalar_mul_field(&a_lo, &uj),
88 &vec_scalar_mul_field(&a_hi, &uj_inv),
89 )?;
90 b = vec_add(
91 &vec_scalar_mul_field(&b_lo, &uj_inv),
92 &vec_scalar_mul_field(&b_hi, &uj),
93 )?;
94 G = vec_add_point(
95 &vec_scalar_mul_point(&G_lo, &uj_inv),
96 &vec_scalar_mul_point(&G_hi, &uj),
97 )?;
98 }
99
100 if a.len() != 1 {
101 return Err(format!("a.len() should be 1, a.len()={}", a.len()));
102 }
103 if b.len() != 1 {
104 return Err(format!("b.len() should be 1, b.len()={}", b.len()));
105 }
106 if G.len() != 1 {
107 return Err(format!("G.len() should be 1, G.len()={}", G.len()));
108 }
109
110 Ok(Proof {
111 a: a[0],
112 l,
113 r,
114 L,
115 R,
116 })
117 }
118 pub fn verify(
119 &self,
120 x: &Fr,
121 v: &Fr,
122 P: &EdwardsProjective,
123 p: &Proof,
124 r: &Fr,
125 u: &[Fr],
126 U: &EdwardsProjective,
127 ) -> Result<bool, String> {
128 let P = *P + U.mul(v.into_repr());
129
130 let mut q_0 = P;
131 let mut r = *r;
132
133 // compute b & G from s
134 let s = build_s(u, self.d as usize);
135 let bs = powers_of(*x, self.d);
136 let b = inner_product_field(&s, &bs)?;
137 let G = inner_product_point(&s, &self.Gs)?;
138
139 #[allow(clippy::needless_range_loop)]
140 for j in 0..u.len() {
141 let uj2 = u[j].square();
142 let uj_inv2 = u[j].inverse().unwrap().square();
143
144 q_0 = q_0 + p.L[j].mul(uj2.into_repr()) + p.R[j].mul(uj_inv2.into_repr());
145 r = r + p.l[j] * uj2 + p.r[j] * uj_inv2;
146 }
147
148 let q_1 = G.mul(p.a.into_repr()) + self.H.mul(r.into_repr()) + U.mul((p.a * b).into_repr());
149
150 Ok(q_0 == q_1)
151 }
152}
153
154// s = (
155// u₁⁻¹ u₂⁻¹ … uₖ⁻¹,
156// u₁ u₂⁻¹ … uₖ⁻¹,
157// u₁⁻¹ u₂ … uₖ⁻¹,
158// u₁ u₂ … uₖ⁻¹,
159// ⋮ ⋮ ⋮
160// u₁ u₂ … uₖ
161// )
162fn build_s(u: &[Fr], d: usize) -> Vec<Fr> {
163 let k = (f64::from(d as u32).log2()) as usize;
164 let mut s: Vec<Fr> = vec![Fr::one(); d];
165 let mut t = d;
166 for j in (0..k).rev() {
167 t /= 2;
168 let mut c = 0;
169 #[allow(clippy::needless_range_loop)]
170 for i in 0..d {
171 if c < t {
172 s[i] *= u[j].inverse().unwrap();
173 } else {
174 s[i] *= u[j];
175 }
176 c += 1;
177 if c >= t * 2 {
178 c = 0;
179 }
180 }
181 }
182 s
183}
184
185fn inner_product_field(a: &[Fr], b: &[Fr]) -> Result<Fr, String> {
186 if a.len() != b.len() {
187 return Err(format!(
188 "a.len()={} must be equal to b.len()={}",
189 a.len(),
190 b.len()
191 ));
192 }
193 let mut c: Fr = Fr::zero();
194 for i in 0..a.len() {
195 c += a[i] * b[i];
196 }
197 Ok(c)
198}
199
200fn inner_product_point(a: &[Fr], b: &[EdwardsProjective]) -> Result<EdwardsProjective, String> {
201 if a.len() != b.len() {
202 return Err(format!(
203 "a.len()={} must be equal to b.len()={}",
204 a.len(),
205 b.len()
206 ));
207 }
208 let mut c: EdwardsProjective = EdwardsProjective::zero();
209 for i in 0..a.len() {
210 c += b[i].mul(a[i].into_repr());
211 }
212 Ok(c)
213}
214
215fn vec_add(a: &[Fr], b: &[Fr]) -> Result<Vec<Fr>, String> {
216 if a.len() != b.len() {
217 return Err(format!(
218 "a.len()={} must be equal to b.len()={}",
219 a.len(),
220 b.len()
221 ));
222 }
223 let mut c: Vec<Fr> = vec![Fr::zero(); a.len()];
224 for i in 0..a.len() {
225 c[i] = a[i] + b[i];
226 }
227 Ok(c)
228}
229fn vec_add_point(
230 a: &[EdwardsProjective],
231 b: &[EdwardsProjective],
232) -> Result<Vec<EdwardsProjective>, String> {
233 if a.len() != b.len() {
234 return Err(format!(
235 "a.len()={} must be equal to b.len()={}",
236 a.len(),
237 b.len()
238 ));
239 }
240 let mut c: Vec<EdwardsProjective> = vec![EdwardsProjective::zero(); a.len()];
241 for i in 0..a.len() {
242 c[i] = a[i] + b[i];
243 }
244 Ok(c)
245}
246
247fn vec_scalar_mul_field(a: &[Fr], b: &Fr) -> Vec<Fr> {
248 let mut c: Vec<Fr> = vec![Fr::zero(); a.len()];
249 for i in 0..a.len() {
250 c[i] = a[i] * b;
251 }
252 c
253}
254fn vec_scalar_mul_point(a: &[EdwardsProjective], b: &Fr) -> Vec<EdwardsProjective> {
255 let mut c: Vec<EdwardsProjective> = vec![EdwardsProjective::zero(); a.len()];
256 for i in 0..a.len() {
257 c[i] = a[i].mul(b.into_repr());
258 }
259 c
260}
261
262fn powers_of(x: Fr, d: u32) -> Vec<Fr> {
263 let mut c: Vec<Fr> = vec![Fr::zero(); d as usize];
264 c[0] = x;
265 for i in 1..d as usize {
266 c[i] = c[i - 1] * x;
267 }
268 c
269}
270
271#[cfg(test)]
272#[allow(non_snake_case)]
273mod tests {
274 use super::*;
275
276 #[test]
277 fn test_utils() {
278 let a = vec![
279 Fr::from(1 as u32),
280 Fr::from(2 as u32),
281 Fr::from(3 as u32),
282 Fr::from(4 as u32),
283 ];
284 let b = vec![
285 Fr::from(1 as u32),
286 Fr::from(2 as u32),
287 Fr::from(3 as u32),
288 Fr::from(4 as u32),
289 ];
290 let c = inner_product_field(&a, &b).unwrap();
291 assert_eq!(c, Fr::from(30 as u32));
292 }
293
294 #[test]
295 fn test_homomorphic_property() {
296 let d = 8;
297 let ipa = IPA::new(d);
298
299 let a = vec![
300 Fr::from(1 as u32),
301 Fr::from(2 as u32),
302 Fr::from(3 as u32),
303 Fr::from(4 as u32),
304 Fr::from(5 as u32),
305 Fr::from(6 as u32),
306 Fr::from(7 as u32),
307 Fr::from(8 as u32),
308 ];
309 let b = a.clone();
310
311 let mut rng = ark_std::rand::thread_rng();
312 let r = Fr::rand(&mut rng);
313 let s = Fr::rand(&mut rng);
314
315 let vc_a = ipa.commit(&a, r).unwrap();
316 let vc_b = ipa.commit(&b, s).unwrap();
317
318 let expected_vc_c = ipa.commit(&vec_add(&a, &b).unwrap(), r + s).unwrap();
319 let vc_c = vc_a + vc_b;
320 assert_eq!(vc_c, expected_vc_c);
321 }
322
323 #[test]
324 fn test_inner_product_argument_proof() {
325 let d = 8;
326 let mut ipa = IPA::new(d);
327
328 let a = vec![
329 Fr::from(1 as u32),
330 Fr::from(2 as u32),
331 Fr::from(3 as u32),
332 Fr::from(4 as u32),
333 Fr::from(5 as u32),
334 Fr::from(6 as u32),
335 Fr::from(7 as u32),
336 Fr::from(8 as u32),
337 ];
338
339 let r = Fr::rand(&mut ipa.rng);
340
341 // prover commits
342 let P = ipa.commit(&a, r).unwrap();
343
344 // verifier sets challenges
345 let U = EdwardsProjective::rand(&mut ipa.rng);
346 let k = (f64::from(ipa.d as u32).log2()) as usize;
347 let mut u: Vec<Fr> = vec![Fr::zero(); k];
348 for j in 0..k {
349 u[j] = Fr::rand(&mut ipa.rng);
350 }
351 let x = Fr::from(3 as u32);
352
353 // prover opens at the challenges
354 let b = powers_of(x, ipa.d);
355 let v = inner_product_field(&a, &b).unwrap();
356 let proof = ipa.prove(&a, &b, &u, &U).unwrap();
357
358 // verifier
359 let verif = ipa.verify(&x, &v, &P, &proof, &r, &u, &U).unwrap();
360 assert!(verif);
361 }
362}