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

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

[Ali Sherief]

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

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

[Pieter Wuille]

------- Original Message -------
On Thursday, July 28th, 2022 at 3:27 AM, Ali Sherief via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

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

Yes, that's an intentional design choice in BIP340, see note 5: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#cite_ref-5-0. The choice is either batch verifiability or public key recovery.

I regret ever using public key recovery when introducing the old legacy message signing scheme. It should just have used script signatures like BIP322 proposes.

> 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

You can avoid relying on public key recovery, and include the public key + BIP340 signature in the encoded signature.

> (which, in my view, is redundant - there is already the draft BIP322 which can verify anything and everything, but nobody is implementing that

I think it would be much better if people would cooperate to get BIP322 to move forward than to keep inventing other formats. It's the obvious solution in my opinion: not restricted to single-key policies, compatible with every script type, and trivially extensible to future schemes.

> , just like BIP340).

How so? Every taproot compatible wallet has a BIP340 implementation.

Cheers,

--
Pieter

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

[Ali Sherief]

> Yes, that's an intentional design choice in BIP340, see note 5: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#cite_ref-5-0. The choice is either batch verifiability or public key recovery.

The way I understood the BIP, was that a user can do batch recovery or single-key recovery. Can you explain how it is possible to recover a public key from a single-key signature, because a few days earlier on the BIP-notatether-messageverify thread I was told (I think it was achow) that Schnorr doesn't allow for public key recovery.

At any case, I was already planning on just concatenating the public key after the signature (the other option I was thinking of, appending it after the Taproot address, is quite unruly in my opinion).

> I think it would be much better if people would cooperate to get BIP322 to move forward than to keep inventing other formats. It's the obvious solution in my opinion: not restricted to single-key policies, compatible with every script type, and trivially extensible to future schemes.

This is why I especially tried to avoid making a new format - My BIP is strictly an Informational one. That strategy worked pretty well up to now, but now I find myself forced to make a small concession in the design to support the verification of Taproot address. But I'm glad it's quite trivial as appending a single variable. So at least this BIP won't be an obstacle to any such effort.

[Besides, since I'm also planning on detecting BIP137 in the verification methods, I can assume the Signature field contains arbitrary data.]

> > , just like BIP340).
>
>
> How so? Every taproot compatible wallet has a BIP340 implementation.

I guess I made an assumption, since almost all of the wallets I have seen did not have a sign message feature, not even for legacy addresses.

- Ali

------- Original Message -------
On Thursday, July 28th, 2022 at 3:27 PM, Pieter Wuille <bitcoin-dev@wuille.net> wrote:


> ------- Original Message -------
> On Thursday, July 28th, 2022 at 3:27 AM, Ali Sherief via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:
>
> > 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.
>
>
> Yes, that's an intentional design choice in BIP340, see note 5: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#cite_ref-5-0. The choice is either batch verifiability or public key recovery.
>
> I regret ever using public key recovery when introducing the old legacy message signing scheme. It should just have used script signatures like BIP322 proposes.
>
> > 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
>
>
> You can avoid relying on public key recovery, and include the public key + BIP340 signature in the encoded signature.
>
> > (which, in my view, is redundant - there is already the draft BIP322 which can verify anything and everything, but nobody is implementing that
>
>
> I think it would be much better if people would cooperate to get BIP322 to move forward than to keep inventing other formats. It's the obvious solution in my opinion: not restricted to single-key policies, compatible with every script type, and trivially extensible to future schemes.
>
> > , just like BIP340).
>
>
> How so? Every taproot compatible wallet has a BIP340 implementation.
>
> Cheers,
>
> --
> Pieter

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

[Pieter Wuille]

------- Original Message -------
On Thursday, July 28th, 2022 at 11:51 AM, Ali Sherief <ali@notatether.com> wrote:

> The way I understood the BIP, was that a user can do batch recovery or single-key recovery. Can you explain how it is possible to recover a public key from a single-key signature, because a few days earlier on the BIP-notatether-messageverify thread I was told (I think it was achow) that Schnorr doesn't allow for public key recovery.

No, BIP340, in its design decisions, had to choice to either support public key recovery, or support batch validation. We chose to support batch validation for a variety of reason. BIP340 does not in any way support key recovery.

> > > , just like BIP340).
> >
> > How so? Every taproot compatible wallet has a BIP340 implementation.
>
>
> I guess I made an assumption, since almost all of the wallets I have seen did not have a sign message feature, not even for legacy addresses.

I'm not talking about sign message, I'm talking about BIP340 for the purpose of transaction signing, as it's the signature scheme used in BIP341/BIP342.

My point being: for any prospective message signing feature, if the wallet supports taproot signing, they inevitably already have code to produce BIP340 signatures. If they don't support taproot signing, then message signing for it is irrelevant.

Cheers,

--
Pieter