babyjubjub-ark/src/lib.rs
src/lib.rsRaw
1extern crate num;
2extern crate num_bigint;
3extern crate num_traits;
4
5use num_bigint::BigInt;
6use num_traits::{One, Zero};
7
8mod utils;
9
10#[derive(Clone, Debug)]
11pub struct Point {
12 pub x: BigInt,
13 pub y: BigInt,
14}
15
16pub struct Babyjubjub {
17 d: BigInt,
18 a: BigInt,
19 q: BigInt,
20}
21
22impl Babyjubjub {
23 pub fn new() -> Babyjubjub {
24 let d: BigInt = BigInt::parse_bytes(b"168696", 10).unwrap();
25 let a: BigInt = BigInt::parse_bytes(b"168700", 10).unwrap();
26 let q: BigInt = BigInt::parse_bytes(
27 b"21888242871839275222246405745257275088548364400416034343698204186575808495617",
28 10,
29 )
30 .unwrap();
31 Babyjubjub { d: d, a: a, q: q }
32 }
33
34 pub fn add(&self, p: &Point, q: &Point) -> Point {
35 // x = (x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2))
36 // y = (y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2))
37
38 // x = (x1 * y2 + y1 * x2) / (1 + d * x1 * y1 * y2)
39 let one: BigInt = One::one();
40 let x_num: BigInt = &p.x * &q.y + &p.y * &q.x;
41 let x_den: BigInt = &one + &self.d * &p.x * &q.x * &p.y * &q.y;
42 let x_den_inv = utils::mod_inverse0(&x_den, &self.q);
43 // let x_den_inv = utils::mod_inverse1(x_den, self.q.clone());
44 // let x_den_inv = utils::mod_inverse2(x_den, self.q.clone());
45 let x: BigInt = utils::modulus(&(&x_num * &x_den_inv), &self.q);
46
47 // y = (y1 * y2 - a * x1 * x2) / (1 - d * x1 * x2 * y1 * y2)
48 let y_num = &p.y * &q.y - &self.a * &p.x * &q.x;
49 let y_den = utils::modulus(&(&one - &self.d * &p.x * &q.x * &p.y * &q.y), &self.q);
50 let y_den_inv = utils::mod_inverse0(&y_den, &self.q);
51 // let y_den_inv = utils::mod_inverse1(y_den, self.q.clone());
52 // let y_den_inv = utils::mod_inverse2(y_den, self.q.clone());
53 let y: BigInt = utils::modulus(&(&y_num * &y_den_inv), &self.q);
54
55 Point { x: x, y: y }
56 }
57
58 pub fn mul_scalar(&self, p: Point, n: BigInt) -> Point {
59 // TODO use & in p and n to avoid clones on function call
60 let mut r: Point = Point {
61 x: Zero::zero(),
62 y: One::one(),
63 };
64 let mut rem: BigInt = n;
65 let mut exp: Point = p;
66
67 let zero: BigInt = Zero::zero();
68 let one: BigInt = One::one();
69 while rem != zero {
70 let is_odd = &rem & &one == one;
71 if is_odd == true {
72 r = self.add(&r, &exp);
73 }
74 exp = self.add(&exp, &exp);
75 rem = rem >> 1;
76 }
77 r
78 }
79}
80
81#[cfg(test)]
82mod tests {
83 use super::*;
84 use num_bigint::ToBigInt;
85
86 #[test]
87 fn test_add_same_point() {
88 let p: Point = Point {
89 x: BigInt::parse_bytes(
90 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
91 10,
92 )
93 .unwrap(),
94 y: BigInt::parse_bytes(
95 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
96 10,
97 )
98 .unwrap(),
99 };
100 let q: Point = Point {
101 x: BigInt::parse_bytes(
102 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
103 10,
104 )
105 .unwrap(),
106 y: BigInt::parse_bytes(
107 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
108 10,
109 )
110 .unwrap(),
111 };
112 let bbj = Babyjubjub::new();
113 let res = bbj.add(&p, &q);
114 assert_eq!(
115 res.x.to_string(),
116 "6890855772600357754907169075114257697580319025794532037257385534741338397365"
117 );
118 assert_eq!(
119 res.y.to_string(),
120 "4338620300185947561074059802482547481416142213883829469920100239455078257889"
121 );
122 }
123 #[test]
124 fn test_add_different_points() {
125 let p: Point = Point {
126 x: BigInt::parse_bytes(
127 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
128 10,
129 )
130 .unwrap(),
131 y: BigInt::parse_bytes(
132 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
133 10,
134 )
135 .unwrap(),
136 };
137 let q: Point = Point {
138 x: BigInt::parse_bytes(
139 b"16540640123574156134436876038791482806971768689494387082833631921987005038935",
140 10,
141 )
142 .unwrap(),
143 y: BigInt::parse_bytes(
144 b"20819045374670962167435360035096875258406992893633759881276124905556507972311",
145 10,
146 )
147 .unwrap(),
148 };
149 let bbj = Babyjubjub::new();
150 let res = bbj.add(&p, &q);
151 assert_eq!(
152 res.x.to_string(),
153 "7916061937171219682591368294088513039687205273691143098332585753343424131937"
154 );
155 assert_eq!(
156 res.y.to_string(),
157 "14035240266687799601661095864649209771790948434046947201833777492504781204499"
158 );
159 }
160
161 #[test]
162 fn test_mul_scalar() {
163 let p: Point = Point {
164 x: BigInt::parse_bytes(
165 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
166 10,
167 )
168 .unwrap(),
169 y: BigInt::parse_bytes(
170 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
171 10,
172 )
173 .unwrap(),
174 };
175 let bbj = Babyjubjub::new();
176 let res_m = bbj.mul_scalar(p.clone(), 3.to_bigint().unwrap());
177 let res_a = bbj.add(&p, &p);
178 let res_a = bbj.add(&res_a, &p);
179 assert_eq!(res_m.x, res_a.x);
180 assert_eq!(
181 res_m.x.to_string(),
182 "19372461775513343691590086534037741906533799473648040012278229434133483800898"
183 );
184 assert_eq!(
185 res_m.y.to_string(),
186 "9458658722007214007257525444427903161243386465067105737478306991484593958249"
187 );
188
189 let n = BigInt::parse_bytes(
190 b"14035240266687799601661095864649209771790948434046947201833777492504781204499",
191 10,
192 )
193 .unwrap();
194 let res2 = bbj.mul_scalar(p.clone(), n);
195 assert_eq!(
196 res2.x.to_string(),
197 "17070357974431721403481313912716834497662307308519659060910483826664480189605"
198 );
199 assert_eq!(
200 res2.y.to_string(),
201 "4014745322800118607127020275658861516666525056516280575712425373174125159339"
202 );
203 }
204}