[bitcoin-dev] Zero-knowledge proofs e.g. Schnorr are incompatible with address signing without compromise

[Ali Sherief <ali@notatether.com>]

Here is an except of the BIP-notatether-messageverify thread, where I contemplate how to implement address/message signing support for Taproot i.e. Schnorr signatures, in my post at:

https://bitcointalk.org/index.php?topic=5407517.msg60642144#msg60642144

(stripped of bbcode formatting)

======

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.

--------

==== Default Signing ====

Input:
* The secret key ''sk'': a 32-byte array
* The message ''m'': a 32-byte array
* Auxiliary random data ''a'': a 32-byte array

The algorithm ''Sign(sk, m)'' is defined as:
* Let ''d' = int(sk)''
* Fail if ''d' = 0'' or ''d' ≥ n''
* Let ''P = d' · G''
* Let ''d = d' '' if ''has_even_y(P)'', otherwise let ''d = n - d' ''.
* Let ''t'' be the byte-wise xor of ''bytes(d)'' and ''hash<sub>BIP0340/aux</sub>(a)''<ref>The auxiliary random data is hashed (with a unique tag) as a precaution against situations where the randomness may be correlated with the private key itself. It is xored with the private key (rather than combined with it in a hash) to reduce the number of operations exposed to the actual secret key.</ref>.
* Let ''rand = hash<sub>BIP0340/nonce</sub>(t || bytes(P) || m)''<ref>Including the [https://moderncrypto.org/mail-archive/curves/2020/001012.html public key as input to the nonce hash] helps ensure the robustness of the signing algorithm by preventing leakage of the secret key if the calculation of the public key ''P'' is performed incorrectly or maliciously, for example if it is left to the caller for performance reasons.</ref>.
* Let ''k' = int(rand) mod n''<ref>Note that in general, taking a uniformly random 256-bit integer modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2<sup>256</sup>'' that this bias is not observable (''1 - n / 2<sup>256</sup>'' is around ''1.27 * 2<sup>-128</sup>'').</ref>.
* Fail if ''k' = 0''.
* Let ''R = k' · G''.
* Let ''k = k' '' if ''has_even_y(R)'', otherwise let ''k = n - k' ''.
* Let ''e = int(hash<sub>BIP0340/challenge</sub>(bytes(R) || bytes(P) || m)) mod n''.
* Let ''sig = bytes(R) || bytes((k + ed) mod n)''.
* If ''Verify(bytes(P), m, sig)'' (see below) returns failure, abort<ref>Verifying the signature before leaving the signer prevents random or attacker provoked computation errors. This prevents publishing invalid signatures which may leak information about the secret key. It is recommended, but can be omitted if the computation cost is prohibitive.</ref>.
* Return the signature ''sig''.


==== Verification ====

Input:
* The public key ''pk'': a 32-byte array
* The message ''m'': a 32-byte array
* A signature ''sig'': a 64-byte array

The algorithm ''Verify(pk, m, sig)'' is defined as:
* Let ''P = lift_x(int(pk))''; fail if that fails.
* Let ''r = int(sig[0:32])''; fail if ''r &ge; p''.
* Let ''s = int(sig[32:64])''; fail if ''s &ge; n''.
* Let ''e = int(hash<sub>BIP0340/challenge</sub>(bytes(r) || bytes(P) || m)) mod n''.
* Let ''R = s · G - e · P''.
* Fail if ''is_infinite(R)''.
* Fail if ''not has_even_y(R)''.
* Fail if ''x(R) &ne; r''.
* Return success iff no failure occurred before reaching this point.

For every valid secret key ''sk'' and message ''m'', ''Verify(PubKey(sk),m,Sign(sk,m))'' will succeed.

-------

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 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?

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 between 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?

========

Essentially, zero-knowledge proofs such as Schnorr are not compatible with address message signing - the public key cannot be retrieved from the address or the signature, so the address does not actually prove the authenticity of a Schnorr signature. That's why the public key is required as an input in the first place.

In order to make it compatible with the address signing mechanism, the zero-knowledge part would have to be sacrificed in my BIP, or else a completely separate message signing format just for Taproot would be required (which, in my view, is redundant - there is already the draft BIP322 which can verify anything and everything, but nobody is implementing that, just like BIP340).