MIME-Version: 1.0
In-Reply-To: <CAMZUoKm4Qs2yAc+WKgN1J2D8MDgbzNnK69kF+hbY2GDyRqdVdg@mail.gmail.com>
References: <CAPg+sBj7f+=OYXuOMdNeJk3NBG67FSQSF8Xv3seFCvwxCWq69A@mail.gmail.com>
	<A899D97B-5D47-4AB0-8A7F-57F91C58ADE1@sprovoost.nl>
	<CAPg+sBg1WuG1MihC3zBHJpxVqC2Sys7Y52iWs6JXEMmnL_tE_w@mail.gmail.com>
	<CAMZUoKm4Qs2yAc+WKgN1J2D8MDgbzNnK69kF+hbY2GDyRqdVdg@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Sun, 5 Aug 2018 10:33:52 -0400
Message-ID: <CAMZUoKm_ij4Ffzx5Wpipa5RAFA=5F06jhiTCMJhp3vAj1q+2jA@mail.gmail.com>
To: Pieter Wuille <pieter.wuille@gmail.com>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000ff7b700572b10d19"
Subject: Re: [bitcoin-dev] Schnorr signatures BIP
Precedence: list

--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 <roconnor@blockstream.io>
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

<div dir=3D"ltr"><div>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.</div><div><br></div><div>In light of this, I revise my propo=
sed change to make the verification equation</div><div><br></div><div>R + s=
G + eP =3D 0.</div><div><br></div><div> (by 0 in the equation above I mean =
the identity element for the (+) operation, which is the point at infinity.=
)<br></div><div><br></div><div>This equation is suitable for batch verifica=
tion.=C2=A0 This equation is clearly written as a linear combination that d=
oesn&#39;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.<br></div><div><br></div><div>For single signat=
ure verification the check becomes, compute Q :=3D sG + eP.=C2=A0 Verify th=
at Q isn&#39;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.) <b=
r></div><div><br></div><div>Effectively in my first email I was suggesting =
that the &#39;e&#39; value in a signature be negated from the current BIP p=
roposal.=C2=A0 In this revision I am effectively suggesting that the &#39;s=
&#39; value in a signature should be the one that is negated instead.<br></=
div><div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Sat, =
Aug 4, 2018 at 8:22 AM, Russell O&#39;Connor <span dir=3D"ltr">&lt;<a href=
=3D"mailto:roconnor@blockstream.io" target=3D"_blank">roconnor@blockstream.=
io</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"marg=
in:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"=
><div>I propose changing the verification equation from &quot;Let <i>R =3D =
sG - eP</i>&quot; to</div><div><br></div><div>=C2=A0=C2=A0=C2=A0 Let <i>R =
=3D sG + eP</i><br></div><div><br></div><div>This allows faster verificatio=
n by avoiding negating a point (or a coefficient).</div><div><br></div><div=
><br></div><div>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</div><div><br></div><div>=C2=A0=C2=A0 <i>sG - eP =3D R<br></i></div><div>=
<br></div><div>which is effectively verifying</div><div><br></div><div>=C2=
=A0 0 =3D <i>sG - eP</i> - R=C2=A0 or 0 =3D R - <i>sG + eP</i><br></div><di=
v><br></div><div>Either way one needs to negate at least one point (or one =
coefficient) because of the opposite signs between sG and eP.<br></div><div=
><br></div><div><br></div><div>Under my proposed revised verification schem=
e, one would instead verify</div><div><br></div><div>=C2=A0 0 =3D sG + eP +=
 (-R).</div><div><br></div><div>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.<br></div><div><br></=
div><div>In either verification procedure, changing the verification equati=
on to my proposal removes one negation operation from the cost of doing ver=
ification.</div><div class=3D"gmail_extra"><br><br></div></div>
</blockquote></div><br></div></div></div>

--000000000000ff7b700572b10d19--