core/ecdsa implementation in runtime?

[michalkucharczyk]

This issue is related to work done in #2044. A goal of this ticket is to gather some opinions on the direction how ECDSA should be implemented in core/ecdsa for runtime usage.

Problem

Substrate core/ecdsa module is using secp256k1 crate. This crate is not pure rust, and depends on libsecp256k1 C library. It can be compiled to WASM, but unfortunately compilation to RISC target fails.

error details

``` running: "clang-15" "-O3" "-ffunction-sections" "-fdata-sections" "--target=riscv32ema-unknown-none-elf" "-I" "depend/secp256k1/" "-I" "depend/secp256k1/include" "-I" "depend/secp256k1/src" "-Wall" "-Wextra" "-DSECP256K1_API=" "-DENABLE_MODULE_ECDH=1" "-DENABLE_MODULE_SCHNORRSIG=1" "-DENABLE_MODULE_EXTRAKEYS=1" "-DENABLE_MODULE_ELLSWIFT=1" "-DECMULT_GEN_PREC_BITS=4" "-DECMULT_WINDOW_SIZE=15" "-DUSE_EXTERNAL_DEFAULT_CALLBACKS=1" "-DENABLE_MODULE_RECOVERY=1" "-o" "/builds/parity/mirrors/polkadot-sdk/target/debug/rbuild/minimal-runtime/target/riscv32ema-unknown-none-elf/release/build/secp256k1-sys-a2573b0b926fe764/out/depend/secp256k1/contrib/lax_der_parsing.o" "-c" "depend/secp256k1/contrib/lax_der_parsing.c" cargo:warning=error: unknown target triple 'riscv32ema-unknown-none-elf', please use -triple or -arch ```

Support for ecdsa is required in runtime in context of #1984. We want maximum flexibility while defining keys (e.g. beefy) in chain specs.

k256

There was also an idea to migrate from secp256k1 to rust-crypto-k256 which is pure-rust. Some work was already done:

• Switch to rust-secp256k1 from libsecp256k1 substrate#8089
• Replace libsecp256k1 with secp256k1 substrate#10798
• Replace libsecp256k1 with k256 in FRAME related code substrate#10883

Some benchmarking done by @davxy shows that performance is slightly worse:

• https://github.com/davxy/crypto-benches/tree/main/ecdsa

This probably would be acceptable as ECDSA is not on critical path.

Options

I see two reasonable directions:

• use ECDSA host functions in core/ecdsa module,
• migrate to k256 in core/ecdsa,

Any other ideas?

tagging: @davxy @koute @bkchr

[burdges]

We only required these changes so that key derivation works inside the runtime, which then permits some genesis block check, right?

We could build using the faster crate for native, and build using the slower rust crate for this key deriviation call in the runtime. We could even always do this one genesis key derivation using the slower crate.. or hotwire the genesis key derivation somehow.

We cannot use the slow wasm build for actual workloads anyways, but this holds for ed25519 and sr25519 too. We've hostcalls for the real verification workloads, but hostcalls could continue invoking the C libsecp256k1

As an aside, there are many "bad feelings" about secp256k1 implementations, but a priori I'd trust the ones by rust crypto and blockstream (probably the C libsecp256k1), but aovid switching back to the old parity one (not even discussed here).

[davxy]

my two options:

• conditional compilation of code in core/ecdsa (a bit ugly from a code design pow)
  • no-std → k256,
  • std → secp256k1
• or just switch to k256

My no-go options:

• Switching back to the old parity one IMO is not an option as it is the slower of the three .
• use ECDSA host functions in core/ecdsa module IMO is not an option as core/ecdsa is a lower level abstraction

I paste the benches here for reference:

Sign:

* secp256k1      time:   [27.813 µs 27.829 µs 27.846 µs]              <= the one with the C backend (the one we're using right now)
* k256           time:   [41.314 µs 41.320 µs 41.329 µs]              <=  from rust-crypto project
* libsecp256k1   time:   [95.844 µs 95.853 µs 95.864 µs]              <= the parity one

Verify:

* secp256k1      time: [31.669 µs 31.697 µs 31.747 µs]
* k256           time: [86.744 µs 86.786 µs 86.827 µs]
* libsecp256k1   time: [137.86 µs 137.93 µs 137.99 µs]

The gap between k256 and secp256k1 is not super bad (considering that not long ago we were using libsecp256k1)

Also depends on the usage of this stuff. Is ecdsa verification in a real hot path to justify a choice based on 50 µs diff?

[davxy]

At some point may be worth to see what magic secp256k1 is doing wrt k256.
If I understood correctly from the last discussion with @tarcieri k256 already implemented several optimizations, maybe at this point only exploiting some machine level instructions can lower the gap? @koute 😏

[koute]

If we only need this to be part of the runtime for genesis then using a pure-Rust slower one only for that would be an option, and that'd probably be the easiest.

I really would like to avoid having non-Rust dependencies for the runtime. We technically could support them (even on RISC-V!), but that'd be extra pain for everyone.

Another option would be to help optimize k256 like I did for dalek, which might or might not be easy (I haven't looked into it).

Also, one thing I'd like to note: the benchmarks that @davxy did were done on bare metal, right? In which case they might give us entirely different results when running inside of the runtime. I'll see if I can port them to my PolkaVM benchmark harness and see how they perform under WASM.

[burdges]

Yes #25 says "the normal production builds should not include the GenesisConfig anymore" so hopefully #1984 makes this code disapear entirely after the genesis WASM, meaning the key derivation stuff could've a feature gate for the rust crypto crate.

I do think @michalkucharczyk or someone should check how GenesisConfig really uses these crates.

Afaik.. We're doing some key derivation check required by our domain seperation for AccountIds, but exactly what and why remains unclear. It's nothing related to session keys since we never had secp256k1 session keys before BEEFY.

[davxy]

@koute yeah the benchmarks were run on bare metal.

• Beefy verification of signatures runs on native client.
• The only exception (for beefy) is verification of equivocation reports, which are run in wasm only when using Bls+Ecdsa. The plain ecdsa jumps into the host function. The equivocations check can't be considered a critical path.

Of course, nothing prevents users to call core/ecdsa directly (without passing through the HF), in this case wasm is what matters. But I was mostly referring to our use cases

[michalkucharczyk]

I do think @michalkucharczyk or someone should check how GenesisConfig really uses these crates.

Afaik.. We're doing some key derivation check required by our domain seperation for AccountIds, but exactly what and why remains unclear. It's nothing related to session keys since we never had secp256k1 session keys before BEEFY.

We only need support for account derivation. The runtime code may contain numerous instances of GenesisConfig containing different keys (typically testnets), possibly provided as URI. From GenesisConfig functionality perspective we don't need anything else. Some example of what is required on runtime side:

polkadot-sdk/polkadot/runtime/rococo/src/genesis_configs.rs

Lines 79 to 94 in 7c6bccb

	fn testnet_accounts() -> Vec<AccountId> {
	Vec::from([
	get_account_id_from_seed::<sr25519::Public>("Alice"),
	get_account_id_from_seed::<sr25519::Public>("Bob"),
	get_account_id_from_seed::<sr25519::Public>("Charlie"),
	get_account_id_from_seed::<sr25519::Public>("Dave"),
	get_account_id_from_seed::<sr25519::Public>("Eve"),
	get_account_id_from_seed::<sr25519::Public>("Ferdie"),
	get_account_id_from_seed::<sr25519::Public>("Alice//stash"),
	get_account_id_from_seed::<sr25519::Public>("Bob//stash"),
	get_account_id_from_seed::<sr25519::Public>("Charlie//stash"),
	get_account_id_from_seed::<sr25519::Public>("Dave//stash"),
	get_account_id_from_seed::<sr25519::Public>("Eve//stash"),
	get_account_id_from_seed::<sr25519::Public>("Ferdie//stash"),
	])
	}

later used in GenesisConfig:

polkadot-sdk/polkadot/runtime/rococo/src/genesis_configs.rs

Line 163 in 7c6bccb

let endowed_accounts: Vec<AccountId> = endowed_accounts.unwrap_or_else(testnet_accounts);

[michalkucharczyk]

conditional compilation of code in core/ecdsa (a bit ugly from a code design pow)

• no-std → k256,
• std → secp256k1

This would require some extra code maintenance burden, however acceptable if we don't want to give up on performance.

[burdges]

It's only doing sr25519 derivations? Would everything work if we made a stub for secp256k1 in which all calls just panic? Or some other conditional compilation on our side?

[michalkucharczyk]

It's only doing sr25519 derivations?

Nope. More kinds of keys can be generated:

polkadot-sdk/polkadot/runtime/rococo/src/genesis_configs.rs

Lines 48 to 77 in 7c6bccb

	pub fn get_authority_keys_from_seed(
	seed: &str,
	) -> (
	AccountId,
	AccountId,
	BabeId,
	GrandpaId,
	ValidatorId,
	AssignmentId,
	AuthorityDiscoveryId,
	BeefyId,
	) {
	let keys = get_authority_keys_from_seed_no_beefy(seed);
	(keys.0, keys.1, keys.2, keys.3, keys.4, keys.5, keys.6, get_from_seed::<BeefyId>(seed))
	}
	/// Helper function to generate stash, controller and session key from seed
	pub fn get_authority_keys_from_seed_no_beefy(
	seed: &str,
	) -> (AccountId, AccountId, BabeId, GrandpaId, ValidatorId, AssignmentId, AuthorityDiscoveryId) {
	(
	get_account_id_from_seed::<sr25519::Public>(&format!("{}//stash", seed)),
	get_account_id_from_seed::<sr25519::Public>(seed),
	get_from_seed::<BabeId>(seed),
	get_from_seed::<GrandpaId>(seed),
	get_from_seed::<ValidatorId>(seed),
	get_from_seed::<AssignmentId>(seed),
	get_from_seed::<AuthorityDiscoveryId>(seed),
	)
	}

[burdges]

As an aside.. It's problematic if someone does "secret // counter" for a session key. We want session keys to be created on the node or its HSM, and then certified by a controller that lives elsewhere. We'd ideally never have placed this derivation mess into the session key code paths, just computation of keys from entropy. Anyways..

[michalkucharczyk]

As an aside.. It's problematic if someone does "secret // counter" for a session key. We want session keys to be created on the node or its HSM, and then certified by a controller that lives elsewhere. We'd ideally never have placed this derivation mess into the session key code paths, just computation of keys from entropy. Anyways..

All this work done here and in #1984 is for testnets / dev chain specs (used in node --chain xyz command). Production is using raw format.

[tarcieri]

If I understood correctly from the last paritytech/substrate#8089 with @tarcieri k256 already implemented several optimizations, maybe at this point only exploiting some machine level instructions can lower the gap?

@davxy it depends what specifically you're interested in. For signing we've done all of the easy optimizations, but there is still a lot of opportunity for improving verification/public key speeds where we've encountered various small blockers, e.g. using wNAF, variable-time linear combinations

[michalkucharczyk]

If there are no other points, I am planning to start work on:

migrate to k256 in core/ecdsa

which either-way is a prerequisite for @davxy 1st option in #3448 (comment) (if we wanted to have it).

[burdges]

If you do a full migration, then it's good to have benchmarks. If they look bad then maybe we continue using the C one in the host.

All that said, ecdsa is only a lower tier scheme for us. It'll never support batch verification anyways, so it'll wind up being way slower eventually, and then we'll have to tell people to use schnorr.

[michalkucharczyk]

If you do a full migration, then it's good to have benchmarks. If they look bad then maybe we continue using the C one in the host.

@burdges do you mean some specific/existing benchmarks? I'd appreciate if you (or maybe @davxy) can share some more info on this.

[burdges]

We only care about signature verification time since we only create ecdsa signatures in beefy. It's likely only the EVM guys who care even about verification, so maybe we could ask them if this change impacts their peformance much?

[davxy]

Replacing secp256k1 with k256 should not have impact for the runtimes shipping with the pallets contained in this repo. We can't know if a third party runtime contains some code using core::ecdsa for some stuff.

Currently (if I've not missed something) only Beefy equivocations are using sp_core::ecdsa to verify signatures. And as I said, this is a scenario which definitely not in the "hot" execution path. Thus for this application is fine to switch to k256.

For what concerns bare metal, I think the results of my benchmarks are quite explicit.

Signing is ~1.5x slower

* k256          time:   [41.314 µs 41.320 µs 41.329 µs]
* secp256k1     time:   [27.813 µs 27.829 µs 27.846 µs]

Verifying is ~2.5x slower

* k256          time: [86.744 µs 86.786 µs 86.827 µs]
* secp256k1     time: [31.669 µs 31.697 µs 31.747 µs]

Said that, beefy for verifying the signature doesn't use the verify function I benchmarked, but uses :

polkadot-sdk/substrate/primitives/io/src/lib.rs

Lines 1180 to 1193 in b0741d4

	fn secp256k1_ecdsa_recover_compressed(
	sig: &[u8; 65],
	msg: &[u8; 32],
	) -> Result<[u8; 33], EcdsaVerifyError> {
	let rid = RecoveryId::from_i32(if sig[64] > 26 { sig[64] - 27 } else { sig[64] } as i32)
	.map_err(|_| EcdsaVerifyError::BadV)?;
	let sig = RecoverableSignature::from_compact(&sig[..64], rid)
	.map_err(|_| EcdsaVerifyError::BadRS)?;
	let msg = Message::from_digest_slice(msg).expect("Message is 32 bytes; qed");
	let pubkey = SECP256K1
	.recover_ecdsa(&msg, &sig)
	.map_err(|_| EcdsaVerifyError::BadSignature)?;
	Ok(pubkey.serialize())
	}

Called from here

Have you already replicated this recovery using k256? If yes, I can add it to my benchmarks

[michalkucharczyk]

Have you already replicated this recovery using k256? If yes, I can add it to my benchmarks

Yes:

polkadot-sdk/substrate/primitives/core/src/ecdsa.rs

Lines 337 to 342 in 35878b2

	pub fn recover_prehashed(&self, message: &[u8; 32]) -> Option<Public> {
	let rid = RecoveryId::from_byte(self.0[64])?;
	let sig = k256::ecdsa::Signature::from_bytes((&self.0[..64]).into()).ok()?;
	VerifyingKey::recover_from_prehash(message, &sig, rid).map(|p| p.into()).ok()
	}

note 1: the final pubkey.serialize() translates to p.to_sec1_bytes(),
note 2: 26/27 is not handled (as it is also not implemented in core::crypto::ecdsa).
note 3: IIUC it is already in your benchmarks: https://github.com/davxy/crypto-benches/blob/12c42902028df73aad1db979118b97cc6e9c5ba8/ecdsa/benches/k256.rs#L36-L47

[burdges]

Verifying is ~2.5x slower

We risk bricking EVM chains by such a large drop.

As observed elsewhere, we've collators who run on older host software, and they hate upgrading, so if we downgrade performance too much, then their collators would think the block runs in 1s or 2s, but it'll run notably slower in backing, and thus get dropped.

We filter this through weights of course, which maybe prevents the problem in practice, but we'd hit these risks if the EVM parachain makes its ecdsa weights wrong because their nodes use secp256k1.

It's likely safest & easiest if we use some feature here, so k256 in the runtime, and secp256k1 in the host. If that's irksome then you could still see how this fairs in the community testnet, or ask some EVM guys. It's also possible EVM spends way way more time doing keccak, and not much time doing ecdsa.

[michalkucharczyk]

It's likely safest & easiest if we use some feature here, so k256 in the runtime, and secp256k1 in the host.

I've added two features backend_k256 and backend_secp256k1. The latter one is by default used in std.

[burdges]

We do not use k256 for much here, and this derivation stuff is as standard as it gets in blockchain, so incompatability risks sound minimal.

[davxy]

Key recovery from signature is even slower(6x). Let's stick with secp256k1 for bare metal execution

* secp256k1       time: [32.765 µs 32.790 µs 32.816 µs]
* k256            time: [193.63 µs 193.83 µs 194.15 µs]

https://github.com/davxy/crypto-benches/blob/main/ecdsa/README.md#verify-pre-hashed-recoverable