substrate_bn/
lib.rs

Help
1#![no_std]
2
3extern crate alloc;
4
5pub mod arith;
6mod fields;
7mod groups;
8
9use crate::fields::FieldElement;
10use crate::groups::{GroupElement, G1Params, G2Params, GroupParams};
11
12use alloc::vec::Vec;
13use core::ops::{Add, Mul, Neg, Sub};
14use rand::Rng;
15
16#[derive(Copy, Clone, Debug, PartialEq, Eq)]
17#[repr(C)]
18pub struct Fr(fields::Fr);
19
20impl Fr {
21    pub fn zero() -> Self {
22        Fr(fields::Fr::zero())
23    }
24    pub fn one() -> Self {
25        Fr(fields::Fr::one())
26    }
27    pub fn random<R: Rng>(rng: &mut R) -> Self {
28        Fr(fields::Fr::random(rng))
29    }
30    pub fn pow(&self, exp: Fr) -> Self {
31        Fr(self.0.pow(exp.0))
32    }
33    pub fn from_str(s: &str) -> Option<Self> {
34        fields::Fr::from_str(s).map(|e| Fr(e))
35    }
36    pub fn inverse(&self) -> Option<Self> {
37        self.0.inverse().map(|e| Fr(e))
38    }
39    pub fn is_zero(&self) -> bool {
40        self.0.is_zero()
41    }
42    pub fn interpret(buf: &[u8; 64]) -> Fr {
43        Fr(fields::Fr::interpret(buf))
44    }
45    pub fn from_slice(slice: &[u8]) -> Result<Self, FieldError> {
46        arith::U256::from_slice(slice)
47            .map_err(|_| FieldError::InvalidSliceLength) // todo: maybe more sensful error handling
48            .map(|x| Fr::new_mul_factor(x))
49    }
50    pub fn to_big_endian(&self, slice: &mut [u8]) -> Result<(), FieldError> {
51        self.0
52            .raw()
53            .to_big_endian(slice)
54            .map_err(|_| FieldError::InvalidSliceLength)
55    }
56    pub fn new(val: arith::U256) -> Option<Self> {
57        fields::Fr::new(val).map(|x| Fr(x))
58    }
59    pub fn new_mul_factor(val: arith::U256) -> Self {
60        Fr(fields::Fr::new_mul_factor(val))
61    }
62    pub fn into_u256(self) -> arith::U256 {
63        (self.0).into()
64    }
65    pub fn set_bit(&mut self, bit: usize, to: bool) {
66        self.0.set_bit(bit, to);
67    }
68}
69
70impl Add<Fr> for Fr {
71    type Output = Fr;
72
73    fn add(self, other: Fr) -> Fr {
74        Fr(self.0 + other.0)
75    }
76}
77
78impl Sub<Fr> for Fr {
79    type Output = Fr;
80
81    fn sub(self, other: Fr) -> Fr {
82        Fr(self.0 - other.0)
83    }
84}
85
86impl Neg for Fr {
87    type Output = Fr;
88
89    fn neg(self) -> Fr {
90        Fr(-self.0)
91    }
92}
93
94impl Mul for Fr {
95    type Output = Fr;
96
97    fn mul(self, other: Fr) -> Fr {
98        Fr(self.0 * other.0)
99    }
100}
101
102#[derive(Debug)]
103pub enum FieldError {
104    InvalidSliceLength,
105    InvalidU512Encoding,
106    NotMember,
107}
108
109#[derive(Debug)]
110pub enum CurveError {
111    InvalidEncoding,
112    NotMember,
113    Field(FieldError),
114    ToAffineConversion,
115}
116
117impl From<FieldError> for CurveError {
118    fn from(fe: FieldError) -> Self {
119        CurveError::Field(fe)
120    }
121}
122
123pub use crate::groups::Error as GroupError;
124
125#[derive(Copy, Clone, Debug, PartialEq, Eq)]
126#[repr(C)]
127pub struct Fq(fields::Fq);
128
129impl Fq {
130    pub fn zero() -> Self {
131        Fq(fields::Fq::zero())
132    }
133    pub fn one() -> Self {
134        Fq(fields::Fq::one())
135    }
136    pub fn random<R: Rng>(rng: &mut R) -> Self {
137        Fq(fields::Fq::random(rng))
138    }
139    pub fn pow(&self, exp: Fq) -> Self {
140        Fq(self.0.pow(exp.0))
141    }
142    pub fn from_str(s: &str) -> Option<Self> {
143        fields::Fq::from_str(s).map(|e| Fq(e))
144    }
145    pub fn inverse(&self) -> Option<Self> {
146        self.0.inverse().map(|e| Fq(e))
147    }
148    pub fn is_zero(&self) -> bool {
149        self.0.is_zero()
150    }
151    pub fn interpret(buf: &[u8; 64]) -> Fq {
152        Fq(fields::Fq::interpret(buf))
153    }
154    pub fn from_slice(slice: &[u8]) -> Result<Self, FieldError> {
155        arith::U256::from_slice(slice)
156            .map_err(|_| FieldError::InvalidSliceLength) // todo: maybe more sensful error handling
157            .and_then(|x| fields::Fq::new(x).ok_or(FieldError::NotMember))
158            .map(|x| Fq(x))
159    }
160    pub fn to_big_endian(&self, slice: &mut [u8]) -> Result<(), FieldError> {
161        let mut a: arith::U256 = self.0.into();
162        // convert from Montgomery representation
163        a.mul(
164            &fields::Fq::one().raw(),
165            &fields::Fq::modulus(),
166            self.0.inv(),
167        );
168        a.to_big_endian(slice)
169            .map_err(|_| FieldError::InvalidSliceLength)
170    }
171    pub fn from_u256(u256: arith::U256) -> Result<Self, FieldError> {
172        Ok(Fq(fields::Fq::new(u256).ok_or(FieldError::NotMember)?))
173    }
174    pub fn into_u256(self) -> arith::U256 {
175        (self.0).into()
176    }
177    pub fn modulus() -> arith::U256 {
178        fields::Fq::modulus()
179    }
180
181    pub fn sqrt(&self) -> Option<Self> {
182        self.0.sqrt().map(Fq)
183    }
184}
185
186impl Add<Fq> for Fq {
187    type Output = Fq;
188
189    fn add(self, other: Fq) -> Fq {
190        Fq(self.0 + other.0)
191    }
192}
193
194impl Sub<Fq> for Fq {
195    type Output = Fq;
196
197    fn sub(self, other: Fq) -> Fq {
198        Fq(self.0 - other.0)
199    }
200}
201
202impl Neg for Fq {
203    type Output = Fq;
204
205    fn neg(self) -> Fq {
206        Fq(-self.0)
207    }
208}
209
210impl Mul for Fq {
211    type Output = Fq;
212
213    fn mul(self, other: Fq) -> Fq {
214        Fq(self.0 * other.0)
215    }
216}
217
218#[derive(Copy, Clone, Debug, PartialEq, Eq)]
219#[repr(C)]
220pub struct Fq2(fields::Fq2);
221
222impl Fq2 {
223    pub fn one() -> Fq2 {
224        Fq2(fields::Fq2::one())
225    }
226
227    pub fn i() -> Fq2 {
228        Fq2(fields::Fq2::i())
229    }
230
231    pub fn zero() -> Fq2 {
232        Fq2(fields::Fq2::zero())
233    }
234
235    /// Initalizes new F_q2(a + bi, a is real coeff, b is imaginary)
236    pub fn new(a: Fq, b: Fq) -> Fq2 {
237        Fq2(fields::Fq2::new(a.0, b.0))
238    }
239
240    pub fn is_zero(&self) -> bool {
241        self.0.is_zero()
242    }
243
244    pub fn pow(&self, exp: arith::U256) -> Self {
245        Fq2(self.0.pow(exp))
246    }
247
248    pub fn real(&self) -> Fq {
249        Fq(*self.0.real())
250    }
251
252    pub fn imaginary(&self) -> Fq {
253        Fq(*self.0.imaginary())
254    }
255
256    pub fn sqrt(&self) -> Option<Self> {
257        self.0.sqrt().map(Fq2)
258    }
259
260    pub fn from_slice(bytes: &[u8]) -> Result<Self, FieldError> {
261        let u512 = arith::U512::from_slice(bytes).map_err(|_| FieldError::InvalidU512Encoding)?;
262        let (res, c0) = u512.divrem(&Fq::modulus());
263        Ok(Fq2::new(
264            Fq::from_u256(c0).map_err(|_| FieldError::NotMember)?,
265            Fq::from_u256(res.ok_or(FieldError::NotMember)?).map_err(|_| FieldError::NotMember)?,
266        ))
267    }
268}
269
270
271impl Add<Fq2> for Fq2 {
272    type Output = Self;
273
274    fn add(self, other: Self) -> Self {
275        Fq2(self.0 + other.0)
276    }
277}
278
279impl Sub<Fq2> for Fq2 {
280    type Output = Self;
281
282    fn sub(self, other: Self) -> Self {
283        Fq2(self.0 - other.0)
284    }
285}
286
287impl Neg for Fq2 {
288    type Output = Self;
289
290    fn neg(self) -> Self {
291        Fq2(-self.0)
292    }
293}
294
295impl Mul for Fq2 {
296    type Output = Self;
297
298    fn mul(self, other: Self) -> Self {
299        Fq2(self.0 * other.0)
300    }
301}
302
303pub trait Group
304    : Send
305    + Sync
306    + Copy
307    + Clone
308    + PartialEq
309    + Eq
310    + Sized
311    + Add<Self, Output = Self>
312    + Sub<Self, Output = Self>
313    + Neg<Output = Self>
314    + Mul<Fr, Output = Self> {
315    fn zero() -> Self;
316    fn one() -> Self;
317    fn random<R: Rng>(rng: &mut R) -> Self;
318    fn is_zero(&self) -> bool;
319    fn normalize(&mut self);
320}
321
322#[derive(Copy, Clone, Debug, PartialEq, Eq)]
323#[repr(C)]
324pub struct G1(groups::G1);
325
326impl G1 {
327    pub fn new(x: Fq, y: Fq, z: Fq) -> Self {
328        G1(groups::G1::new(x.0, y.0, z.0))
329    }
330
331    pub fn x(&self) -> Fq {
332        Fq(self.0.x().clone())
333    }
334
335    pub fn set_x(&mut self, x: Fq) {
336        *self.0.x_mut() = x.0
337    }
338
339    pub fn y(&self) -> Fq {
340        Fq(self.0.y().clone())
341    }
342
343    pub fn set_y(&mut self, y: Fq) {
344        *self.0.y_mut() = y.0
345    }
346
347    pub fn z(&self) -> Fq {
348        Fq(self.0.z().clone())
349    }
350
351    pub fn set_z(&mut self, z: Fq) {
352        *self.0.z_mut() = z.0
353    }
354
355    pub fn b() -> Fq {
356        Fq(G1Params::coeff_b())
357    }
358
359    pub fn from_compressed(bytes: &[u8]) -> Result<Self, CurveError> {
360        if bytes.len() != 33 { return Err(CurveError::InvalidEncoding); }
361
362        let sign = bytes[0];
363        let fq = Fq::from_slice(&bytes[1..])?;
364        let x = fq;
365        let y_squared = (fq * fq * fq) + Self::b();
366
367        let mut y = y_squared.sqrt().ok_or(CurveError::NotMember)?;
368
369        if sign == 2 && y.into_u256().get_bit(0).expect("bit 0 always exist; qed") { y = y.neg(); }
370        else if sign == 3 && !y.into_u256().get_bit(0).expect("bit 0 always exist; qed") { y = y.neg(); }
371        else if sign != 3 && sign != 2 {
372            return Err(CurveError::InvalidEncoding);
373        }
374        AffineG1::new(x, y).map_err(|_| CurveError::NotMember).map(Into::into)
375    }
376}
377
378impl Group for G1 {
379    fn zero() -> Self {
380        G1(groups::G1::zero())
381    }
382    fn one() -> Self {
383        G1(groups::G1::one())
384    }
385    fn random<R: Rng>(rng: &mut R) -> Self {
386        G1(groups::G1::random(rng))
387    }
388    fn is_zero(&self) -> bool {
389        self.0.is_zero()
390    }
391    fn normalize(&mut self) {
392        let new = match self.0.to_affine() {
393            Some(a) => a,
394            None => return,
395        };
396
397        self.0 = new.to_jacobian();
398    }
399}
400
401impl Add<G1> for G1 {
402    type Output = G1;
403
404    fn add(self, other: G1) -> G1 {
405        G1(self.0 + other.0)
406    }
407}
408
409impl Sub<G1> for G1 {
410    type Output = G1;
411
412    fn sub(self, other: G1) -> G1 {
413        G1(self.0 - other.0)
414    }
415}
416
417impl Neg for G1 {
418    type Output = G1;
419
420    fn neg(self) -> G1 {
421        G1(-self.0)
422    }
423}
424
425impl Mul<Fr> for G1 {
426    type Output = G1;
427
428    fn mul(self, other: Fr) -> G1 {
429        G1(self.0 * other.0)
430    }
431}
432
433#[derive(Copy, Clone, Debug, PartialEq, Eq)]
434#[repr(C)]
435pub struct AffineG1(groups::AffineG1);
436
437impl AffineG1 {
438    pub fn new(x: Fq, y: Fq) -> Result<Self, GroupError> {
439        Ok(AffineG1(groups::AffineG1::new(x.0, y.0)?))
440    }
441
442    pub fn x(&self) -> Fq {
443        Fq(self.0.x().clone())
444    }
445
446    pub fn set_x(&mut self, x: Fq) {
447        *self.0.x_mut() = x.0
448    }
449
450    pub fn y(&self) -> Fq {
451        Fq(self.0.y().clone())
452    }
453
454    pub fn set_y(&mut self, y: Fq) {
455        *self.0.y_mut() = y.0
456    }
457
458    pub fn from_jacobian(g1: G1) -> Option<Self> {
459        g1.0.to_affine().map(|x| AffineG1(x))
460    }
461}
462
463impl From<AffineG1> for G1 {
464    fn from(affine: AffineG1) -> Self {
465        G1(affine.0.to_jacobian())
466    }
467}
468
469#[derive(Copy, Clone, Debug, PartialEq, Eq)]
470#[repr(C)]
471pub struct G2(groups::G2);
472
473impl G2 {
474    pub fn new(x: Fq2, y: Fq2, z: Fq2) -> Self {
475        G2(groups::G2::new(x.0, y.0, z.0))
476    }
477
478    pub fn x(&self) -> Fq2 {
479        Fq2(self.0.x().clone())
480    }
481
482    pub fn set_x(&mut self, x: Fq2) {
483        *self.0.x_mut() = x.0
484    }
485
486    pub fn y(&self) -> Fq2 {
487        Fq2(self.0.y().clone())
488    }
489
490    pub fn set_y(&mut self, y: Fq2) {
491        *self.0.y_mut() = y.0
492    }
493
494    pub fn z(&self) -> Fq2 {
495        Fq2(self.0.z().clone())
496    }
497
498    pub fn set_z(&mut self, z: Fq2) {
499        *self.0.z_mut() = z.0
500    }
501
502    pub fn b() -> Fq2 {
503        Fq2(G2Params::coeff_b())
504    }
505
506    pub fn from_compressed(bytes: &[u8]) -> Result<Self, CurveError> {
507
508        if bytes.len() != 65 { return Err(CurveError::InvalidEncoding); }
509
510        let sign = bytes[0];
511        let x = Fq2::from_slice(&bytes[1..])?;
512
513        let y_squared = (x * x * x) + G2::b();
514        let y = y_squared.sqrt().ok_or(CurveError::NotMember)?;
515        let y_neg = -y;
516
517        let y_gt = y.0.to_u512() > y_neg.0.to_u512();
518
519        let e_y = if sign == 10 { if y_gt { y_neg } else { y } }
520        else if sign == 11 { if y_gt { y } else { y_neg } }
521        else {
522            return Err(CurveError::InvalidEncoding);
523        };
524
525        AffineG2::new(x, e_y).map_err(|_| CurveError::NotMember).map(Into::into)
526    }
527}
528
529impl Group for G2 {
530    fn zero() -> Self {
531        G2(groups::G2::zero())
532    }
533    fn one() -> Self {
534        G2(groups::G2::one())
535    }
536    fn random<R: Rng>(rng: &mut R) -> Self {
537        G2(groups::G2::random(rng))
538    }
539    fn is_zero(&self) -> bool {
540        self.0.is_zero()
541    }
542    fn normalize(&mut self) {
543        let new = match self.0.to_affine() {
544            Some(a) => a,
545            None => return,
546        };
547
548        self.0 = new.to_jacobian();
549    }
550}
551
552impl Add<G2> for G2 {
553    type Output = G2;
554
555    fn add(self, other: G2) -> G2 {
556        G2(self.0 + other.0)
557    }
558}
559
560impl Sub<G2> for G2 {
561    type Output = G2;
562
563    fn sub(self, other: G2) -> G2 {
564        G2(self.0 - other.0)
565    }
566}
567
568impl Neg for G2 {
569    type Output = G2;
570
571    fn neg(self) -> G2 {
572        G2(-self.0)
573    }
574}
575
576impl Mul<Fr> for G2 {
577    type Output = G2;
578
579    fn mul(self, other: Fr) -> G2 {
580        G2(self.0 * other.0)
581    }
582}
583
584#[derive(Copy, Clone, PartialEq, Eq)]
585#[repr(C)]
586pub struct Gt(fields::Fq12);
587
588impl Gt {
589    pub fn one() -> Self {
590        Gt(fields::Fq12::one())
591    }
592    pub fn pow(&self, exp: Fr) -> Self {
593        Gt(self.0.pow(exp.0))
594    }
595    pub fn inverse(&self) -> Option<Self> {
596        self.0.inverse().map(Gt)
597    }
598    pub fn final_exponentiation(&self) -> Option<Self> {
599        self.0.final_exponentiation().map(Gt)
600    }
601}
602
603impl Mul<Gt> for Gt {
604    type Output = Gt;
605
606    fn mul(self, other: Gt) -> Gt {
607        Gt(self.0 * other.0)
608    }
609}
610
611pub fn pairing(p: G1, q: G2) -> Gt {
612    Gt(groups::pairing(&p.0, &q.0))
613}
614
615pub fn pairing_batch(pairs: &[(G1, G2)]) -> Gt {
616    let mut ps : Vec<groups::G1> = Vec::new();
617    let mut qs : Vec<groups::G2> = Vec::new();
618    for (p, q) in pairs {
619        ps.push(p.0);
620        qs.push(q.0);
621    }
622    Gt(groups::pairing_batch(&ps, &qs))
623}
624
625pub fn miller_loop_batch(pairs: &[(G2, G1)]) -> Result<Gt, CurveError> {
626    let mut ps : Vec<groups::G2Precomp> = Vec::new();
627    let mut qs : Vec<groups::AffineG<groups::G1Params>> = Vec::new();
628    for (p, q) in pairs {
629        ps.push(p.0.to_affine().ok_or(CurveError::ToAffineConversion)?.precompute());
630        qs.push(q.0.to_affine().ok_or(CurveError::ToAffineConversion)?);
631    }
632    Ok(Gt(groups::miller_loop_batch(&ps, &qs)))
633}
634
635#[derive(Copy, Clone, PartialEq, Eq)]
636#[repr(C)]
637pub struct AffineG2(groups::AffineG2);
638
639impl AffineG2 {
640    pub fn new(x: Fq2, y: Fq2) -> Result<Self, GroupError> {
641        Ok(AffineG2(groups::AffineG2::new(x.0, y.0)?))
642    }
643
644    pub fn x(&self) -> Fq2 {
645        Fq2(self.0.x().clone())
646    }
647
648    pub fn set_x(&mut self, x: Fq2) {
649        *self.0.x_mut() = x.0
650    }
651
652    pub fn y(&self) -> Fq2 {
653        Fq2(self.0.y().clone())
654    }
655
656    pub fn set_y(&mut self, y: Fq2) {
657        *self.0.y_mut() = y.0
658    }
659
660    pub fn from_jacobian(g2: G2) -> Option<Self> {
661        g2.0.to_affine().map(|x| AffineG2(x))
662    }
663}
664
665impl From<AffineG2> for G2 {
666    fn from(affine: AffineG2) -> Self {
667        G2(affine.0.to_jacobian())
668    }
669}
670
671#[cfg(test)]
672mod tests {
673    use alloc::vec::Vec;
674    use super::{G1, Fq, G2, Fq2};
675
676    fn hex(s: &'static str) -> Vec<u8> {
677        use rustc_hex::FromHex;
678        s.from_hex().unwrap()
679    }
680
681    #[test]
682    fn g1_from_compressed() {
683        let g1 = G1::from_compressed(&hex("0230644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd46"))
684            .expect("Invalid g1 decompress result");
685        assert_eq!(g1.x(), Fq::from_str("21888242871839275222246405745257275088696311157297823662689037894645226208582").unwrap());
686        assert_eq!(g1.y(), Fq::from_str("3969792565221544645472939191694882283483352126195956956354061729942568608776").unwrap());
687        assert_eq!(g1.z(), Fq::one());
688    }
689
690
691    #[test]
692    fn g2_from_compressed() {
693        let g2 = G2::from_compressed(
694            &hex("0a023aed31b5a9e486366ea9988b05dba469c6206e58361d9c065bbea7d928204a761efc6e4fa08ed227650134b52c7f7dd0463963e8a4bf21f4899fe5da7f984a")
695        ).expect("Valid g2 point hex encoding");
696
697        assert_eq!(g2.x(),
698                   Fq2::new(
699                       Fq::from_str("5923585509243758863255447226263146374209884951848029582715967108651637186684").unwrap(),
700                       Fq::from_str("5336385337059958111259504403491065820971993066694750945459110579338490853570").unwrap(),
701                   )
702        );
703
704        assert_eq!(g2.y(),
705                   Fq2::new(
706                       Fq::from_str("10374495865873200088116930399159835104695426846400310764827677226300185211748").unwrap(),
707                       Fq::from_str("5256529835065685814318509161957442385362539991735248614869838648137856366932").unwrap(),
708                   )
709        );
710
711        // 0b prefix is point reflection on the curve
712        let g2 = -G2::from_compressed(
713            &hex("0b023aed31b5a9e486366ea9988b05dba469c6206e58361d9c065bbea7d928204a761efc6e4fa08ed227650134b52c7f7dd0463963e8a4bf21f4899fe5da7f984a")
714        ).expect("Valid g2 point hex encoding");
715
716        assert_eq!(g2.x(),
717                   Fq2::new(
718                       Fq::from_str("5923585509243758863255447226263146374209884951848029582715967108651637186684").unwrap(),
719                       Fq::from_str("5336385337059958111259504403491065820971993066694750945459110579338490853570").unwrap(),
720                   )
721        );
722
723        assert_eq!(g2.y(),
724                   Fq2::new(
725                       Fq::from_str("10374495865873200088116930399159835104695426846400310764827677226300185211748").unwrap(),
726                       Fq::from_str("5256529835065685814318509161957442385362539991735248614869838648137856366932").unwrap(),
727                   )
728        );
729
730        // valid point but invalid sign prefix
731        assert!(
732            G2::from_compressed(
733                &hex("0c023aed31b5a9e486366ea9988b05dba469c6206e58361d9c065bbea7d928204a761efc6e4fa08ed227650134b52c7f7dd0463963e8a4bf21f4899fe5da7f984a")
734            ).is_err()
735        );
736    }
737}
substrate_bn/lib.rs

substrate_bn/
lib.rs
