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) -> Result<Point, String> {
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 Ok(Point { x: x, y: y })
83 }
84
85 pub fn mul_scalar(&self, n: &BigInt) -> Result<Point, String> {
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.clone();
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 Ok(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 den = utils::modinv(
137 &utils::modulus(
138 &(&A.clone() - utils::modulus(&(&D.clone() * (&y * &y)), &Q)),
139 &Q,
140 ),
141 &Q,
142 )?;
143 let mut x: BigInt = utils::modulus(&((one - utils::modulus(&(&y * &y), &Q)) * den), &Q);
144 x = utils::modsqrt(&x, &Q)?;
145
146 if sign && !(&x > &(&Q.clone() >> 1)) || (!sign && (&x > &(&Q.clone() >> 1))) {
147 x = x * -1.to_bigint().unwrap();
148 }
149 x = utils::modulus(&x, &Q);
150 Ok(Point { x: x, y: y })
151}
152
153pub struct Signature {
154 r_b8: Point,
155 s: BigInt,
156}
157
158impl Signature {
159 pub fn compress(&self) -> [u8; 64] {
160 let mut b: Vec<u8> = Vec::new();
161 b.append(&mut self.r_b8.compress().to_vec());
162 let (_, s_bytes) = self.s.to_bytes_le();
163 let mut s_32bytes: [u8; 32] = [0; 32];
164 let len = min(s_bytes.len(), s_32bytes.len());
165 s_32bytes[..len].copy_from_slice(&s_bytes[..len]);
166 b.append(&mut s_32bytes.to_vec());
167 let mut r: [u8; 64] = [0; 64];
168 r[..].copy_from_slice(&b[..]);
169 r
170 }
171}
172
173pub fn decompress_signature(b: &[u8; 64]) -> Result<Signature, String> {
174 let r_b8_bytes: [u8; 32] = *array_ref!(b[..32], 0, 32);
175 let s: BigInt = BigInt::from_bytes_le(Sign::Plus, &b[32..]);
176 let r_b8 = decompress_point(r_b8_bytes);
177 match r_b8 {
178 Result::Err(err) => return Err(err.to_string()),
179 Result::Ok(res) => Ok(Signature {
180 r_b8: res.clone(),
181 s: s,
182 }),
183 }
184}
185
186pub struct PrivateKey {
187 key: BigInt,
188}
189
190impl PrivateKey {
191 pub fn public(&self) -> Result<Point, String> {
192 // https://tools.ietf.org/html/rfc8032#section-5.1.5
193 let pk = B8.mul_scalar(&self.key)?;
194 Ok(pk.clone())
195 }
196
197 pub fn sign_mimc(&self, msg: BigInt) -> Result<Signature, String> {
198 // https://tools.ietf.org/html/rfc8032#section-5.1.6
199 let mut hasher = Blake2b::new();
200 let (_, sk_bytes) = self.key.to_bytes_be();
201 hasher.input(sk_bytes);
202 let mut h = hasher.result(); // h: hash(sk)
203 // s: h[32:64]
204 let s = GenericArray::<u8, generic_array::typenum::U32>::from_mut_slice(&mut h[32..64]);
205 let (_, msg_bytes) = msg.to_bytes_be();
206 let r_bytes = utils::concatenate_arrays(s, &msg_bytes);
207 let mut r = BigInt::from_bytes_be(Sign::Plus, &r_bytes[..]);
208 r = utils::modulus(&r, &SUBORDER);
209 let r8: Point = B8.mul_scalar(&r)?;
210 let a = &self.public()?;
211
212 let hm_input = vec![r8.x.clone(), r8.y.clone(), a.x.clone(), a.y.clone(), msg];
213 let mimc7 = Mimc7::new();
214 let hm = mimc7.hash(hm_input)?;
215
216 let mut s = &self.key << 3;
217 s = hm * s;
218 s = r + s;
219 s = s % &SUBORDER.clone();
220
221 Ok(Signature {
222 r_b8: r8.clone(),
223 s: s,
224 })
225 }
226 pub fn sign_poseidon(&self, msg: BigInt) -> Result<Signature, String> {
227 // https://tools.ietf.org/html/rfc8032#section-5.1.6
228 let mut hasher = Blake2b::new();
229 let (_, sk_bytes) = self.key.to_bytes_be();
230 hasher.input(sk_bytes);
231 let mut h = hasher.result(); // h: hash(sk)
232 // s: h[32:64]
233 let s = GenericArray::<u8, generic_array::typenum::U32>::from_mut_slice(&mut h[32..64]);
234 let (_, msg_bytes) = msg.to_bytes_be();
235 let r_bytes = utils::concatenate_arrays(s, &msg_bytes);
236 let mut r = BigInt::from_bytes_be(Sign::Plus, &r_bytes[..]);
237 r = utils::modulus(&r, &SUBORDER);
238 let r8: Point = B8.mul_scalar(&r)?;
239 let a = &self.public()?;
240
241 let hm_input = vec![r8.x.clone(), r8.y.clone(), a.x.clone(), a.y.clone(), msg];
242 let poseidon = Poseidon::new();
243 let hm = poseidon.hash(hm_input)?;
244
245 let mut s = &self.key << 3;
246 s = hm * s;
247 s = r + s;
248 s = s % &SUBORDER.clone();
249
250 Ok(Signature {
251 r_b8: r8.clone(),
252 s: s,
253 })
254 }
255}
256
257pub fn new_key() -> PrivateKey {
258 // https://tools.ietf.org/html/rfc8032#section-5.1.5
259 let mut rng = rand::thread_rng();
260 let sk_raw = rng.gen_biguint(1024).to_bigint().unwrap();
261
262 let mut hasher = Blake2b::new();
263 let (_, sk_raw_bytes) = sk_raw.to_bytes_be();
264 hasher.input(sk_raw_bytes);
265 let mut h = hasher.result();
266
267 h[0] = h[0] & 0xF8;
268 h[31] = h[31] & 0x7F;
269 h[31] = h[31] | 0x40;
270
271 let sk = BigInt::from_bytes_le(Sign::Plus, &h[..]);
272
273 PrivateKey { key: sk }
274}
275
276pub fn verify_mimc(pk: Point, sig: Signature, msg: BigInt) -> bool {
277 let hm_input = vec![
278 sig.r_b8.x.clone(),
279 sig.r_b8.y.clone(),
280 pk.x.clone(),
281 pk.y.clone(),
282 msg,
283 ];
284 let mimc7 = Mimc7::new();
285 let hm = match mimc7.hash(hm_input) {
286 Result::Err(_) => return false,
287 Result::Ok(hm) => hm,
288 };
289 let l = match B8.mul_scalar(&sig.s) {
290 Result::Err(_) => return false,
291 Result::Ok(l) => l,
292 };
293 let r = match sig
294 .r_b8
295 .add(&pk.mul_scalar(&(8.to_bigint().unwrap() * hm)).unwrap())
296 {
297 Result::Err(_) => return false,
298 Result::Ok(r) => r,
299 };
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 = match B8.mul_scalar(&sig.s) {
319 Result::Err(_) => return false,
320 Result::Ok(l) => l,
321 };
322 let r = match sig
323 .r_b8
324 .add(&pk.mul_scalar(&(8.to_bigint().unwrap() * hm)).unwrap())
325 {
326 Result::Err(_) => return false,
327 Result::Ok(r) => r,
328 };
329 if l.x == r.x && l.y == r.y {
330 return true;
331 }
332 false
333}
334
335#[cfg(test)]
336mod tests {
337 use super::*;
338 extern crate rustc_hex;
339 use rustc_hex::{FromHex, ToHex};
340
341 #[test]
342 fn test_add_same_point() {
343 let p: Point = Point {
344 x: BigInt::parse_bytes(
345 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
346 10,
347 )
348 .unwrap(),
349 y: BigInt::parse_bytes(
350 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
351 10,
352 )
353 .unwrap(),
354 };
355 let q: Point = Point {
356 x: BigInt::parse_bytes(
357 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
358 10,
359 )
360 .unwrap(),
361 y: BigInt::parse_bytes(
362 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
363 10,
364 )
365 .unwrap(),
366 };
367 let res = p.add(&q).unwrap();
368 assert_eq!(
369 res.x.to_string(),
370 "6890855772600357754907169075114257697580319025794532037257385534741338397365"
371 );
372 assert_eq!(
373 res.y.to_string(),
374 "4338620300185947561074059802482547481416142213883829469920100239455078257889"
375 );
376 }
377 #[test]
378 fn test_add_different_points() {
379 let p: Point = Point {
380 x: BigInt::parse_bytes(
381 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
382 10,
383 )
384 .unwrap(),
385 y: BigInt::parse_bytes(
386 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
387 10,
388 )
389 .unwrap(),
390 };
391 let q: Point = Point {
392 x: BigInt::parse_bytes(
393 b"16540640123574156134436876038791482806971768689494387082833631921987005038935",
394 10,
395 )
396 .unwrap(),
397 y: BigInt::parse_bytes(
398 b"20819045374670962167435360035096875258406992893633759881276124905556507972311",
399 10,
400 )
401 .unwrap(),
402 };
403 let res = p.add(&q).unwrap();
404 assert_eq!(
405 res.x.to_string(),
406 "7916061937171219682591368294088513039687205273691143098332585753343424131937"
407 );
408 assert_eq!(
409 res.y.to_string(),
410 "14035240266687799601661095864649209771790948434046947201833777492504781204499"
411 );
412 }
413
414 #[test]
415 fn test_mul_scalar() {
416 let p: Point = Point {
417 x: BigInt::parse_bytes(
418 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
419 10,
420 )
421 .unwrap(),
422 y: BigInt::parse_bytes(
423 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
424 10,
425 )
426 .unwrap(),
427 };
428 let res_m = p.mul_scalar(&3.to_bigint().unwrap()).unwrap();
429 let res_a = p.add(&p).unwrap();
430 let res_a = res_a.add(&p).unwrap();
431 assert_eq!(res_m.x, res_a.x);
432 assert_eq!(
433 res_m.x.to_string(),
434 "19372461775513343691590086534037741906533799473648040012278229434133483800898"
435 );
436 assert_eq!(
437 res_m.y.to_string(),
438 "9458658722007214007257525444427903161243386465067105737478306991484593958249"
439 );
440
441 let n = BigInt::parse_bytes(
442 b"14035240266687799601661095864649209771790948434046947201833777492504781204499",
443 10,
444 )
445 .unwrap();
446 let res2 = p.mul_scalar(&n).unwrap();
447 assert_eq!(
448 res2.x.to_string(),
449 "17070357974431721403481313912716834497662307308519659060910483826664480189605"
450 );
451 assert_eq!(
452 res2.y.to_string(),
453 "4014745322800118607127020275658861516666525056516280575712425373174125159339"
454 );
455 }
456
457 #[test]
458 fn test_new_key_sign_verify_mimc_0() {
459 let sk = new_key();
460 let pk = sk.public().unwrap();
461 let msg = 5.to_bigint().unwrap();
462 let sig = sk.sign_mimc(msg.clone()).unwrap();
463 let v = verify_mimc(pk, sig, msg);
464 assert_eq!(v, true);
465 }
466
467 #[test]
468 fn test_new_key_sign_verify_mimc_1() {
469 let sk = new_key();
470 let pk = sk.public().unwrap();
471 let msg = BigInt::parse_bytes(b"123456789012345678901234567890", 10).unwrap();
472 let sig = sk.sign_mimc(msg.clone()).unwrap();
473 let v = verify_mimc(pk, sig, msg);
474 assert_eq!(v, true);
475 }
476 #[test]
477 fn test_new_key_sign_verify_poseidon_0() {
478 let sk = new_key();
479 let pk = sk.public().unwrap();
480 let msg = 5.to_bigint().unwrap();
481 let sig = sk.sign_poseidon(msg.clone()).unwrap();
482 let v = verify_poseidon(pk, sig, msg);
483 assert_eq!(v, true);
484 }
485
486 #[test]
487 fn test_new_key_sign_verify_poseidon_1() {
488 let sk = new_key();
489 let pk = sk.public().unwrap();
490 let msg = BigInt::parse_bytes(b"123456789012345678901234567890", 10).unwrap();
491 let sig = sk.sign_poseidon(msg.clone()).unwrap();
492 let v = verify_poseidon(pk, sig, msg);
493 assert_eq!(v, true);
494 }
495
496 #[test]
497 fn test_point_compress_decompress() {
498 let p: Point = Point {
499 x: BigInt::parse_bytes(
500 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
501 10,
502 )
503 .unwrap(),
504 y: BigInt::parse_bytes(
505 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
506 10,
507 )
508 .unwrap(),
509 };
510 let p_comp = p.compress();
511 assert_eq!(
512 p_comp[..].to_hex(),
513 "53b81ed5bffe9545b54016234682e7b2f699bd42a5e9eae27ff4051bc698ce85"
514 );
515 let p2 = decompress_point(p_comp).unwrap();
516 assert_eq!(p.x, p2.x);
517 assert_eq!(p.y, p2.y);
518 }
519
520 #[test]
521 fn test_point_decompress0() {
522 let y_bytes_raw = "b5328f8791d48f20bec6e481d91c7ada235f1facf22547901c18656b6c3e042f"
523 .from_hex()
524 .unwrap();
525 let mut y_bytes: [u8; 32] = [0; 32];
526 y_bytes.copy_from_slice(&y_bytes_raw);
527 let p = decompress_point(y_bytes).unwrap();
528
529 let expected_px_raw = "b86cc8d9c97daef0afe1a4753c54fb2d8a530dc74c7eee4e72b3fdf2496d2113"
530 .from_hex()
531 .unwrap();
532 let mut e_px_bytes: [u8; 32] = [0; 32];
533 e_px_bytes.copy_from_slice(&expected_px_raw);
534 let expected_px: BigInt = BigInt::from_bytes_le(Sign::Plus, &e_px_bytes);
535 assert_eq!(&p.x, &expected_px);
536 }
537
538 #[test]
539 fn test_point_decompress1() {
540 let y_bytes_raw = "70552d3ff548e09266ded29b33ce75139672b062b02aa66bb0d9247ffecf1d0b"
541 .from_hex()
542 .unwrap();
543 let mut y_bytes: [u8; 32] = [0; 32];
544 y_bytes.copy_from_slice(&y_bytes_raw);
545 let p = decompress_point(y_bytes).unwrap();
546
547 let expected_px_raw = "30f1635ba7d56f9cb32c3ffbe6dca508a68c7f43936af11a23c785ce98cb3404"
548 .from_hex()
549 .unwrap();
550 let mut e_px_bytes: [u8; 32] = [0; 32];
551 e_px_bytes.copy_from_slice(&expected_px_raw);
552 let expected_px: BigInt = BigInt::from_bytes_le(Sign::Plus, &e_px_bytes);
553 assert_eq!(&p.x, &expected_px);
554 }
555
556 #[test]
557 fn test_point_decompress_loop() {
558 for _ in 0..5 {
559 let mut rng = rand::thread_rng();
560 let sk_raw = rng.gen_biguint(1024).to_bigint().unwrap();
561 let mut hasher = Blake2b::new();
562 let (_, sk_raw_bytes) = sk_raw.to_bytes_be();
563 hasher.input(sk_raw_bytes);
564 let mut h = hasher.result();
565
566 h[0] = h[0] & 0xF8;
567 h[31] = h[31] & 0x7F;
568 h[31] = h[31] | 0x40;
569
570 let sk = BigInt::from_bytes_le(Sign::Plus, &h[..]);
571 let point = B8.mul_scalar(&sk).unwrap();
572 let cmp_point = point.compress();
573 let dcmp_point = decompress_point(cmp_point).unwrap();
574
575 assert_eq!(&point.x, &dcmp_point.x);
576 assert_eq!(&point.y, &dcmp_point.y);
577 }
578 }
579
580 #[test]
581 fn test_signature_compress_decompress() {
582 let sk = new_key();
583 let pk = sk.public().unwrap();
584
585 for i in 0..5 {
586 let msg_raw = "123456".to_owned() + &i.to_string();
587 let msg = BigInt::parse_bytes(msg_raw.as_bytes(), 10).unwrap();
588 let sig = sk.sign_mimc(msg.clone()).unwrap();
589
590 let compressed_sig = sig.compress();
591 let decompressed_sig = decompress_signature(&compressed_sig).unwrap();
592 assert_eq!(&sig.r_b8.x, &decompressed_sig.r_b8.x);
593 assert_eq!(&sig.r_b8.y, &decompressed_sig.r_b8.y);
594 assert_eq!(&sig.s, &decompressed_sig.s);
595
596 let v = verify_mimc(pk.clone(), decompressed_sig, msg);
597 assert_eq!(v, true);
598 }
599 }
600}