# Difference between revisions of "Message signing"

NotATether (talk | contribs) (added algorithm) |
NotATether (talk | contribs) m (add references) |
||

Line 238: | Line 238: | ||

# Compute ''DerivedAddress = Bech32("bc", 0, AddressHash)'' | # Compute ''DerivedAddress = Bech32("bc", 0, AddressHash)'' | ||

# If ''DerivedAddress == Address'', succeed verification. Else fail verification with an error similar to "Wrong address for signature". | # If ''DerivedAddress == Address'', succeed verification. Else fail verification with an error similar to "Wrong address for signature". | ||

+ | |||

+ | == References == |

## Revision as of 06:08, 6 August 2022

**Message signing** is the action of signing a cryptographic message using a private key and its associated address, to prove that you have access to the address. These messages can be verified by wallets by checking the signature against the address to see if they correspond to each other. The result of message signing is often called a **signed message**.

Bitcoin signed messages have three parts, which are the **Message**, **Address**, and **Signature**. The message is the actual message text - all kinds of text is supported, but it is recommended to avoid using non-ASCII characters in the signature because they might be encoded in different character sets, preventing signature verification from succeeding.

The address is a legacy, nested segwit, or native segwit address. Message signing from legacy addresses was added by Satoshi himself and therefore does not have a BIP. Message signing from segwit addresses has been added by BIP137^{[1]}.

The Signature is a base64-encoded ECDSA signature that, when decoded, with fields described in the next section.

As of this writing, there is no message signing support for Taproot addresses. Not only do they use a different signing algorithm in the form of Schnorr, but public key recovery is not possible with Schnorr signatures, so they cannot be compared to addresses.

## Contents

## Detailed specification of the message signature

ECDSA signatures generate a 32-byte r-value and a 32-byte s-value (see Elliptic Curve Digital Signature Algorithm), which collectively represent the signature. Bitcoin signatures have the r and s values mentioned above, and a 1-byte header. Therefore, the size of a signature is 65 bytes.

The header is used to specify information about the signature. It can be thought of as a bitmask with each bit in this byte having a meaning. The serialization format of a Bitcoin signature is as follows:

(1 byte for header data)(32 bytes for r-value)(32 bytes for s-value)

The header byte has a few components to it. First, it stores something known as the recID. This value is stored in the least significant 2 bits of the header, and uniquely identifies the correct signature for the signing public key. The lower bit represents the parity of the Y coordinate of the signature - even or odd - and the higher bit represents the correct r-value: 'r' or 'n+r'. For a rare subset of signatures which have r>=p-n, the only possible r-value will be 'r', thus the highest bit of the recID should be zero.

The following list demonstrates the correct signature corresponding to the value of recID:

- 0: even Y, r = r
- 1: odd Y, r = r
- 2: even Y, r = n+r
- 3: odd Y, r = n+r

The remaining bytes of the header format must be read together to fetch the correct address format. The original message signing format by Satoshi defined the following ranges for address types:

- Header byte is 27-30: P2PKH uncompressed
- Header byte is 31-34: P2PKH compressed

BIP137 additionally defines the following ranges for compressed segwit address types:

- Header byte is 35-38: P2WPKH-P2SH compressed
- Header byte is 39-42: P2WPKH compressed

## Algorithm for signing and verifying messages

It is not required, but you should strip trailing newlines from the message before signing it, because some clients cannot process messages that contain trailing newlines.

Below is a list of steps for signing and verifying a message, for each supported address type.

### Definitions used in the algorithms

Modulo is written as *mod*, for example *x* modulo *n* is written as *x mod n*.

Byte concatenation is written as *||* and implies that both operands shall be cast to byte arrays before concatenation.

Array subscripting for byte arrays is written as *x[i:j]* and should be interpreted to create a copy of the byte array *x* of length *(j-i)* with the *i*-th byte as the first byte and the *(j-1)*-th byte as the last byte (*i ≥ 0*, *j ≥ 0*).

Floor division is written as */* and involves truncating the floating-point remainder from the division result.

Modular inverse is written as *modinv(x,n)*, where *n* is a constant, variable, or expression, and is equivalent to *x^-1 mod p*.

Modular exponentiation is written as *x^n* where n is a constant, variable, or expression, and does not include modulus. The modulus must be explicitly specified using *mod* eg. *x^2 mod n*.

Bitwise AND is written as *AND*.

Bitwise XOR is written as *XOR*.

Hexadecimal byte arrays are represented as *hex(byte sequence)*, where the byte sequence consists of sequences of two hexadecimal characters which may or may not be separated by space (for example *hex(01 02)* and *hex(0102)* both generate the byte array identical to the evaluation of '\x01\x02' in the C programming language). There is no leading '0x' or '0X' in the output.

Cast from byte array or byte sequence to 256-bit integer is represented as *int(x)*.

Cast from string or 256-bit integer to byte array is represented as *bytes(x)*.

Construction of a point with an x-coordinate *x* and y-coordinate *y* is represented as *(x, y)* and implies that both *x* and *y* will be cast to integers before point construction.

For a point *P*, its x-coordinate is represented as *P.x*, and its y-coordinate is represented as *P.y*. All coordinates have

Test for whether a y-coordinate of a point is even is written has *is_even(y)* for integers. *is_even(P)* is equivalent to *is_even(P.y)*. This function is identical to computing *y AND 1 == 0* or *y mod 2 == 0*, because odd numbers represent negative Y coordinates, which is the actual basis for even/odd classification.

For brevity, *is_odd(P)* and *is_odd(P.y)* is equivalent to *!is_even(P)* and *!is_even(y)* respectively.

UTF-8 strings are represented as *"text"*, where *text* is the desired text. It should be noted that all string constants in this document contain only ASCII characters.

### Constants

The constant *Inf* shall refer to the point at infinity, of the secp256k1 curve.

The constant *p* shall refer to the secp256k1 field size, aka. curve characteristic, defined as *int(FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F)*

The constant *n* shall refer to the secp256k1 curve order, defined as *int(FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141)*

The constant *G* shall refer to the secp256k1 generator point, defined as *(79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798, 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8)*

### Message signing Method

It takes the following parameters

- The private key (PrivateKey)
- The public key (PublicKey) (optional, if performance is desired)
- The address (Address)
- The message (Message)

#### ECDSA signing, with P2PKH uncompressed addresses

- Compute
*z = SHA256(Message)* - Generate a cryptographically secure random nonce
*k*between*1*and*n-1*. This can be implemented by generating four 64-bit random unsigned integers. If the resulting integer is out of range (e.g. it's*0*or ≥*n*), then discard the entire nonce and generate its entirety all over again. This is to avoid attacks on specific parts of the nonce. - Compute
*(x,y) = G*k* - If
*r mod n == 0*or*(x,y) == Inf*, go back to step 3. - Compute
*s = modinv(k) * (z + r * PrivateKey) mod n*. If*s == 0*, go back to step 3. - Compute the header byte. If
*r < p-n*and*is_even(y)*, set HeaderByte to 30. If*r < p-n*and*is_odd(y)*, set HeaderByte to 27. If*r ≥ p-n*and*is_even(y)*, set HeaderByte to 28. If*r ≥ p-n*and*is_odd(y)*, set HeaderByte to 29. - Compute
*Signature=Base64Encode(HeaderByte || r || s)*

#### ECDSA signing, with P2PKH compressed addresses

- Compute
*z = SHA256(Message)* - Generate a cryptographically secure random nonce
*k*between*1*and*n-1*. This can be implemented by generating four 64-bit random unsigned integers. If the resulting integer is out of range (e.g. it's*0*or ≥*n*), then discard the entire nonce and generate its entirety all over again. This is to avoid attacks on specific parts of the nonce. - Compute
*(x,y) = G*k* - If
*r mod n == 0*or*(x,y) == Inf*, go back to step 3. - Compute
*s = modinv(k, n) * (z + r * PrivateKey) mod n*. If*s == 0*, go back to step 3. - Compute the header byte. If
*r < p-n*and*is_even(y)*, set HeaderByte to 34. If*r < p-n*and*is_odd(y)*, set HeaderByte to 31. If*r ≥ p-n*and*is_even(y)*, set HeaderByte to 32. If*r ≥ p-n*and*is_odd(y)*, set HeaderByte to 31. - Compute
*Signature=Base64Encode(HeaderByte || r || s)*

#### ECDSA signing, with P2WPKH-P2SH compressed addresses

- Compute
*z = SHA256(Message)* - Generate a cryptographically secure random nonce
*k*between*1*and*n-1*. This can be implemented by generating four 64-bit random unsigned integers. If the resulting integer is out of range (e.g. it's*0*or ≥*n*), then discard the entire nonce and generate its entirety all over again. This is to avoid attacks on specific parts of the nonce. - Compute
*(x,y) = G*k* - If
*r mod n == 0*or*(x,y) == Inf*, go back to step 3. - Compute
*s = modinv(k, n) * (z + r * PrivateKey) mod n*. If*s == 0*, go back to step 3. - Compute the header byte. If
*r < p-n*and*is_even(y)*, set HeaderByte to 38. If*r < p-n*and*is_odd(y)*, set HeaderByte to 35. If*r ≥ p-n*and*is_even(y)*, set HeaderByte to 36. If*r ≥ p-n*and*is_odd(y)*, set HeaderByte to 37. - Compute
*Signature=Base64Encode(HeaderByte || r || s)*

#### ECDSA signing, with P2WPKH compressed addresses

- Compute
*z = SHA256(Message)* - Generate a cryptographically secure random nonce
*k*between*1*and*n-1*. This can be implemented by generating four 64-bit random unsigned integers. If the resulting integer is out of range (e.g. it's*0*or ≥*n*), then discard the entire nonce and generate its entirety all over again. This is to avoid attacks on specific parts of the nonce. - Compute
*(x,y) = G*k* - If
*r mod n == 0*or*(x,y) == Inf*, go back to step 3. - Compute
*s = modinv(k, n) * (z + r * PrivateKey) mod n*. If*s == 0*, go back to step 3. - Compute the header byte. If
*r < p-n*and*is_even(y)*, set HeaderByte to 42. If*r < p-n*and*is_odd(y)*, set HeaderByte to 39. If*r ≥ p-n*and*is_even(y)*, set HeaderByte to 40. If*r ≥ p-n*and*is_odd(y)*, set HeaderByte to 41. - Compute
*Signature=Base64Encode(HeaderByte || r || s)*

### Message verification Method

It takes the following parameters:

- The message (Message)
- The address (Address)
- An ECDSA signature (Signature)

The Header byte in the signature shall dictate the verification algorithm that is used.

Upon verification success, you should display a status message similar to: "Genuine signed message from address <Address>".

#### Preliminary steps for all verification Algorithms

- Set
*DecodedSignature = Base64Decode(Signature)* - Set
*HeaderByte = DecodedSignature[0]*- If HeaderByte is bettwen 27 and 30 inclusive, use "ECDSA verification, P2PKH uncompressed address".
- Else, if HeaderByte is bettwen 31 and 34 inclusive, use "ECDSA verification, P2PKH compressed address".
- Else, if HeaderByte is bettwen 35 and 38 inclusive, use "ECDSA verification, P2WPKH-P2SH compressed address".
- Else, if HeaderByte is bettwen 39 and 42 inclusive, use "ECDSA verification, P2WPKH compressed address".
- Else, if HeaderByte is bettwen 43 and 46 inclusive, use "Schnorr verification, P2TR (Taproot) compressed address".
- Else, fail verification with an error similar to "Unknown signature type".

#### ECDSA verification, P2PKH uncompressed address

- Set
*r = DecodedSignature[1:33]*. If*r ≥ n*or*r == 0*, fail verification with an error similar to "Invalid ECDSA signature parameters". - Set
*s = DecodedSignature[33:65]*. If*s ≥ n*or*s == 0*, fail verification with an error similar to "Invalid ECDSA signature parameters". - Set
*z = SHA256(Message)* - Set
*recID = Header AND 0x3* - If
*recID AND 0x2 == 0*, set*x = r*, else set*x = r+n* - Set
*x = (x^3 + 7) mod p* - Set
*y = x^((p+1)/4) mod p* - Calculate the correct parity of
*y*using the 'recID':- If (
*is_even(beta)*and*is_odd(recID)*) or (*is_odd(beta) and is_even(recID)*), set*y = p-y*.

- If (
- Set
*R = (x,y)* - Set
*e = (-int(z)) % n* - Set
*PublicKey = (R*s + G*e) * modinv(r, n)* - Compute
*EncodedPublicKey = "04" || hex(x) || hex(y)* - Compute
*AddressHash = RIPEMD160(SHA256(EncodedPublicKey*) - Compute
*DerivedAddress = Base58Check(hex(00) || AddressHash)*. - If
*DerivedAddress == Address*, succeed verification. Else fail verification with an error similar to "Wrong address for signature".

#### ECDSA verification, P2PKH compressed address

- Set
*r = DecodedSignature[1:33]*. If*r ≥ n*or*r == 0*, fail verification with an error similar to "Invalid ECDSA signature parameters". - Set
*s = DecodedSignature[33:65]*. If*s ≥ n*or*s == 0*, fail verification with an error similar to "Invalid ECDSA signature parameters". - Set
*z = SHA256(Message)* - Set
*recID = Header AND 0x3* - If
*recID AND 0x2 == 0*, set*x = r*, else set*x = r+n*. - Set
*x = (x^3 + 7) mod p* - Set
*y = x^((p+1)/4) mod p* - Calculate the correct parity of
*y*using the 'recID':- If (
*is_even(beta)*and*is_odd(recID)*) or (*is_odd(beta) and is_even(recID)*), set*y = p-y*.

- If (
- Set
*R = (x,y)* - Set
*e = (-int(z)) % n* - Set
*PublicKey = (R*s + G*e) * modinv(r, n)* - If
*is_even(y)*, compute*EncodedPublicKey = "02" || hex(x)*. Else, compute*EncodedPublicKey = "03" || hex(x)* - Compute
*AddressHash = RIPEMD160(SHA256(EncodedPublicKey)* - Compute
*DerivedAddress = Base58Check(hex(00) || AddressHash)* - If
*DerivedAddress == Address*, succeed verification. Else fail verification with an error similar to "Wrong address for signature".

#### ECDSA verification, P2WPKH-P2SH compressed address

- Set
*r = DecodedSignature[1:33]*. If*r ≥ n*or*r == 0*, fail verification with an error similar to "Invalid ECDSA signature parameters". - Set
*s = DecodedSignature[33:65]*. If*s ≥ n*or*s == 0*, fail verification with an error similar to "Invalid ECDSA signature parameters". - Set
*z = SHA256(Message)* - Set
*recID = Header AND 0x3* - If
*recID AND 0x2 == 0*, set*x = r*, else set*x = r+n*. - Set
*x = (x^3 + 7) mod p* - Set
*y = x^((p+1)/4) mod p* - Calculate the correct parity of
*y*using the 'recID':- If (
*is_even(beta)*and*is_odd(recID)*) or (*is_odd(beta) and is_even(recID)*), set*y = p-y*.

- If (
- Set
*R = (x,y)* - Set
*e = (-int(z)) % n* - Set
*PublicKey = (R*s + G*e) * modinv(r, n)* - If
*is_even(y)*, compute*EncodedPublicKey = "02" || hex(x)*. Else, compute*EncodedPublicKey = "03" || hex(x)* - Compute
*AddressHash = RIPEMD160(SHA256(EncodedPublicKey)* - Compute
*RedeemScript = hex(00 14) || AddressHash* - Compute
*RedeemScriptHash = RIPEMD160(SHA256(RedeemScript))* - Compute
*DerivedAddress = Base58Check(hex(05) || RedeemScriptHash)* - If
*DerivedAddress == Address*, succeed verification. Else fail verification with an error similar to "Wrong address for signature".

#### ECDSA verification, P2WPKH compressed address

- Set
*r = DecodedSignature[1:33]*. If*r ≥ n*or*r == 0*, fail verification with an error similar to "Invalid ECDSA signature parameters". - Set
*s = DecodedSignature[33:65]*. If*s ≥ n*or*s == 0*, fail verification with an error similar to "Invalid ECDSA signature parameters". - Set
*z = SHA256(Message)* - Set
*recID = Header AND 0x3* - If
*recID AND 0x2 == 0*, set*x = r*, else set*x = r+n*. - Set
*x = (x^3 + 7) mod p* - Set
*y = x^((p+1)/4) mod p* - Calculate the correct parity of
*y*using the 'recID':- If (
*is_even(beta)*and*is_odd(recID)*) or (*is_odd(beta) and is_even(recID)*), set*y = p-y*.

- If (
- Set
*R = (x,y)* - Set
*e = (-int(z)) % n* - Set
*PublicKey = (R*s + G*e) * modinv(r, n)* - If
*is_even(y)*, compute*EncodedPublicKey = "02" || hex(x)*. Else, compute*EncodedPublicKey = "03" || hex(x)* - Compute
*AddressHash = RIPEMD160(SHA256(EncodedPublicKey)* - Compute
*DerivedAddress = Bech32("bc", 0, AddressHash)* - If
*DerivedAddress == Address*, succeed verification. Else fail verification with an error similar to "Wrong address for signature".