From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id EBA01C002D for ; 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 ; 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 ; 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 ; 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" From: Ali Sherief Reply-To: Ali Sherief Message-ID: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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' ≥ 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 ''hashBIP0340/aux= (a)''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.. * Let ''rand =3D hashBIP0340/nonce(t || bytes(P) || m)''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.. * Let ''k' =3D int(rand) mod n''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 ''2256'' that this bias is not observable (''1 - n /= 2256'' is around ''1.27 * 2-128'').. * 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(hashBIP0340/challenge(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, abortVe= 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.. * 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 ≥ p''. * Let ''s =3D int(sig[32:64])''; fail if ''s ≥ n''. * Let ''e =3D int(hashBIP0340/challenge(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) ≠ 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).