1schnorr
2=======
3
4[](https://github.com/decred/dcrd/actions)
5[](http://copyfree.org)
6[](https://pkg.go.dev/github.com/decred/dcrd/dcrec/secp256k1/v4/schnorr)
7
8Package schnorr provides custom Schnorr signing and verification via secp256k1.
9
10This package provides data structures and functions necessary to produce and
11verify deterministic canonical Schnorr signatures using a custom scheme named
12`EC-Schnorr-DCRv0` that is described herein. The signatures and implementation
13are optimized specifically for the secp256k1 curve. See
14https://www.secg.org/sec2-v2.pdf for details on the secp256k1 standard.
15
16It also provides functions to parse and serialize the Schnorr signatures
17according to the specification described herein.
18
19A comprehensive suite of tests is provided to ensure proper functionality.
20
21## Overview
22
23A Schnorr signature is a digital signature scheme that is known for its
24simplicity, provable security and efficient generation of short signatures.
25
26It provides many advantages over ECDSA signatures that make them ideal for use
27with the only real downside being that they are not well standardized at the
28time of this writing.
29
30Some of the advantages over ECDSA include:
31
32* They are linear which makes them easier to aggregate and use in protocols that
33 build on them such as multi-party signatures, threshold signatures, adaptor
34 signatures, and blind signatures
35* They are provably secure with weaker assumptions than the best known security
36 proofs for ECDSA
37 * Specifically Schnorr signatures are provably secure under SUF-CMA (Strong
38 Existential Unforgeability under Chosen Message Attack) in the ROM (Random
39 Oracle Model) which guarantees that as long as the hash function behaves
40 ideally, the only way to break Schnorr signatures is by solving the ECDLP
41 (Elliptic Curve Discrete Logarithm Problem).
42* Their relatively straightforward and efficient aggregation properties make
43 them excellent for scalability and allow them to provide some nice privacy
44 characteristics
45* They support faster batch verification unlike the standardized version of
46 ECDSA signatures
47
48## Custom Schnorr-based Signature Scheme
49
50As mentioned in the overview, the primary downside of Schnorr signatures for
51elliptic curves is that they are not standardized as well as ECDSA signatures
52which means there are a number of variations that are not compatible with each
53other.
54
55In addition, many of the standardization attempts have various disadvantages
56that make them unsuitable for use in Decred. Some of these details will be
57discussed further in the Design section along with providing some insight into
58the design decisions made.
59
60Consequently, this package implements a custom Schnorr-based signature scheme
61named `EC-Schnorr-DCRv0` suitable for use in Decred.
62
63The following provides a high-level overview of the key design features of the
64scheme:
65
66* Uses signatures of the form `(R, s)`
67* Produces 64-byte signatures by only encoding the `x` coordinate of `R`
68* Enforces even `y` coordinates for `R` to support efficient verification by
69 disambiguating the two possible `y` coordinates
70* Canonically encodes by both components of the signature with 32-bytes each
71* Uses BLAKE-256 with 14 rounds for the hash function to calculate challenge `e`
72* Uses RFC6979 to obviate the need for an entropy source at signing time
73* Produces deterministic signatures for a given message and private key pair
74
75## Design Details And Rationale
76
77As previously mentioned, unfortunately, Schnorr signatures for elliptic curves
78are not standardized as well as ECDSA signatures which means there are a number
79of variations that are not compatible with each other. For example, different
80schemes can be found in ISO/IEC 14888-3:2016 (`EC-SDSA`, `EC-SDSA-opt`, and
81`EC-FSDSA`), BSI TR-03111, Versions 2.0 (`EC-Schnorr-v2.0`) and 2.10
82(`EC-Schnorr-v2.10`), and published by Clause Schnorr himself in Efficient
83Signature Generation by Smart Cards in the Journal of Cryptology, Vol.4,
84pp.161-174, 1991 (`Sc91`). There are other variants not covered here as well.
85
86Further, each of these schemes have various disadvantages that are discussed
87more in the following sections which make them unsuitable for use with Decred.
88Consequently, Decred makes use of a custom scheme named `EC-Schnorr-DCRv0`.
89
90That said, the various schemes are all fairly simple variations which involve
91using an agreed upon elliptic curve with generator `G`, and hash function `hash`
92where the signer, with public key `Q` and signing message `m`, picks a _unique_
93random point `R` and two integers `s` and `e` such that the following equations
94hold:
95
96* `e = hash(R || m)`
97* `s*G = R + e*Q`
98
99The signature itself then consists of two components with two major variants
100that depend on which of `e` or `R` the signer wishes to reveal and further minor
101variants which depend on the data that is hashed as well as the sign used in the
102calculation of `s`, which in a sense, can be thought of as the sign applied to
103the public key.
104
105For reference, the following is a high-level breakdown of some of the key
106differences between the aforementioned schemes, where `d` is the signers
107private key and `k` is the secret nonce used to generate the random point
108`R = k*G` (note that `R.x` and `R.y` indicate the x and y coordinates of the
109point `R`, respectively):
110
111| Scheme | Pubkey | Challenge (e) | 1st part | 2nd part (mod N) |
112|------------------|--------|---------------------|-----------|------------------|
113| Sc91 | -d*G | hash(R ∥ m) | e | k + d*e |
114| EC-SDSA | -d*G | hash(R.x ∥ R.y ∥ m) | e | k + d*e |
115| EC-SDSA-opt | -d*G | hash(R.x ∥ m) | e | k + d*e |
116| EC-FSDSA | d*G | hash(R.x ∥ R.y ∥ m) | R.x ∥ R.y | k - d*e |
117| EC-Schnorr-v2.0 | d*G | hash(m ∥ R.x) | e | k - d*e |
118| EC-Schnorr-v2.10 | -d*G | hash(R.x ∥ R.y ∥ m) | e | k + d*e |
119| EC-Schnorr-DCRv0 | d*G | hash(R.x ∥ m) | R.x | k - d*e |
120
121Notice the main differences are:
122
123* The signature pair is either `(e, s)` or `(R, s)`
124* The `y` coordinate of `R` is either explicit or implicit leaving it up to the
125 verifier to calculate from the `x` coordinate
126* The exact serialization of the data used to create the challenge `e` varies, but
127 they all commit to the random point `R` and the message `m`
128* The calculation of `s` either uses addition or subtraction meaning the
129 verifier must use the opposite operation which essentially changes the sign of
130 the public key in the addition case
131
132### Revealing `e` vs `R`
133
134The first main difference is whether or not `e` or `R` is revealed, meaning the
135signature is either the pair `(e, s)` or the pair `(R, s)`, respectively.
136
137In the case `e` is revealed, the verifier must calculate `R = s*G - e*Q` and
138thus implies the pair must satisfy `e = hash(s*G - e*Q || m)`. On the other
139hand, when `R` is revealed, the verifier must calculate
140`s*G = R + hash(R || m)*Q`.
141
142This is an important distinction because, while the first approach of revealing
143`e` does have the theoretical potential for smaller signatures, since it is the
144result of a hash function as opposed to encoding `R`, it also has a couple of
145important disadvantages that the second approach does not:
146
147* It makes the implementation of secure joint multi-party and threshold
148 signatures more difficult
149* It does not support fast batch verification due to the fact the necessary
150 elliptic curve operations are performed inside the hash function which
151 prevents the ability to take advantage of their homomorphic properties
152
153Further, when the size of the field elements for the elliptic curve is the same
154size as the hash function, as is the case in Decred, techniques which are
155discussed in the next section can be used to make `(R, s)` signatures the same
156size as `(e, s)` signatures.
157
158Therefore, the second approach of `(R, s)` signatures is chosen.
159
160### Explicit Versus Implicit `y` Coordinate for `R`
161
162The second main difference is whether or not the full `R` point is explicitly or
163implicitly specified. Explicitly specifying it refers to committing directly to
164and/or revealing both the `x` and `y` coordinates of the point while the
165implicit option only makes use of the `x` coordinate.
166
167Using the implicit option provides for smaller signatures of the `(R, s)` form
168since it means the `R` component requires less bytes to encode.
169
170However, even though all that is required for single signature validations in
171some implicit schemes is the `x` coordinate of `R`, in order to support batch
172validation the verifiers must know the full point, which includes the `y`
173coordinate.
174
175Since there are two possible `y` coordinates corresponding to the `x`
176coordinate, in cases where the full point `R` must be known to verifiers, some
177additional semantics are required to correctly identify which one is the correct
178one.
179
180While there are various methods, the choice made for `EC-Schnorr-DCRv0` is to
181enforce the `y` coordinate to be even which can be efficiently accomplished at
182signing time by negating the nonce in the case it is odd and it does not involve
183adding an additional byte in the signature to specify the oddness. This is
184possible because all valid points on the secp256k1 curve always have
185corresponding `y` coordinates where one is even and the other is odd due to them
186being the negation of each other modulo the underlying field prime, which an odd
187number.
188
189### Challenge (`e`) Calculation
190
191The third main difference is the specific format of the data that is used to
192create the challenge via the hash function. Some variants include both the `x`
193and `y` coordinates of the point `R` while others only include the `x`
194coordinate. See the previous section about explicit versus implicit `y`
195coordinates since this choice also ties into that. Also, one of the variants
196reverses the order of the concatenation of the message `m` and the point `R`.
197
198Combining these details with the following additional information specific to
199Decred results in the choice of `e = BLAKE-256(R.x || m)` for the challenge with
200additional restrictions on `R` to ensure verifiers can reconstruct the full
201point:
202
203* The order of the committed information for the challenge is not important and
204 the more common formulation consists of `R` followed by `m`
205* Compact signatures are more desirable since they end up in the public ledger
206* The BLAKE-256 hash function with 14 rounds is already in widespread use and
207 satisfies all requirements needed for the hash function
208
209### Sign For `s` Calculation
210
211The final main difference is whether or not `s` is calculated as `s = k - d*e`
212or `s = k + d*e`. The verification equation naturally changes depending on
213which variant is used: `R = s*G + e*Q` for the first and `R = s*G - e*Q` for
214the second. For this reason, it is perhaps easier to think of it terms of the
215the signature scheme choosing whether or not to flip the sign on the public key
216`Q` depending on which `s` calculation is used.
217
218The only option among the covered standardization attempts that returns
219signatures pairs in the `(R, s)` form uses the `s = k - d*e` variant, so that
220variant is chosen for `EC-Schnorr-DCRv0` as well.
221
222## Future Design Considerations
223
224It is worth noting that there are some additional optimizations and
225modifications that have been identified since the introduction of
226`EC-Schnorr-DCRv0` that can be made to further harden security for multi-party
227and threshold signature use cases as well provide the opportunity for faster
228signature verification with a sufficiently optimized implementation.
229
230However, the v0 scheme is used in the existing consensus rules and any changes
231to the signature scheme would invalidate existing uses. Therefore changes in
232this regard will need to come in the form of a v1 signature scheme and be
233accompanied by the necessary consensus updates.
234
235## EC-Schnorr-DCRv0 Specification
236
237### EC-Schnorr-DCRv0 Signing Algorithm
238
239The algorithm for producing an EC-Schnorr-DCRv0 signature is as follows:
240
241G = curve generator
242n = curve order
243d = private key
244m = message
245r, s = signature
246
2471. Fail if m is not 32 bytes
2482. Fail if d = 0 or d >= n
2493. Use RFC6979 to generate a deterministic nonce k in [1, n-1] parameterized by
250 the private key, message being signed, extra data that identifies the scheme
251 (`0x0b75f97b60e8a5762876c004829ee9b926fa6f0d2eeaec3a4fd1446a768331cb`), and
252 an iteration count
2534. R = kG
2545. Negate nonce k if R.y is odd (R.y is the y coordinate of the point R)
2556. r = R.x (R.x is the x coordinate of the point R)
2567. e = BLAKE-256(r || m) (Ensure r is padded to 32 bytes)
2578. Repeat from step 3 (with iteration + 1) if e >= n
2589. s = k - e*d mod n
25910. Return (r, s)
260
261### EC-Schnorr-DCRv0 Verification Algorithm
262
263The algorithm for verifying an EC-Schnorr-DCRv0 signature is as follows:
264
265G = curve generator
266n = curve order
267p = field size
268Q = public key
269m = message
270r, s = signature
271
2721. Fail if m is not 32 bytes
2732. Fail if Q is not a point on the curve
2743. Fail if r >= p
2754. Fail if s >= n
2765. e = BLAKE-256(r || m) (Ensure r is padded to 32 bytes)
2776. Fail if e >= n
2787. R = s*G + e*Q
2798. Fail if R is the point at infinity
2809. Fail if R.y is odd
28110. Verified if R.x == r
282
283### EC-Schnorr-DCRv0 Signature Serialization Format
284
285The serialization format consists of the two components of the signature, `R.x`
286(the `x` coordinate of the point `R`) and `s`, each serialized as a padded
287big-endian uint256 (32-bytes with the most significant byte first) and
288concatenated together to form a 64-byte signature.
289
290See the file `signature_test.go` for test vectors.
291
292## Schnorr use in Decred
293
294At the time of this writing, Schnorr signatures are not yet in widespread use on
295the Decred network, largely due to the current lack of support in wallets and
296infrastructure for secure multi-party and threshold signatures.
297
298However, the consensus rules and scripting engine supports the necessary
299primitives and given many of the beneficial properties of Schnorr signatures, a
300good goal is to work towards providing the additional infrastructure to increase
301their usage.
302
303## Acknowledgements
304
305The EC-Schnorr-DCRv0 scheme is partly based on work that was ongoing in the
306Bitcoin community at the time it was implemented along with the following
307standardization attempts:
308
309* `EC-SDSA`, `EC-SDSA-opt`, and `EC-FSDSA` specified in ISO/IEC 14888-3:2016
310* `EC-Schnorr-v2.0` and `EC-Schnorr-v2.10` specified in BSI TR-03111, Versions 2.0
311 and v2.10, respectively
312* `Sc91` specified in Efficient Signature Generation by Smart Cards in the
313 Journal of Cryptology, Vol.4, pp.161-174, 1991
314
315## Installation and Updating
316
317This package is part of the `github.com/decred/dcrd/dcrec/secp256k1/v4` module.
318Use the standard go tooling for working with modules to incorporate it.
319
320## Examples
321
322* [Sign Message](https://pkg.go.dev/github.com/decred/dcrd/dcrec/secp256k1/v4/schnorr#example-package-SignMessage)
323 Demonstrates signing a message with the EC-Schnorr-DCRv0 scheme using a
324 secp256k1 private key that is first parsed from raw bytes and serializing the
325 generated signature.
326
327* [Verify Signature](https://pkg.go.dev/github.com/decred/dcrd/dcrec/secp256k1/v4/schnorr#example-Signature.Verify)
328 Demonstrates verifying an EC-Schnorr-DCRv0 signature against a public key that
329 is first parsed from raw bytes. The signature is also parsed from raw bytes.
330
331## License
332
333Package schnorr is licensed under the [copyfree](http://copyfree.org) ISC
334License.
View as plain text