babyjubjub-ark/src/lib.rs
src/lib.rsRaw
1extern crate generic_array;
2extern crate mimc_rs;
3extern crate num;
4extern crate num_bigint;
5extern crate num_traits;
6extern crate rand;
7
8use blake2::{Blake2b, Digest};
9use mimc_rs::Mimc7;
10
11use num_bigint::RandBigInt;
12
13use num_bigint::{BigInt, 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}
25pub struct Signature {
26 r_b8: Point,
27 s: BigInt,
28}
29
30pub struct Babyjubjub {
31 d: BigInt,
32 a: BigInt,
33 q: BigInt,
34 b8: Point,
35 // order: BigInt,
36 sub_order: BigInt,
37}
38
39impl Babyjubjub {
40 pub fn new() -> Babyjubjub {
41 let d: BigInt = BigInt::parse_bytes(b"168696", 10).unwrap();
42 let a: BigInt = BigInt::parse_bytes(b"168700", 10).unwrap();
43 let q: BigInt = BigInt::parse_bytes(
44 b"21888242871839275222246405745257275088548364400416034343698204186575808495617",
45 10,
46 )
47 .unwrap();
48 let b8: Point = Point {
49 x: BigInt::parse_bytes(
50 b"5299619240641551281634865583518297030282874472190772894086521144482721001553",
51 10,
52 )
53 .unwrap(),
54 y: BigInt::parse_bytes(
55 b"16950150798460657717958625567821834550301663161624707787222815936182638968203",
56 10,
57 )
58 .unwrap(),
59 };
60 let order: BigInt = BigInt::parse_bytes(
61 b"21888242871839275222246405745257275088614511777268538073601725287587578984328",
62 10,
63 )
64 .unwrap();
65 let sub_order: BigInt = &order >> 3;
66
67 Babyjubjub {
68 d: d,
69 a: a,
70 q: q,
71 b8: b8,
72 // order: order,
73 sub_order: sub_order,
74 }
75 }
76
77 pub fn add(&self, p: &Point, q: &Point) -> Point {
78 // x = (x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2))
79 // y = (y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2))
80
81 // x = (x1 * y2 + y1 * x2) / (1 + d * x1 * y1 * y2)
82 let one: BigInt = One::one();
83 let x_num: BigInt = &p.x * &q.y + &p.y * &q.x;
84 let x_den: BigInt = &one + &self.d * &p.x * &q.x * &p.y * &q.y;
85 let x_den_inv = utils::mod_inverse0(&x_den, &self.q);
86 // let x_den_inv = utils::mod_inverse1(x_den, self.q.clone());
87 // let x_den_inv = utils::mod_inverse2(x_den, self.q.clone());
88 let x: BigInt = utils::modulus(&(&x_num * &x_den_inv), &self.q);
89
90 // y = (y1 * y2 - a * x1 * x2) / (1 - d * x1 * x2 * y1 * y2)
91 let y_num = &p.y * &q.y - &self.a * &p.x * &q.x;
92 let y_den = utils::modulus(&(&one - &self.d * &p.x * &q.x * &p.y * &q.y), &self.q);
93 let y_den_inv = utils::mod_inverse0(&y_den, &self.q);
94 // let y_den_inv = utils::mod_inverse1(y_den, self.q.clone());
95 // let y_den_inv = utils::mod_inverse2(y_den, self.q.clone());
96 let y: BigInt = utils::modulus(&(&y_num * &y_den_inv), &self.q);
97
98 Point { x: x, y: y }
99 }
100
101 pub fn mul_scalar(&self, p: Point, n: BigInt) -> Point {
102 // TODO use & in p and n to avoid clones on function call
103 let mut r: Point = Point {
104 x: Zero::zero(),
105 y: One::one(),
106 };
107 let mut rem: BigInt = n;
108 let mut exp: Point = p;
109
110 let zero: BigInt = Zero::zero();
111 let one: BigInt = One::one();
112 while rem != zero {
113 let is_odd = &rem & &one == one;
114 if is_odd == true {
115 r = self.add(&r, &exp);
116 }
117 exp = self.add(&exp, &exp);
118 rem = rem >> 1;
119 }
120 r.x = utils::modulus(&r.x, &self.q);
121 r.y = utils::modulus(&r.y, &self.q);
122 r
123 }
124
125 pub fn new_key(&self) -> BigInt {
126 // https://tools.ietf.org/html/rfc8032#section-5.1.5
127 let mut rng = rand::thread_rng();
128 let sk_raw = rng.gen_biguint(1024).to_bigint().unwrap();
129
130 let mut hasher = Blake2b::new();
131 let (_, sk_raw_bytes) = sk_raw.to_bytes_be();
132 hasher.input(sk_raw_bytes);
133 let mut h = hasher.result();
134
135 h[0] = h[0] & 0xF8;
136 h[31] = h[31] & 0x7F;
137 h[31] = h[31] | 0x40;
138
139 let sk = BigInt::from_bytes_le(Sign::Plus, &h[..]);
140
141 sk
142 }
143
144 pub fn sk_to_pk(&self, sk: BigInt) -> Point {
145 // https://tools.ietf.org/html/rfc8032#section-5.1.5
146 // TODO this will be moved into a method of PrivateKey type
147 let pk = &self.mul_scalar(self.b8.clone(), sk);
148 pk.clone()
149 }
150
151 pub fn sign(&self, sk: BigInt, msg: BigInt) -> Signature {
152 // https://tools.ietf.org/html/rfc8032#section-5.1.6
153 let mut hasher = Blake2b::new();
154 let (_, sk_bytes) = sk.to_bytes_be();
155 hasher.input(sk_bytes);
156 let mut h = hasher.result(); // h: hash(sk)
157 // s: h[32:64]
158 let s = GenericArray::<u8, generic_array::typenum::U32>::from_mut_slice(&mut h[32..64]);
159 let (_, msg_bytes) = msg.to_bytes_be();
160 let r_bytes = utils::concatenate_arrays(s, &msg_bytes);
161 let mut r = BigInt::from_bytes_be(Sign::Plus, &r_bytes[..]);
162 r = utils::modulus(&r, &self.sub_order);
163 let r8: Point = self.mul_scalar(self.b8.clone(), r.clone());
164 let a = &self.sk_to_pk(sk.clone());
165
166 let hm_input = vec![r8.x.clone(), r8.y.clone(), a.x.clone(), a.y.clone(), msg];
167 let mimc7 = Mimc7::new();
168 let hm = mimc7.hash(hm_input);
169
170 let mut s = sk << 3;
171 s = hm * s;
172 s = r + s;
173 s = s % &self.sub_order;
174
175 Signature {
176 r_b8: r8.clone(),
177 s: s,
178 }
179 }
180
181 pub fn verify(&self, pk: Point, sig: Signature, msg: BigInt) -> bool {
182 let hm_input = vec![
183 sig.r_b8.x.clone(),
184 sig.r_b8.y.clone(),
185 pk.x.clone(),
186 pk.y.clone(),
187 msg,
188 ];
189 let mimc7 = Mimc7::new();
190 let hm = mimc7.hash(hm_input);
191 let l = self.mul_scalar(self.b8.clone(), sig.s);
192 let r = self.add(&sig.r_b8, &self.mul_scalar(pk, 8.to_bigint().unwrap() * hm));
193 if l.x == r.x && l.y == r.y {
194 return true;
195 }
196 false
197 }
198}
199
200#[cfg(test)]
201mod tests {
202 use super::*;
203
204 #[test]
205 fn test_add_same_point() {
206 let p: Point = Point {
207 x: BigInt::parse_bytes(
208 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
209 10,
210 )
211 .unwrap(),
212 y: BigInt::parse_bytes(
213 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
214 10,
215 )
216 .unwrap(),
217 };
218 let q: Point = Point {
219 x: BigInt::parse_bytes(
220 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
221 10,
222 )
223 .unwrap(),
224 y: BigInt::parse_bytes(
225 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
226 10,
227 )
228 .unwrap(),
229 };
230 let bbjj = Babyjubjub::new();
231 let res = bbjj.add(&p, &q);
232 assert_eq!(
233 res.x.to_string(),
234 "6890855772600357754907169075114257697580319025794532037257385534741338397365"
235 );
236 assert_eq!(
237 res.y.to_string(),
238 "4338620300185947561074059802482547481416142213883829469920100239455078257889"
239 );
240 }
241 #[test]
242 fn test_add_different_points() {
243 let p: Point = Point {
244 x: BigInt::parse_bytes(
245 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
246 10,
247 )
248 .unwrap(),
249 y: BigInt::parse_bytes(
250 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
251 10,
252 )
253 .unwrap(),
254 };
255 let q: Point = Point {
256 x: BigInt::parse_bytes(
257 b"16540640123574156134436876038791482806971768689494387082833631921987005038935",
258 10,
259 )
260 .unwrap(),
261 y: BigInt::parse_bytes(
262 b"20819045374670962167435360035096875258406992893633759881276124905556507972311",
263 10,
264 )
265 .unwrap(),
266 };
267 let bbjj = Babyjubjub::new();
268 let res = bbjj.add(&p, &q);
269 assert_eq!(
270 res.x.to_string(),
271 "7916061937171219682591368294088513039687205273691143098332585753343424131937"
272 );
273 assert_eq!(
274 res.y.to_string(),
275 "14035240266687799601661095864649209771790948434046947201833777492504781204499"
276 );
277 }
278
279 #[test]
280 fn test_mul_scalar() {
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 bbjj = Babyjubjub::new();
294 let res_m = bbjj.mul_scalar(p.clone(), 3.to_bigint().unwrap());
295 let res_a = bbjj.add(&p, &p);
296 let res_a = bbjj.add(&res_a, &p);
297 assert_eq!(res_m.x, res_a.x);
298 assert_eq!(
299 res_m.x.to_string(),
300 "19372461775513343691590086534037741906533799473648040012278229434133483800898"
301 );
302 assert_eq!(
303 res_m.y.to_string(),
304 "9458658722007214007257525444427903161243386465067105737478306991484593958249"
305 );
306
307 let n = BigInt::parse_bytes(
308 b"14035240266687799601661095864649209771790948434046947201833777492504781204499",
309 10,
310 )
311 .unwrap();
312 let res2 = bbjj.mul_scalar(p.clone(), n);
313 assert_eq!(
314 res2.x.to_string(),
315 "17070357974431721403481313912716834497662307308519659060910483826664480189605"
316 );
317 assert_eq!(
318 res2.y.to_string(),
319 "4014745322800118607127020275658861516666525056516280575712425373174125159339"
320 );
321 }
322
323 #[test]
324 fn test_new_key_sign_verify() {
325 let bbjj = Babyjubjub::new();
326 let sk = bbjj.new_key();
327 let pk = bbjj.sk_to_pk(sk.clone());
328 let msg = 5.to_bigint().unwrap();
329 let sig = bbjj.sign(sk, msg.clone());
330 let v = bbjj.verify(pk, sig, msg);
331 assert_eq!(v, true);
332 }
333}