Add Support for BIP-340 Schnorr

[GeekArthur]

Bitcoin's BIP-340 Schnorr signature scheme is a secp256k1 curve variant not directly supported by Rosetta.

The primary outward distinction between the Ecdsa/Secp256k1 scheme and BIP-340 is the use of x-only 32-byte publicKeys and 64-byte ([R,s]) signatures.

BIP-340's underlying Sign/Verify scheme also internally encodes the signing keyPairs' signature and public point as its variants whose 'Y' coordinates are a quadratic residue ('even'). (see more here: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#design)

Benefits

BIP-340 provides greater (provable) security than ECDSA/secp256k1-based schemes and offers signature non-malleability and linearity. Signing also makes use of "tagged hashes" to mitigate things like related-key attacks, which accordingly "...increases robustness in multi-user settings."

While this proposal to introduce BIP-340 does not include multisignature support, this would be a likely precondition to doing so. (e.g., #50)

Solution

Add the following to rosetta-specifications:

• ./models/CurveType.yaml - Secp256k1Bip340
• ./models/SignatureType.yaml - SchnorrBip340

Once approved and released, implement the following in rosetta-sdk-go including any relevant tests:

• ./keys/keys.go - Key Import & Generation
• ./keys/signer_bip340.go - Sign & Verify

It should be mentioned that the new CurveType is necessary due to BIP-340's requirement of 32-byte/x-only keys while the existing rosetta-sdk-go key interface extends no such ability under the existing Secp256k1 curve.

CurveType

rosetta-specifications

# CurveType.yaml

description: |
  CurveType is the type of cryptographic curve associated with a PublicKey.
  * secp256k1: SEC compressed - `33 bytes` (https://secg.org/sec1-v2.pdf#subsubsection.2.3.3)
+ * secp256k1_bip340: x-only - `32 bytes`  (implicitly even `Y` coord. Secp256k1 compressed keys may be repurposed by dropping the first byte. (https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#Public_Key_Generation))
  * secp256r1: SEC compressed - `33 bytes` (https://secg.org/sec1-v2.pdf#subsubsection.2.3.3)
  * edwards25519: `y (255-bits) || x-sign-bit (1-bit)` - `32 bytes` (https://ed25519.cr.yp.to/ed25519-20110926.pdf)
  * tweedle: 1st pk : Fq.t (32 bytes) || 2nd pk : Fq.t (32 bytes) (https://github.com/CodaProtocol/coda/blob/develop/rfcs/0038-rosetta-construction-api.md#marshal-keys)
  * pallas: `x (255 bits) || y-parity-bit (1-bit) - 32 bytes` (https://github.com/zcash/pasta)
type: string
enum:
  - secp256k1
+ - secp256k1_bip340
  - secp256r1
  - edwards25519
  - tweedle
  - pallas

rosetta-sdk-go Key Import

• Accept the import of any standard secp256k1 privateKey and drop the first byte (compression odd/even flag) of its associated publicKey per BIP-340 spec to extend backward compatibility.
  • This results in a 32-byte publicKey vs. secp256k1's 33-byte compressed publicKey.
  • No further tweaks need to be performed to an imported keyPair as the Sign/Verify scheme implicitly chooses the 'Y' coordinates that are a quadratic residue.

The above would be implemented in rosetta-sdk-go in the file ./keys/keys.go and add the import of the following package:

• "github.com/btcsuite/btcd/btcec/v2"

*note that github.com/btcsuite/btcd packages are already used by rosetta-sdk-go.

rosetta-sdk-go Key Generation

• Explicitly choose the keyPair whose public key has a Y value that is a quadratic residue by negating the newly-generated privateKey when its associated public key is found to be 'odd' in its compressed form.

The above would be implemented in rosetta-sdk-go in the file ./keys/keys.go and add the import of the following package:

• "github.com/btcsuite/btcd/btcec/v2"

*note that github.com/btcsuite/btcd packages are already used by rosetta-sdk-go.

References

• BIP-340 Design: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#design
• BIP-340 PublicKey Generation: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#public-key-generation
• BIP-340 PublicKey Conversion: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#public-key-conversion

SignatureType

rosetta-specifications

# SignatureType.yaml

description: |
  SignatureType is the type of a cryptographic signature.
  * ecdsa: `r (32-bytes) || s (32-bytes)` - `64 bytes`
  * ecdsa_recovery: `r (32-bytes) || s (32-bytes) || v (1-byte)` - `65 bytes`
  * ed25519: `R (32-byte) || s (32-bytes)` - `64 bytes`
  * schnorr_1: `r (32-bytes) || s (32-bytes)` - `64 bytes`  (schnorr signature implemented by Zilliqa where both `r` and `s` are scalars encoded as `32-bytes` values, most significant byte first.)
+ * schnorr_bip340: `r (32-bytes) || s (32-bytes)` - `64 bytes`  (sig = (bytes(R) || bytes((k + ed) mod n) where `r` is the `X` coordinate of a point `R` whose `Y` coordinate is even, most significant bytes first.)
  * schnorr_poseidon: `r (32-bytes) || s (32-bytes)` where s = Hash(1st pk || 2nd pk || r) - `64 bytes`  (schnorr signature w/ Poseidon hash function implemented by O(1) Labs where both `r` and `s` are scalars encoded as `32-bytes` values, least significant byte first. https://github.com/CodaProtocol/signer-reference/blob/master/schnorr.ml )
type: string
enum:
  - ecdsa
  - ecdsa_recovery
  - ed25519
  - schnorr_1
+ - schnorr_bip340
  - schnorr_poseidon

rosetta-sdk-go Sign & Verify

• Sign: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#default-signing
• Verify https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#verification

The above would be implemented in rosetta-sdk-go as the file ./keys/signer_bip340.go and make use of the following import packages:

• "github.com/btcsuite/btcd/btcec/v2"
• "github.com/btcsuite/btcd/btcec/v2/schnorr"

*note that github.com/btcsuite/btcd packages are already used by rosetta-sdk-go.

Backwards Compatible

Key Imports: Yes
Everything Else: n/a

[GeekArthur]

Generally speaking, I think the proposal makes sense to me as the new curve and sign algorithm will increase the scalability of Rosetta from transaction signing perspective so that more future assets will be integrated with Rosetta easily. Given only new curve and sign algorithm is added, there should be no or very few breaking changes. One small comment related to implementation is that we should also update the corresponding asserter (e.g. https://github.com/coinbase/rosetta-sdk-go/blob/a48f742c1d904ad2e022585affa2eee63e437908/asserter/construction.go#L250)

@shrimalmadhur Please review this proposal as well

[sleepdefic1t]

Thank you, @GeekArthur

Indeed, this is a network-agnostic implementation of BIP-340 to spec, so other projects and features (e.g., Taproot) would be able to make use of this addition.

This proposal also only adds new functionality and does not remove anything. As such, there should be no breaking changes as you have already mentioned.

As for the /asserter/construction.go file...
Yes, that file would be updated as well. In our working implementation of rosetta-sdk-go, CurveType appears as the following after using the built-in formatters:

func CurveType(
	curve types.CurveType,
) error {
	switch curve {
	case types.Secp256k1,
		types.Secp256k1Bip340,
		types.Secp256r1,
		types.Edwards25519,
		types.Tweedle,
		types.Pallas:
		return nil
	default:
		return ErrCurveTypeNotSupported
	}
}

Any other files would be updated/generated using rosetta-specifications (i.e., ./types/curve_type.go and ./types/signature_type.go).

[shrimalmadhur]

Thanks @GeekArthur for creating this discussion and @sleepdefic1t for proposing this. I think this would be a good addition from the open source spec per se so I am supportive of this addition.

@GeekArthur from Coinbase perspective if any chain wants to use it, we have to make sure our internal key management systems supports this curve type. So as an open source spec we can add it, but there will be more work required if any chain with this curve wants to integrate with Coinbase.

[sleepdefic1t]

Thank you, @shrimalmadhur
I appreciate your response.

I'm not familiar with your key management; but if it matters, the BIP-340 signature scheme is fully compatible with any valid secp256k1 keyPair.

The only distinction — as previously noted — is that a BIP-340 publicKey drops the compression byte. Odd and even keys remain fully compatible because Sign/Verify implicitly chooses the "even" variant internally.

For example, in our working implementation, ImportPrivateKey for BIP-340 and Secp256k1 are nearly identical except that the former slices the 1st byte (Bytes: rawPubKey.SerializeCompressed()[1:],).

Upon key generation, the privateKey is scalar negated where rawPubKey.SerializeCompressed()[0] == 0x03 before also slicing the 1st byte of the pubKey.

So while I'm certain there's much more to it, two primary requirements may be that your key management supports secp256k1 and allows publicKeys to be 32 bytes.

I hope this brings further clarification, and thank you again for your response.

[shrimalmadhur]

@sleepdefic1t thanks for explanation. This has nothing to do with your proposal, we just have to make sure we implement this curve type (sign & verify) in our systems properly. As you said, we will have to make some changes in our systems if we want to support in our internal systems. Spec and SDK changes proposed can be done irrespective of that.

[sleepdefic1t]

No problem at all, and understood.
Just aiming to be thorough for community and internal reference.

Thanks again, @shrimalmadhur 🙏

[GeekArthur]

@sleepdefic1t Proposal is approved, you can work on the corresponding specs and sdk changes, thanks for proposing this!

[sleepdefic1t]

:excellent:

Thank you, @GeekArthur 🙏

I'll have the spec PR up shortly.
Presumably, I should wait for that to be pulled into rosetta-sdk-go before proceeding with the SDK PR?

[GeekArthur]

Yup, that's correct order

[sleepdefic1t]

Perfect. Thanks again for you help, @GeekArthur

Spec PR is up 🎉

• Add Support for BIP-340 Schnorr #114