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