Deterministic ECDSA Signatures

# Abstract

This document specifies an ECDSA signing algorithm whose output is fully determined by the secret key and the message being signed. Its signatures are at most 70 bytes when DER encoded, rather than 72 for an arbitrary valid ECDSA signature.

# Motivation

Under current consensus rules, a valid ECDSA signature of any message under any key has two degrees of freedom: the signer's free choice of nonce fixes r¹, and two possible values of s follow from a specific r. A malicious signer can exploit that freedom to generate signatures that leak key material², but a standardized, deterministic signing algorithm removes that freedom. Signers expected to comply with such an algorithm cannot leak key material without risking detection: a key holder can load the same secret key into two independent signers, sign the same message on both, and compare the results, as any difference reveals that at least one signer is not following this specification.

The standardization of the deterministic algorithm is what enables leak detection, as a nonstandard algorithm has no other implementations to cross-check against.

# Definitions

• The value (n - 1) / 2 is the half curve order, where n is the order of the secp256k1 curve.
• A given signature (r, s) is considered low-r when r < 2²⁵⁵, and is otherwise considered high-r.
• A given signature (r, s) is considered low-s when s is less than or equal to the half curve order, and is otherwise considered high-s.
• Low-r grinding is the process of regenerating a signature with a new nonce until it is a low-r signature.
• Low-s normalization is the process of replacing a signature (r, s) with the equivalent signature (r, n - s) if (r, s) is high-s.³

# Specification

# Notation

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

• Lowercase variables represent integers, byte arrays, or signatures:

  • The constant p refers to the field size, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F.
  • The constant n refers to the curve order, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141.
  • The constant half_order refers to the half curve order, (n - 1) / 2.
  • The constant empty_bytestring refers to the byte array of length zero.
  • An ECDSA signature sig can be represented literally by an integer pair (r, s), with 0 < r, s < n.

• Points on the curve with equation y² = x³ + 7 over the integers modulo p:

  • The point at infinity is the identity element of the curve group, and is the only point without X and Y coordinates.
  • The function 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 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 bytes(l, x), where x is an integer, returns the l-byte encoding of x, most significant byte first.
  • The function bytes_le(l, x), where x is an integer, returns the l-byte encoding of x, least significant byte first.
  • The function fill_bytes(l, x), where x is a byte, returns the length l byte array in which every byte is x.
  • The function hmac(k, m), where k and m are byte arrays, returns HMAC-SHA256⁴ with key k over message m.
  • x^-1 refers to the modular multiplicative inverse of the integer x modulo n.

# Algorithms

This section specifies the following algorithms:

• nonce_rfc6979(sk, msghash, extra, count) derives a nonce deterministically.
• sign(sk, msghash, extra) produces an ECDSA signature under a given additional data input.
• verify(sig, P, msghash) checks an ECDSA signature.
• DeterministicSign(sk, msghash) grinds sign until r is low and normalizes s.

Nonce Derivation

Input:

• The secret key sk: a 32-byte array
• The message hash msghash: a 32-byte array
• The additional data extra: a byte array, possibly empty
• The attempt counter count: an integer, count >= 0

The algorithm nonce_rfc6979(sk, msghash, extra, count) is defined as:⁵

• Let h = bytes(32, int(msghash) mod n)⁶
• Let V = fill_bytes(32, 0x01)
• Let K = fill_bytes(32, 0x00)
• Let K = hmac(K, V || 0x00 || sk || h || extra)
• Let V = hmac(K, V)
• Let K = hmac(K, V || 0x01 || sk || h || extra)
• Let V = hmac(K, V)
• Let V = hmac(K, V)
• For j = 1, ..., count:
  • Let K = hmac(K, V || 0x00)
  • Let V = hmac(K, V)
  • Let V = hmac(K, V)
• Return V

ECDSA Signing

Input:

• The secret key sk: a 32-byte array
• The message hash msghash: a 32-byte array
• The additional data extra: a byte array, possibly empty

The algorithm sign(sk, msghash, extra) is defined as:

• Let d = int(sk)
• Fail if d = 0 or d >= n
• For count = 0, 1, ..., 2³² - 1:⁷
  • Let nonce = nonce_rfc6979(sk, msghash, extra, count)
  • Let k = int(nonce)
  • Continue if k = 0 or k >= n
  • Let R = k⋅G
  • Let r = x(R) mod n
  • Continue if r = 0
  • Let s = k^-1 * (d * r + int(msghash)) mod n
  • Continue if s = 0
  • Return (r, s)
• Fail

ECDSA Verification

Input:

• The signature sig: (r, s)
• The public key P: a point
• The message hash msghash: a 32-byte array

The algorithm verify(sig, P, msghash) is defined as:

• If is_infinite(P):
  • Return false
• If y(P)² ≠ x(P)³ + 7 mod p:
  • Return false
• Let (r, s) = sig
• If r <= 0 or r >= n:
  • Return false
• If s <= 0 or s >= n:
  • Return false
• Let w = s^-1
• Let u₁ = w * int(msghash) mod n
• Let u₂ = w * r mod n
• Let R = u₁⋅G + u₂⋅P
• If is_infinite(R):
  • Return false
• If x(R) mod n ≠ r:
  • Return false
• Return true

Deterministic Signing

Input:

• The secret key sk: a 32-byte array
• The message hash msghash: a 32-byte array

The algorithm DeterministicSign(sk, msghash) is defined as follows. The grind counter is 0 for the initial call to sign, which supplies no additional data, and takes the value of the loop variable i for every subsequent call.

• Fail if int(sk) = 0 or int(sk) >= n
• Let (r, s) = sign(sk, msghash, empty_bytestring)⁸
• Let i = 1
• While r >= 2²⁵⁵:⁹
  • If i >= 2³²:
    • Fail
  • Let extra = bytes_le(4, i) || fill_bytes(28, 0x00)¹⁰
  • Let (r, s) = sign(sk, msghash, extra)
  • Let i = i + 1
• If s > half_order:¹¹
  • Let s = n - s
• Let P = int(sk)⋅G
• If verify((r, s), P, msghash) returns false, abort¹²
• Return (r, s)

The predicate r >= 2²⁵⁵ is equivalent to testing that the most significant byte of bytes(32, r) is greater than or equal to 0x80.

# Rationale

Bitcoin encodes ECDSA signatures in a strict DER form with an additional 1-byte sighash flag, which serializes r and s as arbitrary-length big-endian signed integers¹³. Their encoding being signed means that even though every value of r and s can be encoded in 32 bytes or less as an unsigned integer, a null byte must be prepended if the most significant bit is set, raising the maximum size to 33 bytes each. The maximum size of a DER encoded ECDSA signature is 72 bytes, or 73 with the sighash flag.

The signing algorithm as specified makes use of low-r grinding and low-s normalization¹⁴ to exclusively produce low-r and low-s signatures. This produces signatures with a maximum DER encoding size of 70 bytes, or 71 with the sighash flag.¹⁵ Against a signer that normalizes s but does not grind, low-r grinding saves on average 0.5 vbytes per signature in legacy inputs and 0.125 vbytes in v0 segwit inputs.¹⁶ In 2-of-3 P2SH inputs it saves 2.5 vbytes on average, as a single high-r signature pushes the input script's length indicator from one byte to three. The cost is rather cheap: low-r grinding requires an additional signing operation and low-s normalization requires a scalar subtraction. Uniform adoption is worthwhile independently of the savings, as a signer that does not grind is identifiable on-chain by its high-r signatures.¹⁷

# Low-r Grinding

Why RFC 6979

Grinding requires a nonce derivation that is deterministic in the secret key and message, and that additionally accepts a counter, so that a fresh and unrelated nonce can be derived for the same key and message.¹⁸ RFC 6979 provides exactly this: it is the IETF's standard deterministic nonce derivation for ECDSA, and its section 3.6 admits an additional data input, for which it names a signature counter as an example:¹⁹

It suffices that the additional data k' is non-repeating (e.g., a signature counter or a monotonic clock) to ensure "random-looking" signatures are indistinguishable, in a cryptographic way, from plain (EC)DSA signatures.

Potential Alternate Grinding Methods

A fresh random nonce on each attempt. Drawing each candidate nonce from a cryptographically secure random source also yields unrelated nonces, and is a valid means of producing low-r signatures. Such a method is not adopted because the resulting signatures are not reproducible, which reopens the exfiltration problem described in the Motivation. Randomness would buy some protection against fault injection, which is why BIP 340 recommends it for Schnorr signatures. Deterministic derivation is nonetheless established practice for ECDSA in Bitcoin, as RFC 6979 is libsecp256k1's default nonce function and Bitcoin Core requests it explicitly.²⁰

Grinding for smaller r. In order for a lower r value to save any space, it must be an entire byte smaller, and thus must have the leading 9 bits unset rather than just the leading bit. Computing such an r value would take 512 signing operations on average, as opposed to the two of regular low-r grinding.²¹ Grinding for a smaller r was deemed too expensive to be adopted widely. Because few signers would do so, the signers that did would be identifiable on-chain.²²

Speeding up grinding with the λ endomorphism. It was suggested to use secp256k1's λ endomorphism to quickly compute alternative nonces.²³ Low-r grinding as specified takes only two point multiplications on average. The added complexity of using the λ endomorphism cannot meaningfully improve on that.²⁴

# Backward Compatibility

Signatures generated under this specification are normal valid signatures and will verify under existing consensus rules, and thus are fully backward compatible.

# Copyright

This BIP is licensed under the CC0-1.0 license.