Prepared by Electron Labs
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.
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.
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.
- 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.
- 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)
- Our solution is already being deployed with Rainbow bridge, and hence a lot of integration specifics have been figured out.
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
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.
We will love to work with the relevant teams to take this to production.