From: "Russell O'Connor" <roconnor@blockstream•io>
To: Pieter Wuille <pieter.wuille@gmail•com>,
Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Schnorr signatures BIP
Date: Sun, 5 Aug 2018 10:33:52 -0400 [thread overview]
Message-ID: <CAMZUoKm_ij4Ffzx5Wpipa5RAFA=5F06jhiTCMJhp3vAj1q+2jA@mail.gmail.com> (raw)
In-Reply-To: <CAMZUoKm4Qs2yAc+WKgN1J2D8MDgbzNnK69kF+hbY2GDyRqdVdg@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 2720 bytes --]
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.
>
>
>
[-- Attachment #2: Type: text/html, Size: 3607 bytes --]
next prev parent reply other threads:[~2018-08-05 14:34 UTC|newest]
Thread overview: 31+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-07-06 18:08 Pieter Wuille
2018-07-06 21:05 ` Russell O'Connor
2018-07-06 22:00 ` Gregory Maxwell
2018-07-06 22:01 ` Gregory Maxwell
2018-07-08 14:36 ` Russell O'Connor
2018-07-14 15:42 ` Sjors Provoost
2018-07-14 21:20 ` Pieter Wuille
2018-08-04 12:22 ` Russell O'Connor
2018-08-05 14:33 ` Russell O'Connor [this message]
2018-08-06 8:39 ` Anthony Towns
2018-08-06 14:00 ` Russell O'Connor
2018-08-06 21:12 ` Tim Ruffing
2018-08-12 16:37 ` Andrew Poelstra
2018-08-29 12:09 ` Erik Aronesty
2018-09-03 0:05 ` Andrew Poelstra
2018-09-05 12:26 ` Erik Aronesty
2018-09-05 13:05 ` Andrew Poelstra
2018-09-05 13:14 ` Erik Aronesty
2018-09-05 15:35 ` Gregory Maxwell
2018-09-11 16:34 ` Erik Aronesty
2018-09-11 17:00 ` Gregory Maxwell
2018-09-11 17:20 ` Erik Aronesty
2018-09-11 17:27 ` Gregory Maxwell
2018-09-11 17:37 ` Erik Aronesty
2018-09-11 17:51 ` Gregory Maxwell
2018-09-11 18:30 ` Erik Aronesty
2018-09-13 18:46 ` Andrew Poelstra
2018-09-13 20:20 ` Erik Aronesty
2018-09-14 14:38 ` Andrew Poelstra
2018-09-20 21:12 ` Russell O'Connor
2018-07-07 2:47 Артём Литвинович
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAMZUoKm_ij4Ffzx5Wpipa5RAFA=5F06jhiTCMJhp3vAj1q+2jA@mail.gmail.com' \
--to=roconnor@blockstream$(echo .)io \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=pieter.wuille@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox