Verify ed25519 signatures cheaply on Eth using ZK-Snarks

Prepared by : Garvit Goel, Rahul Ghangas, Jinank Jain

In this article, we will discuss how you can verify Ed25519 signatures on Ethereum today in a very gas-efficient way, without the use of any pre-compiles such as the proposed EIP665. We will use the same principles as used by many zk-rollups. We have already shipped the code for this, albeit not yet audited. Let’s get to it.

For dApps that want to verify Ed25519 signatures on Ethereum, rather than verifying the signature(s) directly on Ethereum, (and performing the curve operations inside a solidity smart contract), one can construct a zk-proof of signature validity and verify the proof on-chain instead.

Gas cost for verification of a single Ed25519 signature is about ~500K gas (when the Ed25519 curve is implemented directly in Solidity). On the other hand, the gas cost for verifying a zk-snark on-chain is about ~300k gas. These gas savings become significant when you want to verify a large number of signatures in one batch, then you can just create a single ZK-proof for the entire batch.

At Electron Labs, we have built a circom-based library that allows you to generate a zk-snark proof for a batch of Ed25519 signatures.
You can check out the details of our mathematical approach here. You can even test proof generation today using the APIs given on the previous link.
Check out the complete code base here

The Performance of a Single Ed25519 is as below:

All metrics were measured on a 16-core 3.0GHz, 32G RAM machine (AWS c5a.4xlarge instance).

Single ED25519 Signature
Constraints 2,564,061
Circuit compilation 72s
Witness generation 6s
Trusted setup phase 2 key generation 841s
Trusted setup phase 2 contribution 1040s
Proving key size 1.6G
Proving time (rapidsnark) 6s
Proof verification Cost ~300K gas

Furthermore, for batching we support:

  1. Max batch size supported = 99 signatures
  2. Proof generation time for a batch of 99 signatures = ~16 minutes.

While these metrics are good for a PoC, we need to do a lot better. Hence, as next steps, we are planning to integrate recursive snarks. This will increase the max batch size and reduce proof generation time by multiple orders of magnitude.

Use Cases:

We believe one of the best use cases for this tech is extending light client bridges to Ethereum. This includes Polygon Avail, IBC and Rainbow Bridge. One could also build zk-rollups that use Ed25519 for user accounts.

Ending Note:

We would love to work with teams that want to use this tech. We are also looking for research groups who are working on recursive snark technology to help us scale our tech.

5 Likes

Hi there,

author of EIP665 here, I just stumbled across this post now: this is really a cool approach, great work! Love it. Thanks for sharing!

FWIW, the EIP665 never went anywhere even though I’ve implemented the proposal as a precompile in different EVM implementations. Reasons were worries about precompile security / added complexity, and by pointing to eWASM which would then presumably render the whole “new precompiles suck” angle pointless, as one could then efficiently implement those directly in user contracts. I agree in principle with the latter. However, years later, eWASM has yet to arrive;)

We would love to work with teams that want to use this tech.

Please let me expand a bit and then explain why I’m still interested in this stuff.

I am doing quite a bit of OSS work, e.g. I am original author of https://wamp-proto.org/

This is a modern and unique application messaging protocol that can run natively over WebSocket and provides both PubSub and RPC (in a routed fashion) in one protocol (a network protocol that is).

There are many implementations, one of which is another project of mine:

You’ll find a couple of client library implementations under that some GitHub org.

Now, WAMP is using Ed25519 since ages for one of it’s authentication methods (“WAMP-cryptosign”).

This is where my original interest came from: being able to use such “WAMP native” signatures.

Another, independent motivation was: make application services exposed via WAMP in a payable fashion, e.g. every 1000 calls to this procedure, or every 1h of events on some topic cost so and so much.

We’ve implemented this using off-chain payment channels implemented in Crossbar:

[sorry, I can only post 2 links per post]

One problem with that still is:

  • 2 signature schemes (Eth and Ed25519) are used in the system
  • high gas costs for payment channel open/close

Actually, sorry for the amount of stuff, but I’d like to give you the “complete picture”.

After all of above “experiments”, we now want to reuse the end-to-end encryption stuff we’ve added to WAMP during above service payment experiments, and first want to expand single-operator WAMP to a federated WAMP network of router nodes operated by different parties. And use Eth L2.

If we could also reuse Ed25519, and if we could improve meta-data privacy at the WAMP network level using ZK-Snarks, that sounds fantastic !!!

So yes, if you are interested in discussing this stuff, possibly working together, pls let me know, I’m interested/curious =)

Cheers,
/Tobias

1 Like

Hi @oberstet
Many thanks for reaching out! Would love to connect and discuss more. Have DM’ed you :slightly_smiling_face:

1 Like