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}; // BigInteger
5use ark_std::{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 b: Fr, // TODO not needed
19 G: EdwardsProjective, // TODO not needed
20 l: Vec<Fr>,
21 r: Vec<Fr>,
22 L: Vec<EdwardsProjective>,
23 R: Vec<EdwardsProjective>,
24}
25
26#[allow(non_snake_case)]
27#[allow(clippy::many_single_char_names)]
28impl IPA {
29 pub fn new(d: u32) -> IPA {
30 let mut rng = ark_std::rand::thread_rng();
31
32 let mut gs: Vec<EdwardsProjective> = Vec::new();
33 for _ in 0..d {
34 gs.push(EdwardsProjective::rand(&mut rng));
35 }
36
37 IPA {
38 d,
39 H: EdwardsProjective::rand(&mut rng),
40 Gs: gs,
41 rng,
42 }
43 }
44
45 pub fn commit(&self, a: &[Fr], r: Fr) -> EdwardsProjective {
46 inner_product_point(a, &self.Gs) + self.H.mul(r.into_repr())
47 }
48
49 pub fn ipa(&mut self, a: &[Fr], b: &[Fr], u: &[Fr], U: &EdwardsProjective) -> Proof {
50 let mut a = a.to_owned();
51 let mut b = b.to_owned();
52 let mut G = self.Gs.clone();
53
54 let k = (f64::from(self.d as u32).log2()) as usize;
55 let mut l: Vec<Fr> = vec![Fr::zero(); k];
56 let mut r: Vec<Fr> = vec![Fr::zero(); k];
57 let mut L: Vec<EdwardsProjective> = vec![EdwardsProjective::zero(); k];
58 let mut R: Vec<EdwardsProjective> = vec![EdwardsProjective::zero(); k];
59
60 for j in (0..k).rev() {
61 let m = a.len() / 2;
62 let a_lo = a[..m].to_vec();
63 let a_hi = a[m..].to_vec();
64 let b_lo = b[..m].to_vec();
65 let b_hi = b[m..].to_vec();
66 let G_lo = G[..m].to_vec();
67 let G_hi = G[m..].to_vec();
68
69 l[j] = Fr::rand(&mut self.rng);
70 r[j] = Fr::rand(&mut self.rng);
71
72 L[j] = inner_product_point(&a_lo, &G_hi)
73 + self.H.mul(l[j].into_repr())
74 + U.mul(inner_product_field(&a_lo, &b_hi).into_repr());
75 R[j] = inner_product_point(&a_hi, &G_lo)
76 + self.H.mul(r[j].into_repr())
77 + U.mul(inner_product_field(&a_hi, &b_lo).into_repr());
78
79 let uj = u[j];
80 let uj_inv = u[j].inverse().unwrap();
81
82 a = vec_add(
83 &vec_scalar_mul_field(&a_lo, &uj),
84 &vec_scalar_mul_field(&a_hi, &uj_inv),
85 );
86 b = vec_add(
87 &vec_scalar_mul_field(&b_lo, &uj_inv),
88 &vec_scalar_mul_field(&b_hi, &uj),
89 );
90 G = vec_add_point(
91 &vec_scalar_mul_point(&G_lo, &uj_inv),
92 &vec_scalar_mul_point(&G_hi, &uj),
93 );
94 }
95
96 // TODO assert len a,b,G == 1
97
98 Proof {
99 a: a[0],
100 b: b[0],
101 G: G[0],
102 l,
103 r,
104 L,
105 R,
106 }
107 }
108 pub fn verify(
109 &self,
110 P: &EdwardsProjective,
111 p: &Proof,
112 r: &Fr,
113 u: &[Fr],
114 U: &EdwardsProjective,
115 ) -> bool {
116 let mut q_0 = *P;
117 let mut r = *r;
118
119 // TODO compute b & G without getting them in the proof package
120
121 #[allow(clippy::needless_range_loop)]
122 for j in 0..u.len() {
123 let uj2 = u[j].square();
124 let uj_inv2 = u[j].inverse().unwrap().square();
125
126 q_0 = q_0 + p.L[j].mul(uj2.into_repr()) + p.R[j].mul(uj_inv2.into_repr());
127 r = r + p.l[j] * uj2 + p.r[j] * uj_inv2;
128 }
129
130 let q_1 =
131 p.G.mul(p.a.into_repr()) + self.H.mul(r.into_repr()) + U.mul((p.a * p.b).into_repr());
132
133 q_0 == q_1
134 }
135}
136
137fn inner_product_field(a: &[Fr], b: &[Fr]) -> Fr {
138 // TODO require lens equal
139 let mut c: Fr = Fr::zero();
140 for i in 0..a.len() {
141 c += a[i] * b[i];
142 }
143 c
144}
145
146fn inner_product_point(a: &[Fr], b: &[EdwardsProjective]) -> EdwardsProjective {
147 // TODO require lens equal
148 let mut c: EdwardsProjective = EdwardsProjective::zero();
149 for i in 0..a.len() {
150 c += b[i].mul(a[i].into_repr());
151 }
152 c
153}
154
155fn vec_add(a: &[Fr], b: &[Fr]) -> Vec<Fr> {
156 // TODO require len equal
157 let mut c: Vec<Fr> = vec![Fr::zero(); a.len()];
158 for i in 0..a.len() {
159 c[i] = a[i] + b[i];
160 }
161 c
162}
163fn vec_add_point(a: &[EdwardsProjective], b: &[EdwardsProjective]) -> Vec<EdwardsProjective> {
164 // TODO require len equal
165 let mut c: Vec<EdwardsProjective> = vec![EdwardsProjective::zero(); a.len()];
166 for i in 0..a.len() {
167 c[i] = a[i] + b[i];
168 }
169 c
170}
171
172fn vec_scalar_mul_field(a: &[Fr], b: &Fr) -> Vec<Fr> {
173 let mut c: Vec<Fr> = vec![Fr::zero(); a.len()];
174 for i in 0..a.len() {
175 c[i] = a[i] * b;
176 }
177 c
178}
179fn vec_scalar_mul_point(a: &[EdwardsProjective], b: &Fr) -> Vec<EdwardsProjective> {
180 let mut c: Vec<EdwardsProjective> = vec![EdwardsProjective::zero(); a.len()];
181 for i in 0..a.len() {
182 c[i] = a[i].mul(b.into_repr());
183 }
184 c
185}
186
187#[allow(dead_code)]
188fn powers_of(x: Fr, d: u32) -> Vec<Fr> {
189 let mut c: Vec<Fr> = vec![Fr::zero(); d as usize];
190 c[0] = x;
191 for i in 1..d as usize {
192 // TODO redo better
193 c[i] = c[i - 1] * x;
194 }
195 c
196}
197
198// fn inner_product<T>(a: Vec<T>, b: Vec<T>) -> T {
199// // require lens equal
200// let mut c: T = Zero();
201// for i in 0..a.len() {
202// c = c + a[i] * b[i];
203// }
204// c
205// }
206
207#[cfg(test)]
208#[allow(non_snake_case)]
209mod tests {
210 use super::*;
211
212 #[test]
213 fn test_utils() {
214 // let a = Fr::from(1 as u32);
215 // let b = Fr::one();
216 // println!("A: {:?}", Fr::from(1 as u32));
217 // println!("A: {:?}", a);
218 // println!("B: {:?}", b);
219
220 let a = vec![
221 Fr::from(1 as u32),
222 Fr::from(2 as u32),
223 Fr::from(3 as u32),
224 Fr::from(4 as u32),
225 ];
226 let b = vec![
227 Fr::from(1 as u32),
228 Fr::from(2 as u32),
229 Fr::from(3 as u32),
230 Fr::from(4 as u32),
231 ];
232 let c = inner_product_field(&a, &b);
233 println!("c: {:?}", c);
234
235 // let result = 2 + 2;
236 // assert_eq!(result, 4);
237 }
238
239 #[test]
240 fn test_inner_product() {
241 let d = 8;
242 let mut ipa = IPA::new(d);
243
244 let a = vec![
245 Fr::from(1 as u32),
246 Fr::from(2 as u32),
247 Fr::from(3 as u32),
248 Fr::from(4 as u32),
249 Fr::from(5 as u32),
250 Fr::from(6 as u32),
251 Fr::from(7 as u32),
252 Fr::from(8 as u32),
253 ];
254
255 let x = Fr::from(3 as u32);
256 let b = powers_of(x, ipa.d);
257
258 let r = Fr::rand(&mut ipa.rng);
259
260 let mut P = ipa.commit(&a, r);
261 let v = inner_product_field(&a, &b);
262
263 let U = EdwardsProjective::rand(&mut ipa.rng);
264
265 let k = (f64::from(ipa.d as u32).log2()) as usize;
266 let mut u: Vec<Fr> = vec![Fr::zero(); k];
267 for j in 0..k {
268 u[j] = Fr::rand(&mut ipa.rng);
269 }
270
271 P = P + U.mul(v.into_repr());
272
273 let proof = ipa.ipa(&a, &b, &u, &U);
274 let verif = ipa.verify(&P, &proof, &r, &u, &U);
275 assert!(verif);
276 }
277}