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 ipa(
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 P: &EdwardsProjective,
122 p: &Proof,
123 r: &Fr,
124 u: &[Fr],
125 U: &EdwardsProjective,
126 ) -> Result<bool, String> {
127 let mut q_0 = *P;
128 let mut r = *r;
129
130 // compute b & G from s
131 let s = build_s(u, self.d as usize);
132 let bs = powers_of(*x, self.d);
133 let b = inner_product_field(&s, &bs)?;
134 let G = inner_product_point(&s, &self.Gs)?;
135
136 #[allow(clippy::needless_range_loop)]
137 for j in 0..u.len() {
138 let uj2 = u[j].square();
139 let uj_inv2 = u[j].inverse().unwrap().square();
140
141 q_0 = q_0 + p.L[j].mul(uj2.into_repr()) + p.R[j].mul(uj_inv2.into_repr());
142 r = r + p.l[j] * uj2 + p.r[j] * uj_inv2;
143 }
144
145 let q_1 = G.mul(p.a.into_repr()) + self.H.mul(r.into_repr()) + U.mul((p.a * b).into_repr());
146
147 Ok(q_0 == q_1)
148 }
149}
150
151// s = (
152// u₁⁻¹ u₂⁻¹ … uₖ⁻¹,
153// u₁ u₂⁻¹ … uₖ⁻¹,
154// u₁⁻¹ u₂ … uₖ⁻¹,
155// u₁ u₂ … uₖ⁻¹,
156// ⋮ ⋮ ⋮
157// u₁ u₂ … uₖ
158// )
159fn build_s(u: &[Fr], d: usize) -> Vec<Fr> {
160 let k = (f64::from(d as u32).log2()) as usize;
161 let mut s: Vec<Fr> = vec![Fr::one(); d];
162 let mut t = d;
163 for j in (0..k).rev() {
164 t /= 2;
165 let mut c = 0;
166 #[allow(clippy::needless_range_loop)]
167 for i in 0..d {
168 if c < t {
169 s[i] *= u[j].inverse().unwrap();
170 } else {
171 s[i] *= u[j];
172 }
173 c += 1;
174 if c >= t * 2 {
175 c = 0;
176 }
177 }
178 }
179 s
180}
181
182fn inner_product_field(a: &[Fr], b: &[Fr]) -> Result<Fr, String> {
183 if a.len() != b.len() {
184 return Err(format!(
185 "a.len()={} must be equal to b.len()={}",
186 a.len(),
187 b.len()
188 ));
189 }
190 let mut c: Fr = Fr::zero();
191 for i in 0..a.len() {
192 c += a[i] * b[i];
193 }
194 Ok(c)
195}
196
197fn inner_product_point(a: &[Fr], b: &[EdwardsProjective]) -> Result<EdwardsProjective, String> {
198 if a.len() != b.len() {
199 return Err(format!(
200 "a.len()={} must be equal to b.len()={}",
201 a.len(),
202 b.len()
203 ));
204 }
205 let mut c: EdwardsProjective = EdwardsProjective::zero();
206 for i in 0..a.len() {
207 c += b[i].mul(a[i].into_repr());
208 }
209 Ok(c)
210}
211
212fn vec_add(a: &[Fr], b: &[Fr]) -> Result<Vec<Fr>, String> {
213 if a.len() != b.len() {
214 return Err(format!(
215 "a.len()={} must be equal to b.len()={}",
216 a.len(),
217 b.len()
218 ));
219 }
220 let mut c: Vec<Fr> = vec![Fr::zero(); a.len()];
221 for i in 0..a.len() {
222 c[i] = a[i] + b[i];
223 }
224 Ok(c)
225}
226fn vec_add_point(
227 a: &[EdwardsProjective],
228 b: &[EdwardsProjective],
229) -> Result<Vec<EdwardsProjective>, String> {
230 if a.len() != b.len() {
231 return Err(format!(
232 "a.len()={} must be equal to b.len()={}",
233 a.len(),
234 b.len()
235 ));
236 }
237 let mut c: Vec<EdwardsProjective> = vec![EdwardsProjective::zero(); a.len()];
238 for i in 0..a.len() {
239 c[i] = a[i] + b[i];
240 }
241 Ok(c)
242}
243
244fn vec_scalar_mul_field(a: &[Fr], b: &Fr) -> Vec<Fr> {
245 let mut c: Vec<Fr> = vec![Fr::zero(); a.len()];
246 for i in 0..a.len() {
247 c[i] = a[i] * b;
248 }
249 c
250}
251fn vec_scalar_mul_point(a: &[EdwardsProjective], b: &Fr) -> Vec<EdwardsProjective> {
252 let mut c: Vec<EdwardsProjective> = vec![EdwardsProjective::zero(); a.len()];
253 for i in 0..a.len() {
254 c[i] = a[i].mul(b.into_repr());
255 }
256 c
257}
258
259fn powers_of(x: Fr, d: u32) -> Vec<Fr> {
260 let mut c: Vec<Fr> = vec![Fr::zero(); d as usize];
261 c[0] = x;
262 for i in 1..d as usize {
263 c[i] = c[i - 1] * x;
264 }
265 c
266}
267
268#[cfg(test)]
269#[allow(non_snake_case)]
270mod tests {
271 use super::*;
272
273 #[test]
274 fn test_utils() {
275 let a = vec![
276 Fr::from(1 as u32),
277 Fr::from(2 as u32),
278 Fr::from(3 as u32),
279 Fr::from(4 as u32),
280 ];
281 let b = vec![
282 Fr::from(1 as u32),
283 Fr::from(2 as u32),
284 Fr::from(3 as u32),
285 Fr::from(4 as u32),
286 ];
287 let c = inner_product_field(&a, &b).unwrap();
288 assert_eq!(c, Fr::from(30 as u32));
289 }
290
291 #[test]
292 fn test_homomorphic_property() {
293 let d = 8;
294 let ipa = IPA::new(d);
295
296 let a = vec![
297 Fr::from(1 as u32),
298 Fr::from(2 as u32),
299 Fr::from(3 as u32),
300 Fr::from(4 as u32),
301 Fr::from(5 as u32),
302 Fr::from(6 as u32),
303 Fr::from(7 as u32),
304 Fr::from(8 as u32),
305 ];
306 let b = a.clone();
307
308 let mut rng = ark_std::rand::thread_rng();
309 let r = Fr::rand(&mut rng);
310 let s = Fr::rand(&mut rng);
311
312 let vc_a = ipa.commit(&a, r).unwrap();
313 let vc_b = ipa.commit(&b, s).unwrap();
314
315 let expected_vc_c = ipa.commit(&vec_add(&a, &b).unwrap(), r + s).unwrap();
316 let vc_c = vc_a + vc_b;
317 assert_eq!(vc_c, expected_vc_c);
318 }
319
320 #[test]
321 fn test_inner_product_argument_proof() {
322 let d = 8;
323 let mut ipa = IPA::new(d);
324
325 let a = vec![
326 Fr::from(1 as u32),
327 Fr::from(2 as u32),
328 Fr::from(3 as u32),
329 Fr::from(4 as u32),
330 Fr::from(5 as u32),
331 Fr::from(6 as u32),
332 Fr::from(7 as u32),
333 Fr::from(8 as u32),
334 ];
335
336 let x = Fr::from(3 as u32);
337 let b = powers_of(x, ipa.d);
338
339 let r = Fr::rand(&mut ipa.rng);
340
341 let mut P = ipa.commit(&a, r).unwrap();
342 let v = inner_product_field(&a, &b).unwrap();
343
344 let U = EdwardsProjective::rand(&mut ipa.rng);
345
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
352 P = P + U.mul(v.into_repr());
353
354 let proof = ipa.ipa(&a, &b, &u, &U).unwrap();
355 let verif = ipa.verify(&x, &P, &proof, &r, &u, &U).unwrap();
356 assert!(verif);
357 }
358}