From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id A7A5640B for ; Sun, 5 Aug 2018 14:34:14 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-io0-f169.google.com (mail-io0-f169.google.com [209.85.223.169]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id E3479623 for ; Sun, 5 Aug 2018 14:34:13 +0000 (UTC) Received: by mail-io0-f169.google.com with SMTP id v26-v6so8874178iog.5 for ; Sun, 05 Aug 2018 07:34:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream.io; s=google; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=d5Wv3HlM0hfmTDeeVNp2K15eCZwciOP9rFyEYfXTDwE=; b=YmaQJtQ3cSOZptKKoJf4vaa8MLY0pMaUxc7az+8sn9leEMWcwtjl3FPVoVQ57FTPlT UFtP7kz6cx6kSLSDAqhn44mCIQMmav64tbdkc7WsT81s9MI6qT6Fl5iM9DZWdZ7jzqmy Me10FHvNbmwYp9D4CTNXLiSN+67Ax7YMud9oU= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=d5Wv3HlM0hfmTDeeVNp2K15eCZwciOP9rFyEYfXTDwE=; b=UunR5JOt5aXZinn+AWhfH8js0O8N2mN3ZMow2G6anraVVd3KMdwm90ycrVQgRUFohX vvuCebw+jOix4Ig/dnlE0j3Ajl/fidksQdYzOFcRdx3QYqh9unFV3RnGKqiAp8hzXSX4 aUVwu1edLMicWzfaJtZ2kIObxE8si9G7n9ixX2/b5iS2eU/Z+HyUThZawxBiJxUeawV0 YGSM+v0iLIz8cs0zE4QcDdBnKLzx+KVJcFHEh9HfNyoD3b9gEqby+1FwAMBn2sEFVjKT ZBxs5wFzh7cy+Uc6UGc8pVWT2TaXeoy9TFY9b0uBwA0PWFfLpu3pw/PyllDDBq61bvzx OxXw== X-Gm-Message-State: AOUpUlGWSNGtfEUO9e/Jc2YlK0y4cicL267ci9HqipWTrNtw3AlBK/Ie EyI05ZPzsLu9ixl0pkvCD4SnhXDwWccJ5nbx3vj5hg== X-Google-Smtp-Source: AA+uWPxlZV74dQhr+lTUP9hnRB6aea1Mea/S6hsf+OpZQaYuW4e+txJUOekoAkfm5fm2HwKFnzBLSBfhMga3gVXxc2w= X-Received: by 2002:a6b:5208:: with SMTP id g8-v6mr12831311iob.60.1533479653169; Sun, 05 Aug 2018 07:34:13 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:a02:6949:0:0:0:0:0 with HTTP; Sun, 5 Aug 2018 07:33:52 -0700 (PDT) In-Reply-To: References: From: "Russell O'Connor" Date: Sun, 5 Aug 2018 10:33:52 -0400 Message-ID: To: Pieter Wuille , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000ff7b700572b10d19" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] Schnorr signatures BIP X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 05 Aug 2018 14:34:14 -0000 --000000000000ff7b700572b10d19 Content-Type: text/plain; charset="UTF-8" Over chat it has been pointed out to me that computing the non-quadratic residue is not the same cost as computing a quadratic residue. As pointed out in footnote 7 of the the proposed BIP, c^((p+1)/4) is always a quadratic residue and must be negated to find the non-quadratic residue. In light of this, I revise my proposed change to make the verification equation R + sG + eP = 0. (by 0 in the equation above I mean the identity element for the (+) operation, which is the point at infinity.) This equation is suitable for batch verification. This equation is clearly written as a linear combination that doesn't use negation. In most implementations, equality comparison tests are implemented by subtraction and a comparison with zero. By writing the verification equation this way, we clearly see that only the comparison with zero test is needed. For single signature verification the check becomes, compute Q := sG + eP. Verify that Q isn't the point at infinity and Q.x = r. Verify that Q.y is *not* a quadratic residue. (While I was incorrect earlier about the costs of computing a non-residue, it is the case the *verifying* a value is a quadratic residue is the same cost as verifying a value is a non-residue.) Effectively in my first email I was suggesting that the 'e' value in a signature be negated from the current BIP proposal. In this revision I am effectively suggesting that the 's' value in a signature should be the one that is negated instead. On Sat, Aug 4, 2018 at 8:22 AM, Russell O'Connor wrote: > I propose changing the verification equation from "Let *R = sG - eP*" to > > Let *R = sG + eP* > > This allows faster verification by avoiding negating a point (or a > coefficient). > > > If, instead of directly following the literal verification specification, > one is instead reconstructing R from r by finding a y coordinate that is a > quadratic residue, under the existing scheme one would verify > > > *sG - eP = R* > > which is effectively verifying > > 0 = *sG - eP* - R or 0 = R - *sG + eP* > > Either way one needs to negate at least one point (or one coefficient) > because of the opposite signs between sG and eP. > > > Under my proposed revised verification scheme, one would instead verify > > 0 = sG + eP + (-R). > > While it seems that this requires negating R, it does not. Rather (-R) > can be directly constructed from r by finding a y coordinate that is *not* > a quadratic residue, which is precisely the same amount of work that > construction R from r was. > > In either verification procedure, changing the verification equation to my > proposal removes one negation operation from the cost of doing verification. > > > --000000000000ff7b700572b10d19 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Over chat it has been pointed out to me that computin= g the non-quadratic residue is not the same cost as computing a quadratic r= esidue.=C2=A0 As pointed out in footnote 7 of the the proposed BIP, c^((p+1= )/4) is always a quadratic residue and must be negated to find the non-quad= ratic residue.

In light of this, I revise my propo= sed change to make the verification equation

R + s= G + eP =3D 0.

(by 0 in the equation above I mean = the identity element for the (+) operation, which is the point at infinity.= )

This equation is suitable for batch verifica= tion.=C2=A0 This equation is clearly written as a linear combination that d= oesn't use negation.=C2=A0 In most implementations, equality comparison= tests are implemented by subtraction and a comparison with zero. By writin= g the verification equation this way, we clearly see that only the comparis= on with zero test is needed.

For single signat= ure verification the check becomes, compute Q :=3D sG + eP.=C2=A0 Verify th= at Q isn't the point at infinity and Q.x =3D r.=C2=A0 Verify that Q.y i= s *not* a quadratic residue. (While I was incorrect earlier about the costs= of computing a non-residue, it is the case the *verifying* a value is a qu= adratic residue is the same cost as verifying a value is a non-residue.)

Effectively in my first email I was suggesting = that the 'e' value in a signature be negated from the current BIP p= roposal.=C2=A0 In this revision I am effectively suggesting that the 's= ' value in a signature should be the one that is negated instead.

On Sat, = Aug 4, 2018 at 8:22 AM, Russell O'Connor <roconnor@blockstream.= io> wrote:
I propose changing the verification equation from "Let R =3D = sG - eP" to

=C2=A0=C2=A0=C2=A0 Let R = =3D sG + eP

This allows faster verificatio= n by avoiding negating a point (or a coefficient).


If, instead of directly following the literal verification = specification, one is instead reconstructing R from r by finding a y coordi= nate that is a quadratic residue, under the existing scheme one would verif= y

=C2=A0=C2=A0 sG - eP =3D R
=
which is effectively verifying

=C2= =A0 0 =3D sG - eP - R=C2=A0 or 0 =3D R - sG + eP

Either way one needs to negate at least one point (or one = coefficient) because of the opposite signs between sG and eP.


Under my proposed revised verification schem= e, one would instead verify

=C2=A0 0 =3D sG + eP += (-R).

While it seems that this requires negating = R, it does not.=C2=A0 Rather (-R) can be directly constructed from r by fin= ding a y coordinate that is *not* a quadratic residue, which is precisely t= he same amount of work that construction R from r was.

In either verification procedure, changing the verification equati= on to my proposal removes one negation operation from the cost of doing ver= ification.



--000000000000ff7b700572b10d19--