Module 0x1::bls12381_algebra

This module defines marker types, constants and test cases for working with BLS12-381 curves using the generic API defined in algebra.move. See https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-pairing-friendly-curves-11#name-bls-curves-for-the-128-bit- for the full specification of BLS12-381 curves.

Currently-supported BLS12-381 structures include Fq12, Fr, G1, G2 and Gt, along with their widely-used serialization formats, the pairing between G1, G2 and Gt, and the hash-to-curve operations for G1 and G2 defined in https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16.

Other unimplemented BLS12-381 structures and serialization formats are also listed here, as they help define some of the currently supported structures. Their implementation may also be added in the future.

Fq: the finite field $F_q$ used in BLS12-381 curves with a prime order $q$ equal to 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab.

FormatFqLsb: a serialization format for Fq elements, where an element is represented by a byte array b[] of size 48 with the least significant byte (LSB) coming first.

FormatFqMsb: a serialization format for Fq elements, where an element is represented by a byte array b[] of size 48 with the most significant byte (MSB) coming first.

Fq2: the finite field $F_{q^2}$ used in BLS12-381 curves, which is an extension field of Fq, constructed as $F_{q^2}=F_q[u]/(u^2+1)$.

FormatFq2LscLsb: a serialization format for Fq2 elements, where an element in the form $(c_0+c_1\cdot u)$ is represented by a byte array b[] of size 96, which is a concatenation of its coefficients serialized, with the least significant coefficient (LSC) coming first:

• b[0..48] is $c_0$ serialized using FormatFqLsb.
• b[48..96] is $c_1$ serialized using FormatFqLsb.

FormatFq2MscMsb: a serialization format for Fq2 elements, where an element in the form $(c_0+c_1\cdot u)$ is represented by a byte array b[] of size 96, which is a concatenation of its coefficients serialized, with the most significant coefficient (MSC) coming first:

• b[0..48] is $c_1$ serialized using FormatFqLsb.
• b[48..96] is $c_0$ serialized using FormatFqLsb.

Fq6: the finite field $F_{q^6}$ used in BLS12-381 curves, which is an extension field of Fq2, constructed as $F_{q^6}=F_{q^2}[v]/(v^3-u-1)$.

FormatFq6LscLsb: a serialization scheme for Fq6 elements, where an element in the form $(c_0+c_1\cdot v+c_2\cdot v^2)$ is represented by a byte array b[] of size 288, which is a concatenation of its coefficients serialized, with the least significant coefficient (LSC) coming first:

• b[0..96] is $c_0$ serialized using FormatFq2LscLsb.
• b[96..192] is $c_1$ serialized using FormatFq2LscLsb.
• b[192..288] is $c_2$ serialized using FormatFq2LscLsb.

G1Full: a group constructed by the points on the BLS12-381 curve $E(F_q): y^2=x^3+4$ and the point at infinity, under the elliptic curve point addition. It contains the prime-order subgroup $G_1$ used in pairing.

G2Full: a group constructed by the points on a curve $E’(F_{q^2}): y^2=x^3+4(u+1)$ and the point at infinity, under the elliptic curve point addition. It contains the prime-order subgroup $G_2$ used in pairing.

• Struct Fq12
• Struct FormatFq12LscLsb
• Struct G1
• Struct FormatG1Uncompr
• Struct FormatG1Compr
• Struct G2
• Struct FormatG2Uncompr
• Struct FormatG2Compr
• Struct Gt
• Struct FormatGt
• Struct Fr
• Struct FormatFrLsb
• Struct FormatFrMsb
• Struct HashG1XmdSha256SswuRo
• Struct HashG2XmdSha256SswuRo

Struct Fq12

The finite field $F_{q^12}$ used in BLS12-381 curves, which is an extension field of Fq6 (defined in the module documentation), constructed as $F_{q^12}=F_{q^6}[w]/(w^2-v)$.

struct Fq12

Struct FormatFq12LscLsb

A serialization scheme for Fq12 elements, where an element $(c_0+c_1\cdot w)$ is represented by a byte array b[] of size 576, which is a concatenation of its coefficients serialized, with the least significant coefficient (LSC) coming first.

• b[0..288] is $c_0$ serialized using FormatFq6LscLsb (defined in the module documentation).
• b[288..576] is $c_1$ serialized using FormatFq6LscLsb.

NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.

struct FormatFq12LscLsb

Struct G1

The group $G_1$ in BLS12-381-based pairing $G_1 \times G_2 \rightarrow G_t$. It is a subgroup of G1Full (defined in the module documentation) with a prime order $r$ equal to 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001. (so Fr is the associated scalar field).

struct G1

Struct FormatG1Uncompr

A serialization scheme for G1 elements derived from https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11.html#name-zcash-serialization-format-.

Below is the serialization procedure that takes a G1 element p and outputs a byte array of size 96.

1. Let (x,y) be the coordinates of p if p is on the curve, or (0,0) otherwise.
2. Serialize x and y into b_x[] and b_y[] respectively using FormatFqMsb (defined in the module documentation).
3. Concatenate b_x[] and b_y[] into b[].
4. If p is the point at infinity, set the infinity bit: b[0]: = b[0] | 0x40.
5. Return b[].

Below is the deserialization procedure that takes a byte array b[] and outputs either a G1 element or none.

1. If the size of b[] is not 96, return none.
2. Compute the compression flag as b[0] & 0x80 != 0.
3. If the compression flag is true, return none.
4. Compute the infinity flag as b[0] & 0x40 != 0.
5. If the infinity flag is set, return the point at infinity.
6. Deserialize [b[0] & 0x1f, b[1], …, b[47]] to x using FormatFqMsb. If x is none, return none.
7. Deserialize [b[48], …, b[95]] to y using FormatFqMsb. If y is none, return none.
8. Check if (x,y) is on curve E. If not, return none.
9. Check if (x,y) is in the subgroup of order r. If not, return none.
10. Return (x,y).

NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.

struct FormatG1Uncompr

Struct FormatG1Compr

A serialization scheme for G1 elements derived from https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11.html#name-zcash-serialization-format-.

Below is the serialization procedure that takes a G1 element p and outputs a byte array of size 48.

1. Let (x,y) be the coordinates of p if p is on the curve, or (0,0) otherwise.
2. Serialize x into b[] using FormatFqMsb (defined in the module documentation).
3. Set the compression bit: b[0] := b[0] | 0x80.
4. If p is the point at infinity, set the infinity bit: b[0]: = b[0] | 0x40.
5. If y > -y, set the lexicographical flag: b[0] := b[0] | 0x20.
6. Return b[].

Below is the deserialization procedure that takes a byte array b[] and outputs either a G1 element or none.

1. If the size of b[] is not 48, return none.
2. Compute the compression flag as b[0] & 0x80 != 0.
3. If the compression flag is false, return none.
4. Compute the infinity flag as b[0] & 0x40 != 0.
5. If the infinity flag is set, return the point at infinity.
6. Compute the lexicographical flag as b[0] & 0x20 != 0.
7. Deserialize [b[0] & 0x1f, b[1], …, b[47]] to x using FormatFqMsb. If x is none, return none.
8. Solve the curve equation with x for y. If no such y exists, return none.
9. Let y’ be max(y,-y) if the lexicographical flag is set, or min(y,-y) otherwise.
10. Check if (x,y’) is in the subgroup of order r. If not, return none.
11. Return (x,y’).

NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.

struct FormatG1Compr

Struct G2

The group $G_2$ in BLS12-381-based pairing $G_1 \times G_2 \rightarrow G_t$. It is a subgroup of G2Full (defined in the module documentation) with a prime order $r$ equal to 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001. (so Fr is the scalar field).

struct G2

Struct FormatG2Uncompr

A serialization scheme for G2 elements derived from https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11.html#name-zcash-serialization-format-.

Below is the serialization procedure that takes a G2 element p and outputs a byte array of size 192.

1. Let (x,y) be the coordinates of p if p is on the curve, or (0,0) otherwise.
2. Serialize x and y into b_x[] and b_y[] respectively using FormatFq2MscMsb (defined in the module documentation).
3. Concatenate b_x[] and b_y[] into b[].
4. If p is the point at infinity, set the infinity bit in b[]: b[0]: = b[0] | 0x40.
5. Return b[].

Below is the deserialization procedure that takes a byte array b[] and outputs either a G2 element or none.

1. If the size of b[] is not 192, return none.
2. Compute the compression flag as b[0] & 0x80 != 0.
3. If the compression flag is true, return none.
4. Compute the infinity flag as b[0] & 0x40 != 0.
5. If the infinity flag is set, return the point at infinity.
6. Deserialize [b[0] & 0x1f, …, b[95]] to x using FormatFq2MscMsb. If x is none, return none.
7. Deserialize [b[96], …, b[191]] to y using FormatFq2MscMsb. If y is none, return none.
8. Check if (x,y) is on the curve E’. If not, return none.
9. Check if (x,y) is in the subgroup of order r. If not, return none.
10. Return (x,y).

NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.

struct FormatG2Uncompr

Struct FormatG2Compr

A serialization scheme for G2 elements derived from https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11.html#name-zcash-serialization-format-.

Below is the serialization procedure that takes a G2 element p and outputs a byte array of size 96.

1. Let (x,y) be the coordinates of p if p is on the curve, or (0,0) otherwise.
2. Serialize x into b[] using FormatFq2MscMsb (defined in the module documentation).
3. Set the compression bit: b[0] := b[0] | 0x80.
4. If p is the point at infinity, set the infinity bit: b[0]: = b[0] | 0x40.
5. If y > -y, set the lexicographical flag: b[0] := b[0] | 0x20.
6. Return b[].

Below is the deserialization procedure that takes a byte array b[] and outputs either a G2 element or none.

1. If the size of b[] is not 96, return none.
2. Compute the compression flag as b[0] & 0x80 != 0.
3. If the compression flag is false, return none.
4. Compute the infinity flag as b[0] & 0x40 != 0.
5. If the infinity flag is set, return the point at infinity.
6. Compute the lexicographical flag as b[0] & 0x20 != 0.
7. Deserialize [b[0] & 0x1f, b[1], …, b[95]] to x using FormatFq2MscMsb. If x is none, return none.
8. Solve the curve equation with x for y. If no such y exists, return none.
9. Let y’ be max(y,-y) if the lexicographical flag is set, or min(y,-y) otherwise.
10. Check if (x,y’) is in the subgroup of order r. If not, return none.
11. Return (x,y’).

NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.

struct FormatG2Compr

Struct Gt

The group $G_t$ in BLS12-381-based pairing $G_1 \times G_2 \rightarrow G_t$. It is a multiplicative subgroup of Fq12, with a prime order $r$ equal to 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001. (so Fr is the scalar field). The identity of Gt is 1.

struct Gt

Struct FormatGt

A serialization scheme for Gt elements.

To serialize, it treats a Gt element p as an Fq12 element and serialize it using FormatFq12LscLsb.

To deserialize, it uses FormatFq12LscLsb to try deserializing to an Fq12 element then test the membership in Gt.

NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.

struct FormatGt

Struct Fr

The finite field $F_r$ that can be used as the scalar fields associated with the groups $G_1$, $G_2$, $G_t$ in BLS12-381-based pairing.

struct Fr

Struct FormatFrLsb

A serialization format for Fr elements, where an element is represented by a byte array b[] of size 32 with the least significant byte (LSB) coming first.

NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0, blst-0.3.7.

struct FormatFrLsb

Struct FormatFrMsb

A serialization scheme for Fr elements, where an element is represented by a byte array b[] of size 32 with the most significant byte (MSB) coming first.

NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0, blst-0.3.7.

struct FormatFrMsb

Struct HashG1XmdSha256SswuRo

The hash-to-curve suite BLS12381G1_XMD:SHA-256_SSWU_RO_ that hashes a byte array into G1 elements.

Full specification is defined in https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16#name-bls12-381-g1.

struct HashG1XmdSha256SswuRo

Struct HashG2XmdSha256SswuRo

The hash-to-curve suite BLS12381G2_XMD:SHA-256_SSWU_RO_ that hashes a byte array into G2 elements.

Full specification is defined in https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16#name-bls12-381-g2.

struct HashG2XmdSha256SswuRo