Bringing IBC to NEAR using ZK-SNARKS (no NEP required)

Prepared by Electron Labs: Garvit Goel, Rahul Ghangas, Jinank Jain

This is in response to the proposal submitted by @sitoula on Near gov under the title "NEAR <> Polkadot using IBC Trustless bridging: Requests"

As pointed out by sitoula, bringing IBC to NEAR will require acceptance of pre-compiles, which will require design, implementation and acceptance of relevant NEPs. NEPs can require a lot of work and take time, and hence we present a simpler solution.

Here, we present a proposal to bring IBC to NEAR without the need for pre-compiles. We achieve this by use of zero knowledge proofs to achieve signature compression. At this time, the proposed solution is ready to be used with IBC. What is even more encouraging is that the Rainbow bridge is already in the process of integrating our solution. Rainbow (NEAR<>Eth Bridge) faces a similar problem i.e. lack of ed25519 pre-compiles on Ethereum.

The Composable/IBC team can start the integration process today by referring to our documentation given at Electron Docs (see comments for link)

No developer bandwidth is required from the NEAR core team, as our solution exists completely as a smart contract and does not require any work on NEARCore.

An Overview of our Solution

The Composable team has requested pre-compiles since it is important to be able to verify a batch of digital signatures (ed25519, sr25519, ecdsa on secp256k1) in a single NEAR transaction. The batch size is required to be 130 signatures but is likely to increase to 667 in near future.

We propose that rather than submitting the signatures directly on-chain, one can create a zk-proof of the validity of the signature batch and submit the proof on-chain instead.

By use of zk-snarks, it will cost 104T gas per batch of signatures. (see comments for link)

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 (see comments for link). Check out the complete code base here.

For now, our solution supports batch sizes of up to 99 signatures per zk-proof. This means we will need two zk-proofs to verify the entire 130 signatures batch. These should fit easily into one transaction consuming 208T (2*104T) gas.

In order to scale up to 667 signatures, we would need to integrate recursive snark technology. At Electron Labs, we already have this in our roadmap, and can bring it forward if required. Post this integration, we can scale the batch size to a very large number.

How to integrate our solution?

Our proof generation system can be shipped as a microservice such that the relayer infrastructure can run it on their machine. To make integration smoother, we have deployed a server whose endpoints allow you to submit a batch of signatures and get the zk-proof in return. You can test this out right now using the API reference given here - Electron Server

Once the proof is generated, you will need to verify it on-chain. For this, we have shipped a zk-snark verifier as a smart contract. You can find link to the code in the comments.

Additional Advantages of using our solution over NEP

  1. As the number of validators in the Polkadot set grows, the number of signatures could further increase which can become difficult to handle with pre-compiles. This is easily solved with our approach as one will be able to prove a large number of signatures once snark recursion is integrated into our tech.
  2. Our approach will enable the verification of sr25519 as well as it can be easily included in the zk-proof. This is helpful since it is possible that sr25519 may not be included in the NEP (based on github comments for the NEP364)
  3. Our solution is already being deployed with Rainbow bridge, and hence a lot of integration specifics have been figured out.

Rainbow Bridge is already integrating our solution

Rainbow Bridge (NEAR<>Eth) also faces a similar problem since Ethereum does not have pre-compiles for ed25519. The cost of verifying a batch of 100 signatures on Ethereum is prohibitively large. We are currently in the process of integrating our zk-based solution and working with the Rainbow team on this.

You can check out the initial proposal for this idea here which was submitted on Nov, 21

Our approach is significantly cheaper as well.

zk-proof verification requires operations on the altbn128 curve. The pre-complies for this have already been accepted into NEARCore, and are likely to go live in the next release. See link to GitHub in comments.

Once these pre-compiles are live, the cost of verifying a zk-proof will come down significantly (from the current 104T gas), making the process extremely cheap.

Ending Note:

We will love to work with the relevant teams to take this to production.

cc: @Bowen

8 Likes

Relevant Links

  1. Electron Intergration Docs - Overview

  2. Execution of on-chain zk-verifier costing 104T gas - NEAR Explorer | Transaction

3 Likes

Relevant Links

  1. Mathematics behind our approach - Large numbers in circom

  2. Zk-Verifer Smart contract - GitHub - Electron-Labs/electron-rs: SDK for Zero Knowledge Proof Verification on Rust based chains

3 Likes

Thanks, @garvitgoel !

You guys have been building a truly useful tool; thanks for sharing it with us.

Do you have benchmarks of proof construction time with different hardware? Since we will be using this for validating blocks, I need to be sure that the latency is good for us to keep up with the block production.

Has your circuit + verifier been audited? If not, are you planning to do so?

Hi @sitoula
Thank you for your interest.
The Proof production time is roughly 8 minutes, and you can expect the total latency introduced to be similar to this number. Is this acceptable? If not, there are techniques (such as recursive snarks) to reduce this time by orders of magnitude, though it will require a bit of work.

Regarding audits, since the Rainbow bridge is planning to integrate this, we are working with them to schedule audits for our circuits.

Hope this helps and looking forward to your feedback!

1 Like