commonware_cryptography/bls12381/primitives/
group.rs

1//! Group operations over the BLS12-381 scalar field.
2//!
3//! This crate implements basic group operations over BLS12-381 elements,
4//! including point addition, scalar multiplication, and pairing operations.
5//!
6//! # Warning
7//!
8//! Ensure that points are checked to belong to the correct subgroup
9//! (G1 or G2) to prevent small subgroup attacks. This is particularly important
10//! when handling deserialized points or points received from untrusted sources. This
11//! is already taken care of for you if you use the provided `deserialize` function.
12
13use blst::{
14    blst_bendian_from_scalar, blst_fp12, blst_fr, blst_fr_add, blst_fr_from_scalar,
15    blst_fr_from_uint64, blst_fr_inverse, blst_fr_mul, blst_fr_sub, blst_hash_to_g1,
16    blst_hash_to_g2, blst_keygen, blst_p1, blst_p1_add_or_double, blst_p1_affine, blst_p1_compress,
17    blst_p1_from_affine, blst_p1_in_g1, blst_p1_is_inf, blst_p1_mult, blst_p1_to_affine,
18    blst_p1_uncompress, blst_p2, blst_p2_add_or_double, blst_p2_affine, blst_p2_compress,
19    blst_p2_from_affine, blst_p2_in_g2, blst_p2_is_inf, blst_p2_mult, blst_p2_to_affine,
20    blst_p2_uncompress, blst_scalar, blst_scalar_from_bendian, blst_scalar_from_fr, blst_sk_check,
21    Pairing, BLS12_381_G1, BLS12_381_G2, BLS12_381_NEG_G1, BLST_ERROR,
22};
23use commonware_utils::SizedSerialize;
24use rand::RngCore;
25use std::ptr;
26use zeroize::Zeroize;
27
28/// Domain separation tag used when hashing a message to a curve (G1 or G2).
29///
30/// Reference: <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bls-signature-05#name-ciphersuites>
31pub type DST = &'static [u8];
32
33/// An element of a group.
34pub trait Element: Clone + Eq + PartialEq + Send + Sync {
35    /// Returns the additive identity.
36    fn zero() -> Self;
37
38    /// Returns the multiplicative identity.
39    fn one() -> Self;
40
41    /// Adds to self in-place.
42    fn add(&mut self, rhs: &Self);
43
44    /// Multiplies self in-place.
45    fn mul(&mut self, rhs: &Scalar);
46
47    /// Canonically serializes the element.
48    fn serialize(&self) -> Vec<u8>;
49
50    /// Serialized size of the element.
51    fn size() -> usize;
52
53    /// Deserializes an untrusted, canonically-encoded element.
54    ///
55    /// This function performs any validation necessary to ensure the decoded
56    /// element is valid (like an infinity or group check).
57    fn deserialize(bytes: &[u8]) -> Option<Self>;
58}
59
60/// An element of a group that supports message hashing.
61pub trait Point: Element {
62    /// Maps the provided data to a group element.
63    fn map(&mut self, dst: DST, message: &[u8]);
64}
65
66/// A scalar representing an element of the BLS12-381 finite field.
67#[derive(Debug, Clone, Copy, Eq, PartialEq)]
68#[repr(transparent)]
69pub struct Scalar(blst_fr);
70
71/// Length of a scalar in bytes.
72const SCALAR_LENGTH: usize = 32;
73
74/// This constant serves as the multiplicative identity (i.e., "one") in the
75/// BLS12-381 finite field, ensuring that arithmetic is carried out within the
76/// correct modulo.
77///
78/// `R = 2^256 mod q` in little-endian Montgomery form which is equivalent to 1 in little-endian
79/// non-Montgomery form:
80///
81/// ```txt
82/// mod(2^256, 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001) = 0x1824b159acc5056f998c4fefecbc4ff55884b7fa0003480200000001fffffffe
83/// ```
84///
85/// Reference: <https://github.com/filecoin-project/blstrs/blob/ffbb41d1495d84e40a712583346439924603b49a/src/scalar.rs#L77-L89>
86const BLST_FR_ONE: Scalar = Scalar(blst_fr {
87    l: [
88        0x0000_0001_ffff_fffe,
89        0x5884_b7fa_0003_4802,
90        0x998c_4fef_ecbc_4ff5,
91        0x1824_b159_acc5_056f,
92    ],
93});
94
95/// A point on the BLS12-381 G1 curve.
96#[derive(Debug, Clone, Copy, Eq, PartialEq)]
97#[repr(transparent)]
98pub struct G1(blst_p1);
99
100/// The size in bytes of an encoded G1 element.
101pub const G1_ELEMENT_BYTE_LENGTH: usize = 48;
102
103/// Domain separation tag for hashing a proof of possession (compressed G2) to G1.
104pub const G1_PROOF_OF_POSSESSION: DST = b"BLS_POP_BLS12381G1_XMD:SHA-256_SSWU_RO_POP_";
105
106/// Domain separation tag for hashing a message to G1.
107///
108/// We use the `POP` scheme for hashing all messages because this crate is expected to be
109/// used in a Byzantine environment (where any player may attempt a rogue key attack) and
110/// any message could be aggregated into a multi-signature (which requires a proof-of-possession
111/// to be safely deployed in this environment).
112pub const G1_MESSAGE: DST = b"BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_POP_";
113
114/// A point on the BLS12-381 G2 curve.
115#[derive(Debug, Clone, Copy, Eq, PartialEq)]
116#[repr(transparent)]
117pub struct G2(blst_p2);
118
119/// The size in bytes of an encoded G2 element.
120pub const G2_ELEMENT_BYTE_LENGTH: usize = 96;
121
122/// Domain separation tag for hashing a proof of possession (compressed G1) to G2.
123pub const G2_PROOF_OF_POSSESSION: DST = b"BLS_POP_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_";
124
125/// Domain separation tag for hashing a message to G2.
126///
127/// We use the `POP` scheme for hashing all messages because this crate is expected to be
128/// used in a Byzantine environment (where any player may attempt a rogue key attack) and
129/// any message could be aggregated into a multi-signature (which requires a proof-of-possession
130/// to be safely deployed in this environment).
131pub const G2_MESSAGE: DST = b"BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_";
132
133/// The target group of the BLS12-381 pairing.
134///
135/// This is an element in the extension field `F_p^12` and is
136/// produced as the result of a pairing operation.
137#[derive(Debug, Clone, Copy, Eq, PartialEq)]
138pub struct GT(blst_fp12);
139
140/// The private key type.
141pub type Private = Scalar;
142
143/// The private key length.
144pub const PRIVATE_KEY_LENGTH: usize = SCALAR_LENGTH;
145
146/// The default public key type (G1).
147pub type Public = G1;
148
149/// The default public key length (G1).
150pub const PUBLIC_KEY_LENGTH: usize = G1_ELEMENT_BYTE_LENGTH;
151
152/// The default signature type (G2).
153pub type Signature = G2;
154
155/// The default signature length (G2).
156pub const SIGNATURE_LENGTH: usize = G2_ELEMENT_BYTE_LENGTH;
157
158/// The DST for hashing a proof of possession to the default signature type (G2).
159pub const PROOF_OF_POSSESSION: DST = G2_PROOF_OF_POSSESSION;
160
161/// The DST for hashing a message to the default signature type (G2).
162pub const MESSAGE: DST = G2_MESSAGE;
163
164/// Returns the size in bits of a given blst_scalar (represented in little-endian).
165fn bits(scalar: &blst_scalar) -> usize {
166    let mut bits: usize = SCALAR_LENGTH * 8;
167    for i in scalar.b.iter().rev() {
168        let leading = i.leading_zeros();
169        bits -= leading as usize;
170        if leading < 8 {
171            break;
172        }
173    }
174    bits
175}
176
177/// A share of a threshold signing key.
178#[derive(Debug, Clone, PartialEq, Copy)]
179pub struct Share {
180    /// The share's index in the polynomial.
181    pub index: u32,
182    /// The scalar corresponding to the share's secret.
183    pub private: Private,
184}
185
186impl Share {
187    /// Returns the public key corresponding to the share.
188    ///
189    /// This can be verified against the public polynomial.
190    pub fn public(&self) -> Public {
191        let mut public = <Public as Element>::one();
192        public.mul(&self.private);
193        public
194    }
195
196    /// Canonically serializes the share.
197    pub fn serialize(&self) -> Vec<u8> {
198        let mut bytes = [0u8; u32::SERIALIZED_LEN + SCALAR_LENGTH];
199        bytes[..u32::SERIALIZED_LEN].copy_from_slice(&self.index.to_be_bytes());
200        bytes[u32::SERIALIZED_LEN..].copy_from_slice(&self.private.serialize());
201        bytes.to_vec()
202    }
203
204    /// Deserializes a canonically encoded share.
205    pub fn deserialize(bytes: &[u8]) -> Option<Self> {
206        if bytes.len() != u32::SERIALIZED_LEN + SCALAR_LENGTH {
207            return None;
208        }
209        let index = u32::from_be_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]);
210        let private = Private::deserialize(&bytes[u32::SERIALIZED_LEN..])?;
211        Some(Self { index, private })
212    }
213}
214
215impl Scalar {
216    /// Generates a random scalar using the provided RNG.
217    pub fn rand<R: RngCore>(rng: &mut R) -> Self {
218        // Generate a random 64 byte buffer
219        let mut ikm = [0u8; 64];
220        rng.fill_bytes(&mut ikm);
221
222        // Generate a scalar from the randomly populated buffer
223        let mut ret = blst_fr::default();
224        unsafe {
225            let mut sc = blst_scalar::default();
226            blst_keygen(&mut sc, ikm.as_ptr(), ikm.len(), ptr::null(), 0);
227            blst_fr_from_scalar(&mut ret, &sc);
228        }
229
230        // Zeroize the ikm buffer
231        ikm.zeroize();
232        Self(ret)
233    }
234
235    /// Sets the scalar to be the provided integer.
236    pub fn set_int(&mut self, i: u32) {
237        // blst requires a buffer of 4 uint64 values. Failure to provide one will
238        // result in unexpected behavior (will read past the provided buffer).
239        //
240        // Reference: https://github.com/supranational/blst/blob/415d4f0e2347a794091836a3065206edfd9c72f3/bindings/blst.h#L102
241        let buffer = [i as u64, 0, 0, 0];
242        unsafe { blst_fr_from_uint64(&mut self.0, buffer.as_ptr()) };
243    }
244
245    /// Computes the inverse of the scalar.
246    pub fn inverse(&self) -> Option<Self> {
247        if *self == Self::zero() {
248            return None;
249        }
250        let mut ret = blst_fr::default();
251        unsafe { blst_fr_inverse(&mut ret, &self.0) };
252        Some(Self(ret))
253    }
254
255    /// Subtracts the provided scalar from self in-place.
256    pub fn sub(&mut self, rhs: &Self) {
257        unsafe { blst_fr_sub(&mut self.0, &self.0, &rhs.0) }
258    }
259}
260
261impl Zeroize for Scalar {
262    fn zeroize(&mut self) {
263        self.0.l.zeroize();
264    }
265}
266
267impl Element for Scalar {
268    fn zero() -> Self {
269        Self(blst_fr::default())
270    }
271
272    fn one() -> Self {
273        BLST_FR_ONE
274    }
275
276    fn add(&mut self, rhs: &Self) {
277        unsafe {
278            blst_fr_add(&mut self.0, &self.0, &rhs.0);
279        }
280    }
281
282    fn mul(&mut self, rhs: &Self) {
283        unsafe {
284            blst_fr_mul(&mut self.0, &self.0, &rhs.0);
285        }
286    }
287
288    fn serialize(&self) -> Vec<u8> {
289        let mut bytes = [0u8; SCALAR_LENGTH];
290        unsafe {
291            let mut scalar = blst_scalar::default();
292            blst_scalar_from_fr(&mut scalar, &self.0);
293            blst_bendian_from_scalar(bytes.as_mut_ptr(), &scalar);
294        }
295        bytes.to_vec()
296    }
297
298    fn deserialize(bytes: &[u8]) -> Option<Self> {
299        if bytes.len() != SCALAR_LENGTH {
300            return None;
301        }
302        let mut ret = blst_fr::default();
303        unsafe {
304            let mut scalar = blst_scalar::default();
305            blst_scalar_from_bendian(&mut scalar, bytes.as_ptr());
306            // We use `blst_sk_check` instead of `blst_scalar_fr_check` because the former
307            // performs a non-zero check.
308            //
309            // The IETF BLS12-381 specification allows for zero scalars up to (inclusive) Draft 3
310            // but disallows them after.
311            //
312            // References:
313            // * https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bls-signature-03#section-2.3
314            // * https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bls-signature-04#section-2.3
315            if !blst_sk_check(&scalar) {
316                return None;
317            }
318            blst_fr_from_scalar(&mut ret, &scalar);
319        }
320        Some(Self(ret))
321    }
322
323    fn size() -> usize {
324        SCALAR_LENGTH
325    }
326}
327
328impl Element for G1 {
329    fn zero() -> Self {
330        Self(blst_p1::default())
331    }
332
333    fn one() -> Self {
334        let mut ret = blst_p1::default();
335        unsafe {
336            blst_p1_from_affine(&mut ret, &BLS12_381_G1);
337        }
338        Self(ret)
339    }
340
341    fn add(&mut self, rhs: &Self) {
342        unsafe {
343            blst_p1_add_or_double(&mut self.0, &self.0, &rhs.0);
344        }
345    }
346
347    fn mul(&mut self, rhs: &Scalar) {
348        let mut scalar: blst_scalar = blst_scalar::default();
349        unsafe {
350            blst_scalar_from_fr(&mut scalar, &rhs.0);
351            blst_p1_mult(&mut self.0, &self.0, scalar.b.as_ptr(), bits(&scalar));
352        }
353    }
354
355    fn serialize(&self) -> Vec<u8> {
356        let mut bytes = [0u8; G1_ELEMENT_BYTE_LENGTH];
357        unsafe {
358            blst_p1_compress(bytes.as_mut_ptr(), &self.0);
359        }
360        bytes.to_vec()
361    }
362
363    fn deserialize(bytes: &[u8]) -> Option<Self> {
364        if bytes.len() != G1_ELEMENT_BYTE_LENGTH {
365            return None;
366        }
367        let mut ret = blst_p1::default();
368        unsafe {
369            let mut affine = blst_p1_affine::default();
370            if blst_p1_uncompress(&mut affine, bytes.as_ptr()) != BLST_ERROR::BLST_SUCCESS {
371                return None;
372            }
373            blst_p1_from_affine(&mut ret, &affine);
374
375            // Verify that deserialized element isn't infinite
376            if blst_p1_is_inf(&ret) {
377                return None;
378            }
379
380            // Verify that the deserialized element is in G1
381            if !blst_p1_in_g1(&ret) {
382                return None;
383            }
384        }
385        Some(Self(ret))
386    }
387
388    fn size() -> usize {
389        G1_ELEMENT_BYTE_LENGTH
390    }
391}
392
393impl Point for G1 {
394    fn map(&mut self, dst: DST, data: &[u8]) {
395        unsafe {
396            blst_hash_to_g1(
397                &mut self.0,
398                data.as_ptr(),
399                data.len(),
400                dst.as_ptr(),
401                dst.len(),
402                ptr::null(),
403                0,
404            );
405        }
406    }
407}
408
409impl Element for G2 {
410    fn zero() -> Self {
411        Self(blst_p2::default())
412    }
413
414    fn one() -> Self {
415        let mut ret = blst_p2::default();
416        unsafe {
417            blst_p2_from_affine(&mut ret, &BLS12_381_G2);
418        }
419        Self(ret)
420    }
421
422    fn add(&mut self, rhs: &Self) {
423        unsafe {
424            blst_p2_add_or_double(&mut self.0, &self.0, &rhs.0);
425        }
426    }
427
428    fn mul(&mut self, rhs: &Scalar) {
429        let mut scalar = blst_scalar::default();
430        unsafe {
431            blst_scalar_from_fr(&mut scalar, &rhs.0);
432            blst_p2_mult(&mut self.0, &self.0, scalar.b.as_ptr(), bits(&scalar));
433        }
434    }
435
436    fn serialize(&self) -> Vec<u8> {
437        let mut bytes = [0u8; G2_ELEMENT_BYTE_LENGTH];
438        unsafe {
439            blst_p2_compress(bytes.as_mut_ptr(), &self.0);
440        }
441        bytes.to_vec()
442    }
443
444    fn deserialize(bytes: &[u8]) -> Option<Self> {
445        if bytes.len() != G2_ELEMENT_BYTE_LENGTH {
446            return None;
447        }
448        let mut ret = blst_p2::default();
449        unsafe {
450            let mut affine = blst_p2_affine::default();
451            if blst_p2_uncompress(&mut affine, bytes.as_ptr()) != BLST_ERROR::BLST_SUCCESS {
452                return None;
453            }
454            blst_p2_from_affine(&mut ret, &affine);
455
456            // Verify that deserialized element isn't infinite
457            if blst_p2_is_inf(&ret) {
458                return None;
459            }
460
461            // Verify that the deserialized element is in G2
462            if !blst_p2_in_g2(&ret) {
463                return None;
464            }
465        }
466        Some(Self(ret))
467    }
468
469    fn size() -> usize {
470        G2_ELEMENT_BYTE_LENGTH
471    }
472}
473
474impl Point for G2 {
475    fn map(&mut self, dst: DST, data: &[u8]) {
476        unsafe {
477            blst_hash_to_g2(
478                &mut self.0,
479                data.as_ptr(),
480                data.len(),
481                dst.as_ptr(),
482                dst.len(),
483                ptr::null(),
484                0,
485            );
486        }
487    }
488}
489
490/// Verifies that `e(pk,hm)` is equal to `e(G1::one(),sig)` using a single product check with
491/// a negated G1 generator (`e(pk,hm) * e(-G1::one(),sig) == 1`).
492pub(super) fn equal(pk: &G1, sig: &G2, hm: &G2) -> bool {
493    // Create a pairing context
494    //
495    // We only handle pre-hashed messages, so we leave the domain separator tag (`DST`) empty.
496    let mut pairing = Pairing::new(false, &[]);
497
498    // Convert `sig` into affine and aggregate `e(-G1::one(), sig)`
499    let mut q = blst_p2_affine::default();
500    unsafe {
501        blst_p2_to_affine(&mut q, &sig.0);
502        pairing.raw_aggregate(&q, &BLS12_381_NEG_G1);
503    }
504
505    // Convert `pk` and `hm` into affine
506    let mut p = blst_p1_affine::default();
507    let mut q = blst_p2_affine::default();
508    unsafe {
509        blst_p1_to_affine(&mut p, &pk.0);
510        blst_p2_to_affine(&mut q, &hm.0);
511    }
512
513    // Aggregate `e(pk, hm)`
514    pairing.raw_aggregate(&q, &p);
515
516    // Finalize the pairing accumulation and verify the result
517    //
518    // If `finalverify()` returns `true`, it means `e(pk,hm) * e(-G1::one(),sig) == 1`. This
519    // is equivalent to `e(pk,hm) == e(G1::one(),sig)`.
520    pairing.commit();
521    pairing.finalverify(None)
522}
523
524#[cfg(test)]
525mod tests {
526    use super::*;
527    use rand::prelude::*;
528
529    #[test]
530    fn basic_group() {
531        // Reference: https://github.com/celo-org/celo-threshold-bls-rs/blob/b0ef82ff79769d085a5a7d3f4fe690b1c8fe6dc9/crates/threshold-bls/src/curve/bls12381.rs#L200-L220
532        let s = Scalar::rand(&mut thread_rng());
533        let mut e1 = s;
534        let e2 = s;
535        let mut s2 = s;
536        s2.add(&s);
537        s2.mul(&s);
538        e1.add(&e2);
539        e1.mul(&e2);
540
541        // p1 = s2 * G = (s+s)G
542        let mut p1 = G1::zero();
543        p1.mul(&s2);
544
545        // p2 = sG + sG = s2 * G
546        let mut p2 = G1::zero();
547        p2.mul(&s);
548        p2.add(&p2.clone());
549        assert_eq!(p1, p2);
550    }
551}
commonware_cryptography/bls12381/primitives/group.rs

commonware_cryptography/bls12381/primitives/
group.rs
