babyjubjub-ark/src/lib.rs
src/lib.rsRaw
1#[macro_use]
2extern crate arrayref;
3extern crate generic_array;
4extern crate mimc_rs;
5extern crate num;
6extern crate num_bigint;
7extern crate num_traits;
8extern crate rand;
9
10use blake2::{Blake2b, Digest};
11use mimc_rs::Mimc7;
12
13use num_bigint::{BigInt, RandBigInt, Sign, ToBigInt};
14use num_traits::{One, Zero};
15
16use generic_array::GenericArray;
17
18mod utils;
19
20#[derive(Clone, Debug)]
21pub struct Point {
22 pub x: BigInt,
23 pub y: BigInt,
24}
25
26pub struct Signature {
27 r_b8: Point,
28 s: BigInt,
29}
30
31pub struct PrivateKey {
32 bbjj: Babyjubjub,
33 key: BigInt,
34}
35
36impl PrivateKey {
37 pub fn public(&self) -> Point {
38 // https://tools.ietf.org/html/rfc8032#section-5.1.5
39 let pk = &self.bbjj.mul_scalar(self.bbjj.b8.clone(), self.key.clone());
40 pk.clone()
41 }
42
43 pub fn sign(&self, msg: BigInt) -> Signature {
44 // https://tools.ietf.org/html/rfc8032#section-5.1.6
45 let mut hasher = Blake2b::new();
46 let (_, sk_bytes) = self.key.to_bytes_be();
47 hasher.input(sk_bytes);
48 let mut h = hasher.result(); // h: hash(sk)
49 // s: h[32:64]
50 let s = GenericArray::<u8, generic_array::typenum::U32>::from_mut_slice(&mut h[32..64]);
51 let (_, msg_bytes) = msg.to_bytes_be();
52 let r_bytes = utils::concatenate_arrays(s, &msg_bytes);
53 let mut r = BigInt::from_bytes_be(Sign::Plus, &r_bytes[..]);
54 r = utils::modulus(&r, &self.bbjj.sub_order);
55 let r8: Point = self.bbjj.mul_scalar(self.bbjj.b8.clone(), r.clone());
56 let a = &self.public();
57
58 let hm_input = vec![r8.x.clone(), r8.y.clone(), a.x.clone(), a.y.clone(), msg];
59 let mimc7 = Mimc7::new();
60 let hm = mimc7.hash(hm_input);
61
62 let mut s = &self.key << 3;
63 s = hm * s;
64 s = r + s;
65 s = s % &self.bbjj.sub_order;
66
67 Signature {
68 r_b8: r8.clone(),
69 s: s,
70 }
71 }
72}
73
74pub struct Babyjubjub {
75 d: BigInt,
76 a: BigInt,
77 q: BigInt,
78 b8: Point,
79 // order: BigInt,
80 sub_order: BigInt,
81}
82
83impl Babyjubjub {
84 pub fn new() -> Babyjubjub {
85 let d: BigInt = BigInt::parse_bytes(b"168696", 10).unwrap();
86 let a: BigInt = BigInt::parse_bytes(b"168700", 10).unwrap();
87 let q: BigInt = BigInt::parse_bytes(
88 b"21888242871839275222246405745257275088548364400416034343698204186575808495617",
89 10,
90 )
91 .unwrap();
92 let b8: Point = Point {
93 x: BigInt::parse_bytes(
94 b"5299619240641551281634865583518297030282874472190772894086521144482721001553",
95 10,
96 )
97 .unwrap(),
98 y: BigInt::parse_bytes(
99 b"16950150798460657717958625567821834550301663161624707787222815936182638968203",
100 10,
101 )
102 .unwrap(),
103 };
104 let order: BigInt = BigInt::parse_bytes(
105 b"21888242871839275222246405745257275088614511777268538073601725287587578984328",
106 10,
107 )
108 .unwrap();
109 let sub_order: BigInt = &order >> 3;
110
111 Babyjubjub {
112 d: d,
113 a: a,
114 q: q,
115 b8: b8,
116 // order: order,
117 sub_order: sub_order,
118 }
119 }
120
121 pub fn add(&self, p: &Point, q: &Point) -> Point {
122 // x = (x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2))
123 // y = (y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2))
124
125 // x = (x1 * y2 + y1 * x2) / (1 + d * x1 * y1 * y2)
126 let one: BigInt = One::one();
127 let x_num: BigInt = &p.x * &q.y + &p.y * &q.x;
128 let x_den: BigInt = &one + &self.d * &p.x * &q.x * &p.y * &q.y;
129 let x_den_inv = utils::modinv(&x_den, &self.q);
130 let x: BigInt = utils::modulus(&(&x_num * &x_den_inv), &self.q);
131
132 // y = (y1 * y2 - a * x1 * x2) / (1 - d * x1 * x2 * y1 * y2)
133 let y_num = &p.y * &q.y - &self.a * &p.x * &q.x;
134 let y_den = utils::modulus(&(&one - &self.d * &p.x * &q.x * &p.y * &q.y), &self.q);
135 let y_den_inv = utils::modinv(&y_den, &self.q);
136 let y: BigInt = utils::modulus(&(&y_num * &y_den_inv), &self.q);
137
138 Point { x: x, y: y }
139 }
140
141 pub fn mul_scalar(&self, p: Point, n: BigInt) -> Point {
142 // TODO use & in p and n to avoid clones on function call
143 let mut r: Point = Point {
144 x: Zero::zero(),
145 y: One::one(),
146 };
147 let mut rem: BigInt = n;
148 let mut exp: Point = p;
149
150 let zero: BigInt = Zero::zero();
151 let one: BigInt = One::one();
152 while rem != zero {
153 let is_odd = &rem & &one == one;
154 if is_odd == true {
155 r = self.add(&r, &exp);
156 }
157 exp = self.add(&exp, &exp);
158 rem = rem >> 1;
159 }
160 r.x = utils::modulus(&r.x, &self.q);
161 r.y = utils::modulus(&r.y, &self.q);
162 r
163 }
164
165 pub fn compress_point(&self, p: &Point) -> [u8; 32] {
166 let mut r: [u8; 32];
167 let (_, y_bytes) = p.y.to_bytes_le();
168 r = *array_ref!(y_bytes, 0, 32);
169 if &p.x > &(&self.q >> 1) {
170 r[31] = r[31] | 0x80;
171 }
172 r
173 }
174
175 pub fn decompress_point(&self, bb: [u8; 32]) -> Point {
176 // https://tools.ietf.org/html/rfc8032#section-5.2.3
177 let mut sign: bool = false;
178 let mut b = bb.clone();
179 if b[31] & 0x80 != 0x00 {
180 sign = true;
181 b[31] = b[31] & 0x7F;
182 }
183 let y: BigInt = BigInt::from_bytes_le(Sign::Plus, &b[..]);
184 if y >= self.q {
185 // println!("ERROR0");
186 }
187 let one: BigInt = One::one();
188
189 // x^2 = (1 - y^2) / (a - d * y^2) (mod p)
190 let mut x: BigInt = utils::modulus(
191 &((one - utils::modulus(&(&y * &y), &self.q))
192 * utils::modinv(
193 &utils::modulus(
194 &(&self.a - utils::modulus(&(&self.d * (&y * &y)), &self.q)),
195 &self.q,
196 ),
197 &self.q,
198 )),
199 &self.q,
200 );
201 x = utils::modsqrt(&x, &self.q);
202
203 if (sign && x >= Zero::zero()) || (!sign && x < Zero::zero()) {
204 x = x * -1.to_bigint().unwrap();
205 }
206 x = utils::modulus(&x, &self.q);
207 Point { x: x, y: y }
208 }
209
210 pub fn compress_sig(&self, sig: &Signature) -> [u8; 64] {
211 let mut b: Vec<u8> = Vec::new();
212 b.append(&mut self.compress_point(&sig.r_b8).to_vec());
213 // let (_, mut s_bytes) = sig.s.to_bytes_le();
214 let (_, mut s_bytes) = sig.s.to_bytes_le();
215 println!("sbytes LENGTH {:?}", s_bytes.len());
216 // let mut s_32bytes: [u8; 32] = [0; 32];
217 // s_32bytes[..].copy_from_slice(&s_bytes[..]);
218 b.append(&mut s_bytes);
219 let mut r: [u8; 64] = [0; 64];
220 // r = *array_ref!(b, 0, 64);
221 // r.copy_from_slice(&b[..]);
222 println!("b LENGTH {:?}", b.len());
223 // if b.len() < 64 {
224 // // let diff = 64 - b.len();
225 // println!("less than 64, add padding");
226 // let e: [u8; 1] = [0];
227 // b.append(&mut e.to_vec());
228 // }
229 r.copy_from_slice(&b[..]);
230 println!("r {:?}", r.len());
231 r
232 }
233
234 pub fn decompress_sig(&self, b: &[u8; 64]) -> Signature {
235 let r_b8_bytes: [u8; 32] = *array_ref!(b[..32], 0, 32);
236 let s: BigInt = BigInt::from_bytes_le(Sign::Plus, &b[32..]);
237 let r_b8 = &self.decompress_point(r_b8_bytes);
238 Signature {
239 r_b8: r_b8.clone(),
240 s: s,
241 }
242 }
243
244 pub fn new_key(&self) -> PrivateKey {
245 // https://tools.ietf.org/html/rfc8032#section-5.1.5
246 let mut rng = rand::thread_rng();
247 let sk_raw = rng.gen_biguint(1024).to_bigint().unwrap();
248
249 let mut hasher = Blake2b::new();
250 let (_, sk_raw_bytes) = sk_raw.to_bytes_be();
251 hasher.input(sk_raw_bytes);
252 let mut h = hasher.result();
253
254 h[0] = h[0] & 0xF8;
255 h[31] = h[31] & 0x7F;
256 h[31] = h[31] | 0x40;
257
258 let sk = BigInt::from_bytes_le(Sign::Plus, &h[..]);
259
260 let bbjj_new = Babyjubjub {
261 d: self.d.clone(),
262 a: self.a.clone(),
263 q: self.q.clone(),
264 b8: self.b8.clone(),
265 sub_order: self.sub_order.clone(),
266 };
267 PrivateKey {
268 bbjj: bbjj_new,
269 key: sk,
270 }
271 }
272
273 pub fn verify(&self, pk: Point, sig: Signature, msg: BigInt) -> bool {
274 let hm_input = vec![
275 sig.r_b8.x.clone(),
276 sig.r_b8.y.clone(),
277 pk.x.clone(),
278 pk.y.clone(),
279 msg,
280 ];
281 let mimc7 = Mimc7::new();
282 let hm = mimc7.hash(hm_input);
283 let l = self.mul_scalar(self.b8.clone(), sig.s);
284 let r = self.add(&sig.r_b8, &self.mul_scalar(pk, 8.to_bigint().unwrap() * hm));
285 if l.x == r.x && l.y == r.y {
286 return true;
287 }
288 false
289 }
290}
291
292#[cfg(test)]
293mod tests {
294 use super::*;
295 extern crate rustc_hex;
296 use rustc_hex::ToHex;
297
298 #[test]
299 fn test_add_same_point() {
300 let p: Point = Point {
301 x: BigInt::parse_bytes(
302 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
303 10,
304 )
305 .unwrap(),
306 y: BigInt::parse_bytes(
307 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
308 10,
309 )
310 .unwrap(),
311 };
312 let q: Point = Point {
313 x: BigInt::parse_bytes(
314 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
315 10,
316 )
317 .unwrap(),
318 y: BigInt::parse_bytes(
319 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
320 10,
321 )
322 .unwrap(),
323 };
324 let bbjj = Babyjubjub::new();
325 let res = bbjj.add(&p, &q);
326 assert_eq!(
327 res.x.to_string(),
328 "6890855772600357754907169075114257697580319025794532037257385534741338397365"
329 );
330 assert_eq!(
331 res.y.to_string(),
332 "4338620300185947561074059802482547481416142213883829469920100239455078257889"
333 );
334 }
335 #[test]
336 fn test_add_different_points() {
337 let p: Point = Point {
338 x: BigInt::parse_bytes(
339 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
340 10,
341 )
342 .unwrap(),
343 y: BigInt::parse_bytes(
344 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
345 10,
346 )
347 .unwrap(),
348 };
349 let q: Point = Point {
350 x: BigInt::parse_bytes(
351 b"16540640123574156134436876038791482806971768689494387082833631921987005038935",
352 10,
353 )
354 .unwrap(),
355 y: BigInt::parse_bytes(
356 b"20819045374670962167435360035096875258406992893633759881276124905556507972311",
357 10,
358 )
359 .unwrap(),
360 };
361 let bbjj = Babyjubjub::new();
362 let res = bbjj.add(&p, &q);
363 assert_eq!(
364 res.x.to_string(),
365 "7916061937171219682591368294088513039687205273691143098332585753343424131937"
366 );
367 assert_eq!(
368 res.y.to_string(),
369 "14035240266687799601661095864649209771790948434046947201833777492504781204499"
370 );
371 }
372
373 #[test]
374 fn test_mul_scalar() {
375 let p: Point = Point {
376 x: BigInt::parse_bytes(
377 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
378 10,
379 )
380 .unwrap(),
381 y: BigInt::parse_bytes(
382 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
383 10,
384 )
385 .unwrap(),
386 };
387 let bbjj = Babyjubjub::new();
388 let res_m = bbjj.mul_scalar(p.clone(), 3.to_bigint().unwrap());
389 let res_a = bbjj.add(&p, &p);
390 let res_a = bbjj.add(&res_a, &p);
391 assert_eq!(res_m.x, res_a.x);
392 assert_eq!(
393 res_m.x.to_string(),
394 "19372461775513343691590086534037741906533799473648040012278229434133483800898"
395 );
396 assert_eq!(
397 res_m.y.to_string(),
398 "9458658722007214007257525444427903161243386465067105737478306991484593958249"
399 );
400
401 let n = BigInt::parse_bytes(
402 b"14035240266687799601661095864649209771790948434046947201833777492504781204499",
403 10,
404 )
405 .unwrap();
406 let res2 = bbjj.mul_scalar(p.clone(), n);
407 assert_eq!(
408 res2.x.to_string(),
409 "17070357974431721403481313912716834497662307308519659060910483826664480189605"
410 );
411 assert_eq!(
412 res2.y.to_string(),
413 "4014745322800118607127020275658861516666525056516280575712425373174125159339"
414 );
415 }
416
417 #[test]
418 fn test_point_compress_decompress() {
419 let bbjj = Babyjubjub::new();
420 let p: Point = Point {
421 x: BigInt::parse_bytes(
422 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
423 10,
424 )
425 .unwrap(),
426 y: BigInt::parse_bytes(
427 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
428 10,
429 )
430 .unwrap(),
431 };
432 let p_comp = bbjj.compress_point(&p);
433 assert_eq!(
434 p_comp[..].to_hex(),
435 "53b81ed5bffe9545b54016234682e7b2f699bd42a5e9eae27ff4051bc698ce85"
436 );
437 let p2 = bbjj.decompress_point(p_comp);
438 assert_eq!(p.x, p2.x);
439 assert_eq!(p.y, p2.y);
440 }
441
442 #[test]
443 fn test_new_key_sign_verify0() {
444 let bbjj = Babyjubjub::new();
445 let sk = bbjj.new_key();
446 let pk = sk.public();
447 let msg = 5.to_bigint().unwrap();
448 let sig = sk.sign(msg.clone());
449 let v = bbjj.verify(pk, sig, msg);
450 assert_eq!(v, true);
451 }
452
453 #[test]
454 fn test_new_key_sign_verify1() {
455 let bbjj = Babyjubjub::new();
456 let sk = bbjj.new_key();
457 let pk = sk.public();
458 let msg = BigInt::parse_bytes(b"123456789012345678901234567890", 10).unwrap();
459 let sig = sk.sign(msg.clone());
460 let v = bbjj.verify(pk, sig, msg);
461 assert_eq!(v, true);
462 }
463
464 #[test]
465 fn test_signature_compress_decompress() {
466 let bbjj = Babyjubjub::new();
467 let sk = bbjj.new_key();
468 let pk = sk.public();
469 let msg = 5.to_bigint().unwrap();
470 let sig = sk.sign(msg.clone());
471
472 let compressed_sig = bbjj.compress_sig(&sig);
473 println!("compressedsig {:?}", compressed_sig.to_hex());
474 let decompressed_sig = bbjj.decompress_sig(&compressed_sig);
475 assert_eq!(&sig.r_b8.x, &decompressed_sig.r_b8.x);
476 assert_eq!(&sig.r_b8.y, &decompressed_sig.r_b8.y);
477 assert_eq!(&sig.s, &decompressed_sig.s);
478
479 let v = bbjj.verify(pk, decompressed_sig, msg);
480 assert_eq!(v, true);
481 }
482}