RIP-7696 : generic Double Scalar Multiplication (DSM) for all curves

RIPs
1

This proposal creates two precompiled contracts that perform a double point multiplication (DSM) and sum then over any elliptic curve given p, a,b curve parameters.
This operation consists in computing the value uP+vQ, u and v being scalars, P and Q being points.

We managed to implement generic DSM in full solidity with a lower cost than previous implementations (FCL, Daimo, p256-verifier-huff). Such genericity will enable curves such as Ed25519 and Babyjujub (with the use of isogeny we will describe later), Palla,Vesta, Starkcurve, etc.

The proposal includes two precompiles, taking curves parameters as calldata.
The first one is very comparable to RIP7212 and EIP6565, only taking those extra p,a,b parameters.
The second them uses extra values (namely 2^128.P and 2^128Q), to provide a GLV comparable speedup, which is 50% asymptotically (less in full solidity, but ZK version will benefit largely from it).

As of now there is a huge traction on P256, being the first FIDO curve implemented in WebAuthn. Ed25519 shall follow, and is superior in all ways (Schnorr based, no hidden seed constant,MPC friendly).

This precompile also solve the ‘hacky’ use of ecrecover (as implemented for Schnorr based Dapps, such as Ambire Wallet, and secure MPC uses relying on Musig2). This cunning use of ecrecover in fact enables DSM.

Implementing DSM at lower levels (for ZKEVM or nodes) only requires to implement Montgomery multiplications to emulate prime fields. (It is how it is done by Lambda for ZKsync right now). This is how are implemented most generic libraries (OpenSSL, libECC, Bolos, etc.).

9 Likes
2

insert youtube video “Shia LaBeouf “Just Do It” Motivational Speech”
Thanks for this RIP that will also benefit EVM L2 not sequencing on the Ethereum mainnet.

1 Like
3

Personally, I would be super happy to see Ed25519 and EdDSA in general over ECDSA. However, AFAIU it uses SHA-512 as the hashing function, for which there is no precompile at the moment, making it not so useful (which is a shame IMO).

Also, as far as I understand, Ed25519 is a twisted Edwards curve, while this precompile implements uP + vQ given scalars u and v and points P and Q for Weierstrass curves with coefficients a and b. Correct me if I’m wrong (this is not my area of expertise), but I think you can map twisted Edwards curves to and from Weierstrass form, allowing this precompile to be used for efficient EdDSA signature verification, but it would be nice to spell out how this is done somewhere (for less cryptographically savvy engineers like myself).

1 Like
4

You are totally right, it is very cheap to reuse Weierstrass formulae to implement Ed25519 (only a few multiplication/inversion), the name of the isogeneous curve is Wei25519, here is the solidity code:

function Edwards2WeierStrass(uint256 x,uint256 y) view returns (uint256 X, uint256 Y){
//wx = ((1 + ey) * (1 - ey)^-1) + delta
X=addmod(delta, mulmod(addmod(1,y,p),pModInv(addmod(1, p-y,p)),p) ,p);
// wy = (c * (1 + ey)) * ((1 - ey) * ex)^-1

Y=mulmod(mulmod(c, addmod(1, y, p),p), pModInv(mulmod(addmod(1, p-y,p), x,p)),p);
}

Concerning SHA512 you are right for L1 where gas is cheap for SHA256 (but that should change as gas cost on L1 shall reflect more the ZK cost in the future). But for a L2, implementing SHA512 circuit is a similar cost to SHA256.

There are also equivalent version of EDdsa, over babyjujub, which uses Poseidon instead (Circom framework), sometimes ZK is not necessary everywhere and using ZK verifier for a simple Eddsa verification is “crushing a fly with a Hammer”.

The concern is also over MPC versions. ECDSA is crippled with vulnerabilities, while Musig2, used for Taproot BTC gives better security proofs. DSM enables MPC signatures.

The thing is also “why choose now ?” option, using 7696 instead of limiting to a single curve through 6565 or 7212 provides maximum degree of freedom.

5

You are totally right, it is very cheap to reuse Weierstrass formulae to implement Ed25519 (only a few multiplication/inversion), the name of the isogeneous curve is Wei25519, here is the solidity code:

Ok, so if I understand correctly, this code maps Ed25519 curve points to a point on the Wei25519 Weierstrass curve. Given the signature verification equation [s]B = R + [k]A (B is base/generator point, s and R are signature components, A is the public key), you would implement this by mapping B, R, and A to Wei25519 and using ecmulmuladd to verify the equality holds?

An additional point, I noticed that the EIP assumes ECs over prime fields where p fits into 256-bit integers. I wonder if it makes sense to consider a mechanism like the EXPMOD precompile where additional widths for the values in Fp are included in the parameters. This would allow supporting ecmulmuladd for curves over larger prime fields like P-384. To elaborate on this a bit, the input data would look like:

  • Input data: 64 + 7n + 2l bytes of data including:
    • 32 bytes of the size n in bytes required to represent elements of the prime field over which the elliptic curve is defined
    • 32 bytes of the size l in bytes required to represent the curve order
    • n bytes of the modulus p modulus of the prime field of the curve
    • n bytes of the a first coefficient of the curve
    • n bytes of the b second coefficient of the curve
    • n bytes of the Px x coordinate of the first point
    • n bytes of the Py y coordinate of the first point
    • n bytes of the Qx x coordinate of the first point
    • n bytes of the Qy y coordinate of the first point
    • l bytes of the u first scalar to multiply with P
    • l bytes of the v second scalar to multiply with Q

We can probably conflate n and l use a single “size” for all values, since they tend to have a similar order of magnitude in most cases and max(n, l) will always suffice.

6

The thing is that the implication to handle 384 bits curve has a lot of implication at ZK level. Handling variable length is more complex in term of code coverage, audits and potential vulnerabilities.
It implies to handle multiprecision integers (EVM is a 256 bit machine). It seems less probable to be accepted any time soon, as MSM which has been proposed for long now. There is a cursor to place between a fully configurable MSM (not limited to double, but any number of points) over any curve, and very specific (limited to one curve) precompile.

MSM is superior, but too complex. Specific curves precompiles are too limited. Optimized DSM is only 100 lines of solidity code. Actually it is very close to the specific one (mainly handling constant into calldata, and more efforts to handle the stack without via IR which crush performances).

Actually the provided code will be used as a temporary solution by some L2s before implementing it at circuit level.

7

I forgot to answer the Ed25519 part. Yes I did it. I reproduced the RFC8032 vectors for short length, ECC is OK, but I still work on the SHA512 part.

8

I agree it is at first glance more complex, however, I just figured that since expmod precompile already requires arbitrary precision integer math, that it would not be a stretch to add it for mulmuladd. I would argue that the implementation difference between implementing this precompile for 256 bit integers vs. arbitrary precision integers is not that crazy, and mostly boil down to figuring out an appropriate gas schedule that is in function of the integer width, like expmod does.

For sure. I also would generally assume that use cases for curves over prime fields where log2(p) > 256 is not so widespread, and as you mentioned would eliminate the possibility of providing a Solidity fallback.

I do think it might be worth documenting this rationale in the RIP itself.

9

Another significant advantage over 7212 IMO is that this would also allow ECDSA recovery to be implemented efficiently for curves like P-256.