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 66778BAD for ; Sat, 4 Aug 2018 12:22:50 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f41.google.com (mail-it0-f41.google.com [209.85.214.41]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id DCC52713 for ; Sat, 4 Aug 2018 12:22:49 +0000 (UTC) Received: by mail-it0-f41.google.com with SMTP id g141-v6so12140108ita.4 for ; Sat, 04 Aug 2018 05:22:49 -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=pvoTSor1XVozFA7+/qfu+PJ9fgI/r3UT7lgHvvU3yqI=; b=X5lswPSANcCCDYtJWY7ja+ZcabjA57cwh2BWW0cAi7RcBuinfRHB/VwOo5MJOcZei7 6eSZrZ4jzIgEWvJRA8TzXcj89nmhjMkW+Fxb6OtxQ79sCdV3REslqs76TFZLptdIwdbO dFilHdQVbzWftn+53+06QZUwlfUKyaxuFuXCs= 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=pvoTSor1XVozFA7+/qfu+PJ9fgI/r3UT7lgHvvU3yqI=; b=gJ2eoOzD/fUwkQWTdsQYiVqZxiE21IOCaWSpAvhCD6fK86L1xZq+UXD8aAeQPqrTlP 5AeXPNBl6mFRAPDVpmYYk3+CbGnx/z/Uv8ktgSUZyROvFms9JR396Fl8Mz9FQifI6Oka r6EsXwMwNEw2oN07/0gvUIpG5JzZO8QAZ+8msoUQgJay1MxwFaOfQBVKY/I9Ks7EfDq0 NS+r21XLEZJ1j8Q3aS2NNRr2/Wv077iTOY8tvHN+sZlyPO59rKWtl2Ro/4KuCjR4SERQ CUT4Cd3L+ApEwrnbVdn/c3XPHNimzVvRk67XqvEjF18N7HFrS0aJ3Y6yPSQIPCvcItLc 1a0A== X-Gm-Message-State: AOUpUlHqJ5etw+Y64JMhCt6xm1NUl8taytEqKvyaNn1NpJ96efJCFsE0 MIFhCyCkM0pyI83BdVtuVSB6AtBAVOOrTj2AMufDJg== X-Google-Smtp-Source: AAOMgpfhkvfHtVzrfGkj8dxhBldkwI8tGuwa7+DFH9St3rl0f9TO9BjWRt6mscvdGfz1akXxRdx6W5SHA27TOBSPuBQ= X-Received: by 2002:a02:4ac3:: with SMTP id s64-v6mr6722380jad.93.1533385369195; Sat, 04 Aug 2018 05:22:49 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:a02:6949:0:0:0:0:0 with HTTP; Sat, 4 Aug 2018 05:22:28 -0700 (PDT) In-Reply-To: References: From: "Russell O'Connor" Date: Sat, 4 Aug 2018 08:22:28 -0400 Message-ID: To: Pieter Wuille , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="0000000000003c309b05729b1a0e" 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: Sat, 04 Aug 2018 12:22:50 -0000 --0000000000003c309b05729b1a0e Content-Type: text/plain; charset="UTF-8" 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. --0000000000003c309b05729b1a0e Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I propose changing the verification equation from &qu= ot;Let R =3D sG - eP" to

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

This allows fa= ster verification by avoiding negating a point (or a coefficient).


If, instead of directly following the liter= al verification specification, one is instead reconstructing R from r by fi= nding a y coordinate that is a quadratic residue, under the existing scheme= one would verify

=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 ver= ification scheme, one would instead verify

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

While it seems that this req= uires negating R, it does not.=C2=A0 Rather (-R) can be directly constructe= d 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 veri= fication equation to my proposal removes one negation operation from the co= st of doing verification.


--0000000000003c309b05729b1a0e--