Module 0x1::bn254_algebra

This module defines marker types, constants and test cases for working with BN254 curves using the generic API defined in algebra.move. BN254 was sampled as part of the [BCTV14] paper . The name denotes that it is a Barreto-Naehrig curve of embedding degree 12, defined over a 254-bit (prime) field. The scalar field is highly 2-adic which supports subgroups of roots of unity of size <= 2^28. (as (21888242871839275222246405745257275088548364400416034343698204186575808495617 - 1) mod 2^28 = 0)

This curve is also implemented in libff under the name bn128. It is the same as the bn254 curve used in Ethereum (eg: go-ethereum).

CAUTION

This curve does not satisfy the 128-bit security level anymore.

Its current security is estimated at 128-bits (see “Updating Key Size Estimations for Pairings”; by Barbulescu, Razvan and Duquesne, Sylvain; in Journal of Cryptology; 2019; https://doi.org/10.1007/s00145-018-9280-5)

Curve information:

• Base field: q = 21888242871839275222246405745257275088696311157297823662689037894645226208583
• Scalar field: r = 21888242871839275222246405745257275088548364400416034343698204186575808495617
• valuation(q - 1, 2) = 1
• valuation(r - 1, 2) = 28
• G1 curve equation: y^2 = x^3 + 3
• G2 curve equation: y^2 = x^3 + B, where
• B = 3/(u+9) where Fq2 is represented as Fq[u]/(u^2+1) = Fq2(19485874751759354771024239261021720505790618469301721065564631296452457478373, 266929791119991161246907387137283842545076965332900288569378510910307636690)

Currently-supported BN254 structures include Fq12, Fr, Fq, Fq2, G1, G2 and Gt, along with their widely-used serialization formats, the pairing between G1, G2 and Gt.

Other unimplemented BN254 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.

Fq2: The finite field $F_{q^2}$ that can be used as the base field of $G_2$ which is an extension field of Fq, constructed as $F_{q^2}=F_{q}[u]/(u^2+1)$.

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

• b[0..32] is $c_0$ serialized using FormatFqLscLsb.
• b[32..64] is $c_1$ serialized using FormatFqLscLsb.

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

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 192, which is a concatenation of its coefficients serialized, with the least significant coefficient (LSC) coming first:

• b[0..64] is $c_0$ serialized using FormatFq2LscLsb.
• b[64..128] is $c_1$ serialized using FormatFq2LscLsb.
• b[128..192] is $c_2$ serialized using FormatFq2LscLsb.

G1Full: a group constructed by the points on the BN254 curve $E(F_q): y^2=x^3+3$ 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+3/(u+9)$ and the point at infinity, under the elliptic curve point addition. It contains the prime-order subgroup $G_2$ used in pairing.

• CAUTION
• Struct Fr
• Struct FormatFrLsb
• Struct FormatFrMsb
• Struct Fq
• Struct FormatFqLsb
• Struct FormatFqMsb
• Struct Fq12
• Struct FormatFq12LscLsb
• Struct G1
• Struct FormatG1Uncompr
• Struct FormatG1Compr
• Struct G2
• Struct FormatG2Uncompr
• Struct FormatG2Compr
• Struct Gt
• 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 BN254-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-bn254-0.4.0.

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-bn254-0.4.0.

struct FormatFrMsb

Struct Fq

The finite field $F_q$ that can be used as the base field of $G_1$

struct Fq

Struct FormatFqLsb

A serialization format for Fq 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-bn254-0.4.0.

struct FormatFqLsb

Struct FormatFqMsb

A serialization scheme for Fq 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-bn254-0.4.0.

struct FormatFqMsb

Struct Fq12

The finite field $F_{q^12}$ used in BN254 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)$. The field can downcast to Gt if it’s an element of the multiplicative subgroup Gt of Fq12 with a prime order $r$ = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001.

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 384, which is a concatenation of its coefficients serialized, with the least significant coefficient (LSC) coming first.

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

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

struct FormatFq12LscLsb

Struct G1

The group $G_1$ in BN254-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 arkworks.rs.

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

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 FormatFqLsb (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[N-1]: = b[N-1] | 0b0100_0000.
5. If y > -y, set the lexicographical bit: b[N-1]: = b[N-1] | 0b1000_0000.
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 N, return none.
2. Compute the infinity flag as b[N-1] & 0b0100_0000 != 0.
3. If the infinity flag is set, return the point at infinity.
4. Deserialize [b[0], b[1], …, b[N/2-1]] to x using FormatFqLsb. If x is none, return none.
5. Deserialize [b[N/2], …, b[N] & 0b0011_1111] to y using FormatFqLsb. If y is none, return none.
6. Check if (x,y) is on curve E. If not, return none.
7. Check if (x,y) is in the subgroup of order r. If not, return none.
8. Return (x,y).

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

struct FormatG1Uncompr

Struct FormatG1Compr

A serialization scheme for G1 elements derived from arkworks.rs

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

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 FormatFqLsb (defined in the module documentation).
3. If p is the point at infinity, set the infinity bit: b[N-1]: = b[N-1] | 0b0100_0000.
4. If y > -y, set the lexicographical flag: b[N-1] := b[N-1] | 0x1000_0000.
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 N, return none.
2. Compute the infinity flag as b[N-1] & 0b0100_0000 != 0.
3. If the infinity flag is set, return the point at infinity.
4. Compute the lexicographical flag as b[N-1] & 0b1000_0000 != 0.
5. Deserialize [b[0], b[1], …, b[N/2-1] & 0b0011_1111] to x using FormatFqLsb. If x is none, return none.
6. Solve the curve equation with x for y. If no such y exists, return none.
7. Let y’ be max(y,-y) if the lexicographical flag is set, or min(y,-y) otherwise.
8. Check if (x,y’) is in the subgroup of order r. If not, return none.
9. Return (x,y’).

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

struct FormatG1Compr

Struct G2

The group $G_2$ in BN254-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 arkworks.rs.

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

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 FormatFq2LscLsb (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[N-1]: = b[N-1] | 0b0100_0000.
5. If y > -y, set the lexicographical bit: b[N-1]: = b[N-1] | 0b1000_0000.
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 N, return none.
2. Compute the infinity flag as b[N-1] & 0b0100_0000 != 0.
3. If the infinity flag is set, return the point at infinity.
4. Deserialize [b[0], b[1], …, b[N/2-1]] to x using FormatFq2LscLsb. If x is none, return none.
5. Deserialize [b[N/2], …, b[N] & 0b0011_1111] to y using FormatFq2LscLsb. If y is none, return none.
6. Check if (x,y) is on curve E. If not, return none.
7. Check if (x,y) is in the subgroup of order r. If not, return none.
8. Return (x,y).

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

struct FormatG2Uncompr

Struct FormatG2Compr

A serialization scheme for G1 elements derived from arkworks.rs

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

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 FormatFq2LscLsb (defined in the module documentation).
3. If p is the point at infinity, set the infinity bit: b[N-1]: = b[N-1] | 0b0100_0000.
4. If y > -y, set the lexicographical flag: b[N-1] := b[N-1] | 0x1000_0000.
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 N, return none.
2. Compute the infinity flag as b[N-1] & 0b0100_0000 != 0.
3. If the infinity flag is set, return the point at infinity.
4. Compute the lexicographical flag as b[N-1] & 0b1000_0000 != 0.
5. Deserialize [b[0], b[1], …, b[N/2-1] & 0b0011_1111] to x using FormatFq2LscLsb. If x is none, return none.
6. Solve the curve equation with x for y. If no such y exists, return none.
7. Let y’ be max(y,-y) if the lexicographical flag is set, or min(y,-y) otherwise.
8. Check if (x,y’) is in the subgroup of order r. If not, return none.
9. Return (x,y’).

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

struct FormatG2Compr

Struct Gt

The group $G_t$ in BN254-based pairing $G_1 \times G_2 \rightarrow G_t$. It is a multiplicative subgroup of Fq12, so it can upcast to 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-bn254-0.4.0.

struct FormatGt