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;
12use poseidon_rs::Poseidon;
13use std::cmp::min;
14
15use num_bigint::{BigInt, RandBigInt, Sign, ToBigInt};
16use num_traits::{One, Zero};
17
18use generic_array::GenericArray;
19
20mod utils;
21
22#[macro_use]
23extern crate lazy_static;
24
25lazy_static! {
26 static ref D: BigInt = BigInt::parse_bytes(b"168696", 10).unwrap();
27 static ref A: BigInt = BigInt::parse_bytes(b"168700", 10).unwrap();
28 static ref Q: BigInt = BigInt::parse_bytes(
29 b"21888242871839275222246405745257275088548364400416034343698204186575808495617",
30 10,
31 )
32 .unwrap();
33 static ref B8: Point = Point {
34 x: BigInt::parse_bytes(
35 b"5299619240641551281634865583518297030282874472190772894086521144482721001553",
36 10,
37 )
38 .unwrap(),
39 y: BigInt::parse_bytes(
40 b"16950150798460657717958625567821834550301663161624707787222815936182638968203",
41 10,
42 )
43 .unwrap(),
44 };
45 static ref ORDER: BigInt = BigInt::parse_bytes(
46 b"21888242871839275222246405745257275088614511777268538073601725287587578984328",
47 10,
48 )
49 .unwrap();
50 static ref SUBORDER: BigInt = &BigInt::parse_bytes(
51 b"21888242871839275222246405745257275088614511777268538073601725287587578984328",
52 10,
53 )
54 .unwrap()
55 >> 3;
56}
57
58#[derive(Clone, Debug)]
59pub struct Point {
60 pub x: BigInt,
61 pub y: BigInt,
62}
63
64impl Point {
65 pub fn add(&self, q: &Point) -> Point {
66 // x = (x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2))
67 // y = (y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2))
68
69 // x = (x1 * y2 + y1 * x2) / (1 + d * x1 * y1 * y2)
70 let one: BigInt = One::one();
71 let x_num: BigInt = &self.x * &q.y + &self.y * &q.x;
72 let x_den: BigInt = &one + &D.clone() * &self.x * &q.x * &self.y * &q.y;
73 let x_den_inv = utils::modinv(&x_den, &Q);
74 let x: BigInt = utils::modulus(&(&x_num * &x_den_inv), &Q);
75
76 // y = (y1 * y2 - a * x1 * x2) / (1 - d * x1 * x2 * y1 * y2)
77 let y_num = &self.y * &q.y - &A.clone() * &self.x * &q.x;
78 let y_den = utils::modulus(&(&one - &D.clone() * &self.x * &q.x * &self.y * &q.y), &Q);
79 let y_den_inv = utils::modinv(&y_den, &Q);
80 let y: BigInt = utils::modulus(&(&y_num * &y_den_inv), &Q);
81
82 Point { x: x, y: y }
83 }
84
85 pub fn mul_scalar(&self, n: BigInt) -> Point {
86 // TODO use & in n to avoid clones on function call
87 let mut r: Point = Point {
88 x: Zero::zero(),
89 y: One::one(),
90 };
91 let mut rem: BigInt = n;
92 let mut exp: Point = self.clone();
93
94 let zero: BigInt = Zero::zero();
95 let one: BigInt = One::one();
96 while rem != zero {
97 let is_odd = &rem & &one == one;
98 if is_odd == true {
99 r = r.add(&exp);
100 }
101 exp = exp.add(&exp);
102 rem = rem >> 1;
103 }
104 r.x = utils::modulus(&r.x, &Q);
105 r.y = utils::modulus(&r.y, &Q);
106 r
107 }
108
109 pub fn compress(&self) -> [u8; 32] {
110 let mut r: [u8; 32] = [0; 32];
111 let (_, y_bytes) = self.y.to_bytes_le();
112 let len = min(y_bytes.len(), r.len());
113 r[..len].copy_from_slice(&y_bytes[..len]);
114 if &self.x >= &(&Q.clone() >> 1) {
115 r[31] = r[31] | 0x80;
116 }
117 r
118 }
119}
120
121pub fn decompress_point(bb: [u8; 32]) -> Result<Point, String> {
122 // https://tools.ietf.org/html/rfc8032#section-5.2.3
123 let mut sign: bool = false;
124 let mut b = bb.clone();
125 if b[31] & 0x80 != 0x00 {
126 sign = true;
127 b[31] = b[31] & 0x7F;
128 }
129 let y: BigInt = BigInt::from_bytes_le(Sign::Plus, &b[..]);
130 if y >= Q.clone() {
131 return Err("y outside the Finite Field over R".to_string());
132 }
133 let one: BigInt = One::one();
134
135 // x^2 = (1 - y^2) / (a - d * y^2) (mod p)
136 let mut x: BigInt = utils::modulus(
137 &((one - utils::modulus(&(&y * &y), &Q))
138 * utils::modinv(
139 &utils::modulus(
140 &(&A.clone() - utils::modulus(&(&D.clone() * (&y * &y)), &Q)),
141 &Q,
142 ),
143 &Q,
144 )),
145 &Q,
146 );
147 x = utils::modsqrt(&x, &Q);
148
149 if sign && !(&x > &(&Q.clone() >> 1)) || (!sign && (&x > &(&Q.clone() >> 1))) {
150 x = x * -1.to_bigint().unwrap();
151 }
152 x = utils::modulus(&x, &Q);
153 Ok(Point { x: x, y: y })
154}
155
156pub struct Signature {
157 r_b8: Point,
158 s: BigInt,
159}
160
161impl Signature {
162 pub fn compress(&self) -> [u8; 64] {
163 let mut b: Vec<u8> = Vec::new();
164 b.append(&mut self.r_b8.compress().to_vec());
165 let (_, s_bytes) = self.s.to_bytes_le();
166 let mut s_32bytes: [u8; 32] = [0; 32];
167 let len = min(s_bytes.len(), s_32bytes.len());
168 s_32bytes[..len].copy_from_slice(&s_bytes[..len]);
169 b.append(&mut s_32bytes.to_vec());
170 let mut r: [u8; 64] = [0; 64];
171 r[..].copy_from_slice(&b[..]);
172 r
173 }
174}
175
176pub fn decompress_signature(b: &[u8; 64]) -> Result<Signature, String> {
177 let r_b8_bytes: [u8; 32] = *array_ref!(b[..32], 0, 32);
178 let s: BigInt = BigInt::from_bytes_le(Sign::Plus, &b[32..]);
179 let r_b8 = decompress_point(r_b8_bytes);
180 match r_b8 {
181 Result::Err(err) => return Err(err.to_string()),
182 Result::Ok(res) => Ok(Signature {
183 r_b8: res.clone(),
184 s: s,
185 }),
186 }
187}
188
189pub struct PrivateKey {
190 key: BigInt,
191}
192
193impl PrivateKey {
194 pub fn public(&self) -> Point {
195 // https://tools.ietf.org/html/rfc8032#section-5.1.5
196 let pk = B8.mul_scalar(self.key.clone());
197 pk.clone()
198 }
199
200 pub fn sign_mimc(&self, msg: BigInt) -> Result<Signature, String> {
201 // https://tools.ietf.org/html/rfc8032#section-5.1.6
202 let mut hasher = Blake2b::new();
203 let (_, sk_bytes) = self.key.to_bytes_be();
204 hasher.input(sk_bytes);
205 let mut h = hasher.result(); // h: hash(sk)
206 // s: h[32:64]
207 let s = GenericArray::<u8, generic_array::typenum::U32>::from_mut_slice(&mut h[32..64]);
208 let (_, msg_bytes) = msg.to_bytes_be();
209 let r_bytes = utils::concatenate_arrays(s, &msg_bytes);
210 let mut r = BigInt::from_bytes_be(Sign::Plus, &r_bytes[..]);
211 r = utils::modulus(&r, &SUBORDER);
212 let r8: Point = B8.mul_scalar(r.clone());
213 let a = &self.public();
214
215 let hm_input = vec![r8.x.clone(), r8.y.clone(), a.x.clone(), a.y.clone(), msg];
216 let mimc7 = Mimc7::new();
217 let hm = match mimc7.hash(hm_input) {
218 Result::Err(err) => return Err(err.to_string()),
219 Result::Ok(hm) => hm,
220 };
221
222 let mut s = &self.key << 3;
223 s = hm * s;
224 s = r + s;
225 s = s % &SUBORDER.clone();
226
227 Ok(Signature {
228 r_b8: r8.clone(),
229 s: s,
230 })
231 }
232 pub fn sign_poseidon(&self, msg: BigInt) -> Result<Signature, String> {
233 // https://tools.ietf.org/html/rfc8032#section-5.1.6
234 let mut hasher = Blake2b::new();
235 let (_, sk_bytes) = self.key.to_bytes_be();
236 hasher.input(sk_bytes);
237 let mut h = hasher.result(); // h: hash(sk)
238 // s: h[32:64]
239 let s = GenericArray::<u8, generic_array::typenum::U32>::from_mut_slice(&mut h[32..64]);
240 let (_, msg_bytes) = msg.to_bytes_be();
241 let r_bytes = utils::concatenate_arrays(s, &msg_bytes);
242 let mut r = BigInt::from_bytes_be(Sign::Plus, &r_bytes[..]);
243 r = utils::modulus(&r, &SUBORDER);
244 let r8: Point = B8.mul_scalar(r.clone());
245 let a = &self.public();
246
247 let hm_input = vec![r8.x.clone(), r8.y.clone(), a.x.clone(), a.y.clone(), msg];
248 let poseidon = Poseidon::new();
249 let hm = match poseidon.hash(hm_input) {
250 Result::Err(err) => return Err(err.to_string()),
251 Result::Ok(hm) => hm,
252 };
253
254 let mut s = &self.key << 3;
255 s = hm * s;
256 s = r + s;
257 s = s % &SUBORDER.clone();
258
259 Ok(Signature {
260 r_b8: r8.clone(),
261 s: s,
262 })
263 }
264}
265
266pub fn new_key() -> PrivateKey {
267 // https://tools.ietf.org/html/rfc8032#section-5.1.5
268 let mut rng = rand::thread_rng();
269 let sk_raw = rng.gen_biguint(1024).to_bigint().unwrap();
270
271 let mut hasher = Blake2b::new();
272 let (_, sk_raw_bytes) = sk_raw.to_bytes_be();
273 hasher.input(sk_raw_bytes);
274 let mut h = hasher.result();
275
276 h[0] = h[0] & 0xF8;
277 h[31] = h[31] & 0x7F;
278 h[31] = h[31] | 0x40;
279
280 let sk = BigInt::from_bytes_le(Sign::Plus, &h[..]);
281
282 PrivateKey { key: sk }
283}
284
285pub fn verify_mimc(pk: Point, sig: Signature, msg: BigInt) -> bool {
286 let hm_input = vec![
287 sig.r_b8.x.clone(),
288 sig.r_b8.y.clone(),
289 pk.x.clone(),
290 pk.y.clone(),
291 msg,
292 ];
293 let mimc7 = Mimc7::new();
294 let hm = match mimc7.hash(hm_input) {
295 Result::Err(_) => return false,
296 Result::Ok(hm) => hm,
297 };
298 let l = B8.mul_scalar(sig.s);
299 let r = sig.r_b8.add(&pk.mul_scalar(8.to_bigint().unwrap() * hm));
300 if l.x == r.x && l.y == r.y {
301 return true;
302 }
303 false
304}
305pub fn verify_poseidon(pk: Point, sig: Signature, msg: BigInt) -> bool {
306 let hm_input = vec![
307 sig.r_b8.x.clone(),
308 sig.r_b8.y.clone(),
309 pk.x.clone(),
310 pk.y.clone(),
311 msg,
312 ];
313 let poseidon = Poseidon::new();
314 let hm = match poseidon.hash(hm_input) {
315 Result::Err(_) => return false,
316 Result::Ok(hm) => hm,
317 };
318 let l = B8.mul_scalar(sig.s);
319 let r = sig.r_b8.add(&pk.mul_scalar(8.to_bigint().unwrap() * hm));
320 if l.x == r.x && l.y == r.y {
321 return true;
322 }
323 false
324}
325
326#[cfg(test)]
327mod tests {
328 use super::*;
329 extern crate rustc_hex;
330 use rustc_hex::{FromHex, ToHex};
331
332 #[test]
333 fn test_add_same_point() {
334 let p: Point = Point {
335 x: BigInt::parse_bytes(
336 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
337 10,
338 )
339 .unwrap(),
340 y: BigInt::parse_bytes(
341 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
342 10,
343 )
344 .unwrap(),
345 };
346 let q: Point = Point {
347 x: BigInt::parse_bytes(
348 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
349 10,
350 )
351 .unwrap(),
352 y: BigInt::parse_bytes(
353 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
354 10,
355 )
356 .unwrap(),
357 };
358 let res = p.add(&q);
359 assert_eq!(
360 res.x.to_string(),
361 "6890855772600357754907169075114257697580319025794532037257385534741338397365"
362 );
363 assert_eq!(
364 res.y.to_string(),
365 "4338620300185947561074059802482547481416142213883829469920100239455078257889"
366 );
367 }
368 #[test]
369 fn test_add_different_points() {
370 let p: Point = Point {
371 x: BigInt::parse_bytes(
372 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
373 10,
374 )
375 .unwrap(),
376 y: BigInt::parse_bytes(
377 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
378 10,
379 )
380 .unwrap(),
381 };
382 let q: Point = Point {
383 x: BigInt::parse_bytes(
384 b"16540640123574156134436876038791482806971768689494387082833631921987005038935",
385 10,
386 )
387 .unwrap(),
388 y: BigInt::parse_bytes(
389 b"20819045374670962167435360035096875258406992893633759881276124905556507972311",
390 10,
391 )
392 .unwrap(),
393 };
394 let res = p.add(&q);
395 assert_eq!(
396 res.x.to_string(),
397 "7916061937171219682591368294088513039687205273691143098332585753343424131937"
398 );
399 assert_eq!(
400 res.y.to_string(),
401 "14035240266687799601661095864649209771790948434046947201833777492504781204499"
402 );
403 }
404
405 #[test]
406 fn test_mul_scalar() {
407 let p: Point = Point {
408 x: BigInt::parse_bytes(
409 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
410 10,
411 )
412 .unwrap(),
413 y: BigInt::parse_bytes(
414 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
415 10,
416 )
417 .unwrap(),
418 };
419 let res_m = p.mul_scalar(3.to_bigint().unwrap());
420 let res_a = p.add(&p);
421 let res_a = res_a.add(&p);
422 assert_eq!(res_m.x, res_a.x);
423 assert_eq!(
424 res_m.x.to_string(),
425 "19372461775513343691590086534037741906533799473648040012278229434133483800898"
426 );
427 assert_eq!(
428 res_m.y.to_string(),
429 "9458658722007214007257525444427903161243386465067105737478306991484593958249"
430 );
431
432 let n = BigInt::parse_bytes(
433 b"14035240266687799601661095864649209771790948434046947201833777492504781204499",
434 10,
435 )
436 .unwrap();
437 let res2 = p.mul_scalar(n);
438 assert_eq!(
439 res2.x.to_string(),
440 "17070357974431721403481313912716834497662307308519659060910483826664480189605"
441 );
442 assert_eq!(
443 res2.y.to_string(),
444 "4014745322800118607127020275658861516666525056516280575712425373174125159339"
445 );
446 }
447
448 #[test]
449 fn test_new_key_sign_verify_mimc_0() {
450 let sk = new_key();
451 let pk = sk.public();
452 let msg = 5.to_bigint().unwrap();
453 let sig = sk.sign_mimc(msg.clone()).unwrap();
454 let v = verify_mimc(pk, sig, msg);
455 assert_eq!(v, true);
456 }
457
458 #[test]
459 fn test_new_key_sign_verify_mimc_1() {
460 let sk = new_key();
461 let pk = sk.public();
462 let msg = BigInt::parse_bytes(b"123456789012345678901234567890", 10).unwrap();
463 let sig = sk.sign_mimc(msg.clone()).unwrap();
464 let v = verify_mimc(pk, sig, msg);
465 assert_eq!(v, true);
466 }
467 #[test]
468 fn test_new_key_sign_verify_poseidon_0() {
469 let sk = new_key();
470 let pk = sk.public();
471 let msg = 5.to_bigint().unwrap();
472 let sig = sk.sign_poseidon(msg.clone()).unwrap();
473 let v = verify_poseidon(pk, sig, msg);
474 assert_eq!(v, true);
475 }
476
477 #[test]
478 fn test_new_key_sign_verify_poseidon_1() {
479 let sk = new_key();
480 let pk = sk.public();
481 let msg = BigInt::parse_bytes(b"123456789012345678901234567890", 10).unwrap();
482 let sig = sk.sign_poseidon(msg.clone()).unwrap();
483 let v = verify_poseidon(pk, sig, msg);
484 assert_eq!(v, true);
485 }
486
487 #[test]
488 fn test_point_compress_decompress() {
489 let p: Point = Point {
490 x: BigInt::parse_bytes(
491 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
492 10,
493 )
494 .unwrap(),
495 y: BigInt::parse_bytes(
496 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
497 10,
498 )
499 .unwrap(),
500 };
501 let p_comp = p.compress();
502 assert_eq!(
503 p_comp[..].to_hex(),
504 "53b81ed5bffe9545b54016234682e7b2f699bd42a5e9eae27ff4051bc698ce85"
505 );
506 let p2 = decompress_point(p_comp).unwrap();
507 assert_eq!(p.x, p2.x);
508 assert_eq!(p.y, p2.y);
509 }
510
511 #[test]
512 fn test_point_decompress0() {
513 let y_bytes_raw = "b5328f8791d48f20bec6e481d91c7ada235f1facf22547901c18656b6c3e042f"
514 .from_hex()
515 .unwrap();
516 let mut y_bytes: [u8; 32] = [0; 32];
517 y_bytes.copy_from_slice(&y_bytes_raw);
518 let p = decompress_point(y_bytes).unwrap();
519
520 let expected_px_raw = "b86cc8d9c97daef0afe1a4753c54fb2d8a530dc74c7eee4e72b3fdf2496d2113"
521 .from_hex()
522 .unwrap();
523 let mut e_px_bytes: [u8; 32] = [0; 32];
524 e_px_bytes.copy_from_slice(&expected_px_raw);
525 let expected_px: BigInt = BigInt::from_bytes_le(Sign::Plus, &e_px_bytes);
526 assert_eq!(&p.x, &expected_px);
527 }
528
529 #[test]
530 fn test_point_decompress1() {
531 let y_bytes_raw = "70552d3ff548e09266ded29b33ce75139672b062b02aa66bb0d9247ffecf1d0b"
532 .from_hex()
533 .unwrap();
534 let mut y_bytes: [u8; 32] = [0; 32];
535 y_bytes.copy_from_slice(&y_bytes_raw);
536 let p = decompress_point(y_bytes).unwrap();
537
538 let expected_px_raw = "30f1635ba7d56f9cb32c3ffbe6dca508a68c7f43936af11a23c785ce98cb3404"
539 .from_hex()
540 .unwrap();
541 let mut e_px_bytes: [u8; 32] = [0; 32];
542 e_px_bytes.copy_from_slice(&expected_px_raw);
543 let expected_px: BigInt = BigInt::from_bytes_le(Sign::Plus, &e_px_bytes);
544 assert_eq!(&p.x, &expected_px);
545 }
546
547 #[test]
548 fn test_point_decompress_loop() {
549 for _ in 0..5 {
550 let mut rng = rand::thread_rng();
551 let sk_raw = rng.gen_biguint(1024).to_bigint().unwrap();
552 let mut hasher = Blake2b::new();
553 let (_, sk_raw_bytes) = sk_raw.to_bytes_be();
554 hasher.input(sk_raw_bytes);
555 let mut h = hasher.result();
556
557 h[0] = h[0] & 0xF8;
558 h[31] = h[31] & 0x7F;
559 h[31] = h[31] | 0x40;
560
561 let sk = BigInt::from_bytes_le(Sign::Plus, &h[..]);
562 let point = B8.mul_scalar(sk.clone());
563 let cmp_point = point.compress();
564 let dcmp_point = decompress_point(cmp_point).unwrap();
565
566 assert_eq!(&point.x, &dcmp_point.x);
567 assert_eq!(&point.y, &dcmp_point.y);
568 }
569 }
570
571 #[test]
572 fn test_signature_compress_decompress() {
573 let sk = new_key();
574 let pk = sk.public();
575
576 for i in 0..5 {
577 let msg_raw = "123456".to_owned() + &i.to_string();
578 let msg = BigInt::parse_bytes(msg_raw.as_bytes(), 10).unwrap();
579 let sig = sk.sign_mimc(msg.clone()).unwrap();
580
581 let compressed_sig = sig.compress();
582 let decompressed_sig = decompress_signature(&compressed_sig).unwrap();
583 assert_eq!(&sig.r_b8.x, &decompressed_sig.r_b8.x);
584 assert_eq!(&sig.r_b8.y, &decompressed_sig.r_b8.y);
585 assert_eq!(&sig.s, &decompressed_sig.s);
586
587 let v = verify_mimc(pk.clone(), decompressed_sig, msg);
588 assert_eq!(v, true);
589 }
590 }
591}