Topic: [DISCUSSION] BIP-notatether-messageverify: Standardizes message verification (Read 645 times)

Well, I sent it to the mailing list. Let's see how this goes.

A temporary location of the final draft can be viewed at https://github.com/ZenulAbidin/bips/blob/master/bip-notatether-signedmessage.mediawiki .

Edit: thread locked while I prepare the new one.

And now it's time for one last hulk smash on this draft. I'll assume everybody is OK with 43-46 header defining Taproot address and 46 as its default designation, since nobody commented about it. Apparently, Schnorr as used in BIP340 fails if x of R is not equal to r any way.

To keep the BIP reasonably short, I'm going to offload having to specify the internals of base58check and bech32[m] encoding algorithms by writing that it's out of scope for the BIP, and point to working implementations of these encoding/decoding algorithms instead and specify where they have to be used.

---

== Abstract ==

Bitcoin wallets have the capability of signing and verifying messages from individual addresses, by using ECDSA and the public/private key pair belonging to that address. These are often used to prove ownership of coins in the address, the address itself, or simply to relay a message as the owner of that particular address.

Message signing in its current form has been present since the earliest Bitcoin implementations, and its processes are largely still the same as how Satoshi designed it, with a few deviations by some wallet software here and there.

The purpose of message signing from an address is to prove that the signer has ownership of that address, since a valid signature implies a person has access the private key to that address. To that extent, message verification consists of two parts: 1) verifying the signature, and 2) ensuring that the address can be derived from the public key.

The original message signing format (hereby referred to in this BIP as the "Satoshi format") will briefly be described here. Parts of this description were copied from BIP137[1].

ECDSA signatures generate a 32-byte r-value and a 32-byte s-value, 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 in the Satoshi format 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 of 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 singature - 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 Satoshi format defines 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

The word "Standardization" will be used here to mean reaching a consensus to using a particular proposal by implementing it in software. "Design-standardization" will be used to refer to the original meaning - the verbal consensus of technical persons for a particular proposal without necessarily implementing it in software.

== Motivation ==

The Satoshi format's message verification algorithm has only been designed to validate messages from Legacy addresses, since that was the only existing address type when message signing was invented. Unlike how BIP 322 words it, message signing and verification is technically possible for Segwit addresses, and a signature format has even been invented for it [See 1], but it has never been standardized by wallet implementations.

The result of this oversight on the part of the wallet developers is that some wallets allow you to sign messages from a Segwit address, such as Electrum, but those messages cannot be verified anywhere except on that particular wallet software.

Critically, no attempt has been made so far to officially standardize the message signing algorithm for the Segwit address types P2WPKH, P2WPKH-P2SH, also known as Nested and native Segwit respectively (the existing proposals have only design-standardized. The existing BIPs only attempt to define a new message signing format, and have not gained a large-enough consensus for their de facto use over existing signature formats.

== Rationale ==

This document should be viewed as a manual for implementing address signing rather than as a standard. That is because it does not attempt to define a novel message signing format. It also avoids extending existing message formats, unless such extensions are required to identify or verify a particular signature type.

The only non-standard extention to the message signing format that this BIP introduces is in the Signature field format for Taproot addresses, to enable message verification for these addresses and also to make the format compatible with the Satoshi format and BIP137. In this respect, signatures generated by this BIP differ from those from BIP340[2] (albeit BIP340 does not define signing formats for addresses), but the signing and verification algorithms are otherwise compatible with BIP340. The extensions made are as follows:

- The (R,s) payload of the Schnorr signature is preceded by the one-byte header.
- When constructing the signature, the header must have a value of 46 for Taproot addresses. This is because the points used will always be even, and r values greater than or equal to n are not allowed (hence x = r+n is not a possibility).
-- However, for compatibility reasons, conforming implementations must also identify any header value between 43-46 inclusive as from a Taproot address when verifying a signature. In other words, the recID bits must be set to zero when signing a message.
- Immediately following the (R,s) payload is the 32-byte x-coordinate of the public key. The public key MUST be interpreted as even and compressed. This is necessary because BIP340 Schnorr signatures do not allow for public key recovery, so the public keys need to be concatenated in the signature.

Thus, the signature payload for Schnorr signatures will be 97 bytes long in total (1-byte header + 64-byte (R,s) + 32-byte public key). For ECDSA signatures, it will be 65 bytes long (1-byte header + 64-byte (r,s)).

This BIP attempts to define the precise algorithms for signing and verifying messages, that are signed using the Satoshi format (a subset of BIP137), BIP137 format, or the Schnorr signature format defined above. Hence, compliance with this BIP implies compliance with BIP137.

A number of extensions to the message signature format have been defined, for error checking purposes. All of these extensions are strictly optional. Implementations are free to implement only the base standard and none of the extensions, or some but not all of the extensions, if this is desired. All of the extensions can be implemented independently from each other. The full list of extensions defined by this BIP are listed below:

- Message Sanitization - Before signing and verification, removes all NUL characters, converts tabs to 8 spaces, converts CRLF and CR to LF, strips trailing space and tab from the ends of lines, and strips all trailing whitespace from the end of the message.
-- The original message is always unmodified.
-- Some users experience difficulties in verifying signatures that contain hidden spaces and tabs, due to naunces in current implementations, so this extension remedies that by eliminating the traling spaces and tabs altogether.
--- In particular, this means that even in the case of a single newline at the end of the message, it is stripped for uniformity with messages without any such newlines.
-- Also, operating systems and programs may have different line ending formats, and lengths for the tab character.
--- To avoid verification errors due to these mis-matches, tabs are expanded to 8 characters (the recognized length of a tab), and sequences of carrige and line feed are reduced to simply line-feed.
-- Also, parsing NUL characters is a common source of vulnerabilities, because most implementations cannot detect them correctly, therefore, they are stripped form the entire message before signing and verification.
--- No other non-graphical characters are removed apart from the trailing whitespace.
-- For the purposes of this extension, the defined whitespace characters are space ' ', newline '\n', tab '\t' and carrige return '\r'.

- UTF-8 Serialization - Converts the character set of the message body to UTF-8 before signing and verifying.
-- Due to operating systems using incongruent default character set (for example Windows uses Windows-1252 by default and Linux programs tend to use ISO 8859-1 aka. Latin-1), signed message containing non-ASCII characters might fail verification depending on the operating system. This is because the actual byte sequences of the message are different for each encoding.
-- By converting the message into UTF-8 using a library such as GNU libiconv[3] or ICU[4], errors due to differences in character sets are eliminated.
-- Even in UTF-8, there are several different valid forms to represent the same text. The result is more verification errors because the byte sequences are inherently different. This BIP resolves this issue by normalizing all UTF-8 text into NFC form, which takes the smallest amount of storage space of all UTF-8 forms.

The phrases "Requirements for extension EXTENSION_NAME" and "End extension requirements" by themselves on a line are used to delimit the parameters and processes that are only required for a specific extension.

While BIP 322 has superior message verification capabilities, such as the ability to verify scripts, no attempt is made to define a verification algorithm for BIP 322 in this proposal.

No attempt is made to define the bodies of the Base58Check, Bech32, Bech32m encoding algorithms, in order to avoid unnecessarily increasing the length of the BIP. Instead, the reader is referred to existing implementations of these algorithms in the Notes section. Any well-formed implementation of the encoding algorithm can be used where the BIP specifies the algorithm's name. It is recommended to thoroughly test the encoding implementations with specially-crafted data to eliminate the security risk of buffer overruns.

The following terminologies apply for the rest of this document:

"Message Signing Format", or simply "Format", refers to one of the cryptographic algorithms and address formats detailed in the Specification section.

"Method" refers to either message signing, message verification, or both.

"Algorithm" refers to the sub-method required to support signing and verification of one of the defined Formats.

== Specification ==

The message signing processes consist of two sub-processes - the signing Method, and the verification Method, the specification for both of these items is detailed separately.


The message signing and verification Methods shall use at least one of the following Formats to create a signature, depending on the wallet implementation:

- ECDSA signatures, with P2PKH uncompressed addresses.
- ECDSA signatures, with P2PKH compressed addresses.
- ECDSA signatures, with P2WPKH-P2SH compressed addresses.
- ECDSA signatures, with P2WPKH compressed addresses.
- Schnorr signatures, with P2TR (Taproot) compressed addresses.

For a particular Format:
- If the implementation shall be used in a wallet software, both its signing and verification Methods must be implemented. In other words, you cannot only implement a Format for signing or verification separately.
- If the implementation shall be ran as a stand-alone application (for example, hosted on a web page), then only the verification Method is required to be implemented. For this scenario it is recommended that the signing should not be implemented, to eliminate the possibility of rogue private key or public key data being supplied at user input.
- Conforming implementations must not implement only the signing Method without the verification Method under any circumstances. This inhibits users from verifying that their signatures are correct.

The "ECDSA with P2PKH", "ECDSA with P2WPKH-P2SH", and "ECDSA with P2WPKH" format produce BIP137-compatible signatures. The "ECDSA with P2PKH" format produces a Satoshi format-compatible signature.

Three fields are defined for all Message Signing Formats: Message, Address, and Signature.

In the case of both ECDSA and Schnorr signatures, the address which is used to sign the message is placed inside the Address area. The message that is being signed should be placed in the Message area. The Signature area will be filled with the output of the method described below.

No other fields are defined by this BIP. Conforming implementations must not define additional fields in the message signature.


=== Definitions ===

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

Array subscripting 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 exponentation 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'.

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

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

Hexadecimal byte arrays are represented as 'hex(byte sequence)', where the byte sequence consists of sequences of two hexadecimal characters separated by space (for example 'hex(01 02)' generates 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.

=== Common steps for all signing and verification Algorithms ===

These steps must be executed before any other step in the Algorithm is ran.

The preliminary steps are listed below, and all operate on the Message field exclusively.

Requirements for extension UTF-8 Serialization:
1. The message is converted to the UTF-8 encoding, if it isn't already in that encoding. If the character set conversion fails (for example if there are invalid bytes in the encoding), then fail signing with a error similar to "UTF-8 conversion error".
2. Scan the message for invalid UTF-8 byte sequences. If any are found, then fail signing with an error similar to "Message contains invalid UTF-8 characters".
3. The resulting UTF-8 should be compressed into NFC form.
End extension requirements

Requirements for extension Message Sanitization:
4. Scan the message for NUL (0x00, or '\0') bytes. If any are found, fail signing with an error similar to "Message contains embedded NUL characters".
5. Strip all tab and space characters from the ends of all lines.
6. Convert CRLF and CR newlines to LF.
7. Remove all trailing newlines from the end of the message.
End extension requirements

=== Message signing method ===

The following parameters must be inserted into all supported signing Algorithms:

- The private key (PrivateKey)
- The public key (PublicKey)
-- Implementations can choose whether to include this parameter or calculate the public key directly in the signing Method, but it is the implementation's responsibility to ensure that the correct public key is being passed to this method.
--- This is because PublicKey is considered as implementation data, not user-generated data.
- The address (Address)
-- It is the implementation's responsibility to ensure that Address corresponds to PrivateKey and PublicKey.
- The message (Message)

Depending on the Format from which the signed message is being created, implementations should choose the apropriate Algorithm from the subsections below.

==== ECDSA signing, with P2PKH uncompressed addresses ====

1. Obtain the generator point G, curve order n and the curve characteristic p for secp256k1.
2. Compute z = SHA256(Message)
3. 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.
4. Compute (x,y) = G*k
5. If r mod n is 0 or (x,y) is the point at infinity, go back to step 3.
6. Compute s = modinv(k) * (z + r * PrivateKey) mod n. If s is 0, go back to step 3.
7. Compute the header byte. If r < p-n and y is even, set HeaderByte to 30. If r < p-n and y is odd, set HeaderByte to 27. If r >= p-n and y is even, set HeaderByte to 28. If r >= p-n and y is odd, set HeaderByte to 29.
8. Compute Signature=Base64(HeaderByte || r || s)

==== ECDSA signing, with P2PKH compressed addresses ====

1. Obtain the generator point G, curve order n and the curve characteristic p for secp256k1.
2. Compute z = SHA256(Message)
3. 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.
4. Compute (x,y) = G*k
5. If r mod n is 0 or (x,y) is the point at infinity, go back to step 3.
6. Compute s = modinv(k, n) * (z + r * PrivateKey) mod n. If s is 0, go back to step 3.
7. Compute the header byte. If r < p-n and y is even, set HeaderByte to 34. If r < p-n and y is odd, set HeaderByte to 31. If r >= p-n and y is even, set HeaderByte to 32. If r >= p-n and y is odd, set HeaderByte to 31.
8. Compute Signature=Base64(HeaderByte || r || s)

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

1. Obtain the generator point G, curve order n and the curve characteristic p for secp256k1.
2. Compute z = SHA256(Message)
3. 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.
4. Compute (x,y) = G*k
5. If r mod n is 0 or (x,y) is the point at infinity, go back to step 3.
6. Compute s = modinv(k, n) * (z + r * PrivateKey) mod n. If s is 0, go back to step 3.
7. Compute the header byte. If r < p-n and y is even, set HeaderByte to 38. If r < p-n and y is odd, set HeaderByte to 35. If r >= p-n and y is even, set HeaderByte to 36. If r >= p-n and y is odd, set HeaderByte to 37.
8. Compute Signature=Base64(HeaderByte || r || s)

==== ECDSA signing, with P2WPKH compressed addresses ====

1. Obtain the generator point G, curve order n and the curve characteristic p for secp256k1.
2. Compute z = SHA256(Message)
3. 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.
4. Compute (x,y) = G*k
5. If r mod n is 0 or (x,y) is the point at infinity, go back to step 3.
6. Compute s = modinv(k, n) * (z + r * PrivateKey) mod n. If s is 0, go back to step 3.
7. Compute the header byte. If r < p-n and y is even, set HeaderByte to 42. If r < p-n and y is odd, set HeaderByte to 39. If r >= p-n and y is even, set HeaderByte to 40. If r >= p-n and y is odd, set HeaderByte to 41.
8. Compute Signature=Base64(HeaderByte || r || s)

==== Schnorr signing, with P2TR (Taproot) compressed addresses ====


1. Obtain the generator point G, curve order n and the curve characteristic p for secp256k1.
2. Generate a cryptographically secure random 32-bit number a. This is recommended by BIP340 to avoid private key leaks, particularly if the public key is supplied as a parameter.
3. If PublicKey has an odd y coordinate, set PrivateKey = n - PrivateKey.
4. Compute t = PrivateKey XOR SHA256(SHA256(BIP0340/aux) || SHA256(BIP340/aux) || a).
5. Compute rand = SHA256(SHA256(BIP0340/nonce) || SHA256(BIP340/nonce) || t || PublicKey's x-coordinate || Message)
6. Compute k = int(rand) mod n. If k = 0, go back to step 2.
7. Compute R = k*G
8. If R has odd y coordinate, compute k = n-k.
9. Compute e = int(SHA256(SHA256(BIP0340/challenge) || SHA256(BIP0340/challenge) || R's x coordinate || P's x coordinate || Message)) mod n.
10. Compute sig = R's x coordinate || (k + e*PrivateKey mod n)
11. Set HeaderByte = 46 (even Y coordinate, r size will never be n+r or greater than or equal to n).
12. Compute Signature = Base64(HeaderByte || sig || PublicKey).

=== Message verification method ===

The following parameters must be inserted into all supported verification Algorithms:

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

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

Upon verification success, implementations must display a status message similar to: "Genuine signed message from address

".

==== Preliminary steps for all verification Algorithms ====

1. Set DecodedSignature = The decoded Base64 of Signature.
2. 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 ====

1. Set r = DecodedSignature[1:33]. If r >= n or r == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
2. Set s = DecodedSignature[33:65]. If s >= n or s == 0, fail verification with an error similar to "Invalid Ecdsa signature parameters".
3. Set z = SHA256(Message)
4. Set recID = Header AND 0x3
5. If recID AND 0x2 is not zero, set x = r+n, else set x = r.
6. Set alpha = (x^3 + 7) mod p
7. Set beta = alpha^((p+1)/4) mod p
8. If least-significant-bit of beta-recID is 0 (i.e. beta-recID is even):
-- Set y = beta
-- Else, set y = p-beta
9. Set R = Point(x,y)
10. Set e = (-(bytes(z))) % n
11. Set PublicKey = (R*s + G*e) * modinv(r, n)).
12. Compute EncodedPublicKey = "04" || hex(x) || hex(y)
13. Compute AddressHash = RIPEMD160(SHA256(EncodedPublicKey)
14. Compute DerivedAddress = Base58Check(hex(00) || AddressHash).
15. If DerivedAddress is equal to Address, succeed verificaion. Else fail verification with an error similar to "Wrong address for signature".

==== ECDSA verification, P2PKH compressed address ====

1. Set r = DecodedSignature[1:33]. If r >= n or r == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
2. Set s = DecodedSignature[33:65]. If s >= n or s == 0, fail verification with an error similar to "Invalid Ecdsa signature parameters".
3. Set z = SHA256(Message)
4. Set recID = Header AND 0x3
5. If recID AND 0x2 is not zero, set x = r+n, else set x = r.
6. Set alpha = (x^3 + 7) mod p
7. Set beta = alpha^((p+1)/4) mod p
8. If least-significant-bit of beta-recID is 0 (i.e. beta-recID is even):
-- Set y = beta
-- Else, set y = p-beta
9. Set R = Point(x,y)
10. Set e = (-(bytes(z))) % n
11. Set PublicKey = (R*s + G*e) * modinv(r, n)
12. If y is even, compute EncodedPublicKey = "02" || hex(x). Else, compute EncodedPublicKey = "03" || hex(x).
13. Compute AddressHash = RIPEMD160(SHA256(EncodedPublicKey)
14. Compute DerivedAddress = Base58Check(hex(00) || AddressHash).
15. If DerivedAddress is equal to Address, succeed verificaion. Else fail verification with an error similar to "Wrong address for signature".

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

1. Set r = DecodedSignature[1:33]. If r >= n or r == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
2. Set s = DecodedSignature[33:65]. If s >= n or s == 0, fail verification with an error similar to "Invalid Ecdsa signature parameters".
3. Set z = SHA256(Message)
4. Set recID = Header AND 0x3
5. If recID AND 0x2 is not zero, set x = r+n, else set x = r.
6. Set alpha = (x^3 + 7) mod p
7. Set beta = alpha^((p+1)/4) mod p
8. If least-significant-bit of beta-recID is 0 (i.e. beta-recID is even):
-- Set y = beta
-- Else, set y = p-beta
9. Set R = Point(x,y)
10. Set e = (-(bytes(z))) % n
11. Set PublicKey = (R*s + G*e) * modinv(r, n)
12. If y is even, compute EncodedPublicKey = "02" || hex(x). Else, compute EncodedPublicKey = "03" || hex(x).
13. Compute AddressHash = RIPEMD160(SHA256(EncodedPublicKey)
14. Compute RedeemScript = hex(00 14) || AddressHash
15. Compute RedeemScriptHash = RIPEMD160(SHA256(RedeemScript)).
16. Compute DerivedAddress = Base58Check(hex(05) || RedeemScriptHash).
17. If DerivedAddress is equal to Address, succeed verificaion. Else fail verification with an error similar to "Wrong address for signature".

==== ECDSA verification, P2WPKH compressed address ====

1. Set r = DecodedSignature[1:33]. If r >= n or r == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
2. Set s = DecodedSignature[33:65]. If s >= n or s == 0, fail verification with an error similar to "Invalid Ecdsa signature parameters".
3. Set z = SHA256(Message)
4. Set recID = Header AND 0x3
5. If recID AND 0x2 is not zero, set x = r+n, else set x = r.
6. Set alpha = (x^3 + 7) mod p
7. Set beta = alpha^((p+1)/4) mod p
8. If least-significant-bit of beta-recID is 0 (i.e. beta-recID is even):
-- Set y = beta
-- Else, set y = p-beta
9. Set R = Point(x,y)
10. Set e = (-(bytes(z))) % n
11. Set PublicKey = (R*s + G*e) * modinv(r, n)
12. If y is even, compute EncodedPublicKey = "02" || hex(x). Else, compute EncodedPublicKey = "03" || hex(x).
13. Compute AddressHash = RIPEMD160(SHA256(EncodedPublicKey)
16. Compute DerivedAddress = Bech32("bc", 0, AddressHash).
17. If DerivedAddress is equal to Address, succeed verificaion. Else fail verification with an error similar to "Wrong address for signature".

==== Schnorr verification, P2TR (Taproot) compressed addresss ====

1. Set DecodedSignature = The decoded Base64 of Signature.
2. Set HeaderByte = DecodedSignature[0]. If HeaderByte is less than 43 or greater than 46, fail verification with an error similar to "Not a Taproot address signature".
3. Set r = DecodedSignature[1:33]. If r >= p or r == 0, fail verification with an error similar to "Invalid Schnorr signature parameters".
4. Set s = DecodedSignature[33:65]. If s >= n or s == 0, fail verification with an error similar to "Invalid Schnorr signature parameters".
5. Set x = DecondedSignature[65:97].
6. Compute c = x^3 + 7 mod p
7. Compute y = c^((p+1)/4) mod p
8. If y^2 mod p is not equal to c, fail verification with an error similar to "Invalid Schnorr signature parameters".
9. If y mod 2 is equal to zero, compute P = the point (x,y), else compute P = the point (x,p-y).
10. Compute e = int(SHA256(SHA256(BIP0340/challenge) || SHA256(BIP0340/challenge) || r || x || Message)) mod n
11. Compute R = s*G - e*P. If R is infinity or has an odd y, or if R's x coordinate is not equal to r, fail verification with an error similar to "Invalid Schnorr signature parameters".
12. Compute EncodedPublicKey = "02" || hex(x).
13. Compute AddressHash = RIPEMD160(SHA256(EncodedPublicKey)
16. Compute DerivedAddress = Bech32m("bc", 1, AddressHash).
17. If DerivedAddress is equal to Address, succeed verificaion. Else fail verification with an error similar to "Wrong address for signature".

== Displaying signed messages ==

Implementations can choose to display and process the Message, Address, and Signature separately. Alternatively, all three of these fields can be condensed into the following standardized format:

-----BEGIN BITCOIN SIGNED MESSAGE-----
Message
-----BEGIN BITCOIN SIGNATURE-----
Address
Signature
-----END BITCOIN SIGNATURE-----

If implementations choose to display the signed message using this format, it should be able to extract the Message, Address and Signature parts from it as well.

== Notes ==

The signing methods do not check whether Address can be generated from the PrivateKey or PublicKey. This ommission allows for the generation and distribution of "forged signatures" - signed messages where Signature derives an address different from the supplied Address, but this vulnerability is mitigated by thorough checking in the verification Method that the address can be generated from the public key, this failing verification for all such signatures. This is why when the signing Method is implemented, the verification Method must also be implemented.

Checking that the correct address can be derived from the public key and displaying an appropriate message, as opposed to just checking the validity of the signature, ensures that a signed message can be cryptographically proven to be legitimate or a fake. In particular, displaying error text such as "The signed message is not genuine" as opposed to "Message verification failed" gives credibility to the theorem that the message is of fraudulent origin, since faults in the verification Method of the implementation can be ruled out.

For instance, a conforming implementation with all extensions implemented can be utilized to demonstrate whether person A can provide a valid signed message from address B, thereby proving whether they have access to that address.

For this reason, it is highly recommended for implementations to implement both the Message Sanitization and UTF-8 serialization extensions, to eliminate byte-level differences that could prevent the signatures from being verified correctly.

A Base58 and Base58Check implementation written in Python is available at https://github.com/keis/base58, and a Bech32 and Bech32m implementation in multiple languages is available at https://github.com/sipa/bech32.

== References ==

[1] - https://github.com/bitcoin/bips/blob/master/bip-0137.mediawiki

[2] - https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki

[3] - https://www.gnu.org/software/libiconv/

[4] - https://icu.unicode.org/

After reading BIP173 and BIP350, here's what I ended up with for my own project (Python 3 with mypy annotations):



It's less general than the reference implementation (e.g. you have to replace '[3, 3, 0, 2, 3]' with '[3, 3, 0, 20, 2]' for testnet addresses) but you may find it helpful seeing a slightly different take on the same algorithm.

Has only been lightly tested. Parameter 'isModified' switches between Bech32/Bech32m.

For anyone unaware, these functions expect their input lists to only contain (unsigned) 5-bit ints.

Edit: That's all the attention I can spare for now, good luck with your BIP!

Yeah, inclusive should cover all of the cases where there is a between range.

Let me eliminate the spelling errors very quickly and add the Schnorr signature code, and then I will come back for the bech32[m] algo.



I think you meant BIP173.

---

So guys, I guess everyone's OK with the header byte in front to Taproot signatures as well, set to the value 46?

I think that's already been addressed by following each[1] case with the word "inclusive".

[1] There's one case where an "inclusive" is missing ("Verify that both r and s are between 1 and n-1").

Bech32 (BIP173[1]) and Bech32m (BIP350[2]) both have reference implementation that could help you see how things are done. The difference between the two BIPs is the checksum computation where BIP173 uses 1 as its constant while BIP350 uses 0x2bc830a3. That's all.

[1] https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki
[2] https://github.com/bitcoin/bips/blob/master/bip-0350.mediawiki

Okay, I'm about to add some SegWit/Taproot address generation stuff to my own code, so I need to research Bech32/Bech32m anyway. Once I've got it all working on my end I'll let you know.

Yeah, I need to see how to compute the Bech32 checksum (and if Bech32m uses a very different algorithm from Bech32 - I also need to see some code for that), that would be very helpful.

I'm sure you would have spotted these, but here you go (no overlap with Cricktor's notes):

    (Abstract) "ECDSA signatures generate a 32-byte r-value and a 32-bit s-value" -> "ECDSA signatures generate a 32-byte r-value and a 32-byte s-value"

    (Motivation) "since that were the only existing address type when message signing was invented" -> "since that was the only existing address type when message signing was invented"

    "=== Message verificaion method ===" -> "=== Message verification method ==="

    (ECDSA verification) "If they match, succeed verifcation, else fail." -> "If they match, succeed verification, else fail."

    (ECDSA verification) "Compare Base58Check(RedeemScriptHash) it with the read address." -> "Compare Base58Check(RedeemScriptHash) with the read address."

    (ECDSA verification) "If they match, succeed verificaiton" -> "If they match, succeed verification"

    (ECDSA verification) "fail verification with the message similar to" -> "fail verification with a message similar to"

I also think (to prevent confusion with xor):

    (ECDSA verification) "Note: '/' represents floor division, truncating the floating-point part, and '%' represents modulus." -> "Note: '/' represents floor division, truncating the floating-point part, '^' represents exponentiation, and '%' represents modulus."

Edit: If you have small bits of work that need doing (researching something, going through Electrum's source code, etc.) feel free to let me know (by PM or post) and I'll help if I'm able to.

Minimal corrections while reading your post and by no means a complete proof reading:
"31-34 to represent P2PKH uncompressed" should be "... P2PKH compressed" which is properly expressed in the == Abtract == section.

I highlighted proposed corrections or missing characters...

[Where did everyone go? I obviously did not make this topic just for merit. Besides, I can't be replying to myself forever. Come on don't you guys want to see standardized segwit signatures? ]

I got the green light from Pieter Wuille on the mailing list to append the public key to the signature payload, so this is what I will do for Taproot. The address field will be left unmolested.

Note before I post the draft: It appears that all "Brainwallet sites" such as https://jochen-hoenicke.de/brainwallet/#verify are using a subset of the BIP137 data format internally [but cannot verify anything but legacy address messages - keep reading]. They use 27-30[1] in the first byte, before any R or S bytes, to represent a P2PKH uncompressed, 31-34 to represent P2PKH compressed, and BIP137 additionally defines the following additional designations:

35-38: P2WPKH-P2SH
39-42: P2WPKH

[1] Why is it between 27 and 30 inclusive? Because the lowest two bits of the first byte are occupied by something known as the recID, and is auxilliary data for verifying ECDSA signatures. This is not needed for Schnorr signatures, so for Taproot signatures the lowest two bits should be set to 0.

So, that is the signature field for legacy signing standard and also for BIP137. Can we reuse this format for Taproot addresses? I think so, but we have to add the public key after the signature as I mentioned above. So I will define the following range for taproot P2TR addresses:
43-46: P2TR

Since the two-bit, recID is not used in Taproot, implementations are recommended to always set the first byte to 46 (for backwads compatibility, besides the signature will always generate even Y - I am not so sure about if it generates X = r though) however, any of these four values can identify a P2TR Schnorr signature.

Warning: I have no idea if this data-range definition will be shot down by the community as some kind of unorthodox construct. After all, I am shoehorning Schnorr signature format into BIP137 format. Alternatively, I'm open to considering specifying Taproot Schnorr signatures to be ONLY the (e,s) or (R,s) signature, followed by the public key.

---

== Abstract ==

Bitcoin wallets have the capability of signing and verifying messages from individual addresses, by using ECDSA and the public/private key pair belonging to that address. These are often used to prove ownership of coins in the address, the address itself, or simply to relay a message as the owner of that particular address.

Message signing in its current form has been present since the earliest Bitcoin implementations, and its processes are largely still the same as how Satoshi designed it, with a few deviations by some wallet software here and there.

The original message signing format (hereby referred to in this BIP as the "Satoshi format") will briefly be described here. Parts of this description were copied from BIP137[TODO include reference].

ECDSA signatures generate a 32-byte r-value and a 32-byte s-value, 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 in the Satoshi format 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 of 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 singature - 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 Satoshi format defines 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

The word "Standardization" will be used here to mean reaching a consensus to using a particular proposal by implementing it in software. "Design-standardization" will be used to refer to the original meaning - the verbal consensus of technical persons for a particular proposal without necessarily implementing it in software.

== Motivation ==

The Satoshi format's message verification algorithm has only been designed to validate messages from Legacy addresses, since that was the only existing address type when message signing was invented. Unlike how BIP 322 words it, message signing and verification is technically possible for Segwit addresses, and a signature format has even been invented for it [See 1], but it has never been standardized by wallet implementations.

The result of this oversight on the part of the wallet developers is that some wallets allow you to sign messages from a Segwit address, such as Electrum, but those messages cannot be verified anywhere except on that particular wallet software.

Critically, no attempt has been made so far to officially standardize the message signing algorithm for the Segwit address types P2WPKH, P2WPKH-P2SH, also known as Nested and native Segwit respectively (the existing proposals have only design-standardized. The existing BIPs only attempt to define a new message signing format, and have not gained a large-enough consensus for their de facto use over existing signature formats.

== Rationale ==

This BIP does not attempt to define a novel message signing format. It also avoids extending existing message formats, unless such an extension is required to verify a particular signature.

This BIP attempts to define the precise algorithms for signing and verifying messages, that are signed using one of the existing formats. While BIP 322 has superior message verification capabilities, such as the ability to verify scripts, no attempt is made to define a verification algorithm for BIP 322 in this proposal.

Hereafter, this BIP will refer to the methods that sign and verify messages as "message signing processes".

The message signing processes consist of two sub-processes - the signing method, and the verification method, the specification for both of these items is detailed separately.

=== Message signing method ===

The message signing method shall use at least one of the following algorithms to create a signature, depending on the wallet implementation:
- ECDSA signatures, with P2PKH addresses.
- ECDSA signatures, with P2WPKH-P2SH addresses.
- ECDSA signatures, with P2WPKH addresses.
- Schnorr signatures, with P2TR (Taproot) addresses.
- BIP 137 signatures, with P2PKH, P2WPKH-P2SH, and P2WPKH addresses.

In the case of the ECDSA signatures, the address which is used to sign the message is placed inside the Address area.

[As this is not yet a draft, I will fill in the exact ECDSA signing process on a later date. Essentially, it is exactly the same as the current algorithm.]

=== Message verification method ===

First, the message, address, and signature fields are read from the signed message document.

The Length of the signature is calculated and the appropriate code path is chosen based on its length:

- If the Length is 65 bytes, then the ECDSA verification algorithm will be used.
- If the Length is 96 bytes, then the Schnorr verification algorithm will be used.

==== ECDSA verification ====

For the ECDSA verification method, the following values will be extracted from the signature:

- The header [byte 0, using 0-based indices]
- The r-value [bytes 1-32 inclusive]
- The s-value [bytes 33-64 inclusive]

After the signature is decoded from Base64 notation, The value of the header is compared to the ranges below, and the appropriate address type is deduced:

If the header is between 27 and 30 inclusive, define SigAddressType to P2PKH Uncompressed.
Else, if the header is between 31 and 34 inclusive, define SigAddressType to P2PKH Compressed.
Else, if the header is between 35 and 38 inclusive, define SigAddressType to P2WPKH-P2SH Compressed.
Else, if the header is between 39 and 42 inclusive, define SigAddressType to P2WPKH Compressed.
Else, fail verification with a message similar to "Unknown address type in ECDSA signature".

Next, the address is compared to the SigAddressType to ensure that the types match:

Then, the public key will be computed from the r-value and s-value (for brevity they will be referred to as "r" and "s"):

- Compute "z", the byte representation of the SHA256 hash of the message that is to be verified
- Verify that both r and s are between 1 and n-1. Otherwise, fail verification with a message similar to "malformed ECDSA signature".
- Set "n" equal to the curve order, and "p" equal to the curve characteristic.
- Next, the public key must be computed. The following algorithm has been derived from bitcoinsig.js [it will be uploaded soon because I could not find the main Github repository for it]:
-- Set x = r + n * recID/2
[Note: This will almost always be just "r", but in extremely rare cases it could also be "r+n", because if r < p-n, then r=p+n is another valid r-value]
-- Set alpha = (x^3 + 7) % p
-- Set beta = alpha^((p+1)/4) % p
-- If least-significant-bit of beta-recID is 0 (i.e. beta-recID is even):
--- Set y = beta
--- Else, set y = p-beta
-- Set R = Point(x,y)
-- Set e = (-(byte_array_to_unsigned_bigint(z))) % n
-- Set PublicKey = (R*s + G*e) * (r^(-1) % n)).
Note: '/' represents floor division, truncating the floating-point part, '^' represents modular exponentation (that is, the modulus must be taken after the exponentation) and '%' represents modulus. 'byte_array_to_unsigned_bigint()' converts a byte array into an unsigned integer which can represent arbitrarily large values.

Next, the public key must be verified against the r,s values [TODO: I am not a cryptographer, can someone weigh in on this and tell me if this is necessary, or will the autogenerated pubkey pass this part every time? It's not necessar because we derived pubkey from x=r. But this can be used to calculate the recID - bitcoinsig.js just cycles through each value of recID and verifies the signature until it finds one that passes successfully. This should be moved into the messaeg signing part. Thanks to https://bitcointalksearch.org/topic/m.54542481 for the recID codes.]

-- Compute u[1] = z*s^-1 mod n and u[2] = r*s^-1 mod n.
--  Compute (x, y) = u[1]*G + u[2]*PublicKey. If (x,y) is equal to the point at infinity, fail verification with a message similar to "malformed ECDSA signature".
-- If x = r and y is even (least significant bit is 0), then set recID to 0
-- Else if x = r and y is odd (least significant bit is 1), then set recID to 1
-- Else if x = r + n and y is even, then set recID to 2
-- Else if x = r + n and y is odd, then set recID to 3
[There is no Else clause. x will always generate either r or r+n. Also, do not apply modulus to the r, or you will break the recID check.]
[TODO delete]
-- If r = x mod n, then continue. Else, fail verification with a message similar to "malformed ECDSA signature".
[end of TODO]

Then, compute the AddressHash:
If SigAddressType is P2WSH Uncompressed set AddressHash to be RIPEMD160(SHA256(PublicKey encoded in uncompressed form)).
Else set AddressHash to be RIPEMD160(SHA256(PublicKey encoded in compressed form)).

After that, the first bytes (not individual Unicode characters) inside the address are inspected:

- If the address begins with '1':
-- Assert that the Header is between 27 and 34 inclusive. Otherwise, fail verification with a message similar to "Address prefix does not match type in signature".
-- Assume Address is a P2PKH aka Legacy address, encode AddressHash using Base58Check, and compare it with the read address. If they match, succeed verifcation, else fail.
- Else, if the address begins with '3',
-- Assert that the Header is between 35 and 38 inclusive. Otherwise, fail verification with a message similar to "Address prefix does not match type in signature".
-- Assume it is P2WPKH-P2SH
-- Set RedeemScript to the hexadecimal bytes "0x0014" concatenated with the AddressHash.
-- Set RedeemScriptHash to the concatenation of the hexadecimal byte "0x05" with RIPEMD160(SHA256(RedeemScript))
-- Compare Base58Check(RedeemScriptHash) it with the read address. If they match, succeed verificaiton, else fail verification with a message similar to "Address prefix does not match type in signature".
[XXX I do not like doing this for the reason that @achow101 stated, so if anyone has a better way to accomplish this, please let me know. For now this seems to be the only option.]
- Else, if the address begins with 'bc1q', perform additional checks:
-- In accordance to BIP141, this will either be a P2WPKH address or a P2WSH address. However, we do not have a redeem script, but an address hash, so we directly derive a bech32 address from it:
-- Prefix AddressHash with the bits '00000' to create a version 0 address, and then map the groups of 5 bits to bech32 characters, and generate the Bech32 checksum.
--- If this matches the address, succeed verification, else, fail verification with a message similar to "Address prefix does not match type in signature".
-- If the first byte is anything else, fail verification.
- Else, fail verification.

==== Schnorr verification ====

[Work in progress, the ECDSA section took too much time to make.]

== Notes ==

[I may or may not put a header byte in front of the Schnorr signature. I don't want to, because I think it's redundant, but I'm wondering if it is necessary for consistency.]
[I am shocked at how little material is available for generating Bech32 addresses (and the same goes for Bech32m addresses too)!]

== References ==

[1] - https://github.com/bitcoin/bips/blob/master/bip-0137.mediawiki

[2] - https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm

[edited to correct recID behavior.]

Bump [24 hour limit on consecutive posts should be up by now, according to UTC time.]

So I have mostly figured out what should be done regarding the signing and verification from Taproot addresses. The good news is that BIP340 has already made this a standard saving me the headache of having to re-implement this all over again (not that I want to in the first place).

Despite being a draft, I see it as a net positive to include this signing format for Taproot addresses ahead of time i.e. before wallets even support Taproot addresses yet.

A few notes before I begin the quote of relevant parts:

- Eventually they chose "BIP340/challenge" as the key prefix aka. the tag. So I guess a different tag "BIP-notatether" would be incompatible with that so I drop my signing tag.

- They selected encoding only the x coord of R and P (not that this is relevant to use since I chose (e,s) encoding format), and they chose Y must be the even for P and R. It might not be relevant here since I can also use (e,s) as a signature format, but I am having great difficulty deciding between that or (R,s). I believe that only one of these formats should be used for maximum consistency. [But I do not see wallets placing multiple fields for public keys just to support batch verification.]

- The public key is required for all Schnorr verification schemes. This complicates the message signing/verification UI as "address" is supposed to contain an address, however the verification scheme cannot recover the public key (as achow101 mentioned). These differences might call for making a separate draft just for Schnorr signatures. Personally, I want to refrain from making any decision until I review the BIP137 signatures.


It's too early for my draft to cut off some dead wood from this draft, but I will end this post with a note:

- The purpose of address message signing/verification is to cryptographically prove that a message has come from a specific address. Granted, this is malleable, since the signing isn't technically done with address, but with public keys in the case of both ECDSA and Schnorr, so a legacy address which validates a message implies that its corresponding segwit addresses can also validate it, since they all share the same public key. In the case of Taproot, if somebody wanted to verify that a message indeed came from a taproot address, 'Signature' can be overloaded by concatenating the Schnorr signature [/edit] and public key together like this:

(e,s) or (R,s) || public key

And the public key sent to the verification algorithm. The signature will still be a fixed-size payload. It is true that it destructs the "zero-knowledge" benefit with Schnorr signatures, but this will allow maximum compatibility with ECDSA address verification. After all, hasn't BIP340 itself made tradeoffs of its own to preserve compatibility with ECDSA message generation, such as choosing the parity of Y coordinates?

[edit]:

The truth is, is that you can't verify an address message without general knowledge of the public key. And zero-knowledge signatures such as Schnorr completely disallow for that. Given that it is highly likely that future address types will also make use of Schnorr signatures, and the growing disproportion betwen legacy addresses and the rest of the addresses requires that the community make a choice regarding message signatures now - Do they really want them, or not?

I am hoping that the anwser from the majority of readers here is "yes", since many crypto users do in fact rely on messages (in fact it is one of the ONLY ways to recover a bitcointalk account if you lost access to it, with a staked address - the other being with PGP keys that nobody uses - The Stake Your PGP Key Thread can testify to that).

I have decided that Multisig is too complex in order to feasibly support in this BIP. It just leaves generating/verifying the BIP137 signatures and Schnorr signatures correctly as the only obstacles to overcome for the completion of this rough draft (sans code).

You are right. Above I just tried to give an example, the actual standard should go deeper, however it is not necessary to do too much generalization, user should disclose the standard template of the script she is supplying, it'd be useful for other applications as well, e.g., wallets could use such templates asking for the placeholders from users to generate a script which its type is already decided, somehow.

Why uncompressed keys? Also note that in case of Taproot, OP_CHECKMULTISIG is disabled. See: https://bitcointalksearch.org/topic/replacing-opcheckmultisigverify-with-opchecksigadd-5349148

So, if it will be a new standard, it could be based just on ECDSA operations, where "s=(z+rd)/k" would be the default for legacy, and "s=zd+k" would be the default for Schnorr signatures. That means, the standard could define some things like "Point*number" or "Point+number", then any existing signature could be handled by this kind of format, because any legacy signature is just a relation "k=d*first_number+second_number". That means, by storing Q, R, first_number and second_number, you can express any signature, if you can make sure that it is valid from ECDSA point of view, and if the message is hashed correctly.

Yes, and it should have, if it is going to be used for signing-with-script. There are zillion ways for writing a n-of-m multisig script but there is one neat way to do this:
|0x41[...]||OP_CHECKMULTISIG

A verifier should scan the supplied script to follow the exact definition:

Code:

BYTE * multisig_Script_scanner (BYTE &script){
    u_int len;
    len = (u_int *) script;
    u_ int m; 
    m = (len - 2) / 66 ; // size of ECDSA public key = 65 + 1 stackpush directive=66 
    if (m > MAX_KEYS_ALLOWED || m * 66 + 2 <>  len)  
        return null; // not a valid pubkey list
    if (script[len+1] <> 0xAE // OP_CHECKMulTISIG
       return null;
    if (scipt[2] <>  0x52 ) // OP_1 we accept only 1 of m for now
         return; // should be a multiply of 66 
    int i = 0;
    for ( ; i    if i < m 
      return null; // bad format we need pubkeys with a size descriptor of 0x41
    return (script+3); 
    }  

We should have a series of  public keys beginning with 0x41 as their length descriptor, otherwise it is failed, already. Hereafter, it'd be the validators job to check the supplied signature against all the supplied keys until it finds a match, otherwise it fails.

EDIT: improved the code, covering my own mess  

@pooya87 I will put a more detailed version of your Taproot signature generation step inside the BIP, as soon as I can figure out how to verify the Schnorr signatures.


I guess that this includes specializations for checking for (and verifying) multisig scripts? Not that there is any standard way to make them, and the address field won't accomidate multiple public keys. It's like dealing with P2SH and P2PK mashed together.

And in the case of P2WSH, which can be detected precisely, it will have to unilaterally fail verification if one is encountered.

Pretty much the same thing:
- Message hash could be computed the same way as before (append constant, compute SHA256d)
- Compute k using Tagged hash (instead of RFC6979) by using BIP-notatether as its tag
- Generate signature using Schnorr digital signature algorithm the same way you sign a transaction hash

The important part is the second step.

Exactly. Just drop it along with the whole sign-with-script thing, as far as it is about scripts generally, I think the actual improvement would be including well-formed srcipts with standard format and extracting public keys (e.g. using a simple parser) then succeeding to the rest. It is where standards could help.

I've already discussed it above thread, tho.

I see. So in that case, with it not being a regular signed message, BIP 322 signatures, which are apparently just transactions, cannot even be verified in the same place as everything else. Because their implementations are incongruent - one is a transaction, which would require interested wallets to copy the verification code of Bitcoin Core [no wonder why practically no wallets implement it!], the other has a fixed collection of data fields.