Succinct Proof for NEAR light client

[ilblackdragon]

NEAR Bounty Terms

Before beginning work on the bounty, you must submit a proposal. Only if your proposal is accepted will you be able to claim the reward of the bounty. Your proposal should include time that it would take for your to complete this bounty.

There should be at most 1 week between proposal is accepted and you start working on the bounty.

Description

Light client for NEAR is relatively cheap in verifying, outside of set of ed25519 signatures of block producers.

Compressing the light block verification to just verifying of a single proof would provide a useful tool to sync blocks faster and use it in the Rainbow bridge.

Context

NEAR's light client specification is described here: https://nomicon.io/ChainSpec/LightClient.html

Acceptance Criteria

• Light client proof generator, that fetches specific block by height from the node over RPC and generates a succinct proof that takes block hash and a block from previous epoch as arguments
• Tests that verifies that for various blocks proofs are correct
  • Last block in the epoch
  • First block in the epoch
  • Middle of the epoch block
  • Invalid block: invalid data, signatures, etc
  • A test that would scan all blocks in the MainNet, generate proofs and verify that they are correct
• Proof verifier contract in Solidity, that given block hash and block from previous epoch and a proof returns if it's valid

Extra:

• Recursively proof light client from genesis until given block.

Bounty

Name your price!

[Fifiboss98]

Hello

Is the bounty still available?

[garvitgoel]

Hi @ilblackdragon
Very cool! We are currently building the exact same thing between tendermint to Ethereum. So far we have been able to create zk-proofs for a single ed25519 sig. The next step, do it for the entire validator set, and then the complete light client. If this grant is still open, let us know, we would love to submit a proposal for Rainbow.

Interesting, before I saw this Bounty, I submitted a high-level outline for this a couple of days back on the NEAR forum - https://gov.near.org/t/rainbow-upgrade-idea-using-zk-snarks-to-cheaply-verify-ed25519-signatures-on-ethereum-mainnet/7089

[garvitgoel]

Progress Update:
Hi @ilblackdragon
We have already done the ED25519 and ECDSA signature verification implementation in a zero-knowledge circuit and verified it on EVM.

[mfornet]

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)