Rainbow Upgrade Idea: Using zk-SNARKS to cheaply verify ED25519 signatures on Ethereum mainnet

***This article assumes a basic understanding of how the NEAR Rainbow bridge works. Please see - ETH-NEAR Rainbow Bridge - NEAR Protocol

The NEAR Rainbow bridge has a problem, transactions from NEAR to Ethreum are slow, and take up to 3-5 hours. Why is this the case?

When making transactions from NEAR to Ethereum, one needs to verify NEAR validators’ ED25519 signatures on Ethereum. Since Ethereum does not have a precompile for ED25519 signature, this verification costs significant gas fees, and it is not feasible to verify 100’s of validator signatures for every cross-chain transaction.

Currently, NEAR Rainbow gets around this problem by taking an optimistic approach, i.e. rather than verifying sig’s for every transaction, Rainbow verifies only those transactions that get “disputed”. Otherwise, your transaction is deemed correct. However, this means that your transaction must wait for 3-5 hours to provide a chance for others to dispute your transactions. This is often referred to as “Fraud Proofs” approach.

In this article, we show how the Ed25519 sig verification gas fees can be reduced significantly, by using zk-snarks.

The proposed scheme:
Every time an ED25519 signature needs to be verified, instead of running the verification computation on-chain (Ethereum), we can run the verification computation off-chain inside a ZK-circuit and then submit the zk-proof on-chain. A smart contract could then verify the zk-proof on-chain.

Let’s analyze the steps in detail:

  1. A dedicated smart contract on Ethereum shall take as input the following parameters - Signer address, message, signature
  2. These parameters could be provided as cheap calldata to the contract
  3. Then the zk-SNARK operator reads this information and passes them through their pre-built ED25519 verification circuit to produce the boolean output True/False depending on whether the signature is valid or not. A zk-proof of this evaluation is also produced.
  4. The zk-circuit outputs (boolean and proof) and then put back onto the same contract as before.
  5. The contract can now verify using the zk-proof whether the signature verification was carried out correctly or not.

Verification of a single ED25519 signature costs about 500K Ethereum gas and the cost of ZK-SNARK verification is ~600K has (plus some overhead). Hence on the first look, it might appear that this is not a good trade-off. However, we can batch verify multiple ED25519 signatures in a single zk-proof. We believe that several 100 signatures can be batched in a single zk-proof reducing the overall cost significantly.

Since there are 100 validator seats per shard, we can verify the validator signatures of one complete shard block for the gas price of one signature. Hence via this scheme, we can achieve 100x reduction in gas fee for ED25519 signature verification on Ethereum chain.

Finishing Note: If the NEAR team likes the idea, we would love to build this.

Reference:- Our solution is heavily inspired by the technology designed by zk-sync, an Ethereum L2 scaling solution that uses zk-rollups.


Since I posted this, I got to know that NEAR cofounder @illia had previously posted the same concept as a bounty on NEAR’s github ( Succinct Proof for NEAR light client · Issue #34 · near/bounties · GitHub )

We have already done the ED25519 and ECDSA signature verification implementation in a zero-knowledge circuit and verified it on EVM.

Hi @garvitgoel, is there any way to test it with the Rainbow Bridge?

I’m curious to know what is the cost of submitting such proof on Ethereum.

  • Off chain (time to compute this proof?)
  • On chain (gas to verify the proof)

X-Posting as well to GitHub to move the bounty ahead


Hey @garvitgoel . Let’s have a call, I would like to help you get this project funded.