Add ECADD and ECMUL precompiles for secp256k1

[mattdf]

Summary

Add ECADD and ECMUL precompiles for secp256k1

Motivation

Currently the accepted EIP for metropolis only supports addition and multiplication precompiles for alt_bn128. Being a pairings curve with 2 subgroups, the implementation of many smart contracts prototypes (the ones that use solidity secp lib) that assumed secp256k1 ops would be added do not work, and there remains a question whether or not trivial rewrites of those contracts to use the ADD/MUL of alt_bn128 would be safe if DDH isn't hard on that curve. "Safe" use of secp256k1 doesn't have surprises, and is much easier to implement / more performant for contracts that don't require pairings ops.

Furthermore, the community and ecosystem has many libraries and tooling that support reading, verifying and creating secp256k1 signatures, but the same cannot be said for alt_bn128. There is no alt_bn128-js, no user-friendly tools to create those signatures, etc.

There are already existing contracts (such as ring signature contracts) that could immediately benefit from the secp256k1 precompiles being added, by just swapping the solidity library with the precompiles - and would then be performant enough to actually execute within a single block.

One of the largest benefits is also the ability to manipulate the curve points of default ethereum signatures/addresses - which is again not possible with alt_bn128 since it's a different curve.

Specification

Add precompiled contracts for point addition (ECADD) and scalar multiplication (ECMUL) on the elliptic curve "secp256k1".

Address of ECADD: 0x8
Address for ECMUL: 0x9

The curve is the same as the one used for ethereum signatures, hence all clients already support it by default. Addition of the precompile is trivial.

Encoding

Field elements are encoded as 32 byte big-endian numbers. Curve points are encoded as two field elements (x, y), where the point at infinity is encoded as (0, 0).

For both precompiled contracts, if the input is shorter than expected, it is padded with zeros at the end.

The length of the returned data is always as specified (i.e. it is not "unpadded").

Exact semantics

Invalid input: For both contracts, if any input point does not lie on the curve or any of the field elements (point coordinates or scalar) is equal or larger than the field modulus p, the contract fails.

ECADD: Input: two curve points (x, y). Fail on invalid input. Otherwise, return the curve point x + y where + is point addition on the elliptic curve secp256k1 specified above.

ECMUL: Input: curve point and scalar (x, s). Fail on invalid input. Otherwise, return the cureve point x * s, where * is the scalar multiplication on the elliptic curve secp256k1 specified above.

Gas costs

To be determined.

[axic]

It was too late to bring this up for the BN curve precompiles (#213 (comment)), but I think it would still make sense for this PR.

The proposal is to have a single precompile which accepts ABI encoded data:

• ecadd(bytes32, bytes32) -> bytes32
• ecmul(bytes32, uint256) -> bytes32

Benefit:

• no special bindings are needed in most programming languages, a simple interface definition can be used (in Solidity it would be usable as ECPrecompile(0x8).ecmul(a, b))
• when we get to the point (i.e. eWASM) to implement precompiles as actual code, there wouldn't be a lot of code duplication since shared pieces of code wouldn't need to be scattered in two accounts (0x8, 0x9)

Downside:

• incompatible API with BN-curve precompiles
• potentially can be considered more complex (since there is a function selector), but such complexity is already proposed in the blockhash contract and the blake2 precompile

[bbuenz]

If this is added we should use the compressed form for ECPoints, i.e. just x and 1 bit for the sign. y can be inferred from these information (by computing the square root). Space is more important than computation.

[shamatar]

@mattdf

Thanks for bringing this. Secp256k1 is heavily optimized and can potentially have much more much more affordable scalar multiplication and point addition prices. Also use of the compatible curve will allow users of various hardware wallets to use it. We can finally see confidential transactions and ring signatures on chain.

[darioAnongba]

I'm currently facing the exact same issues that @mattdf and @shamatar signaled.

I am creating a token with Confidential transactions and I'm using alt_bn_128 but I have problems with libraries as there is no JS library for alt_bn_128. I am struggling with the web app and mobile app implementation. The solution is trying to use WebAssembly or other hacks with the Rust and C++ libraries but I didn't manage to make it work.

Most libraries like elliptic support secp256k1.

[shamatar]

Hello @darioAnongba

I have a confidential transactions service ready, but to have an appropriate user experience I’d like to have at least 96 bits of range proof fitting into transaction. To have a reasonable gas cost it’s necessary to reduce a cost of ADD and MUL operations 20-fold. Latest optimizations from 1.8.x Geth version achieve even better performance improvement of precompile, so I was hoping for a cost reduction in the next fork. Should definitely file a EIP, thank you @mattdf

Sincerely, Alex

[debasish-raychawdhuri]

Unique ring signatures (as described in Cryptonote) cannot be used with a curve where DDH is easy. I am trying to implement a unique ring signature for my contracts, it would most certainly be nice to have it on secp256k1.

[bbuenz]

The ddh assumption is believed to hold in both subgroups of the BN curve. It’s called the xddh assumption.

[debasish-raychawdhuri]

DDH does not hold in BN curve as the equality of the pairing function will answer the DDH question trivially. xDDH is not the same thing (with x at least 3). To the best of my knowledge, there is no construction for unique ring signature available that would work without the basic DDH assumption. Specifically, the unique ring signature allows and adhoc ring signature that guarantees that the same private key cannot be used to create two different signatures for the same tag (hence the unique part). The pairing function will trivially give up the identity of the signer. Even if there is one, it would probably way more multiplications than the one with that uses DDH. All of that extra processing just to avoid having the ECADD and ECMUL operations available.

[bbuenz]

The DDH assumption may hold in G_1 even though there is a pairing: See page 32 (http://www.ecrypt.eu.org/ecrypt2/documents/D.MAYA.6.pdf).
Also there are ring signatures from many assumptions (https://www.shoup.net/papers/subring.pdf). I am all in favor of adding support for secp256k1 but you can still build ring signature schemes using the BN curve.

[npip99]

This should probably be closed; there is a misunderstanding here. Embedding degree is 12 on alt_bn128, which remains safe against DDH assumption on G_1, since the only known attack on small embedding degrees is the MOV attack on discrete logarithms (which would only work with embedding degree < 4). To quote,

If the group G is equipped with a pairing e : G×G → G_t, then applying e componentwise defines a pairing on G = G^n. However, such a “symmetric” pairing (which only exists on supersingular
elliptic curves) can be used to solve DDH in G, so in this case our DDH-based construction is
not secure. To get around this problem we use the fact that on ordinary elliptic curves there
are two distinguished subgroups, denoted G_1 and G_2, in which DDH is believed to be infeasible
for sufficiently large group orders. We can thus apply our construction twice to produce groups G = G^n_1, H = G^n_2, Gt = G^m_t (for some m), and an “asymmetric” pairing e : G × H → G_t. If the DDH assumption holds in G1 and G2, then the subgroup decision assumption holds in G and H.

Which gives us the final conclusion:

If E is ordinary (i.e., #E(Fq) != q + 1), then there is no known efficient algorithm for solving
the DDH problem in either G1 or G2. In particular, the Weil and Tate pairings are trivial when
restricted to either G1 or G2 [16, Lemma IX.16], so we cannot use the pairing to solve DDH in either
group.

Which was taken from page 25 of this paper. Of course, the curve being used here is not supersingular, which would already negate security, so no pairing can be made with G1 = G2.

Currently, any secp256k1 application can be written in the EVM using the current ECADD/ECMUL. According to the yellow paper it is a Type 3 pairing, so DDH is hard on G_2 too.