schnorr

README

schnorr

Package schnorr provides Schnorr signing and verification via secp256k1.

This design is not yet final.

This package and signature scheme is derived from the EC-Schnorr-DCRv0 scheme defined for decred.

It has been modified for Dogecoin in the following ways:

• We use X-coordinate public keys, encoded as 32 bytes, as descibed in BIP 340.
• During signing, we negate the private key scalar if the public key point derived from that private key has an odd Y coodrinate (equivalently we use the formula s = k + d*e rather than s = k - d*e in this case.) This means signatures are generated "as if" the public key had an even Y coordinate, which allows the signature verification to succeed with x-only public keys. Public keys are always treated as having an even Y coordinate when decoded to a point on the curve.
• Our scheme includes key-prefixing as defined in BIP 340: the public key is prefixed to the message in the challenge hash input. This changes the signature equation to s⋅G = R + hash(r || q || m)⋅Q. This protects against related-key attacks, since we make extensive use of key derivation (specfically BIP 32, unhardened in some cases.)
• Our scheme uses tagged hashing (as described in BIP 340) except that hashing is performed using tagged BLAKE-256 hash. Tagging protects against key disclosure through using the same signature scheme and nonce-derivation; we have changed the RFC6979 extra data for the same reason.
  • e = BLAKE-256(tag || tag || r || q || m)
  • the tag is 0xe4b2451d3706cb8b7df0305ff35f2da49afedec3d8080b4d5d6ed492e6e38eff
  • this is equal to BLAKE-256([]byte("Dogecoin/challenge"))
• In the signing algorithm step 3, use the following RFC6979 extra data to identify the scheme: 0xc13f0efc5ec0e84d8d7ccfbc789ae233122bdb3c7bf0fa062fb2aa7fe90a6f98
  • this is equal to BLAKE-256([]byte("EC-Schnorr-Dogecoin"))

The original description of EC-Schnorr-DCRv0 follows.

Overview

A Schnorr signature is a digital signature scheme that is known for its simplicity, provable security and efficient generation of short signatures.

It provides many advantages over ECDSA signatures that make them ideal for use with the only real downside being that they are not well standardized at the time of this writing.

Some of the advantages over ECDSA include:

• They are linear which makes them easier to aggregate and use in protocols that build on them such as multi-party signatures, threshold signatures, adaptor signatures, and blind signatures
• They are provably secure with weaker assumptions than the best known security proofs for ECDSA
  • Specifically Schnorr signatures are provably secure under SUF-CMA (Strong Existential Unforgeability under Chosen Message Attack) in the ROM (Random Oracle Model) which guarantees that as long as the hash function behaves ideally, the only way to break Schnorr signatures is by solving the ECDLP (Elliptic Curve Discrete Logarithm Problem).
• Their relatively straightforward and efficient aggregation properties make them excellent for scalability and allow them to provide some nice privacy characteristics
• They support faster batch verification unlike the standardized version of ECDSA signatures

Custom Schnorr-based Signature Scheme

As mentioned in the overview, the primary downside of Schnorr signatures for elliptic curves is that they are not standardized as well as ECDSA signatures which means there are a number of variations that are not compatible with each other.

In addition, many of the standardization attempts have various disadvantages that make them unsuitable for use in Decred. Some of these details will be discussed further in the Design section along with providing some insight into the design decisions made.

Consequently, this package implements a custom Schnorr-based signature scheme named EC-Schnorr-DCRv0 suitable for use in Decred.

The following provides a high-level overview of the key design features of the scheme:

• Uses signatures of the form (R, s)
• Produces 64-byte signatures by only encoding the x coordinate of R
• Enforces even y coordinates for R to support efficient verification by disambiguating the two possible y coordinates
• Canonically encodes by both components of the signature with 32-bytes each
• Uses BLAKE-256 with 14 rounds for the hash function to calculate challenge e
• Uses RFC6979 to obviate the need for an entropy source at signing time
• Produces deterministic signatures for a given message and private key pair

Design Details And Rationale

As previously mentioned, unfortunately, Schnorr signatures for elliptic curves are not standardized as well as ECDSA signatures which means there are a number of variations that are not compatible with each other. For example, different schemes can be found in ISO/IEC 14888-3:2016 (EC-SDSA, EC-SDSA-opt, and EC-FSDSA), BSI TR-03111, Versions 2.0 (EC-Schnorr-v2.0) and 2.10 (EC-Schnorr-v2.10), and published by Clause Schnorr himself in Efficient Signature Generation by Smart Cards in the Journal of Cryptology, Vol.4, pp.161-174, 1991 (Sc91). There are other variants not covered here as well.

Further, each of these schemes have various disadvantages that are discussed more in the following sections which make them unsuitable for use with Decred. Consequently, Decred makes use of a custom scheme named EC-Schnorr-DCRv0.

That said, the various schemes are all fairly simple variations which involve using an agreed upon elliptic curve with generator G, and hash function hash where the signer, with public key Q and signing message m, picks a unique random point R and two integers s and e such that the following equations hold:

• e = hash(R || m)
• s*G = R + e*Q

The signature itself then consists of two components with two major variants that depend on which of e or R the signer wishes to reveal and further minor variants which depend on the data that is hashed as well as the sign used in the calculation of s, which in a sense, can be thought of as the sign applied to the public key.

For reference, the following is a high-level breakdown of some of the key differences between the aforementioned schemes, where d is the signers private key and k is the secret nonce used to generate the random point R = k*G (note that R.x and R.y indicate the x and y coordinates of the point R, respectively):

Scheme	Pubkey	Challenge (e)	1st part	2nd part (mod N)
Sc91	-d*G	hash(R ∥ m)	e	k + d*e
EC-SDSA	-d*G	hash(R.x ∥ R.y ∥ m)	e	k + d*e
EC-SDSA-opt	-d*G	hash(R.x ∥ m)	e	k + d*e
EC-FSDSA	d*G	hash(R.x ∥ R.y ∥ m)	R.x ∥ R.y	k - d*e
EC-Schnorr-v2.0	d*G	hash(m ∥ R.x)	e	k - d*e
EC-Schnorr-v2.10	-d*G	hash(R.x ∥ R.y ∥ m)	e	k + d*e
EC-Schnorr-DCRv0	d*G	hash(R.x ∥ m)	R.x	k - d*e

Notice the main differences are:

• The signature pair is either (e, s) or (R, s)
• The y coordinate of R is either explicit or implicit leaving it up to the verifier to calculate from the x coordinate
• The exact serialization of the data used to create the challenge e varies, but they all commit to the random point R and the message m
• The calculation of s either uses addition or subtraction meaning the verifier must use the opposite operation which essentially changes the sign of the public key in the addition case

Revealing e vs R

The first main difference is whether or not e or R is revealed, meaning the signature is either the pair (e, s) or the pair (R, s), respectively.

In the case e is revealed, the verifier must calculate R = s*G - e*Q and thus implies the pair must satisfy e = hash(s*G - e*Q || m). On the other hand, when R is revealed, the verifier must calculate s*G = R + hash(R || m)*Q.

This is an important distinction because, while the first approach of revealing e does have the theoretical potential for smaller signatures, since it is the result of a hash function as opposed to encoding R, it also has a couple of important disadvantages that the second approach does not:

• It makes the implementation of secure joint multi-party and threshold signatures more difficult
• It does not support fast batch verification due to the fact the necessary elliptic curve operations are performed inside the hash function which prevents the ability to take advantage of their homomorphic properties

Further, when the size of the field elements for the elliptic curve is the same size as the hash function, as is the case in Decred, techniques which are discussed in the next section can be used to make (R, s) signatures the same size as (e, s) signatures.

Therefore, the second approach of (R, s) signatures is chosen.

Explicit Versus Implicit y Coordinate for R

The second main difference is whether or not the full R point is explicitly or implicitly specified. Explicitly specifying it refers to committing directly to and/or revealing both the x and y coordinates of the point while the implicit option only makes use of the x coordinate.

Using the implicit option provides for smaller signatures of the (R, s) form since it means the R component requires less bytes to encode.

However, even though all that is required for single signature validations in some implicit schemes is the x coordinate of R, in order to support batch validation the verifiers must know the full point, which includes the y coordinate.

Since there are two possible y coordinates corresponding to the x coordinate, in cases where the full point R must be known to verifiers, some additional semantics are required to correctly identify which one is the correct one.

While there are various methods, the choice made for EC-Schnorr-DCRv0 is to enforce the y coordinate to be even which can be efficiently accomplished at signing time by negating the nonce in the case it is odd and it does not involve adding an additional byte in the signature to specify the oddness. This is possible because all valid points on the secp256k1 curve always have corresponding y coordinates where one is even and the other is odd due to them being the negation of each other modulo the underlying field prime, which an odd number.

Challenge (e) Calculation

The third main difference is the specific format of the data that is used to create the challenge via the hash function. Some variants include both the x and y coordinates of the point R while others only include the x coordinate. See the previous section about explicit versus implicit y coordinates since this choice also ties into that. Also, one of the variants reverses the order of the concatenation of the message m and the point R.

Combining these details with the following additional information specific to Decred results in the choice of e = BLAKE-256(R.x || m) for the challenge with additional restrictions on R to ensure verifiers can reconstruct the full point:

• The order of the committed information for the challenge is not important and the more common formulation consists of R followed by m
• Compact signatures are more desirable since they end up in the public ledger
• The BLAKE-256 hash function with 14 rounds is already in widespread use and satisfies all requirements needed for the hash function

Sign For s Calculation

The final main difference is whether or not s is calculated as s = k - d*e or s = k + d*e. The verification equation naturally changes depending on which variant is used: R = s*G + e*Q for the first and R = s*G - e*Q for the second. For this reason, it is perhaps easier to think of it terms of the the signature scheme choosing whether or not to flip the sign on the public key Q depending on which s calculation is used.

The only option among the covered standardization attempts that returns signatures pairs in the (R, s) form uses the s = k - d*e variant, so that variant is chosen for EC-Schnorr-DCRv0 as well.

Future Design Considerations

It is worth noting that there are some additional optimizations and modifications that have been identified since the introduction of EC-Schnorr-DCRv0 that can be made to further harden security for multi-party and threshold signature use cases as well provide the opportunity for faster signature verification with a sufficiently optimized implementation.

However, the v0 scheme is used in the existing consensus rules and any changes to the signature scheme would invalidate existing uses. Therefore changes in this regard will need to come in the form of a v1 signature scheme and be accompanied by the necessary consensus updates.

EC-Schnorr-DCRv0 Specification

EC-Schnorr-DCRv0 Signing Algorithm

The algorithm for producing an EC-Schnorr-DCRv0 signature is as follows:

G = curve generator n = curve order d = private key m = message r, s = signature

1. Fail if m is not 32 bytes
2. Fail if d = 0 or d >= n
3. Use RFC6979 to generate a deterministic nonce k in [1, n-1] parameterized by the private key, message being signed, extra data that identifies the scheme (0x0b75f97b60e8a5762876c004829ee9b926fa6f0d2eeaec3a4fd1446a768331cb), and an iteration count
4. R = kG
5. Negate nonce k if R.y is odd (R.y is the y coordinate of the point R)
6. r = R.x (R.x is the x coordinate of the point R)
7. e = BLAKE-256(r || m) (Ensure r is padded to 32 bytes)
8. Repeat from step 3 (with iteration + 1) if e >= n
9. s = k - e*d mod n
10. Return (r, s)

EC-Schnorr-DCRv0 Verification Algorithm

The algorithm for verifying an EC-Schnorr-DCRv0 signature is as follows:

G = curve generator n = curve order p = field size Q = public key m = message r, s = signature

1. Fail if m is not 32 bytes
2. Fail if Q is not a point on the curve
3. Fail if r >= p
4. Fail if s >= n
5. e = BLAKE-256(r || m) (Ensure r is padded to 32 bytes)
6. Fail if e >= n
7. R = sG + eQ
8. Fail if R is the point at infinity
9. Fail if R.y is odd
10. Verified if R.x == r

EC-Schnorr-DCRv0 Signature Serialization Format

The serialization format consists of the two components of the signature, R.x (the x coordinate of the point R) and s, each serialized as a padded big-endian uint256 (32-bytes with the most significant byte first) and concatenated together to form a 64-byte signature.

See the file signature_test.go for test vectors.

Schnorr use in Decred

At the time of this writing, Schnorr signatures are not yet in widespread use on the Decred network, largely due to the current lack of support in wallets and infrastructure for secure multi-party and threshold signatures.

However, the consensus rules and scripting engine supports the necessary primitives and given many of the beneficial properties of Schnorr signatures, a good goal is to work towards providing the additional infrastructure to increase their usage.

Acknowledgements

The EC-Schnorr-DCRv0 scheme is partly based on work that was ongoing in the Bitcoin community at the time it was implemented along with the following standardization attempts:

• EC-SDSA, EC-SDSA-opt, and EC-FSDSA specified in ISO/IEC 14888-3:2016
• EC-Schnorr-v2.0 and EC-Schnorr-v2.10 specified in BSI TR-03111, Versions 2.0 and v2.10, respectively
• Sc91 specified in Efficient Signature Generation by Smart Cards in the Journal of Cryptology, Vol.4, pp.161-174, 1991

Installation and Updating

This package is part of the github.com/decred/dcrd/dcrec/secp256k1/v4 module. Use the standard go tooling for working with modules to incorporate it.

Examples

• Sign Message
  Demonstrates signing a message with the EC-Schnorr-DCRv0 scheme using a secp256k1 private key that is first parsed from raw bytes and serializing the generated signature.

• Verify Signature
  Demonstrates verifying an EC-Schnorr-DCRv0 signature against a public key that is first parsed from raw bytes. The signature is also parsed from raw bytes.

License

Package schnorr is licensed under the copyfree ISC License, which can be found in the LICENSE file in this directory.

Documentation

Index

• Constants
• Variables
• type SchnorrImpl
  • func New() SchnorrImpl
  • func (sgn SchnorrImpl) Sign(privKey *secp256k1.PrivateKey, hash []byte) (*Signature, error)
  • func (sgn SchnorrImpl) Verify(sig *Signature, hash []byte, pubKey []byte) bool
• type Signature
  • func NewSignature(r *secp256k1.FieldVal, s *secp256k1.ModNScalar) *Signature
  • func ParseSignature(sig []byte) (*Signature, error)
  • func (sig Signature) IsEqual(otherSig *Signature) bool
  • func (sig *Signature) R() secp256k1.FieldVal
  • func (sig *Signature) S() secp256k1.ModNScalar
  • func (sig Signature) Serialize() []byte

Constants

const (

	// PubKeySize is the size of an encoded Schnorr public key.
	PubKeySize = 32
)

const (
	// SignatureSize is the size of an encoded Schnorr signature.
	SignatureSize = 64
)

Variables

var ErrInvalidHashLen = errors.New("invalid message hash length (want 32 bytes)")

var ErrInvalidPubKey = errors.New("invalid public key")

var ErrPrivateKeyIsZero = errors.New("invalid private key (is zero)")

var ErrPubKeyNotOnCurve = errors.New("pubkey point is not on curve")

var ErrSchnorrHashValue = errors.New("hash of (r || P || m) >= curve order")

var ErrSchnorrNonceValue = errors.New("generated nonce is zero")

var ErrSigInvalidR = errors.New("invalid signature: r >= field prime")

var ErrSigInvalidS = errors.New("invalid signature: s >= curve order")

var ErrSigRAtInifnity = errors.New("calculated R point is the point at infinity")

var ErrSigRYIsOdd = errors.New("calculated R y-value is odd")

var ErrSigSize = errors.New("invalid signature: wrong length")

var ErrUnequalRValues = errors.New("calculated R point was not given R")

Types

type SchnorrImpl

type SchnorrImpl struct {
	ChallengeHasher  *blake256.Hasher256
	RFC6979ExtraData []byte
	PubKeyInHash     bool
}

func New

func New() SchnorrImpl

New creates a Schnorr Signature implementation with Dogecoin tagged-hashing and RFC6979ExtraData. This allows tests to use different parameters.

func (SchnorrImpl) Sign

func (sgn SchnorrImpl) Sign(privKey *secp256k1.PrivateKey, hash []byte) (*Signature, error)

Sign generates an EC-Schnorr-Dogecoin signature over the secp256k1 curve for the provided hash (which should be the result of hashing a larger message) using the given private key. The produced signature is deterministic (same message and same key yield the same signature) and canonical.

Note that the current signing implementation has a few remaining variable time aspects which make use of the private key and the generated nonce, which can expose the signer to constant time attacks. As a result, this function should not be used in situations where there is the possibility of someone having EM field/cache/etc access.

func (SchnorrImpl) Verify

func (sgn SchnorrImpl) Verify(sig *Signature, hash []byte, pubKey []byte) bool

Verify returns whether or not the signature is valid for the provided hash and public key. The public key is always 32 bytes, encoding an X coordinate only, which corresponds (always) to an even Y coordinate.

type Signature

type Signature struct {
	// contains filtered or unexported fields
}

Signature is a type representing a Schnorr signature.

func NewSignature

func NewSignature(r *secp256k1.FieldVal, s *secp256k1.ModNScalar) *Signature

NewSignature instantiates a new signature given some r and s values.

func ParseSignature

func ParseSignature(sig []byte) (*Signature, error)

ParseSignature parses a signature according to the EC-Schnorr-Dogecoin specification in constant time and enforces the following additional restrictions specific to secp256k1:

- The r component must be in the valid range for secp256k1 field elements - The s component must be in the valid range for secp256k1 scalars

func (Signature) IsEqual

func (sig Signature) IsEqual(otherSig *Signature) bool

IsEqual compares this Signature instance to the one passed, returning true if both Signatures are equivalent. A signature is equivalent to another, if they both have the same scalar value for R and S.

func (*Signature) R

func (sig *Signature) R() secp256k1.FieldVal

R returns the r value of the signature.

func (*Signature) S

func (sig *Signature) S() secp256k1.ModNScalar

S returns the s value of the signature.

func (Signature) Serialize

func (sig Signature) Serialize() []byte

Serialize returns the Schnorr signature in the more strict format.

The signatures are encoded as:

sig[0:32]  x coordinate of the point R, encoded as a big-endian uint256
sig[32:64] s, encoded also as big-endian uint256