# BW6-761 curve operations

EIP-3026 proposes the addition of seven separate precompiles to perform operations on the BW6-761 curve, which is necessary for efficiently performing verification of one-layer composed zkSNARKs proofs. These precompiles include point addition and multiplication on a curve defined over a prime field, multiexponentiation on a curve defined over a prime field, point addition and multiplication on a curve twist defined over a prime field, multiexponentiation on a curve twist defined over a prime field, and pairing operations between a set of pairs of (G1, G2) points. The multiexponentiation operations are a generalization of point multiplication, but separate precompiles are proposed because running a single multiplication through multiexponentiation seems to be 20% more expensive. The implementation includes a Golang implementation with Intel assembly and precompiles for OpenEthereum (EY/Parity), as well as SageMath and Magma scripts. The document emphasizes the importance of a "constant time" property for performed operations, but explicitly states that this precompile is not required to perform all operations using constant time algorithms. The document also notes that strictly following the spec will eliminate security implications or consensus implications in contrast to the previous BN254 precompile.

###### Video

###### Original

## Abstract

This precompile adds operations for the BW6-761 curve (from the EY/Inria **Optimized and secure pairing-friendly elliptic curves suitable for one layer proof composition** research paper) as a precompile in a set necessary to *efficiently* perform verification of one-layer composed zkSNARKs proofs.
If `block.number >= X`

we introduce *seven* separate precompiles to perform the following operations (addresses to be determined):

- BW6_G1_ADD - to perform point addition on a curve defined over a prime field
- BW6_G1_MUL - to perform point multiplication on a curve defined over a prime field
- BW6_G1_MULTIEXP - to perform multiexponentiation on a curve defined over a prime field
- BW6_G2_ADD - to perform point addition on a curve twist defined the base a prime field
- BW6_G2_MUL - to perform point multiplication on a curve twist defined over a prime field
- BW6_G2_MULTIEXP - to perform multiexponentiation on a curve twist defined over a prime field
- BW6_PAIRING - to perform a pairing operations between a set of
*pairs*of (G1, G2) points

The multiexponentiation operations are a generalization of point multiplication, but separate precompiles are prosposed because running a single MUL through MULTIEXP seems to be 20% more expensive.

## Motivation

This EIP is based on and tends to replace matter-labs' proposol for significant performance reasons. In most applications, BW6-761 is used as an outer curve to BLS12-377 considered in EIP-2539. The motivation of this precompile is to allow efficient one-layer composition of SNARK proofs. Currently this is done by Zexe using the BLS12-377/CP6-782 pair of curves. This precompile proposes a replacement of CP6-782 by BW6-761, which allows much faster operations. For example, it was shown that verifying a Groth16 proof with BW6-761 is 30 times faster than with CP6-782.

### Proposed addresses table

Precompile | Address |
---|---|

BW6_G1_ADD | 0x1e |

BW6_G1_MUL | 0x1f |

BW6_G1_MULTIEXP | 0x20 |

BW6_G2_ADD | 0x21 |

BW6_G2_MUL | 0x22 |

BW6_G2_MULTIEXP | 0x23 |

BW6_PAIRING | 0x24 |

## Specification

Curve parameters:

The BW6-761 `y^2=x^3-1`

curve is fully defined by the following set of parameters:

```
Base field modulus = 0x122e824fb83ce0ad187c94004faff3eb926186a81d14688528275ef8087be41707ba638e584e91903cebaff25b423048689c8ed12f9fd9071dcd3dc73ebff2e98a116c25667a8f8160cf8aeeaf0a437e6913e6870000082f49d00000000008b
A coefficient = 0x0
B coefficient = 0x122e824fb83ce0ad187c94004faff3eb926186a81d14688528275ef8087be41707ba638e584e91903cebaff25b423048689c8ed12f9fd9071dcd3dc73ebff2e98a116c25667a8f8160cf8aeeaf0a437e6913e6870000082f49d00000000008a
Main subgroup order = 0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
Extension tower:
Fp3 construction: (Fp3 = Fp[u]/u^3+4)
Fp cubic non-residue = 0x122e824fb83ce0ad187c94004faff3eb926186a81d14688528275ef8087be41707ba638e584e91903cebaff25b423048689c8ed12f9fd9071dcd3dc73ebff2e98a116c25667a8f8160cf8aeeaf0a437e6913e6870000082f49d000000000087
Twist parameters:
Twist type: M
twist curve A coefficient c0 = 0x0
c1 = 0x0
twist curve B coefficient c0 = 0x4
c1 = 0x0
Generators:
G1:
X = 0x1075b020ea190c8b277ce98a477beaee6a0cfb7551b27f0ee05c54b85f56fc779017ffac15520ac11dbfcd294c2e746a17a54ce47729b905bd71fa0c9ea097103758f9a280ca27f6750dd0356133e82055928aca6af603f4088f3af66e5b43d
Y = 0x58b84e0a6fc574e6fd637b45cc2a420f952589884c9ec61a7348d2a2e573a3265909f1af7e0dbac5b8fa1771b5b806cc685d31717a4c55be3fb90b6fc2cdd49f9df141b3053253b2b08119cad0fb93ad1cb2be0b20d2a1bafc8f2db4e95363
G2:
X = 0x110133241d9b816c852a82e69d660f9d61053aac5a7115f4c06201013890f6d26b41c5dab3da268734ec3f1f09feb58c5bbcae9ac70e7c7963317a300e1b6bace6948cb3cd208d700e96efbc2ad54b06410cf4fe1bf995ba830c194cd025f1c
Y = 0x17c3357761369f8179eb10e4b6d2dc26b7cf9acec2181c81a78e2753ffe3160a1d86c80b95a59c94c97eb733293fef64f293dbd2c712b88906c170ffa823003ea96fcd504affc758aa2d3a3c5a02a591ec0594f9eac689eb70a16728c73b61
Pairing parameters:
e(P,Q)=(ML1(P,Q)*ML2(P,Q)^q)^FE
|loop_count_1| (first miller loop ML1 count) = 0x8508c00000000002
|loop_count_2| (second miller loop ML2 count) = 0x23ed1347970dec008a442f991fffffffffffffffffffffff
loop_count_1 is negative = false
loop_count_2 is negative = false
```

### Encoding

#### Field elements encoding:

To encode points involved in the operation one has to encode elements of only the base field.

The base field element (Fp) is encoded as `96`

bytes by performing BigEndian encoding of the corresponding (unsigned) integer. The corresponding integer **MUST** be less than the base field modulus.

If encodings do not follow this spec anywhere during parsing in the precompile, the precompile **MUST** revert with "endoding error".

#### Encoding of uncompressed points:

Points in both G1 and G2 can be expressed as `(x, y)`

affine coordinates, where `x`

and `y`

are elements of the base field.
Therefore, points in both G1 and G2 are encoded as the byte concatenation of the field element encodings of the `x`

and `y`

affine coordinates. The total encoding length for a G1/G2 point is thus `192`

bytes.

#### Point at infinity encoding:

Also referred as the "zero point". For BW6-761 (`y^2=x^3-1`

) and its M-twisted curves (`y^3=x^3+4`

), the point with coordinates `(0, 0)`

(formal zeros in Fp) is *not* on the curve, and so the encoding of `(0, 0)`

is used as a convention to encode the point at infinity.

#### Encoding of scalars for multiplication and multiexponentiation operations:

For multiplication and multiexponentiation operations, a scalar is encoded as `64`

bytes by performing BigEndian encoding of the corresponding (unsigned) integer.

Note that the main subgroup order for BW6-761 is actually only `377`

bits (`48`

bytes), but an encoding of `64`

bytes has been chosen to have a `32`

-byte-aligned ABI (representable as e.g. `bytes32[2]`

or `uint256[2]`

).

The corresponding integer **MAY** be greater than the main subgroup order.

### ABI for operations

#### ABI for G1 addition

G1 addition call expects `384`

bytes as an input that is interpreted as the byte concatenation of two G1 points (point-encoded as `192`

bytes each). Output is a point-encoding of the addition operation result.

Error cases:

- Either of the points being not on the curve
- Input has invalid length
- Field element encoding rules apply (obviously)

#### ABI for G1 multiplication

G1 multiplication call expects `256`

bytes as an input that is interpreted as the byte concatenation of the point-encoding of a G1 point (`192`

bytes) and the encoding of a scalar value (`64`

bytes). Output is a point-encoding of the multiplication operation result.

Error cases:

- Point being not on the curve
- Input has invalid length
- Field element encoding rules apply (obviously)
- Scalar encoding rules apply (obviously)

#### ABI for G1 multiexponentiation

G1 multiplication call expects `256*k`

bytes as an input that is interpreted as the byte concatenation of `k`

slices, each of them being a byte concatenation of the point-encoding of a G1 point (`192`

bytes) and the encoding of a scalar value (`64`

bytes). Output is an encoding of the multiexponentiation operation result.

Error cases:

- Any of the G1 points being not on the curve
- Input has invalid length
- Field element encoding rules apply (obviously)
- Scalar encoding rules apply (obviously)

#### ABI for G2 addition

G2 addition call expects `384`

bytes as an input that is interpreted as the byte concatenation of two G2 points (point-encoded as `192`

bytes each). Output is a point-encoding of the addition operation result.

Error cases:

- Either of points being not on the curve
- Input has invalid length
- Field elements encoding rules apply (obviously)

#### ABI for G2 multiplication

G2 multiplication call expects `256`

bytes as an input that is interpreted as the byte concatenation of the point-encoding of a G2 point (`192`

bytes) and the encoding of a scalar value (`64`

bytes). Output is an encoding of multiplication operation result.

Error cases:

- Point being not on the curve must result in error
- Field elements encoding rules apply (obviously)
- Input has invalid length

#### ABI for G2 multiexponentiation

G2 multiplication call expects `240*k`

bytes as an input that is interpreted as byte concatenation of `k`

slices each of them being a byte concatenation of encoding of G2 point (`192`

bytes) and encoding of a scalar value (`48`

bytes). Output is an encoding of multiexponentiation operation result.

Error cases:

- Any of G2 points being not on the curve must result in error
- Field elements encoding rules apply (obviously)
- Input has invalid length

#### ABI for pairing

Pairing call expects `384*k`

bytes as an input, that is interpreted as the byte concatenation of `k`

slices. Each slice has the following structure:

`192`

bytes G1 point encoding`192`

bytes G2 point encoding

Output is `32`

bytes representing a boolean:

`0x0000000000000000000000000000000000000000000000000000000000000001`

if the pairing result is equal the to multiplicative identity in the pairing target field; and`0x0000000000000000000000000000000000000000000000000000000000000000`

otherwise.

Error cases:

- Any of the G1 or G2 points being not on the curve
- Any of the G1 or G2 points being not in the correct subgroup
- Input has invalid length
- Field elements encoding rules apply (obviously)

### Prevention of DDoS on error handling

This precompile performs extensive computations and in case of any errors during execution it **MUST** consume all gas from the the gas schedule for the corresponding operation.

### Gas schedule

#### G1 addition

`180`

gas

#### G1 multiplication

`64000`

gas

#### G2 addition

`180`

gas

#### G2 multiplication

`64000`

gas

#### G1/G2 Multiexponentiation

Discounts table as a vector of pairs `[k, discount]`

:

```
[[1, 1266], [2, 733], [3, 561], [4, 474], [5, 422], [6, 387], [7, 362], [8, 344], [9, 329], [10, 318], [11, 308], [12, 300], [13, 296], [14, 289], [15, 283], [16, 279], [17, 275], [18, 272], [19, 269], [20, 266], [21, 265], [22, 260], [23, 259], [24, 256], [25, 255], [26, 254], [27, 252], [28, 251], [29, 250], [30, 249], [31, 249], [32, 220], [33, 228], [34, 225], [35, 223], [36, 219], [37, 216], [38, 214], [39, 212], [40, 209], [41, 209], [42, 205], [43, 203], [44, 202], [45, 200], [46, 198], [47, 196], [48, 199], [49, 195], [50, 192], [51, 192], [52, 191], [53, 190], [54, 187], [55, 186], [56, 185], [57, 184], [58, 184], [59, 181], [60, 181], [61, 181], [62, 180], [63, 178], [64, 179], [65, 176], [66, 177], [67, 176], [68, 175], [69, 174], [70, 173], [71, 171], [72, 171], [73, 170], [74, 170], [75, 169], [76, 168], [77, 168], [78, 167], [79, 167], [80, 166], [81, 165], [82, 167], [83, 166], [84, 166], [85, 165], [86, 165], [87, 164], [88, 164], [89, 163], [90, 163], [91, 162], [92, 162], [93, 160], [94, 163], [95, 159], [96, 162], [97, 159], [98, 160], [99, 159], [100, 159], [101, 158], [102, 158], [103, 158], [104, 158], [105, 157], [106, 157], [107, 156], [108, 155], [109, 155], [110, 156], [111, 155], [112, 155], [113, 154], [114, 155], [115, 154], [116, 153], [117, 153], [118, 153], [119, 152], [120, 152], [121, 152], [122, 152], [123, 151], [124, 151], [125, 151], [126, 151], [127, 151], [128, 150]]
```

`max_discount = 150`

#### Pairing operation

Base cost of the pairing operation is `120000*k + 320000`

where `k`

is a number of pairs.

## Rationale

Gas costs are based on EIP-1962 estimation strategy (but do not fully include yet parsing of ABI, decoding and encoding of the result as a byte array).

### Gas estimation strategy

Gas cost is derived by taking the average timing of the same operations over different implementations and assuming a constant `30 MGas/second`

. Since the execution time is machine-specific, this constant is determined based on execution times of *ECRECOVER* and *BNPAIR* precompiles on my machine and their proposed gas price (`43.5 MGas/s`

for ECRECOVER and `16.5 MGas/s`

for BNPAIR). Following are the proposed methods to time the precompile operations:

- G1 addition: Average timing of 1000 random samples.
- G1 multiplication: Average timing of 1000 samples of random worst-case of double-and-add algorithm (scalar of max bit length and max hamming weight and random base points in G1)
- G2 addition: Average timing of 1000 random samples
- G2 multiplication: Average timing of 1000 samples of radnom worst-case of double-and-add algorithm (scalar of max bit length and max hamming weight and random base points in G2)
- G1 and G2 multiexponentiations: Expected to be performed by the Peppinger algorithm, with a table prepared for discount in case of
`k <= 128`

points in the multiexponentiation with a discount cup`max_discount`

for`k > 128`

. To avoid non-integer arithmetic call cost is calculated as`k * multiplication_cost * discount / multiplier`

where`multiplier = 1000`

,`k`

is a number of (scalar, point) pairs for the call,`multiplication_cost`

is a corresponding single multiplication call cost for G1/G2. - Pairing: Average timing of 1000 random samples (random points in G1 and G2) for different number of pairs with linear lifting.

### Multiexponentiation as a separate call

Explicit separate multiexponentiation operation that allows one to save execution time (so gas) by both the algorithm used (namely Peppinger algorithm) and (usually forgotten) by the fact that `CALL`

operation in Ethereum is expensive (at the time of writing), so one would have to pay non-negigible overhead if e.g. for multiexponentiation of `100`

points would have to call the multipication precompile `100`

times and addition for `99`

times (roughly `138600`

would be saved).

### Explicit subgroup checks

G2 subgroup check has the same cost as G1 subgroup check. Endomorphisms can be leverages to optimize this operation.

## Backwards Compatibility

There are no backward compatibility questions.

## Test Cases

Due to the large test parameters space we first provide properties that various operations must satisfy. We use additive notation for point operations, capital letters (`P`

, `Q`

) for points, small letters (`a`

, `b`

) for scalars. Generator for G1 is labeled as `G`

, generator for G2 is labeled as `H`

, otherwise we assume random point on a curve in a correct subgroup. `0`

means either scalar zero or point of infinity. `1`

means either scalar one or multiplicative identity. `group_order`

is a main subgroup order. `e(P, Q)`

means pairing operation where `P`

is in G1, `Q`

is in G2.

Requeired properties for basic ops (add/multiply):

- Commutativity:
`P + Q = Q + P`

- Additive negation:
`P + (-P) = 0`

- Doubling
`P + P = 2*P`

- Subgroup check:
`group_order * P = 0`

- Trivial multiplication check:
`1 * P = P`

- Multiplication by zero:
`0 * P = 0`

- Multiplication by the unnormalized scalar
`(scalar + group_order) * P = scalar * P`

Required properties for pairing operation:

- Degeneracy
`e(P, 0*Q) = e(0*P, Q) = 1`

- Bilinearity
`e(a*P, b*Q) = e(a*b*P, Q) = e(P, a*b*Q)`

(internal test, not visible through ABI)

## Reference Implementation

There is a various choice of existing implementations:

**Libraries:**

- Rust implementation (EY/Zexe): github.com/yelhousni/zexe/tree/youssef/BW6-761-Fq-ABLR-2ML-M
- C++ implementation (EY/libff): github.com/EYBlockchain/zk-swap-libff
- Golang implementation (Consensys/gurvy): github.com/ConsenSys/gurvy

**Stand-alone implementation:**

- Golang implementation with Intel assembly (Onur Kilic): github.com/kilic/bw6

**Precompiles:**

- OpenEthereum (EY/Parity): github.com/EYBlockchain/solidity-elliptic-curves
- Frontier (Parity): github.com/paritytech/frontier/pull/1049/files

**Scripts:**

- SageMath and Magma scripts: gitlab.inria.fr/zk-curves/bw6-761/

## Security Considerations

Strictly following the spec will eliminate security implications or consensus implications in a contrast to the previous BN254 precompile.

Important topic is a "constant time" property for performed operations. We explicitly state that this precompile **IS NOT REQUIRED** to perform all the operations using constant time algorithms.

## Copyright

Copyright and related rights waived via CC0.

###### Adopted by projects

### Not miss a beat of EIPs' update?

Subscribe EIPs Fun to receive the latest updates of EIPs Good for Buidlers to follow up.

View all