# EIP-3026: BW6-761 curve operations

### Precompiles for BW6-761 curve operations

## 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:

### 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 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]`

:

`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.