path: root/bd/080a53c4e52c1a351248dd40f6b8c9dadc67b8

Return-Path: <ali@notatether.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id EBA01C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 28 Jul 2022 07:36:00 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 3583C4149D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 28 Jul 2022 07:36:00 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 3583C4149D
Authentication-Results: smtp4.osuosl.org; dkim=pass (2048-bit key,
 unprotected) header.d=notatether.com header.i=@notatether.com
 header.a=rsa-sha256 header.s=protonmail header.b=r/vCb8eO
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.102
X-Spam-Level: 
X-Spam-Status: No, score=-1.102 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, BITCOIN_OBFU_SUBJ=1, DKIM_SIGNED=0.1,
 DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1,
 SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id w4kDu5nn7S5R
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 28 Jul 2022 07:35:58 +0000 (UTC)
X-Greylist: delayed 00:08:34 by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 6AE28402C5
Received: from mail-4327.protonmail.ch (mail-4327.protonmail.ch [185.70.43.27])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 6AE28402C5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 28 Jul 2022 07:35:57 +0000 (UTC)
Date: Thu, 28 Jul 2022 07:27:02 +0000
Authentication-Results: mail-4321.protonmail.ch;
 dkim=pass (2048-bit key) header.d=notatether.com header.i=@notatether.com
 header.b="r/vCb8eO"
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=notatether.com;
 s=protonmail; t=1658993230; x=1659252430;
 bh=i65WE1O69eMsOLkIMKvCMNHuoQCSb1+INhEROMCoe4Q=;
 h=Date:To:From:Reply-To:Subject:Message-ID:Feedback-ID:From:To:Cc:
 Date:Subject:Reply-To:Feedback-ID:Message-ID;
 b=r/vCb8eONgtSS7BjxjsLhLemHMHukHQj9aMRNqHBayyXikR66+mjypK4KbMDmSd3B
 tUS+BtXRvPbNqDy4VsjhE7E+UUz/8qQbi0PsxqhkyTJYJIzlXKvAuvr4oNttOiLAY2
 3Ywyhy9opnHayh4OIx3Ecb4/PCc7GsIQnzurckl/IgrL68z3Bi/i5sRE3dKp4bcdHj
 akjpJCKBK+zItWdG/WfgZWJCCbJ+XUxDEBjo6n6Qnko08eKbAlbMxTVWhcT7RFDmZC
 nd0yOd9GUOaunHL6Nia5qu33zaPI7uVtFyeQXxkA/rXHBjuEVahrT+GpVcO4gRvgxq
 B0HqtyTnWP4kg==
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
X-Mailman-Approved-At: Thu, 28 Jul 2022 10:14:49 +0000
Subject: [bitcoin-dev] Zero-knowledge proofs e.g. Schnorr are incompatible
	with address signing without compromise
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Thu, 28 Jul 2022 07:36:01 -0000

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