# EVMMAX Case Study: BLS12381 G1 Point Multiplication

This document presents benchmarks and costs for an EVM implementation of BLS12381 G1 point multiplication using [EVMMAX](https://github.com/ethereum/EIPs/pull/5843) opcodes. The basic double-and-add algorithm is used. Benchmarks and gas cost estimations of two native implementations are provided for comparison.

The double-and-add algorithm is the basis for the worst-case-input pricing model for the G1/G2-Mul precompiles proposed in [EIP-2537](https://eips.ethereum.org/EIPS/eip-2537).

## Implementation

The algorithm iterates each bit in the scalar accumulating successive point additions and doublings to calculate a result:

def G1Mul(point: G1Point, scalar: int) -> G1Point:
    acc = G1InfPoint()
    for bit in iter_bits_msb_first(scalar):
        acc = point_double(acc)
        if bit == 1:
            acc = point_add(acc, point)
    
    return acc

There are various types of elliptic curve coordinate systems and formulas for point addition and doubling. The EVM and Rust implementations of G1Add implement the formulas described in algorithms 7 and 9 from [this paper](https://eprint.iacr.org/2015/1060.pdf) which use projective coordinates. The Geth implementation is from an older version of [Kilic](https://github.com/kilic/bls12-381) and implements different formulas for [addition](https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl) and [doubling](http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l) which use Jacobian coordinates.

The Geth point addition/doubling formulas use less arithmetic operations than the formulas used by the EVM/Rust implementations. However, they are not "complete": Strictly following the given formulas produces incorrect results for certain valid inputs. For example, the incomplete formula for `point_double` does not produce a correct result when the input is the infinity point.

Because of this, an implementation of the incomplete formulas must perform additional checks to handle certain inputs correctly. For compiled code, the overhead of these checks is minimal compared to the cost of the arithmetic. However, implemented with EVM opcodes they are costly in terms of gas and it is more economical to use the complete formulas which allow the implementation to avoid non-arithmetic operations.

## Benchmark Types

Costs and benchmarks are presented for two EVMMAX variants:
* `evmmax-eip5843` - EIP-compliant implementation of the spec in Go
* `evmmax-asm384` - x86_64 GoAssembly implementation of the arithmetic provided by Supranational team in 2020. The implementation is modified from the EIP to make the value format little-endian. It also currently lacks checks that inputs are less than the modulus. `ADDMODX`, `SUBMODX` and `MULMONTX` opcodes are priced to 1, 1 and 2 respectively for the 320-384bit input size.

Two native implementations of double-and-add are benchmarked:
* `geth` - [Code](https://github.com/ethereum/go-ethereum/blob/6c149fd4ad063f7c24d726a73bc0546badd1bc73/crypto/bls12381/g1.go#L344-L356) from geth bls12381 crypto package with assembly implementations for arithmetic operations
* `rust` - Rust [implementation](https:///github.com/zkcrypto/bls12_381) using complete point addition and doubling formulas

## Costs

**Note**: for the native implementation benchmarks, gas cost is calculated by scaling runtime using 25 ns/gas.

### Worst Case Input: All bits of the scalar are 1

| Implementation | Runtime (ns) | Gas Cost |
| ----- | ----- | ----- |
| evmmax-eip5843 | 1501579 | 60668
| evmmax-asm384 | 897000 | 39485
| rust | 490000 | 19600
| geth | 300146 | 12006

### Average-ish Input:

Chose the group order (`52435875175126190479447740508185965837690552500527637822603658699938581184513`) with 122 0s and 134 1s in its binary representation.

| Implementation | Runtime (ns) | Gas Cost |
| ----- | ----- | ----- |
| evmmax-eip5843 | 1047375 | 46632
| evmmax-asm384 | 643000 | 31862
| rust | 335000 | 13400
| geth | 198461 | 7938

### Code

https://github.com/jwasinger/evmmax-bls12-381