New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add ECADD and ECMUL precompiles for secp256k1 #603

Open
mattdf opened this Issue Apr 14, 2017 · 5 comments

Comments

Projects
None yet
5 participants
@mattdf
Member

mattdf commented Apr 14, 2017

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

This comment has been minimized.

Show comment
Hide comment
@axic

axic Sep 22, 2017

Member

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
Member

axic commented Sep 22, 2017

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

This comment has been minimized.

Show comment
Hide comment
@bbuenz

bbuenz Oct 24, 2017

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.

bbuenz commented Oct 24, 2017

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

This comment has been minimized.

Show comment
Hide comment
@shamatar

shamatar Feb 21, 2018

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

shamatar commented Feb 21, 2018

@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

This comment has been minimized.

Show comment
Hide comment
@darioAnongba

darioAnongba May 17, 2018

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.

darioAnongba commented May 17, 2018

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

This comment has been minimized.

Show comment
Hide comment
@shamatar

shamatar May 17, 2018

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

shamatar commented May 17, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment