Define Crypto API (meta)

[ethanfrey]

There have been a number of requests for suporting various signature verification as "pre-compiles", such as #583 as well as a number of requests in chats. This is an overview ticket to work out what APIs we would like to support. Each individual algorithm should be a separate PR (and maybe a breakout issue). You may also want to address #602 to allow more complex return values in these APIs.

Very important:

• Secp256k1 signature verification base (Add secp256k1_verify API #780)
• Secp256k1 signature verification compatible with Cosmos SDK (Support Cosmos SDK secp256k1 signature verification #752)
• Secp256k1 signature verification compatible with Eth 1.0 (Support Ethereum secp256k1 signature verification #753)
• Secp256k1 signature verification compatible with Bitcoin, Bitcoin forks (Create demo Bitcoin transaction verification #798)
• Secp256k1 signature verification compatible with EOS?
• Ed25519 signature verification compatible with Tendermint block headers (should provide Stellar and Cardano as well as NEAR protocol compatibility) (Support ed25519 signature verification (e.g. Tendermint block headers) #755)

Serious Consideration:

• Batch verification of ed25519 signatures (Batch verification of ed25519 signatures #781)
• sr25519 signature verification commonly used in Polkadot and (passively) supported by Tendermint. schnorkel seems to be needed for Substrate Light Clients (Grandpa). See Chorus One's work as a CosmWasm smart contract (Update from Joe: substrate chains use either ed25519 or sr25519; so addition of the sr25519 crate would be awesome :)
• BLS pairing primitives as needed to allow https://github.com/CosmWasm/drand-verify to be small and fast. In particular support for pairing on the bls12_381 curve. Ideally this is general enough to support ZCash's Jubjub on the same bls12_381 curve

Bonus Points:

• Secp256r1 signature verification: used in EOS, coming in Cosmos SDK v0.42 (found in Android and iOS secure enclaves)
• Secp256k1 schnorr theshhold scheme (verification side), as defined in BIP 340, which seems to be approaching Bitcoin mainnet
• Pairing support that maps to Ethereum ZK-snark support. In particular, supporting similar functionality to EIP 196 and EIP 197 This uses the alt_bn128 curve (maybe the same as bn256?). Reason to support this particular algorithm is the amount of tooling around Ethereum ZK snark contracts, eg. Zokrates, which may be able to be ported to CosmWasm contract.
• Various common blockchain hash functions (most are light enough to include in wasm):
  • keccak3
  • sha2-256
  • sha2-512
  • ripemd160
  • blake2

[ethanfrey]

Decision was made to:

1. Focus on supporting the "must-haves" with clean APIs and a gas metering strategy
2. Look into bls12-381 pairing operations after (when there is time)
3. Add other signature verification algorithms only when strong need/clear request (but the pattern is laid out)
4. Not worry about hashes - those work fine compiled into wasm, we need a clear case when those are an issue

[maurolacy]

Some comments regarding these signature verification schemes.

• Secp256k1 signature verification compatible with cosmos-sdk (uncompressed pubkey/signature format?). Uses DER? Was taking a look at cosmos-sdk, specifically: signverify.go. If you have a better reference, please let me know.
• Secp256k1 signature verification compatible with Eth 1.0, Bitcoin, Bitcoins forks, and EOS (compressed pubkey/signature format). There are multiple serialization schemes here:
• Bitcoin. Uses DER, with the pubkey embedded (new version) or not (old version) in the sig.
• Ethereum. Uses RLP, with the pubkey embedded in the sig.
• EOS. Uses DER with base58 encoded SHA256 hash.
• BTC forks. TODO.
• Ed25519 signature verification compatible with Tendermint block headers (should provide Stellar and Cardano as well as NEAR protocol compatibility). Should be simple to support, after secp256k1 is working with Cosmos formats.

All these schemes(except for the Cosmos alternative), use secp256k1.

My question is: At which level our API must handle signature verification for the different blockchains? That is, what are the formats for message, pubkey, and signature, that we must support as inputs in each case?

Moreover: From which sources do you recommend obtaining (or how to generate) messages, signatures and pubkeys that are compatible / valid for each blockchain? So that I can build test examples on how to deserialize them? The issue here seems to be more about deserialization formats and encodings for messages, keys, and signatures, than anything else.

After that, it will be easy for me to wrap and organize the needed methods / structures (probably from different crates), so that this verification functionality is readily available for contracts.

[ethanfrey]

@webmaster128 had made the proposal that we just define one canonical secp256k1 verify function. And the mapping from chain-specific format to this canonical format happen in the wasm contract. If we can produce some examples that do that for Cosmos SDK, Ethereum, and BTC, then I am happy.

One API function, a sample contract with 2 different calls, mapping the various chain formats to the underlying curve

[ethanfrey]

Moreover: From which sources do you recommend obtaining (or how to generate) messages, signatures and pubkeys that are compatible / valid for each blockchain? So that I can build test examples on how to deserialize them? The issue here seems to be more about deserialization formats and encodings for messages, keys, and signatures, than anything else.

Many of us can get a good Cosmos example. Ask in discord, someone in the team may be able to give good Eth or BTC reference data

[maurolacy]

Thanks for the answers. I'll work in the Cosmos example then (after getting some useful data / examples).

By the way, I've found some data in https://github.com/CosmWasm/wasmd/blob/master/x/wasm/internal/keeper/testdata/genesis.json#L157-L163.
I guess the signature is for the json encoded message, above, but I'm not sure. Wonder if this could be useful for tests.

[webmaster128]

Here you find good set of secp256k1 signatures to test the verification: https://github.com/cosmos/cosmjs/blob/v0.24.0-alpha.22/packages/crypto/src/secp256k1.spec.ts#L195-L517. message is the encoded transaction data. It goes through sha256 (the prehash) in order to be small enough to fit on the elliptic curve. How message is created on different chains does not matter to the signature verification API.

[webmaster128]

Here you find good set of secp256k1 signatures to test the verification: https://github.com/cosmos/cosmjs/blob/v0.24.0-alpha.22/packages/crypto/src/secp256k1.spec.ts#L195-L517.

Unfortunately those do not directly show the public key. It must be calculated from the private key. But I can do that later today.

[ethanfrey]

There is also
https://github.com/cosmos/cosmjs/blob/d0833a34f48733407c9947fafb5c773bca8850d6/packages/proto-signing/src/testutils.spec.ts

which is mainly targeting signing, but it has compressed pubkey, signBytes, and signature for 3 test cases. (The pubkey is on the top line outside the test cases, and base64 encoded not hex)

[webmaster128]

@maurolacy signBytes is the same as message from my comment. sha256(signBytes)/sha256(message) is what goes into the raw secp256k1 verify algorithm.

[webmaster128]

Here are the test vectors for the plain contract-vm interface: https://gist.github.com/webmaster128/919f5b505b2f89844f28b90f0c0cf858

secp256k1_verify(message_hash, signature, pubkey)

with

• message_hash: the pre-hash of the message. This ensure the input data is small enough to be used with secp256k1. Cosmos uses SHA256; Ethereum uses Keccak256. But the API does not need to care about the prehashing step, as it can happen in the contract.
• signature: A fixed length encoded secp256k1 signature (r, s) where both r and s are big endian encoded integers padded to 32 bytes each. Fixed length encoding is used in Cosmos SDK. Ethereum uses DER, which needs re-encoding (as implemented here).
• pubkey: a 65 bytes uncompressed pubkey. Cosmos SDK uses compressed pubkeys, Ethereum uses uncompressed pubkeys. We can have a helper to uncompress later on.

[joe-bowman]

As discussed with @ethanfrey, adding batch verify for ed25519 (supported by ed25519-zebra rust crate) would be super useful for the Cosmos IBC Wasm light-client support.

[ethanfrey]

Let's tackle that with ticket #755 First the single verification, then the batch verification (claim up to 20x speedup).

[webmaster128]

Thank you @joe-bowman. Batch verification of ed25519 signatures has its own ticket now, listed under serious considerations above: #781

[webmaster128]

This is done. We implemented seck256k1 and Ed25519. If we want to add more algorithms in the future, let's open specific tickets for those. Great jobs and thanks everyone ✌️