Skip to content

Latest commit

 

History

History
265 lines (189 loc) · 34.8 KB

bip-0340.mediawiki

File metadata and controls

265 lines (189 loc) · 34.8 KB
Raw

  BIP: 340
  Title: Schnorr Signatures for secp256k1
  Author: Pieter Wuille <[email protected]>
          Jonas Nick <Jonas Nick <[email protected]>
          Tim Ruffing <[email protected]>
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0340
  Status: Draft
  Type: Standards Track
  License: BSD-2-Clause
  Created: 2020-01-19
  Post-History: 2018-07-06: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html [bitcoin-dev] Schnorr signatures BIP

Table of Contents

Introduction

Abstract

This document proposes a standard for 64-byte Schnorr signatures over the elliptic curve secp256k1.

Copyright

This document is licensed under the 2-clause BSD license.

Motivation

Bitcoin has traditionally used ECDSA signatures over the secp256k1 curve with SHA256 hashes for authenticating transactions. These are standardized, but have a number of downsides compared to Schnorr signatures over the same curve:

For all these advantages, there are virtually no disadvantages, apart from not being standardized. This document seeks to change that. As we propose a new standard, a number of improvements not specific to Schnorr signatures can be made:

  • Signature encoding: Instead of using DER-encoding for signatures (which are variable size, and up to 72 bytes), we can use a simple fixed 64-byte format.
  • Public key encoding: Instead of using compressed 33-byte encodings of elliptic curve points which are common in Bitcoin today, public keys in this proposal are encoded as 32 bytes.
  • Batch verification: The specific formulation of ECDSA signatures that is standardized cannot be verified more efficiently in batch compared to individually, unless additional witness data is added. Changing the signature scheme offers an opportunity to address this.
  • Completely specified: To be safe for usage in consensus systems, the verification algorithm must be completely specified at the byte level. This guarantees that nobody can construct a signature that is valid to some verifiers but not all. This is traditionally not a requirement for digital signature schemes, and the lack of exact specification for the DER parsing of ECDSA signatures has caused problems for Bitcoin in the past, needing BIP66 to address it. In this document we aim to meet this property by design. For batch verification, which is inherently non-deterministic as the verifier can choose their batches, this property implies that the outcome of verification may only differ from individual verifications with negligible probability, even to an attacker who intentionally tries to make batch- and non-batch verification differ.
By reusing the same curve and hash function as Bitcoin uses for ECDSA, we are able to retain existing mechanisms for choosing secret and public keys, and we avoid introducing new assumptions about the security of elliptic curves and hash functions.

Description

We first build up the algebraic formulation of the signature scheme by going through the design choices. Afterwards, we specify the exact encodings and operations.

Design

Schnorr signature variant Elliptic Curve Schnorr signatures for message m and public key P generally involve a point R, integers e and s picked by the signer, and the base point G which satisfy e = hash(R || m) and s⋅G = R + e⋅P. Two formulations exist, depending on whether the signer reveals e or R:

  1. Signatures are pairs (e, s) that satisfy e = hash(s⋅G - e⋅P || m). This variant avoids minor complexity introduced by the encoding of the point R in the signature (see paragraphs "Encoding R and public key point P" and "Implicit Y coordinates" further below in this subsection). Moreover, revealing e instead of R allows for potentially shorter signatures: Whereas an encoding of R inherently needs about 32 bytes, the hash e can be tuned to be shorter than 32 bytes, and a short hash of only 16 bytes suffices to provide SUF-CMA security at the target security level of 128 bits. However, a major drawback of this optimization is that finding collisions in a short hash function is easy. This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature (see Applications below). In these scenarios, which are not captured by the SUF-CMA model due its assumption of a single honest signer, a promising attack strategy for malicious co-signers is to find a collision in the hash function in order to obtain a valid signature on a message that an honest co-signer did not intend to sign.
  2. Signatures are pairs (R, s) that satisfy s⋅G = R + hash(R || m)⋅P. This supports batch verification, as there are no elliptic curve operations inside the hashes. Batch verification enables significant speedups.
This graph shows the ratio between the time it takes to verify <i>n</i> signatures individually and to verify a batch of <i>n</i> signatures. This ratio goes up logarithmically with the number of signatures, or in other words: the total time to verify <i>n</i> signatures grows with <i>O(n / log n)</i>.
This graph shows the ratio between the time it takes to verify n signatures individually and to verify a batch of n signatures. This ratio goes up logarithmically with the number of signatures, or in other words: the total time to verify n signatures grows with O(n / log n).

Since we would like to avoid the fragility that comes with short hashes, the e variant does not provide significant advantages. We choose the R-option, which supports batch verification.

Key prefixing Using the verification rule above directly makes Schnorr signatures vulnerable to "related-key attacks" in which a third party can convert a signature (R, s) for public key P into a signature (R, s + a⋅hash(R || m)) for public key P + a⋅G and the same message m, for any given additive tweak a to the signing key. This would render signatures insecure when keys are generated using BIP32's unhardened derivation and other methods that rely on additive tweaks to existing keys such as Taproot.

To protect against these attacks, we choose key prefixed[4] Schnorr signatures; changing the equation to s⋅G = R + hash(R || P || m)⋅P. It can be shown that key prefixing protects against related-key attacks with additive tweaks. In general, key prefixing increases robustness in multi-user settings, e.g., it seems to be a requirement for proving the MuSig multisignature scheme secure (see Applications below).

We note that key prefixing is not strictly necessary for transaction signatures as used in Bitcoin currently, because signed transactions indirectly commit to the public keys already, i.e., m contains a commitment to pk. However, this indirect commitment should not be relied upon because it may change with proposals such as SIGHASH_NOINPUT (BIP118), and would render the signature scheme unsuitable for other purposes than signing transactions, e.g., signing ordinary messages.

Encoding R and public key point P There exist several possibilities for encoding elliptic curve points:

  1. Encoding the full X and Y coordinates of P and R, resulting in a 64-byte public key and a 96-byte signature.
  2. Encoding the full X coordinate and one bit of the Y coordinate to determine one of the two possible Y coordinates. This would result in 33-byte public keys and 65-byte signatures.
  3. Encoding only the X coordinate, resulting in 32-byte public keys and 64-byte signatures.
Using the first option would be slightly more efficient for verification (around 10%), but we prioritize compactness, and therefore choose option 3.

Implicit Y coordinates In order to support efficient verification and batch verification, the Y coordinate of P and of R cannot be ambiguous (every valid X coordinate has two possible Y coordinates). We have a choice between several options for symmetry breaking:

  1. Implicitly choosing the Y coordinate that is in the lower half.
  2. Implicitly choosing the Y coordinate that is even[5].
  3. Implicitly choosing the Y coordinate that is a quadratic residue (has a square root modulo the field size, or "is a square" for short)[6].
In the case of R the third option is slower at signing time but a bit faster to verify, as it is possible to directly compute whether the Y coordinate is a square when the points are represented in Jacobian coordinates (a common optimization to avoid modular inverses for elliptic curve operations). The two other options require a possibly expensive conversion to affine coordinates first. This would even be the case if the sign or oddness were explicitly coded (option 2 in the list above). We therefore choose option 3.

For P the speed of signing and verification does not significantly differ between any of the three options because affine coordinates of the point have to be computed anyway. For consistency reasons we choose the same option as for R. The signing algorithm ensures that the signature is valid under the correct public key by negating the secret key if necessary.

Implicit Y coordinates are not a reduction in security when expressed as the number of elliptic curve operations an attacker is expected to perform to compute the secret key. An attacker can normalize any given public key to a point whose Y coordinate is a square by negating the point if necessary. This is just a subtraction of field elements and not an elliptic curve operation[7].

Tagged Hashes Cryptographic hash functions are used for multiple purposes in the specification below and in Bitcoin in general. To make sure hashes used in one context can't be reinterpreted in another one, hash functions can be tweaked with a context-dependent tag name, in such a way that collisions across contexts can be assumed to be infeasible. Such collisions obviously can not be ruled out completely, but only for schemes using tagging with a unique name. As for other schemes collisions are at least less likely with tagging than without.

For example, without tagged hashing a BIP340 signature could also be valid for a signature scheme where the only difference is that the arguments to the hash function are reordered. Worse, if the BIP340 nonce derivation function was copied or independently created, then the nonce could be accidentally reused in the other scheme leaking the secret key.

This proposal suggests to include the tag by prefixing the hashed data with SHA256(tag) || SHA256(tag). Because this is a 64-byte long context-specific constant and the SHA256 block size is also 64 bytes, optimized implementations are possible (identical to SHA256 itself, but with a modified initial state). Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization.

Final scheme As a result, our final scheme ends up using public key pk which is the X coordinate of a point P on the curve whose Y coordinate is a square and signatures (r,s) where r is the X coordinate of a point R whose Y coordinate is a square. The signature satisfies s⋅G = R + tagged_hash(r || pk || m)⋅P.

Specification

The following conventions are used, with constants as defined for secp256k1:

  • Lowercase variables represent integers or byte arrays.
    • The constant p refers to the field size, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F.
    • The constant n refers to the curve order, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141.
  • Uppercase variables refer to points on the curve with equation y2 = x3 + 7 over the integers modulo p.
    • is_infinite(P) returns whether or not P is the point at infinity.
    • x(P) and y(P) are integers in the range 0..p-1 and refer to the X and Y coordinates of a point P (assuming it is not infinity).
    • The constant G refers to the base point, for which x(G) = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 and y(G) = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8.
    • Addition of points refers to the usual elliptic curve group operation.
    • Multiplication (⋅) of an integer and a point refers to the repeated application of the group operation.
  • Functions and operations:
    • || refers to byte array concatenation.
    • The function x[i:j], where x is a byte array, returns a (j - i)-byte array with a copy of the i-th byte (inclusive) to the j-th byte (exclusive) of x.
    • The function bytes(x), where x is an integer, returns the 32-byte encoding of x, most significant byte first.
    • The function bytes(P), where P is a point, returns bytes(x(P)).
    • The function int(x), where x is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is x.
    • The function is_square(x), where x is an integer, returns whether or not x is a quadratic residue modulo p. Since p is prime, it is equivalent to the Legendre symbol (x / p) = x(p-1)/2 mod p being equal to 1[8].
    • The function has_square_y(P), where P is a point, is defined as not is_infinite(P) and is_square(y(P))[9].
    • The function lift_x(x), where x is an integer in range 0..p-1, returns the point P for which x(P) = x[10] and has_square_y(P)[11], or fails if no such point exists. The function lift_x(x) is equivalent to the following pseudocode:
      • Let c = x3 + 7 mod p.
      • Let y = c(p+1)/4 mod p.
      • Fail if c ≠ y2 mod p.
      • Return the unique point P such that x(P) = x and y(P) = y, or fail if no such point exists.
    • The function point(x), where x is a 32-byte array, returns the point P = lift_x(int(x)).
    • The function hashtag(x) where tag is a UTF-8 encoded tag name and x is a byte array returns the 32-byte hash SHA256(SHA256(tag) || SHA256(tag) || x).

Public Key Generation

Input:

  • The secret key sk: a 32-byte array, generated uniformly at random
The algorithm PubKey(sk) is defined as:
  • Let d = int(sk).
  • Fail if d = 0 or d ≥ n.
  • Return bytes(d⋅G).
Note that we use a very different public key format (32 bytes) than the ones used by existing systems (which typically use elliptic curve points as public keys, or 33-byte or 65-byte encodings of them). A side effect is that PubKey(sk) = PubKey(bytes(n - int(sk)), so every public key has two corresponding secret keys.

As an alternative to generating keys randomly, it is also possible and safe to repurpose existing key generation algorithms for ECDSA in a compatible way. The secret keys constructed by such an algorithm can be used as sk directly. The public keys constructed by such an algorithm (assuming they use the 33-byte compressed encoding) need to be converted by dropping the first byte. Specifically, BIP32 and schemes built on top of it remain usable.

Default Signing

Input:

  • The secret key sk: a 32-byte array
  • The message m: a 32-byte array
The algorithm Sign(sk, m) is defined as:
  • Let d' = int(sk)
  • Fail if d' = 0 or d' ≥ n
  • Let P = d'⋅G
  • Let d = d' if has_square_y(P), otherwise let d = n - d' .
  • Let rand = hashBIPSchnorrDerive(bytes(d) || m).
  • Let k' = int(rand) mod n[12].
  • Fail if k' = 0.
  • Let R = k'⋅G.
  • Let k = k' if has_square_y(R), otherwise let k = n - k' .
  • Let e = int(hashBIPSchnorr(bytes(R) || bytes(P) || m)) mod n.
  • Return the signature bytes(R) || bytes((k + ed) mod n).

Alternative Signing

It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section is deterministic, i.e., it will always produce the same signature for a given message and secret key. This method does not need a random number generator (RNG) at signing time and is thus trivially robust against failures of RNGs. Alternatively the 32-byte rand value may be generated in other ways, producing a different but still valid signature (in other words, this is not a unique signature scheme). No matter which method is used to generate the rand value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.

Synthetic nonces For instance when a RNG is available, 32 bytes of RNG output can be appended to the input to hashBIPSchnorrDerive. This will change the corresponding line in the signing algorithm to rand = hashBIPSchnorrDerive(bytes(d) || m || get_32_bytes_from_rng()), where get_32_bytes_from_rng() is the call to the RNG. It is safe to add the output of a low-entropy RNG. Adding high-entropy RNG output may improve protection against fault injection attacks and side-channel attacks. Therefore, synthetic nonces are recommended in settings where these attacks are a concern - in particular on offline signing devices.

Verifying the signing output To prevent random or attacker provoked computation errors, the signature can be verified with the verification algorithm defined below before leaving the signer. This prevents publishing invalid signatures which may leak information about the secret key. If the additional computational cost is not a concern, it is recommended to verify newly created signatures and reject them in case of failure.

Nonce exfiltration protection It is possible to strengthen the nonce generation algorithm using a second device. In this case, the second device contributes randomness which the actual signer provably incorporates into its nonce. This prevents certain attacks where the signer device is compromised and intentionally tries to leak the secret key through its nonce selection.

Multisignatures This signature scheme is compatible with various types of multisignature and threshold schemes such as MuSig, where a single public key requires holders of multiple secret keys to participate in signing (see Applications below). It is important to note that multisignature signing schemes in general are insecure with the rand generation from the default signing algorithm above (or any other deterministic method).

Verification

Input:

  • The public key pk: a 32-byte array
  • The message m: a 32-byte array
  • A signature sig: a 64-byte array
The algorithm Verify(pk, m, sig) is defined as:
  • Let P = point(pk); fail if point(pk) fails.
  • Let r = int(sig[0:32]); fail if r ≥ p.
  • Let s = int(sig[32:64]); fail if s ≥ n.
  • Let e = int(hashBIPSchnorr(bytes(r) || bytes(P) || m)) mod n.
  • Let R = s⋅G - e⋅P.
  • Fail if not has_square_y(R) or x(R) ≠ r.
  • Return success iff no failure occurred before reaching this point.
For every valid secret key sk and message m, Verify(PubKey(sk),m,Sign(sk,m)) will succeed.

Note that the correctness of verification relies on the fact that point(pk) always returns a point with a square Y coordinate. A hypothetical verification algorithm that treats points as public keys, and takes the point P directly as input would fail any time a point with non-square Y is used. While it is possible to correct for this by negating points with non-square Y coordinate before further processing, this would result in a scheme where every (message, signature) pair is valid for two public keys (a type of malleability that exists for ECDSA as well, but we don't wish to retain). We avoid these problems by treating just the X coordinate as public key.

Batch Verification

Input:

  • The number u of signatures
  • The public keys pk1..u: u 32-byte arrays
  • The messages m1..u: u 32-byte arrays
  • The signatures sig1..u: u 64-byte arrays
The algorithm BatchVerify(pk1..u, m1..u, sig1..u) is defined as:
  • Generate u-1 random integers a2...u in the range 1...n-1. They are generated deterministically using a CSPRNG seeded by a cryptographic hash of all inputs of the algorithm, i.e. seed = seed_hash(pk1..pku || m1..mu || sig1..sigu ). A safe choice is to instantiate seed_hash with SHA256 and use ChaCha20 with key seed as a CSPRNG to generate 256-bit integers, skipping integers not in the range 1...n-1.
  • For i = 1 .. u:
    • Let Pi = point(pki); fail if point(pki) fails.
    • Let ri = int(sigi[0:32]); fail if ri ≥ p.
    • Let si = int(sigi[32:64]); fail if si ≥ n.
    • Let ei = int(hashBIPSchnorr(bytes(ri) || bytes(Pi) || mi)) mod n.
    • Let Ri = lift_x(ri); fail if lift_x(ri) fails.
  • Fail if (s1 + a2s2 + ... + ausu)⋅G ≠ R1 + a2⋅R2 + ... + au⋅Ru + e1⋅P1 + (a2e2)⋅P2 + ... + (aueu)⋅Pu.
  • Return success iff no failure occurred before reaching this point.
If all individual signatures are valid (i.e., Verify would return success for them), BatchVerify will always return success. If at least one signature is invalid, BatchVerify will return success with at most a negligible probability.

Optimizations

Many techniques are known for optimizing elliptic curve implementations. Several of them apply here, but are out of scope for this document. Two are listed below however, as they are relevant to the design decisions:

Squareness testing The function is_square(x) is defined as above, but can be computed more efficiently using an extended GCD algorithm.

Jacobian coordinates Elliptic Curve operations can be implemented more efficiently by using Jacobian coordinates. Elliptic Curve operations implemented this way avoid many intermediate modular inverses (which are computationally expensive), and the scheme proposed in this document is in fact designed to not need any inversions at all for verification. When operating on a point P with Jacobian coordinates (x,y,z) which is not the point at infinity and for which x(P) is defined as x / z2 and y(P) is defined as y / z3:

  • has_square_y(P) can be implemented as is_square(yz mod p).
  • x(P) ≠ r can be implemented as (0 ≤ r < p) and (x ≠ z2r mod p).

Applications

There are several interesting applications beyond simple signatures. While recent academic papers claim that they are also possible with ECDSA, consensus support for Schnorr signature verification would significantly simplify the constructions.

Multisignatures and Threshold Signatures

By means of an interactive scheme such as MuSig, participants can aggregate their public keys into a single public key which they can jointly sign for. This allows n-of-n multisignatures which, from a verifier's perspective, are no different from ordinary signatures, giving improved privacy and efficiency versus CHECKMULTISIG or other means.

Moreover, Schnorr signatures are compatible with distributed key generation, which enables interactive threshold signatures schemes, e.g., the schemes described by Stinson and Strobl (2001) or Genaro, Jarecki and Krawczyk (2003). These protocols make it possible to realize k-of-n threshold signatures, which ensure that any subset of size k of the set of n signers can sign but no subset of size less than k can produce a valid Schnorr signature. However, the practicality of the existing schemes is limited: most schemes in the literature have been proven secure only for the case k-1 < n/2, are not secure when used concurrently in multiple sessions, or require a reliable broadcast mechanism to be secure. Further research is necessary to improve this situation.

Adaptor Signatures

Adaptor signatures can be produced by a signer by offsetting his public nonce with a known point T = t⋅G, but not offsetting his secret nonce. A correct signature (or partial signature, as individual signers' contributions to a multisignature are called) on the same message with same nonce will then be equal to the adaptor signature offset by t, meaning that learning t is equivalent to learning a correct signature. This can be used to enable atomic swaps or even general payment channels in which the atomicity of disjoint transactions is ensured using the signatures themselves, rather than Bitcoin script support. The resulting transactions will appear to verifiers to be no different from ordinary single-signer transactions, except perhaps for the inclusion of locktime refund logic.

Adaptor signatures, beyond the efficiency and privacy benefits of encoding script semantics into constant-sized signatures, have additional benefits over traditional hash-based payment channels. Specifically, the secret values t may be reblinded between hops, allowing long chains of transactions to be made atomic while even the participants cannot identify which transactions are part of the chain. Also, because the secret values are chosen at signing time, rather than key generation time, existing outputs may be repurposed for different applications without recourse to the blockchain, even multiple times.

Blind Signatures

A blind signature protocol is an interactive protocol that enables a signer to sign a message at the behest of another party without learning any information about the signed message or the signature. Schnorr signatures admit a very simple blind signature scheme which is however insecure because it's vulnerable to Wagner's attack. A known mitigation is to let the signer abort a signing session with a certain probability, and the resulting scheme can be proven secure under non-standard cryptographic assumptions.

Blind Schnorr signatures could for example be used in Partially Blind Atomic Swaps, a construction to enable transferring of coins, mediated by an untrusted escrow agent, without connecting the transactors in the public blockchain transaction graph.

Test Vectors and Reference Code

For development and testing purposes, we provide a collection of test vectors in CSV format and a naive, highly inefficient, and non-constant time pure Python 3.7 reference implementation of the signing and verification algorithm. The reference implementation is for demonstration purposes only and not to be used in production environments.

Footnotes

  1. ^ Informally, this means that without knowledge of the secret key but given valid signatures of arbitrary messages, it is not possible to come up with further valid signatures.
  2. ^ A detailed security proof in the random oracle model, which essentially restates the original security proof by Pointcheval and Stern more explicitly, can be found in a paper by Kiltz, Masny and Pan. All these security proofs assume a variant of Schnorr signatures that use (e,s) instead of (R,s) (see Design above). Since we use a unique encoding of R, there is an efficiently computable bijection that maps (R,s) to (e,s), which allows to convert a successful SUF-CMA attacker for the (e,s) variant to a successful SUF-CMA attacker for the (R,s) variant (and vice-versa). Furthermore, the proofs consider a variant of Schnorr signatures without key prefixing (see Design above), but it can be verified that the proofs are also correct for the variant with key prefixing. As a result, all the aforementioned security proofs apply to the variant of Schnorr signatures proposed in this document.
  3. ^ If (r,s) is a valid ECDSA signature for a given message and key, then (r,n-s) is also valid for the same message and key. If ECDSA is restricted to only permit one of the two variants (as Bitcoin does through a policy rule on the network), it can be proven non-malleable under stronger than usual assumptions.
  4. ^ A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification.
  5. ^ Since p is odd, negation modulo p will map even numbers to odd numbers and the other way around. This means that for a valid X coordinate, one of the corresponding Y coordinates will be even, and the other will be odd.
  6. ^ A product of two numbers is a square when either both or none of the factors are squares. As -1 is not a square modulo secp256k1's field size p, and the two Y coordinates corresponding to a given X coordinate are each other's negation, this means exactly one of the two must be a square.
  7. ^ This can be formalized by a simple reduction that reduces an attack on Schnorr signatures with implicit Y coordinates to an attack to Schnorr signatures with explicit Y coordinates. The reduction works by reencoding public keys and negating the result of the hash function, which is modeled as random oracle, whenever the challenge public key has an explicit Y coordinate that is not a square. A proof sketch can be found here.
  8. ^ For points P on the secp256k1 curve it holds that y(P)(p-1)/2 ≠ 0 mod p.
  9. ^ For points P on the secp256k1 curve it holds that has_square_y(P) = not has_square_y(-P).
  10. ^ Given a candidate X coordinate x in the range 0..p-1, there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then x is not a valid X coordinate either, i.e., no point P exists for which x(P) = x. The valid Y coordinates for a given candidate x are the square roots of c = x3 + 7 mod p and they can be computed as y = ±c(p+1)/4 mod p (see Quadratic residue) if they exist, which can be checked by squaring and comparing with c.
  11. ^ If P := lift_x(x) does not fail, then y := y(P) = c(p+1)/4 mod p is square. Proof: If lift_x does not fail, y is a square root of c and therefore the Legendre symbol (c / p) is c(p-1)/2 = 1 mod p. Because the Legendre symbol (y / p) is y(p-1)/2 mod p = c((p+1)/4)((p-1)/2) mod p = 1((p+1)/4) mod p = 1 mod p, y is square.
  12. ^ Note that in general, taking a uniformly random 256-bit integer modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to 2256 that this bias is not observable (1 - n / 2256 is around 1.27 * 2-128).

Acknowledgements

This document is the result of many discussions around Schnorr based signatures over the years, and had input from Johnson Lau, Greg Maxwell, Andrew Poelstra, Rusty Russell, and Anthony Towns. The authors further wish to thank all those who provided valuable feedback and reviews, including the participants of the structured reviews.