schnorr

package
v3.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 14, 2020 License: ISC Imports: 3 Imported by: 5

README

schnorr

Build Status ISC License GoDoc

Package schnorr provides custom Schnorr signing and verification via secp256k1.

This package provides data structures and functions necessary to produce and verify deterministic canonical Schnorr signatures using a custom scheme named EC-Schnorr-DCRv0 that is described herein. The signatures and implementation are optimized specifically for the secp256k1 curve. See https://www.secg.org/sec2-v2.pdf for details on the secp256k1 standard.

It also provides functions to parse and serialize the Schnorr signatures according to the specification described herein.

A comprehensive suite of tests is provided to ensure proper functionality.

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

$ go get -u github.com/decred/dcrd/dcrec/secp25k1/v3/schnorr

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.

Documentation

Overview

Package schnorr provides custom Schnorr signing and verification via secp256k1.

This package provides data structures and functions necessary to produce and verify deterministic canonical Schnorr signatures using a custom scheme named EC-Schnorr-DCRv0 that is described herein. The signatures and implementation are optimized specifically for the secp256k1 curve. See https://www.secg.org/sec2-v2.pdf for details on the secp256k1 standard.

It also provides functions to parse and serialize the Schnorr signatures according to the specification described herein.

A comprehensive suite of tests is provided to ensure proper functionality.

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 and some insight into the design decisions made are discussed further in the README.md file.

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

EC-Schnorr-DCRv0 Specification

See the README.md file for the specific details of the signing and verification algorithm as well as the signature serialization format.

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.

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.

Index

Examples

Constants

View Source 
const (
	PubKeyBytesLen = 33
)

These constants define the lengths of serialized public keys.

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

Variables

This section is empty.

Functions

func ParsePubKey 

func ParsePubKey(pubKeyStr []byte) (key *secp256k1.PublicKey, err error)

ParsePubKey parses a public key for a koblitz curve from a bytestring into a ecdsa.Publickey, verifying that it is valid. It supports compressed signature formats only.

Types

type Error 

type Error struct {
	ErrorCode   ErrorCode // Describes the kind of error
	Description string    // Human readable description of the issue
}

Error identifies a signature-related error. It has full support for errors.Is and errors.As, so the caller can ascertain the specific reason for the error by checking the underlying error code.

func (Error) Error 

func (e Error) Error() string

Error satisfies the error interface and prints human-readable errors.

func (Error) Is 

func (e Error) Is(target error) bool

Is implements the interface to work with the standard library's errors.Is.

It returns true in the following cases: - The target is an Error and the error codes match - The target is an ErrorCode and the error codes match

func (Error) Unwrap 

func (e Error) Unwrap() error

Unwrap returns the underlying wrapped error code.

type ErrorCode 

type ErrorCode int

ErrorCode identifies a kind of signature-related error. It has full support for errors.Is and errors.As, so the caller can directly check against an error code when determining the reason for an error. 

const (
	// ErrInvalidHashLen indicates that the input hash to sign or verify is not
	// the required length.
	ErrInvalidHashLen ErrorCode = iota

	// ErrPrivateKeyIsZero indicates an attempt was made to sign a message with
	// a private key that is equal to zero.
	ErrPrivateKeyIsZero

	// ErrSchnorrHashValue indicates that the hash of (R || m) was too large and
	// so a new nonce should be used.
	ErrSchnorrHashValue

	// ErrPubKeyNotOnCurve indicates that a point was not on the given elliptic
	// curve.
	ErrPubKeyNotOnCurve

	// ErrSigRYIsOdd indicates that the calculated Y value of R was odd.
	ErrSigRYIsOdd

	// ErrSigRNotOnCurve indicates that the calculated or given point R for some
	// signature was not on the curve.
	ErrSigRNotOnCurve

	// ErrUnequalRValues indicates that the calculated point R for some
	// signature was not the same as the given R value for the signature.
	ErrUnequalRValues

	// ErrSigTooShort is returned when a signature that should be a Schnorr
	// signature is too short.
	ErrSigTooShort

	// ErrSigTooLong is returned when a signature that should be a Schnorr
	// signature is too long.
	ErrSigTooLong

	// ErrSigRTooBig is returned when a signature has r with a value that is
	// greater than or equal to the prime of the field underlying the group.
	ErrSigRTooBig

	// ErrSigSTooBig is returned when a signature has s with a value that is
	// greater than or equal to the group order.
	ErrSigSTooBig
)

These constants are used to identify a specific RuleError.

func (ErrorCode) Error 

func (e ErrorCode) Error() string

Error implements the error interface.

func (ErrorCode) Is 

func (e ErrorCode) Is(target error) bool

Is implements the interface to work with the standard library's errors.Is.

It returns true in the following cases: - The target is an Error and the error codes match - The target is an ErrorCode and the error codes match

func (ErrorCode) String 

func (e ErrorCode) String() string

String returns the ErrorCode as a human-readable name.

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-DCRv0 specification 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 Sign 

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

Sign generates an EC-Schnorr-DCRv0 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.

Example

This example 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. 

// Decode a hex-encoded private key.
pkBytes, err := hex.DecodeString("22a47fa09a223f2aa079edf85a7c2d4f8720ee6" +
	"3e502ee2869afab7de234b80c")
if err != nil {
	fmt.Println(err)
	return
}
privKey := secp256k1.PrivKeyFromBytes(pkBytes)

// Sign a message using the private key.
message := "test message"
messageHash := chainhash.HashB([]byte(message))
signature, err := schnorr.Sign(privKey, messageHash)
if err != nil {
	fmt.Println(err)
	return
}

// Serialize and display the signature.
fmt.Printf("Serialized Signature: %x\n", signature.Serialize())

// Verify the signature for the message using the public key.
pubKey := privKey.PubKey()
verified := signature.Verify(messageHash, pubKey)
fmt.Printf("Signature Verified? %v\n", verified)

Output:

Serialized Signature: 970603d8ccd2475b1ff66cfb3ce7e622c5938348304c5a7bc2e6015fb98e3b457d4e912fcca6ca87c04390aa5e6e0e613bbbba7ffd6f15bc59f95bbd92ba50f0
Signature Verified? true

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) 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

func (*Signature) Verify 

func (sig *Signature) Verify(hash []byte, pubKey *secp256k1.PublicKey) bool

Verify returns whether or not the signature is valid for the provided hash and secp256k1 public key.

Example

This example 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. 

package main

import (
	"encoding/hex"
	"fmt"

	"github.com/decred/dcrd/chaincfg/chainhash"
	"github.com/decred/dcrd/dcrec/secp256k1/v3/schnorr"
)

func main() {
	// Decode hex-encoded serialized public key.
	pubKeyBytes, err := hex.DecodeString("02a673638cb9587cb68ea08dbef685c6f2d" +
		"2a751a8b3c6f2a7e9a4999e6e4bfaf5")
	if err != nil {
		fmt.Println(err)
		return
	}
	pubKey, err := schnorr.ParsePubKey(pubKeyBytes)
	if err != nil {
		fmt.Println(err)
		return
	}

	// Decode hex-encoded serialized signature.
	sigBytes, err := hex.DecodeString("970603d8ccd2475b1ff66cfb3ce7e622c59383" +
		"48304c5a7bc2e6015fb98e3b457d4e912fcca6ca87c04390aa5e6e0e613bbbba7ffd" +
		"6f15bc59f95bbd92ba50f0")
	if err != nil {
		fmt.Println(err)
		return
	}
	signature, err := schnorr.ParseSignature(sigBytes)
	if err != nil {
		fmt.Println(err)
		return
	}

	// Verify the signature for the message using the public key.
	message := "test message"
	messageHash := chainhash.HashB([]byte(message))
	verified := signature.Verify(messageHash, pubKey)
	fmt.Println("Signature Verified?", verified)

}

Output:

Signature Verified? true

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.