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