Date: Thu, 28 Jul 2022 07:27:02 +0000
To: "bitcoin-dev@lists.linuxfoundation.org"
 <bitcoin-dev@lists.linuxfoundation.org>
From: Ali Sherief <ali@notatether.com>
Reply-To: Ali Sherief <ali@notatether.com>
Message-ID: <bG2Fk0bM_4lbwijBwZRiGgCAmktVOFSY5vR5k1D7QSc8imn9NWXxfOLPgMl5p22vfAPDHeuEA_p6TDhU7qGFoVmZok57RzA9rEV1LJzHpsM=@notatether.com>
Feedback-ID: 34210769:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: [bitcoin-dev] Zero-knowledge proofs e.g. Schnorr are incompatible
	with address signing without compromise
Precedence: list

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

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

(stripped of bbcode formatting)

=3D=3D=3D=3D=3D=3D

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 alrea=
dy made this a standard saving me the headache of having to re-implement th=
is 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 f=
ormat 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 rele=
vant 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 betwee=
n that or (R,s). I believe that only one of these formats should be used fo=
r maximum consistency. [But I do not see wallets placing multiple fields fo=
r public keys just to support batch verification.]

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

--------

=3D=3D=3D=3D Default Signing =3D=3D=3D=3D

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' =3D int(sk)''
* Fail if ''d' =3D 0'' or ''d' &ge; n''
* Let ''P =3D d' =C2=B7 G''
* Let ''d =3D d' '' if ''has_even_y(P)'', otherwise let ''d =3D 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 comb=
ined with it in a hash) to reduce the number of operations exposed to the a=
ctual secret key.</ref>.
* Let ''rand =3D hash<sub>BIP0340/nonce</sub>(t || bytes(P) || m)''<ref>Inc=
luding the [https://moderncrypto.org/mail-archive/curves/2020/001012.html p=
ublic key as input to the nonce hash] helps ensure the robustness of the si=
gning algorithm by preventing leakage of the secret key if the calculation =
of the public key ''P'' is performed incorrectly or maliciously, for exampl=
e if it is left to the caller for performance reasons.</ref>.
* Let ''k' =3D int(rand) mod n''<ref>Note that in general, taking a uniform=
ly random 256-bit integer modulo the curve order will produce an unacceptab=
ly biased result. However, for the secp256k1 curve, the order is sufficient=
ly 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' =3D 0''.
* Let ''R =3D k' =C2=B7 G''.
* Let ''k =3D k' '' if ''has_even_y(R)'', otherwise let ''k =3D n - k' ''.
* Let ''e =3D int(hash<sub>BIP0340/challenge</sub>(bytes(R) || bytes(P) || =
m)) mod n''.
* Let ''sig =3D bytes(R) || bytes((k + ed) mod n)''.
* If ''Verify(bytes(P), m, sig)'' (see below) returns failure, abort<ref>Ve=
rifying the signature before leaving the signer prevents random or attacker=
 provoked computation errors. This prevents publishing invalid signatures w=
hich 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''.


=3D=3D=3D=3D Verification =3D=3D=3D=3D

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 =3D lift_x(int(pk))''; fail if that fails.
* Let ''r =3D int(sig[0:32])''; fail if ''r &ge; p''.
* Let ''s =3D int(sig[32:64])''; fail if ''s &ge; n''.
* Let ''e =3D int(hash<sub>BIP0340/challenge</sub>(bytes(r) || bytes(P) || =
m)) mod n''.
* Let ''R =3D s =C2=B7 G - e =C2=B7 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 cryptographical=
ly 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 whic=
h validates a message implies that its corresponding segwit addresses can a=
lso validate it, since they all share the same public key. In the case of T=
aproot, if somebody wanted to verify that a message indeed came from a tapr=
oot address, 'Signature' can be overloaded by concatenating the Schnorr sig=
nature 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 s=
till be a fixed-size payload. It is true that it destructs the "zero-knowle=
dge" benefit with Schnorr signatures, but this will allow maximum compatibi=
lity with ECDSA address verification. After all, hasn't BIP340 itself made =
tradeoffs of its own to preserve compatibility with ECDSA message generatio=
n, such as choosing the parity of Y coordinates?

The truth is, is that you can't verify an address message without general k=
nowledge of the public key. And zero-knowledge signatures such as Schnorr c=
ompletely disallow for that. Given that it is highly likely that future add=
ress types will also make use of Schnorr signatures, and the growing dispro=
portion between legacy addresses and the rest of the addresses requires tha=
t the community make a choice regarding message signatures now - Do they re=
ally want them, or not?

=3D=3D=3D=3D=3D=3D=3D=3D

Essentially, zero-knowledge proofs such as Schnorr are not compatible with =
address message signing - the public key cannot be retrieved from the addre=
ss or the signature, so the address does not actually prove the authenticit=
y 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 ver=
ify anything and everything, but nobody is implementing that, just like BIP=
340).