---
NEP: 364
Title: Efficient signature verification and hashing precompile functions
Author: Blas Rodriguez Irizar <rodrigblas@gmail.com>
DiscussionsTo: https://github.com/nearprotocol/neps/pull/364
Status: Draft
Type: Runtime Spec
Category: Contract
Created: 15-Jun-2022
---

## Summary

This NEP introduces the request of adding into the NEAR runtime a pre-compiled
function used to verify signatures that can help IBC compatible light clients run on-chain.

## Motivation

Signature verification and hashing are ubiquitous operations in light clients,
especially in PoS consensus mechanisms. Based on Polkadot's consensus mechanism
there will be a need for verification of ~200 signatures every minute
(Polkadot’s authority set is ~300 signers and it may be increased in the future: https://polkadot.polkassembly.io/referendum/16).

Therefore, a mechanism to perform these operations cost-effectively in terms
of gas and speed would be highly beneficial to have. Currently, NEAR does not have any native signature verification toolbox.
This implies that a light client operating inside NEAR will have to import a library
compiled to WASM as mentioned in [Zulip](https://near.zulipchat.com/#narrow/stream/295302-general/topic/light_client).

Polkadot uses [three different cryptographic schemes](https://wiki.polkadot.network/docs/learn-keys)
for its keys/accounts, which also translates into different signature types. However, for this NEP the focus is on:

- The vanilla ed25519 implementation uses Schnorr signatures.

## Rationale and alternatives

Add a signature verification signatures function into the runtime as host functions.

- ED25519 signature verification function using `ed25519_dalek` crates into NEAR runtime as pre-compiled functions.

Benchmarks were run using a signature verifier smart contract on-chain importing the aforementioned functions from
widespread used crypto Rust crates. The biggest pitfall of these functions running wasm code instead of native
is performance and gas cost. Our [benchmarks](https://github.com/blasrodri/near-test) show the following results:

```log
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
```

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:

```text
ed25519: tx id 6DcJYfkp9fGxDGtQLZ2m6PEDBwKHXpk7Lf5VgDYLi9vB (299 Tgas)
```

- Performance in wall clock time when you compile the signature validation library directly from rust to native.
  Here are the results on an AMD Ryzen 9 5900X 12-Core Processor machine:

```text
# 10k signature verifications
ed25519: took 387ms
```

- 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.

```text
ed25519: took 9926ms
```

As an extra data point, when passing `--enable-simd` instead of `--singlepass`

```text
ed25519: took 3085ms
```

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

```sh
# 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
```

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

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

```text
ed25519: 25.64x slower
```

### What is the impact of not doing this?

Costs of running IBC-compatible trustless bridges would be very high. Plus, the fact that signature verification
is such an expensive operation will force the contract to split the process of batch verification of signatures
into multiple transactions.

### Why is this design the best in the space of possible designs?

Adding existing proved and vetted crypto crates into the runtime is a safe workaround. It will boost performance
between 20-25x according to our benchmarks. This will both reduce operating costs significantly and will also
enable the contract to verify all the signatures in one transaction, which will simplify the contract design.

### What other designs have been considered and what is the rationale for not choosing them?

One possible alternative would be to improve the runtime implementation so that it can compile WASM code to a sufficiently
fast machine code. Even when it may not be as fast as LLVM native produced code it could still be acceptable for
these types of use cases (CPU intensive functions) and will certainly avoid the need of adding host functions.
The effort of adding such a feature will be significantly higher than adding these host functions one by one.
But on the other side, it will decrease the need of including more host functions in the future.

Another alternative is to deal with the high cost of computing/verifying these signatures in some other manner.
Decreasing the overall cost of gas and increasing the limits of gas available to attach to the contract could be a possibility.
Introducing such modification for some contracts, and not for some others can be rather arbitrary
and not straightforward in the implementation, but an alternative nevertheless.

## Specification

This NEP aims to introduce the following host function:

```rust
extern "C"{

/// Verify an ED25519 signature given a message and a public key.
/// Ed25519 is a public-key signature system with several attractive features
///
/// Proof of Stake Validator sets can contain different signature schemes.
/// Ed25519 is one of the most used ones across blockchains, and hence it's importance to be added.
/// For further reference, visit: https://ed25519.cr.yp.to
/// # Returns
/// - 1 if the signature was properly verified
/// - 0 if the signature failed to be verified
///
/// # Cost
///
/// Each input can either be in memory or in a register. Set the length of the input to `u64::MAX`
/// to declare that the input is a register number and not a pointer.
/// Each input has a gas cost input_cost(num_bytes) that depends on whether it is from memory
/// or from a register. It is either read_memory_base + num_bytes * read_memory_byte in the
/// former case or read_register_base + num_bytes * read_register_byte in the latter. This function
/// is labeled as `input_cost` below.
///
/// `input_cost(num_bytes_signature) + input_cost(num_bytes_message) + input_cost(num_bytes_public_key)
///  ed25519_verify_base + ed25519_verify_byte * num_bytes_message`
///
/// # Errors
///
/// If the signature size is not equal to 64 bytes, or public key length is not equal to 32 bytes, contract execution is terminated with an error.
  fn ed25519_verify(
    sig_len: u64,
    sig_ptr: u64,
    msg_len: u64,
    msg_ptr: u64,
    pub_key_len: u64,
    pub_key_ptr: u64,
  ) -> u64;
```

And a `rust-sdk` possible implementation could look like this:

```rs
pub fn ed25519_verify(sig: &ed25519::Signature, msg: &[u8], pub_key: &ed25519::Public) -> bool;
```

Once this NEP is approved and integrated, these functions will be available in the `near_sdk` crate in the
`env` module.

[This blog post](https://hdevalence.ca/blog/2020-10-04-its-25519am) describes the various ways in which the existing Ed25519 implementations differ in practice. The behavior that this proposal uses, which is shared by Go `crypto/ed25519`, Rust `ed25519-dalek` (using `verify` function with `legacy_compatibility` feature turned off) and several others, makes the following decisions:

- The encoding of the values `R` and `s` must be canonical, while the encoding of `A` doesn't need to.
- The verification equation is `R = [s]B − [k]A`.
- No additional checks are performed. In particular, the points outside of the order-l subgroup are accepted, as are the points in the torsion subgroup.

Note that this implementation only refers to the `verify` function in the
crate `ed25519-dalek` and **not** `verify_strict` or `verify_batch`.

## Security Implications (Optional)

We have chosen this crate because it is already integrated into `nearcore`.

## Unresolved Issues (Optional)

- What parts of the design do you expect to resolve through the NEP process before this gets merged?
  Both the function signatures and crates are up for discussion.

## Future possibilities

I currently do not envision any extension in this regard.

## Copyright

Copyright and related rights waived via [CC0](https://creativecommons.org/publicdomain/zero/1.0/).
