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.
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:
build on them such as multi-party signatures, threshold signatures, adaptor signatures, and blind signatures
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).
them excellent for scalability and allow them to provide some nice privacy characteristics
ECDSA signatures
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:
(R, s)x coordinate of Ry coordinates for R to support efficient verification by disambiguating the two possible y coordinates
eAs 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*QThe 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:
(e, s) or (R, s)y coordinate of R is either explicit or implicit leaving it up to the verifier to calculate from the x coordinate
e varies, but they all commit to the random point R and the message m
s either uses addition or subtraction meaning theverifier must use the opposite operation which essentially changes the sign of the public key in the addition case
e vs RThe 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:
signatures more difficult
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.
y Coordinate for RThe 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.
e) CalculationThe 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 more common formulation consists of R followed by m
satisfies all requirements needed for the hash function
s CalculationThe 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.
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.
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
the private key, message being signed, extra data that identifies the scheme
(0x0b75f97b60e8a5762876c004829ee9b926fa6f0d2eeaec3a4fd1446a768331cb), and
an iteration count
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
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.
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.
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:2016EC-Schnorr-v2.0 and EC-Schnorr-v2.10 specified in BSI TR-03111, Versions 2.0and v2.10, respectively
Sc91 specified in Efficient Signature Generation by Smart Cards in theJournal of Cryptology, Vol.4, pp.161-174, 1991
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.
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.
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 schnorr is licensed under the copyfree ISC License.