Keystore overhaul

[davxy]

While thinking about how to introduce new crypto types required by the Sassafras protocol, I ended up thinking that maybe, before blindly start writing code, it may be a better idea to first open a discussion about how cryptographic stuff is used by Substrate in order to maybe reduce some technical debt.

Things to know:

• KeyTypeId: identifies the context of application of a key (e.g. babe or grandpa)
• CryptoTypeId: indetifies the cryptographic scheme (e.g. sr25519 or ed25519)
• Keystore: an object used to work with secrets persisted somewhere (typically in the local filesystem)
• raw public key: an opaque byte array
• constructed public key: a key of one particular scheme (e.g. sr25519::Public)

---

Keystore

Currently, there are some inconsistencies in the keystore API.

I'm going to refer to the Local keystore implementation (currently the only implementation provided by the Substrate if we are not considering the testing one).

Signing

To sign a message there is the sign_with method which takes KeyTypeId, CryptoTypeId and a raw public key.
The public key and key-type-id are used to lookup the secret while the crypto-type-id is used to apply the proper scheme to sign the message. A constructed public key is built within the method after a match over all the supported CryptoTypeId.

The interface also provides sign_with_any and sign_with_all with an interface similar to sign_with.
The former is not used anywhere BTW and the second can be replaced by a loop in the caller (IMO it is not called so often to justify the requirement of an extra method).

Isolated there is a special ecdsa_sign_prehashed. It takes instead a constructed ecdsa::Public key

Lookup

To lookup keys there is one stand-alone method for each crypto scheme (e.g. one for sr25519 and one for ed25519).
These returns a typed Public key.

This API design is not consistent with the one used by sign_with that instead:

1. deals with raw public keys in the interface
2. is a catch-all for all crypto schemes (more crypto agile)

Key generation

The API exposes methods to generate keys and these are designed in the same way of lookup methods.
I.e. one stand-alone method for each scheme.

VRF

There is a sr25519_vrf_sign, stand-alone method for VRF signatures using sr25519. This uses constructed keys a well.

Rework

In the prospective of introducing new crypto schemes to support new protocols, I would like to discuss the interface of the keystore first.

As WiP extensions there is already:

• BLS12-381 signatures introduced by this PR from @drskalman.
  Here the bls_sign method is added as a stand-alone method, i.e. not part of sign_with:

  1. it doesn't follow the same pattern of the others (i.e. is not part of sign_with).
  2. what if we will introduce the usage of other BLS curves in the future?

• Sassafras will make use of ed_on_bls12_381 or ed_on_bls12_381_bandersnatch. A primitive that is related but not the same bls12-381. This will require its methods as well.

• Just look at how many possible future curves just from arkworks we may require one day here

Option 1

One option is to provide a fully agile keystore and be less bound (at least in the interface) to the currently provided primitives.

This also allows users of Substrate that in their client are using protocols with crypto schemes not already supported by us.

To do this we may think of removing specialized methods from the interface, i.e. provide methods in a form similar to sign_with. And thus:

• sign(app_id: KeyTypeId, crypto_id: CryptoTypeId, public: &[u8], msg: &[u8]) -> Result<Vec<u8>>
• sign_prehashed(app_id: KeyTypeId, crypto_id: CryptoTypeId, public: &[u8], hash: &[u8]) -> Result<Vec<u8>>
• vrf_sign(app_id: KeyTypeId, crypto_id: CryptoTypeId, public: &[u8], msg: &[u8]) -> Result<Vec<u8>>
• public_keys(app_id: KeyTypeId, crypto_id: CryptoTypeId) -> Vec<Vec<u8>>
• etc

This interface prevents the explosion of methods and thus is more sustainable.

Obviously, for example, the usage of vrf_sign with a crypto scheme that doesn't support it will return a "not supported" error...

However... should also be considered that we still provide one method per primitive in the
Crypto runtime interface.
So maybe, if a good part of the primitives, are exposed to the runtime as well the explosion will be observed there at some point
(but this may be considered as an independent problem... more below).

Option 2

Remove the generic sign_with method from the keystore and provide only specialized stand-alone methods for all the schemes we support. We already do this for all the operations except for "signing". Thus provide instead sr25519_sign, ed25519_sign, ecdsa_sign.

My only concern is that we will also have to introduce stuff like:

• bls12_381_sign
• bls12_377_sign
• ed_over_bls12_381_sign
• ed_over_bls12_377_sign
• and there are others... who know what we're going to support in the future

---

Host Functions

If we decide to go with Option 1 maybe we should also consider a refactory in the sp_io crate in order to provide more fine-grained capabilities. For example @achimcc is already adopting this approach to define all the host functions he's requiring to work with a bunch of "special" elliptic curves operations.

Maybe we should start grouping these host functions in separate files and better logically organize them.
For example instead of a giant group containing crypto "stuff" divide these in a more fine grained way as:

• Bls12381
• Bls12377
• EdOnBls12381
• EdOnBls12377
• Sp25519
• Ed25519
• Ecdsa
  ...

Strict adoption of this approach also requires to extract the methods from the ever-growing sp_io::crypto module.

The ideal would be having a module like sp_io::crypto::sp25519 instead of embedding all the crypto primitives in one single crypto module.

But maybe is not backward compatible... But is this even possible (having submodules of sp_io::crypto for each crypto scheme)? Maybe we can do this at least for new stuff?

---

Final Considerations

All in all, I wanted to highlight and open a discussion about possible issues that I have noticed before introduce even more new stuff.

The end goal is to introduce new things in a more organized and carefully designed way before is "too late" to rethinking about it (especially for the host functions part) and accumulate technical debt.

[davxy]

cc @burdges @paritytech/sdk-node

[bkchr]

The entire keystore contains currently code for stuff that was never implemented (remote signing). CryptoTypeId alongside the CryptoStore (the async interface) trait are prominent changes that were introduced because of this. We can properly do a clean up of all this stuff.

Option 2

Remove the generic sign_with method from the keystore and provide only specialized stand-alone methods for all the schemes we support. We already do this for all the operations except for "signing". Thus provide instead sr25519_sign, ed25519_sign, ecdsa_sign.

As the host functions need to be explicit any way, I would also go here the explicit way. It is not that we introduce every day a new crypto scheme. I think the current interface is basically the same since its initial creation (besides the split in sync/async).

Maybe we should start grouping these host functions in separate files and better logically organize them. For example instead of a giant group containing crypto "stuff" divide these in a more fine grained way as:

* `Bls12381`

* `Bls12377`

* `EdOnBls12381`

* `EdOnBls12377`

* `Sp25519`

* `Ed25519`

* `Ecdsa`
  ...

Strict adoption of this approach also requires to extract the methods from the ever-growing sp_io::crypto module.

The ideal would be having a module like sp_io::crypto::sp25519 instead of embedding all the crypto primitives in one single crypto module.

But maybe is not backward compatible... But is this even possible (having submodules of sp_io::crypto for each crypto scheme)? Maybe we can do this at least for new stuff?

Yes for sure! We can add these new host functions to new "modules".

[hujw77]

BLS12-381 hash-to-curve-g2 is extremely slow, but it maybe makes more sense for Ethereum light client.
Is there a plan to add host-to-curve-g2 as a host function in substrate?

[burdges]

As discussed in https://eprint.iacr.org/2022/1611 and being implemented in nugget_bls we'll hash-to-G1 but have equivalent public keys on G1 and G2, so then verifiers always sum public keys on G1. It's silly to have any verifier operations on G2 like ethereum does.

[hujw77]

As discussed in https://eprint.iacr.org/2022/1611 we'll hash-to-G1 but have equivalent public keys on G1 and G2, so then verifiers always sum public keys on G1. It's silly to have any verifier operations on G2 like ethereum does.

I see the performance improvement to use hash-to-G1 in that paper, but Ethereum use hash-to-G2.
It has no choice for bridges based on Ethereum beacon light client, such as Snowfork and Darwinia network.
If there is a hash-to-G2 host function in substrate, will be extremely helpful for truthless bridges.

cc @wuminzhe @AlistairStewart

[davxy]

@hujw77 maybe this is a topic for a separate issue.

[AlistairStewart]

Indeed it is. We may well have a hash to G2 host function in the future but we don't envision Substrate nodes BLS signatures to ever need to be in G2.