Topic: [DISCUSSION] BIP-notatether-messageverify: Standardizes message verification - page 2. (Read 593 times)

Guys, I am thinking about adding BIP 322 as a fourth detection & code path in the verification algorithm - the motivation would be to support verifying messages from P2[W]SH (without mandating anything on the signature method, so that I don't have to create my own message format), in case people *do* end up using BIP322. Do you agree with this idea?


If I do end up including BIP 322, it will certainly be done by implementing needed parts. I don't want to mess with signet, especially since wallets may not want to mess with a different network just to verify mssages.

[EDIT: I have decided against including P2PK "addresses" as a separate code path because these are actually not addresses (I don't know why I keep calling them that). These can be verified using BIP322 signatures anyway, so their inclusion depends on whether or not the community thinks its a good idea to standardize BIP322 signature verification, just like P2SH.]

---

== 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.

== Motivation ==

The message verification algorithm has only been designed to validate messages from Legacy addresses, since that were 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, but no standardized signing and verification process has been invented for it yet.

The result of this oversight is that some wallets allow you to sign messages form 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 BIPs only attempt to define a new message signing format, and have not gained a large-enough conesnsus for their de facto use over existing signature formats.

== Rationale ==

This BIP does not attempt to define a new message signing format. Instead, it attempts to define the precise algorithms for signing and verifying messages, that is interopable with all of the widely-used message format. The message signing formats which are used only by a tiny minority of wallets will not be standardized in this BIP, to avoid bloating it.

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.
- ECDSA signatures, with P2WSH addresses [used in multisig wallets e.g. Electrum].
- Shnorr signatures, with P2TR (Taproot) addresses.
- BIP 137 signatures.

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. Essentally, it is exactly the same as the current algorithm.]

[TODO figure out what to do with Schnorr signatures.]

=== Message verificaion method ===

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

Then, the public key of the signed message will be deduced from the signature and the message, followed by the RIPEMD160 hashing of the public key into the address has. [Again, the exact algorithm has to be specified here later even though it's not going to change.]

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

- If the address begins with '1', assume it is a P2PKH aka Legacy address, encode the address hash using Base58, and compare it with the read address. If they match, succeed verifcation, else fail.
- Else, if the address begins with '3', assume it is P2WPKH-P2SH, encode the address hash using Base58, and compare it with the read address. If they match, succeed verificaiton, else fail.
[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.
-- Read the first byte of the witness program, which is located after the witness version 0 (i.e. 'q' in Bech32)
-- If the first byte is 0x20, then it is a P2WPKH address:
--- Ensure that the rest of the witness program is 32 bytes long.
--- Attempt to construct a P2WPKH address from the generated public key. If this succeeds, succeed verification. Else, fail verification.
-- If the first byte is 0x14, then it is a P2WSH address:
--- Ensure that the rest of the witness program is 20 bytes long.
--- Attempt to construct a P2WSH address from the generated public key. If this succeeds, succeed verification. Else, fail verification.
[XXX P2WSH is a script hash, so without the script, the pubkey is useless. Should I only detect P2WSH multisig, and defer everything else to BIP322?]
-- If the first byte is anything else, fail verification.
- [Else if it is bc1p, it is a Taproot address, but I have to study Schnorr signatures some more to see how message signing would even work with that.]
- Else, if the prefix matches that of a BIP137 signature, attempt to use the BIP137 verification algorithm on the address hash. If the addresses match, succeed verifcation, else fail.
- Else, fail verification.

== Notes ==

BIP 322 signatures might be supported here (see the beginning of this post).

P2SH, P2WKPH-P2SH, and P2WSH-P2SH addresses cannot be distinguished from each other using the '3' prefix alone, generation of the latter two addresses will only identify whether an address is positively that address type. Without BIP322, there is no way to conclude that an address is NOT one of the above types, or if an address is a generic P2SH address that is not one of the other specializations.

Similarly, P2PK is not an address type, so cannot be directly supported in a message signing format that deals with addresses.

It is almost used in Signet. Almost, because there is one difference: in Signet, you sign blocks. Here, you sign messages. But otherwise, it is almost identical, so almost ready implementation is already created in Bitcoin Core. As long as BIP-322 is not yet implemented, there are two options:
1) implement needed parts
2) hack the signet
And currently, you can see that all official signet blocks can prove that signing some 1-of-2 multisig address is possible. The only drawback of using "hack the signet" solution here and now, is that you have to mine a block to get a valid solution for "submitblock".

BIP 322 goes beyond message signing as its agenda is to cover a proof of fund availability which other than not being achievable in some (very important) cases like HTLC, it also suffers from a confused definition:
A signed and verified message is typically timeless, i.e., it doesn't expire ever, Alice can sign such a message and have it proven by some verifier, being credited somehow because of her funds, while at the same time she is publishing a tx, spending the funds, and materializing the credit.

So, such a 'proof' is no proof, not a meaningful one, even susceptible to be misleading. It is an over utilization and falls short of compatibility with bitcoin general design principles, where less utility is better than vague or confusing ones, bitcoin is no Ethereum, we don't brag with the portfolio of problem domain we (loosely) cover.

It is why I think Greg Maxwell's comment in support of such an expanded problem domain, is basically wrong and not compatible with his usual hesitation for such practices.

On the other hand, for a more humbly defined problem domain, like when Alice wants to prove her access to a secret without revealing it and this secret is kinda linked to a bitcoin public key which gives Alice an anonymous identity somehow: Like when bitcoitalk users sign messages with their profile key, or when Alice is just saying: I'm the one who made this donation or the person who has/had a call on the address you deposited to etc. It is straightforward for legacy P2PKH addresses, obviously, but for P2SH, p2WSH, … in their most general form it'd be a more efficient way for all the parties to use their human knowledge and spot the appropriate address out of the disclosed script, and go through the trivial process.

In case they need to do it using automated techniques, there is a second option: narrow down the domain to well-formed, standardized script templates for sniffing out the keys and succeed with the basic procedure. The rule of thumb is always: avoid coding as much as possible by trading off costs against the gains.

Going beyond the above recommended specs not only adds restrictions but also is error-prone because either, wallets need to simulate bitcoin interpreter, or the latter has to add such a functionality and support wallets via RPC, whatever be the case we are expanding the code/attack/failure surface for almost nothing.

Back to your message,


A lot of good links in that mailing list thread, but I think this one is going to be the most helpful - https://github.com/brianddk/bips/blob/legacysignverify/bip-0xyz.mediawiki . I'll study this draft BIP and see what I can get from it.

---

OK, so I apparently forgot that Taproot addresses do not even use ECDSA signatures in the first place. So I'm going to rule those out of the BIP.
[EDIT: since I'm already including BIP 137 signature detection in this method, I suppose I should construct this verification method like this:
- Detects one of the following three types of signature:
-- ECDSA signature
-- Schnorr signature (so that Taproot gets verified in a second code path)
-- BIP 137 signature (ditto)
END OF EDIT]

According to @achow101, guessing the signature type from the prefix still makes ambiguous address types, so I'll have to figure out a different strategy to identify P2WPKH-P2SH and P2WPKH (P2SH and P2WSH have already been stiken out of this BIP).

It does, that's the point. BIP 322 allows signing with any script, as it runs the script interpreter when verifying.

Bad assumption. P2SH addresses can include any script, not just segwit.

Bad assumption. P2WSH addresses also begin with bc1q.

No, don't do that. Do not mix things that are used for schnorr signatures with generating ECDSA signatures. Note that the verification process for Taproot addresses will be different to the verification process of the other ones that use ECDSA because Schnorr does not allow for pubkey recovery. Since a Taproot address encodes a pubkey directly, you can do normal verification, but it means that there is no shared code between verifying Taproot and verifying everything else.

Also, this doesn't work for Taproot script path spends, and addresses which are script path spend only.

That depends on how clean or ugly the code already is. If we are dealing with a clean loosely coupled code, it is very easy and smooth to change different parts of it just like replacing a cog in a big machine.
I don't know any C++ but signature verification is already in separate methods and GenericTransactionSignatureChecker seems to be replaceable.

You are overthinking it. Only small modifications need to be made in the interpreter to verify the given script. You just evaluate it as if you were evaluating a transaction only treating certain OP codes differently meaning OP_CHECK(MULTI)SIG(VERIFY/ADD) computes hash of the message instead of tx. Multi-sigs return how many more signatures were missing. OP_CLV acts as OP_NOP, etc. Any complication in script evaluation already taken care of by the existing code.

Since this would require a new message format and @NotATether pointed out he wants to keep it Informational, I think I should stop further expansion on this idea.

Sorry, i made little mistake. I just remember 1st byte in witness program doesn't refer to witness version, but refer to length of witness program (0x0014 for P2WPKH). But IIRC Bech32 specification doesn't include length of witness program to generate Bech32 address.

@ETFBitcoin:

It's a good idea. Does this mean the witness version is technically counted as part of the witness program?

Why don't you check bc1q followed by 38 ASCII character to determine whether an address is P2WPKH? BIP 141 clearly state this.


Don't forget 20 bytes include q (in bc1q) which is witness version and the rest 19 bytes represent 38 ASCII character.

I just read that P2SH and P2WSH addresses are hashed from the redeem script and not a public key. That's going to throw everything out of course because the ECDSA depends on keypairs to work properly.

That is to say, verifying messages from P2SH addresses may not be possible at all.

There's two factors in me making this decision:

1) They are not hashed from a public key, so not only can't these addresses be verified, but we also can't sign a message with them in the first place. Yes, in scripts like Multisig, there are private keys involved, but without defining a new format [which I am trying to refrain from doing to avoid another BIP-322[1]], it is impossible to retrieve them from the redeem script.
2) Almost no wallet has ever supported the generation of P2SH/P2WSH address, wtith the exception for multisig addresses. Generally, these had to be constructed manually.

---
[1] The reason I am abstaining from defining a new format is to attempt to avoid making a BIP that is either stuck in Draft for years (BIP 322 - I'm not even sure if this supports signing from P2[W]SH) or is Final but nobody uses (BIP 137 - I heard that Sparrow wallet can verify BIP 137 signatures but that is just a drop in the bucket).

---

I believe you're thinking in terms that a new message format would definitely be needed to enable the signing of messages from these "edge case" addresses e.g. P2SH and also Mutlisig, "send funds to the next block reward" - type of addresses (I forgot the script opcode that does that but I read it in one of these threads). I agree, but from a practical point of view, I can't shove all this in one BIP - and in particular I cannot define a new message format for the reason above, so in this BIP I chose to tackle only the problem of verifying all address types that can be generated from a public key.

The nice thing about Informational BIPs is that they can instantly be made up-to-date by making another BIP that supersedes it. They only have an "Active" status, unlike Standards Track and Process which both have a myriad of statuses.

@bitmover I will come back to your comment later.

So, the weird idea of 'signing with scripts' is old enough to make people confused. It is not good practice (check my posts, above thread). the only way would be implementing something such as 'script type' for the verifier, and go through the following steps:
1- verify the disclosed script against the P2SH.
2- verify the fitness of the actual script with the claimed script type.
3- Extract the address hash from the standardized place within the script.
4- go through the normal verification.

Note that it brings the specification from "generally signing with scripts" down to earth where we are able to do this just for well-formed, standardized scripts.

Hello NotATether.

This was my first bitcointalk post. I was trying to recover some altcoin airdrop for bitcoin holders and I needed to sign a message. Then I discovered it was not possible.

By the time, in 2018, nullius gave me some technical details about the problems for creating this standard.

Take a look, it might help you:


This is also interesting. As you sign with a private-public key pair (and not with an address), there should be a more generic solution.

I'm afraid, it doesn't, you missed the point.
As I said above, it needs the ugly, infeasible practice of interpreting the script by the verifier using sophisticated techniques beyond the sopes of any existing or future wallet software.

More specifically, putting yourself in the shoes of a dev who wants to support this use case, you'd realize that you need to somehow virtually execute the given script (on a virtual stack, I suppose) to answer a few questions:
1- How many branches are involved?
2- Which addresses are involved in each branch?
3- Except for reasonably set (what is reasonable BTW?) time-Locks, pick the addresses which are eligible for claiming this output by supplying trivial data (not a preimage of a hash, for instance) for their branch to be reached. If an address is  able to unilaterally unlock this branch,  now or some practical future, put it in the special list of "rightful addresses", i.e., people who are able to claim the funds, some when.
4- Does the pubkey of the signature match any of the members of above list?

It is because answering the final question is not trivial and needs diving in semantics of the script.

The only reasonable solution for the owners of such utxos is to rely on the counterparty's human intelligence by Simply signing a message with their actual address which is included in the script, convincing them by disclosing the script with fingers crossed.


Edit:
Taproot scripts have an edge, a huge one, as a candidate for this use:
The owner supplies a path to its branch and trivial data which brings us to her desired branch and all we have to do is to again 'virtually' execute this branch for deciding whether the supplied public key is unilaterally eligible for claiming the funds?
A same optimization is possible for the legacy scripts, but nothing would help the inherent dependency of an ill-defined piece of software.

EDIT 2: I just checked BIP 322 which, thanks God, is in draft stage, with the same purpose of covering something called "proving fund availability" which I'll address below thread.

Actually it makes perfect sense. When you sign a message you are actually proving ownership of any balance that is locked behind a certain locking script. In other words you claim that you can spend that output.

If you sign a message using public key in OP_CLV OP_DROP OP_CHECKSIG you prove you can spend this output.
If you sign a message from pubkey #1 in OP_2 OP_CHECKMULTISIG you prove that you are one of the 2 persons who can spend this output.

Signing messages with P2SH addresses, doesn't make any sense, it is called metaphorically, and not literally, an address. Disclosing the script behind P2SH addresses wouldn't help too, as it is infeasible to parse/interpret the script to extract conventional, true address(es) for choosing one (which one if there are many?) to be verified against the public key, before succeeding to verification of the signature, not to mention the privacy/security consequences.

That's the problem with P2SH, the redeem script can not be fetched from the address since it only includes the hash of it. So the redeem script has to either be guessed (like in case of wrapped SegWit) or be included in the signature+message combo. The later would significantly change the proposal since BIP-137 doesn't include the scripts.

It does not make much sense for me to update BIP 137. It is a Standards Track BIP whereas I plan mine to be an Informational BIP where a consensus is not required as I'm not creating or modifying signing formats. I don't expect every wallet to drop their original verification methods and adopt this one, as a Standards Track BIP would require them to, but I'd be happy if a majority do, especially online ones that Brainwallet website.

Besides, BIP 137 is already in the Final state, so I'd have to create a second BIP anyway in order to (what they call) "replace" it. I am only going to change the verification algorithm - despite about half of it remaining the same.


I'll probably include the first as an additional test for '1' addresss, and the second as an additional test for '3' addresses - that is, for '1' addresses I attempt P2PKH followed by P2PK, and for '3' addresses I attempt P2WPKH-P2SH followed by P2SH.

I am assuming there was a standardized way to create P2SH addresses before segwit, that maybe requires the redeem script to encode, which can be fetched from the Address in the signed message anyway.

If the algorithm and the format are not going to change then it may be best to update the existing BIP-137 that already standardized message signing for P2PKH, P2WPKH-P2SH and P2WPKH.

Otherwise what is your solution to other cases that could be common but not covered here such as P2PK outputs or any other legacy P2SH script types like a simple lock-time script or multi-signature addresses or P2TR that is not using the simple single key spending route?

Amendments:

(This will be regularly cleared as I make new rough drafts of the BIP)

- Message signing as well as message verification will be clearly defined.

- I will not implement BIP322 signature verification. The reason is that those messages have to be signed and verified under completely different circumstances (as a transaction, not as a data format), therefore it is impossible to include it along with all the other verification types in the same method. This also include Multisig signatures, although it is technically possible, it will make this BIP unnecessarily complicated.
- Should implement a code path for verifying P2PK addresses (we have the length to differentiate it from P2PKH, so this is doable) Thrown out
- With the current message format it is impossible to sign/verify P2SH addresses. This is not an amendment just a note, since it wasn't in the rough draft in the first place. Thrown out
- P2WSH addresses will not be verified, in accordance with the decision to scrap BIP 322. I will still detect P2WPKH addresses properly to avoid any P2WSH addresses from slipping through.

The final codepath for P2WPKH address will look like this:


- A blind generation test for P2WPKH-P2SH address is being used, since differentiation from P2SH address is otherwise not possible (i.e. you can't conclusively say that this is not a *-P2SH address).

- BIP 137's header bytes are adopted by this proposal because they overlap with the legacy signing format and also what I was trying to propose. Since the expected idea-apocalypse hasn't come, I will most likely do the same for Taproot addresses, to future-proof the standard.

- I cannot support Taproot multi-key verification, without radically changing the message signing format by adding multiple fields for *addresses* (and the corresponding public keys concatenated). This would make Schnorr signature sizes arbitrary, and leaves the risk of vulnerabilities from incorrect implementations. People who want this in practice are better off supporting BIP 322's efforts instead.

This is a self-moderated thread, for dicussion about the workability of the standardization of the message verification process below. It will be locked when the draft is submitted to the mailing list, and a new thread for the draft will be created.

---

BIP-notatether-messageverify is the temporary name I have given to the BIP I'm drafting that is supposed to standardize the message signature verification method (and in particular, officially recognize segwit signed messages at long last). The rough idea I have devised for it is given below. This is not the draft.

This revision is obsolete, the newest revision is always available here.

---

== 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.

== Motivation ==

The message verification algorithm has only been designed to validate messages from Legacy addresses, since that were 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, but no standardized signing and verification process has been invented for it yet.

The result of this oversight is that some wallets allow you to sign messages form 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 Segwit-type addresses (Nested, Native, and Taproot). The existing BIPs only attempt to define a new message signing format, and have not gained a large-enough conesnsus for their de facto use over existing signature formats.

== Rationale ==

This BIP does not attempt to define a new message signing format. Instead, it attempts to define the precise algorithms for signing and verifying messages, that is interopable with all of the widely-used message format. The message signing formats which are used only by a tiny minority of wallets will not be standardized in this BIP, to avoid bloating it.

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 create the ECDSA signature from the private key and message, and place it into the signature category as usual. However, in the Address section, the address that the user has selected to sign the message with will be placed inside there.

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

=== Message verificaion method ===

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

Then, the public key of the signed message will be deduced from the signature and the message, followed by the RIPEMD160 hashing of the public key into the address has. [Again, the exact algorithm has to be specified here later even though it's not going to change.]

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

- If the address begins with '1', assume it is a P2PKH aka Legacy address, encode the address hash using Base58, and compare it with the read address. If they match, succeed verifcation, else fail.
- Else, if the address begins with '3', assume it is P2WPKH-P2SH, encode the address hash using Base58, and compare it with the read address. If they match, succeed verificaiton, else fail.
- Else, if the address begins with 'bc1q', assume it is P2WPKH, encode the address using Bech32, with version 'q', and compare it with the read address. If they match, succeed verification, else fail.
- Else, if the address begins with 'bc1p', assume it is a P2TR aka Taproot address, encode the address using Bech32m, with version 'p', and compare it with the read address. If they match, succeed verification, else fail.
- Else, if the prefix matches that of a BIP137 signature, attempt to use the BIP137 verification algorithm on the address hash. If the addresses match, succeed verifcation, else fail.
- Else, fail verification.

== Notes ==

I have elected not to support BIP322 message signing format because I did not get an answer on the mailing list on whether BIP322 is used in any walets at all. If there is provable evidence that it is, this BIP might be amended to verify this message format as well.

---

Local rules: No flame wars like in some of the other threads here. This thread will be posted to the mailing list, so I must keep it spot clean. All other comments are welcome.