NEAR <> Polkadot using IBC Trustless bridging: Requests

1. Pre-compiles/Host functions for signature verification

Introduction

In order to deploy a light client that’s able to verify the state of a chain within
another chain, there’s a need to verify signatures. Signature verification is an
ubiquitous operation, especially in PoS consensus mechanisms.

Our rough numbers say that we’ll be verifying ~200 signatures every minute (Polkadot’s authority set is 300 signers). Therefore, we need a mechanism to perform these operations in a cost-effective way in terms of gas and speed. Currently, NEAR does not have any native signature verification toolbox. This implies that a light client operating insid NEAR will have
to import a library compiled to WASM as mentioned in Zulip.

A first draft of how these pre-compiles interface could look like:

pub fn ed25519_verify(sig: &ed25519::Signature, msg: &[u8], pub_key: &ed25519::Public) -> bool
pub fn sr25519_verify(sig: &sr25519::Signature, msg: &[u8], pub_key: &sr25519::Public) -> bool
pub fn ecdsa_verify(sig: &ecdsa::Signature, msg: &[u8], pub_key: &ecdsa::Public) -> bool

Pitfalls and benchmarks

The biggest pitfall of the current solution is performance and cost. Our benchamarks show the following results:

verify_ed25519

near call sitoula-test.testnet verify_ed25519 '{"signature_p1": [145,193,203,18,114,227,14,117,33,213,121,66,130,14,25,4,36,120,46,142,226,215,7,66,122,112,97,30,249,135,61,165], "signature_p2": [221,249,252,23,105,40,56,70,31,152,236,141,154,122,207,20,75,118,79,90,168,6,221,122,213,29,126,196,216,104,191,6], "msg": [107,97,106,100,108,102,107,106,97,108,107,102,106,97,107,108,102,106,100,107,108,97,100,106,102,107,108,106,97,100,115,107], "iterations": 10}' --accountId sitoula-test.testnet --gas 300000000000000

# transaction id DZMuFHisupKW42w3giWxTRw5nhBviPu4YZLgKZ6cK4Uq

verify_schnorrkel

near call sitoula-test.testnet verify_schnorrkel '{"signature_p1": [106, 144, 17, 34, 142, 65, 191, 241, 233, 250, 132, 168, 204, 173, 122, 196, 118, 248, 159, 159, 254, 37, 153, 84, 248, 104, 206, 217, 168, 65, 12, 74], "signature_p2": [183, 134, 143, 30, 123, 61, 112, 153, 244, 109, 199, 195, 164, 0, 7, 55, 26, 199, 164, 219, 147, 217, 157, 239, 198, 108, 162, 246, 52, 49, 116, 132], "msg": [107,97,106,100,108,102,107,106,97,108,107,102,106,97,107,108,102,106,100,107,108,97,100,106,102,107,108,106,97,100,115,107], "iterations": 10}' --accountId sitoula-test.testnet --gas 300000000000000

# transaction id DpWpK2jnyBRgZ7fScaBKULikJyvmMjDHx7AyWMrJL5VB

verify_ecdsa

near call sitoula-test.testnet verify_ecdsa '{"signature_p1": [231, 117, 17, 89, 49, 142, 111, 201, 161, 107, 167, 147, 215, 167, 196, 226, 200, 176, 184, 62, 196, 240, 210, 137, 77, 198, 90, 97, 201, 212, 96, 229], "signature_p2": [1, 31, 7, 121, 178, 247, 150, 131, 108, 250, 173, 71, 100, 192, 83, 64, 145, 85, 254, 69, 176, 7, 114, 89, 64, 205, 30, 243, 193, 78, 142, 27], "msg": [107,97,106,100,108,102,107,106,97,108,107,102,106,97,107,108,102,106,100,107,108,97,100,106,102,107,108,106,97,100,115,107], "iterations": 10}' --accountId sitoula-test.testnet --gas 300000000000000
# transaction id AKFwCuQ8g2a8t9SX7vcve348BvwoU3M42MSef7gy1kPA

With iterations = 130 all these calls return ExecutionError: 'Exceeded the maximum amount of gas allowed to burn per contract.'
With iterations = 50 these are the results:

ed25518: tx id 6DcJYfkp9fGxDGtQLZ2m6PEDBwKHXpk7Lf5VgDYLi9vB (299 Tgas)
schnorrkel: tx id ACYJh7YC4pQM8fu7DsjmmkSb3WSvikfQkVyej3htiuDQ (304 Tgas)
ecdsa: tx id 2FhtFEbakuwQyHWcyeRoPkCDgXz4erTYSD75QkxDTb2e (185 Tgas)

Note that these results show that’s currently not possible to validate all 130 signatures in just one transaction, which would be something very desirable. We are hitting gas limits with the wasm libraries for all schemes. The cutoff number seems to be around 50 signatures into one transaction.

Request

We therefore request that these three signatures schemes (ed25519 + sr25519 + ecdsa on secp256k1) are included
within NEAR’s runtime as precompiled. It will allow us to run these operations in a
fast, secure and cost effective way. This will ultimately yield a better user experience
for users willing to unlock the full potential of a composable ecosystem across chains.

2. Request the state of accounts and contracts with an attached merkle proof

Currently, querying the state of an account (through the below RPC call)

{
  "jsonrpc": "2.0",
  "id": "dontcare",
  "method": "query",
  "params": {
    "request_type": "view_account",
    "finality": "final",
    "account_id": "nearkat.testnet"
  }
}

or requesting the contract’s state (through the following request)

{
  "jsonrpc": "2.0",
  "id": "dontcare",
  "method": "query",
  "params": {
    "request_type": "view_state",
    "finality": "final",
    "account_id": "guest-book.testnet",
    "prefix_base64": ""
  }
}

returns the correct result, but no proof attached.

NOTE: There’s a field called proof
in the response for the view_state endpoint, but in the example is shown as empty.
So, if this is already covered for the smart contract,
the section should be discarded.

The IBC standard requires that the NEAR relayer is able to feed our IBC framework running
in the Polkadot parachain with not only the data, but also the valid proofs that
help us to trustlessly validate that the state is correct.

3. Request block of transaction validations

The NEAR spec contains a detailed section on proof verification. It is possible
for a light client to validate whether a transaction or receipt happened on-chain.

For our purposes of bridging Polkadot with NEAR following the IBC’s (GitHub - cosmos/ibc: Interchain Standards (ICS) for the Cosmos network & interchain ecosystem.)
standard we are requesting the ability to validate a set of transactions as a batch
as opposed to singular verification. This is how IBC works in general, and there is a clear benefit to doing it
that way: proof-verification becomes less expensive as there is no need to re-calculate
hashes.

We would like to request an endpoint where a Vec is passed
and an adapted version of RpcLightClientExecutionProofResponse is returned, where we can still verify that a block_outcome_root matches the block_header_lite.inner_lite
for each transaction. And, as previously mentioned, there will be a reduction in total calculations of:

block_merkle_root = compute_root(block_hash, block_proof)

since we would be able to cache intermediate hashes within the compute_root calculation on the entire batch of transactions.

I had some limits on how many links I could post, since I’m a new user.

• Discussion about gas usage and precompiles of signature verification: Zulip
• Cosmos reference repo for IBC: GitHub - cosmos/ibc: Interchain Standards (ICS) for the Cosmos network & interchain ecosystem.

Adding more links:

• Benchmark code for signature verification on NEAR: blasrodri/near-lite.git on github. Not sure why I’m not allowed to post a link to my own repo…

Hi @sitoula! Thank you very much for your detailed post and benchmark results.

sitoula:

Request

We therefore request that these three signatures schemes ( ed25519 + sr25519 + ecdsa on secp256k1 ) are included
within NEAR’s runtime as precompiled . It will allow us to run these operations in a
fast, secure and cost effective way. This will ultimately yield a better user experience
for users willing to unlock the full potential of a composable ecosystem across chains.

I suppose the idea would be to make these available as host functions that a contract can call. Note that if we were to do this, then the contract would still have to pay for the host functions. So including them into the runtime would only be beneficial if they would be more efficient to run when part of the runtime.

I can see some reasons to believe that including them in the runtime can indeed be more efficient. If they are part of the contract, then they have to be compiled from rust to wasm (by the developer) and then from wasm to native (by the network). The compilation from wasm to native goes through a single pass compiler in wasmer and may not produce as efficient code as possible. Instead if the library were included in the runtime, then it would be compiled from rust to native and go through a more optimising compiler which could produce a efficient code.

An important data point to collect would be to estimate how much benefit we could expect from using a more optimising compiler. Maybe this is an experiment that you can perform yourself? What we would be looking to comparing would be the following:

• Performance in wall clock time when you compile the signature validation library directly from rust to native.
• Performance in wall clock time when you compile the library into wasm first and then use the single pass compiler in wasmer to then compile to native.

Here are the results I’ve gotten on my machine (AMD Ryzen 9 5900X 12-Core Processor):

• Performance in wall clock time when you compile the signature validation library directly from rust to native.

# 10k signature verifications
ed25519: took 387ms
ecdsa: took 324ms
shnorrkel: took 411ms

• Performance in wall clock time when you compile the library into wasm first and then use the single-pass compiler in Wasmer 1 to then compile to native.

ed25519: took 9926ms
ecdsa: took 6725ms
shnorrkel: took 10220ms

As an extra datapoint, when passing --enable-simd instead of --singlepass

ed25519: took 3085ms
ecdsa: took 1895ms
shnorrkel: took 3179ms

Steps to reproduce:
commit: 31cf97fb2e155d238308f062c4b92bae716ac19f in https://github.com/blasrodri/near-test

# wasi singlepass
cargo wasi build --bin benches --release
wasmer compile --singlepass ./target/wasm32-wasi/release/benches.wasi.wasm -o benches_singlepass 
wasmer run ./benches_singlepass

# rust native
cargo run --bin benches --release

Overall: the difference between the two versions (native vs wasi + singlepass are)

ed25519: 25.64x slower
ecdsa: 20.75x slower
shnorrkel: 24.86x slower

Hi @sitoula! Thank you very much for the nice results. Looks like our intuition was correct, natively compiling the libraries does give us a significant performance improvement.

Just to check, is the estimated improvement in performance satisfactory for your usecase?

If so, I think this work is ready to move to the next phase where you create NEP (NEAR Enhancement Proposal) and gather support to get it accepted. GitHub - near/NEPs: The Near Enhancement Proposals repository is the repo that can help guide you into making the NEP. [PROPOSAL] Reduce the gas floor price on the NEAR network is an example of an active proposal currently being worked on. Please tag me on the proposal so I can follow along as well and feel free to ask questions.

Note that I am quite new to the project so this is also a learning experience for me. So I may not always know the answers but I will help find them.

With regards to

2. Request the state of `accounts` and `contracts` with an attached merkle proof

I’ve found this issue to be relevant: https://github.com/near/nearcore/issues/2076

Wow congrats , do you have any introduction for non engineer researchers?

Hi! We wrote a thread in twitter about this.