Precompiles for ECADD and ECMUL

[vbuterin]

Parameters

• METROPOLIS_FORK_BLKNUM: TBA
• GECADD: 200
• GECMUL: 1000

Specification

Adds a precompile at address 0x0000....0a which accepts as input 224 bytes that it interprets as [x1, y1, x2, y2, P, A, B] (if less than 224 bytes are provided the remaining bytes are assumed to be zero, if more than 224 bytes are provided they are ignored). Throws if (x1, y1) or (x2, y2) are not on the curve defined by (P, A, B) (ie. x**3+A*x+B-y**2 is not a multiple of P), otherwise returns 64 bytes representing the elliptic curve addition (x1, y1) + (x2, y2) on that curve.

Adds a precompile at address 0x0000....0b which accepts as input192 bytes that it interprets as [x, y, n, P, A, B] (if less than 192 bytes are provided the remaining bytes are assumed to be zero, if more than 192 bytes are provided they are ignored). Throws if (x1, y1) is not on the curve defined by (P, A, B) (ie. x**3+A*x+B-y**2 is not a multiple of P), otherwise returns 64 bytes representing the elliptic curve multiplication (x1, y1) * n on that curve.

Rationale

Allows for the efficient application of ring signatures and other cryptography based on elliptic curves. Currently, an secp256k1-focused implementation of these operations (see https://github.com/ethereum/serpent/blob/develop/examples/ecc/jacobian_arith.se ) takes ~200k gas for a multiply, ~750k gas for an ecrecover and ~900k gas per linkable ring signature participant, which is unacceptably high.

[chfast]

This seems reasonable if such functions are needed.

1. I like the costs being constant. Where the numbers come from?
2. Are the functions included in the secp256k1 library?

[vbuterin]

Updated to make it more generic (set your own curve parameters).

1. I like the costs being constant. Where the numbers come from?

Reverse engineering from the current ECRECOVER cost, ie. an ECRECOVER is 3 multiply ops plus some adds and modexp, so the cost of ECMUL should be close to a third of that of ECRECOVER.

1. Are the functions included in the secp256k1 library?

Not sure, especially with the curve generalization.

[androlo]

Great. If curve params is supported, maybe it could have more functions, some for validating curve params, some that does an op with some standard checks, and one "unsafe" version that assumes the validation has already been done. A few basic validation functions and math (check If a number is prime, etc.) would be great.

[gcolvin]

In general, I'd rather see the EVM be efficient enough that contracts like this are not necessary.

[holiman]

Can we close this, in favour of #213 ?

[axic]

@Arachnid @Souptacular @nicksavers @cdetrio @gcolvin I think this issue should be closed given EIP196 was merged.