# Polkadot cryptography hostcalls

These small projects would move us towards having flexible cryptography in polkadot, along the lines of https://hackmd.io/@rgbPIkIdTwSICPuAq67Jbw/rkipBanIn

## Arkworks

### ark-ec performance wrappers

Arkworks has among the most flexible framework for implementing elliptic curves, but the proformance often lags more specialized curve implementations.

We want wrapper crates that expose faster backends through the artworks traits in ark-ec whenever possible, including tests that they match the existing arkworks implementation.

[ark-blst](https://github.com/nikkolasg/ark-blst) is one nice example, but if others exist then they should be identified, and implemented. [zka.lc](https://zka.lc/) provides a survey of MSM performance across implementations.

### ark-ed25519-dalek

We particularly want an ark-ec wrapper for curve25519-dalek, including Ed25519, Ristretto, and Curve25519 if possible. Again tests for [ark_ed25519](https://docs.rs/ark-ed25519/latest/ark_ed25519/) compatibility.

See https://github.com/arkworks-rs/algebra/issues/819

### curve25519-dalek multi-threaded MSMs

Implement multi-threaded backend for large multi-scalar multiplications in curve25519-dalek. Ask on curve25519-dalek itself if this exists first though.

If possible, document how much total CPU time this costs, vs the latency trade off.

### Resolve Arkwroks vs ETH ed_on_bn254 issue

This can be solved on the arkworks side, but if they solve it by providing another curve then using that curve sounds easiest.

See https://github.com/arkworks-rs/algebra/issues/858

### art-transcript-eth

At least some fork of [ark-transcript](https://github.com/w3f/ark-transcript) should work nicely in ETH. This requires figuring out how others have done transcripts in ETH.

## Elliptic curves in substrate

### Affine returns in sp-ark-* hostcalls

At present, these return serialized projective points from scalar multiplications in the sp-ark-* hostcalls, which apes the optimisations we use in native code.

We should instead return affine points for two reasons:

1. *The 10x speed gap between wasm/pvm and native alters the optimizations.*

A scalar multiplication should usually return projective because (1) you might do more arithmetic, like an addition, (2) that arithmetic works as fast on the projective point as on the affine point, if not slightly faster, and (3) the conversion from projective to affine costs at least one division. In our case, (3) would run in wasm/pvm making it even slower.

The extra division isn't that heavy in native. In fact, if the division costs 10x in wasm/pvm then we break even doing the division in native inside the hostcall, even if we only require the division 10% of the time. We'll want that division way more than 10% of the time, because even if we do arithmetic we'll likely be hashing the output or whatever, and hashing requires affine. This is especially true if code is optimised by using MSMs even for small equations.

2. *The projective coordinate interface creates a maintenance burden.*

We standardize serializations which pushes uncompressed affine coordinates towards being relatively standard. There is otoh absolutely no standardisation in projective coordinates, because they're insecure to serialise anyways. If arkworks might never change theirs, but we might want to use blst for the background here for performance, or another RC implementaiton might do so. You could always implement the isogeny that maps between the projective coordinate flavors, but that's some EC math so not going to ask people to do that.

### Update sp-ark-* hostcalls

We should update both the substrate elliptic curve hostcalls, first implemented in [substrate PR 13031](https://github.com/paritytech/substrate/pull/13031), and switch over to the faster backends noted above where available, ala ark-blst and ark-ed25519-dalek.

Also, upgrade their invocation path in [sp-ark-* crates](https://github.com/paritytech/arkworks-substrate) ([previously arkworks-extensions](https://github.com/paritytech/arkworks-extensions)), primarily for changes in the ark-ec crates.

### Add sp-ark-bw6-767, sp-ark-ed25519, sp-ark-secp256k1

Add both hostcalls like in [substrate PR 13031](https://github.com/paritytech/substrate/pull/13031), as well as new sp-ark-* crates in [arkworks-substrate](https://github.com/paritytech/arkworks-substrate),

See https://github.com/paritytech/polkadot-sdk/issues/5217#issuecomment-2267180569

### sp-ecdsa-k256/sp-ecdsa-secp256k1

We need a standard and bitcoin compatible secp256k1 ecdsa verification. Ideally we'd fork [k256](https://docs.rs/k256/latest/k256/) and its backend crates to use the new sp-secp256k1 crate proposed above.

### sp-curve25519-dalek

We want a curve25519-dalek fork with a backend that makes substrate hostcalls for Ed25519 and Ristretto.

It should use exactly the same hostcalls as [sp-ark-* crates](https://github.com/paritytech/arkworks-substrate). It should yield the same results as sp-ark-ed25519 and curve25519-dalek.

### Add niche curves

Are flexible parameter curves even possible? Are they fast enough?

Discuss adding sp-ark-secq256k1 and sp-ark-secp256r1. See https://github.com/polkadot-fellows/RFCs/pull/113#issuecomment-2293674448

Discuss adding bn254, grumpkin, and babyjubjub. See https://github.com/arkworks-rs/algebra/issues/858

Discuss adding sister curves for bls12-381 and bls12-377.

Add pasta curve cycle, provided someone first shows good benchmarks for Verkle trees using pasta.

### Audit sp-ark-* hostcalls

Are they reasonably future proof against future curve optimizations?

### Fellowship RFC for sp-ark-* hostcalls

It'd be based upon https://hackmd.io/@rgbPIkIdTwSICPuAq67Jbw/rkipBanIn

### Substrate batch verification

An implementation of batch verification for ed25519 and sr25519 using sp-curve25519-dalek that's compatible with frame, necessarily using unsafe code.

Ring VRFs provide good targets for batch verification too.

In those cases, we could do the batch verification in its own hostcall, but doing it this way buys us flexibility.