Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id B9225D90 for ; Fri, 6 Jul 2018 21:05:25 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f53.google.com (mail-it0-f53.google.com [209.85.214.53]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 0DAB877B for ; Fri, 6 Jul 2018 21:05:24 +0000 (UTC) Received: by mail-it0-f53.google.com with SMTP id p185-v6so18930096itp.4 for ; Fri, 06 Jul 2018 14:05:24 -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=Sip78IMYeRyFDZRoaJs20+v1lNhw21PXMlgt0dquxio=; b=hVSF7sWp3LiDcw4vLinlDbIogz5TPsKzx91d7ljUFZ2bhCOsRx6qgN0rb+yu0HAu6g ZwiFGbHruYfBhaAHoMLWLcdXSJ3bt7pXSAR0w2+R8S2guQmzo5WK+DXlXksxXxNJwCJi lSucImlx4NFWx0DBb9Evu7cNHccefVV5L+KWo= 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=Sip78IMYeRyFDZRoaJs20+v1lNhw21PXMlgt0dquxio=; b=COhVZtNhQZT8L7Scl+qaBdWzgv8LDmO67CDGKJZUwPc8FBNSYPZqfbDSJA0/wvQzHR 9fHPnP2+6YPXhlUu2Iv/0/o2ddw/gpxiVGFknHaA01qAQUx1RvQLVj/1c4S8ayLd+432 Mx84IzUbtvyjcI5b/188FSh+SmjqEkxh+lpHs3e6TsNIAB92Pr8dxfvuJ6xTFIJtVOsw zjdGYywqQ9qcFeU/GK2bPSAPZavehp7OczV/71DHnD0AZl5MafeVUBjSkvuEVY+Ryuh8 8svj52my1XbpM+qwxIXk3xknBKV9Sww0YB14jkzMTQn0CV5aaZ4rEA25366FIPg96vQc WmHQ== X-Gm-Message-State: APt69E0o2nV2KJReo1qeM4OXhI0VimJU3xTQjWyrGs4WY9V9OWxlYy9Z ZvRkpD/lmG+BTHbGWjM8vM8dtSygAdvKfAo0ZOTE+w== X-Google-Smtp-Source: AAOMgpddwVy36TX5CVJJ/w/g1ZZ2B8GKNgeibkZa4TvF980QORzhEzxxFE5qyiopH4L7c07+w/ZOEA0XQCHUlT78bTA= X-Received: by 2002:a24:7b97:: with SMTP id q145-v6mr9325326itc.79.1530911124260; Fri, 06 Jul 2018 14:05:24 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:a02:6949:0:0:0:0:0 with HTTP; Fri, 6 Jul 2018 14:05:03 -0700 (PDT) In-Reply-To: References: From: "Russell O'Connor" Date: Fri, 6 Jul 2018 17:05:03 -0400 Message-ID: To: Pieter Wuille , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000beb71905705b0518" 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: Fri, 06 Jul 2018 21:05:25 -0000 --000000000000beb71905705b0518 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Some quick comments: Signing > > To sign: > > - Let *k =3D int(hash(bytes(d) || m)) mod n*[8 > > ]. > - Let *R =3D kG*. > - If *jacobi(y(R)) =E2=89=A0 1*, let *k =3D n - k*. > - Let *e =3D int(hash(bytes(x(R)) || bytes(dG) || m)) mod n*. > - The signature is *bytes(x(R)) || bytes(k + ex mod n)*. > > Can we avoid mutable variables in these specification? I know this is commonly done in RFCs, but I think it is fairly confusing to have `k` defined in two different ways within a single specification. Let's let k' =3D k when jacobi(y(R)) =3D 1 and let k' =3D n - k when jacobi= (y(R)) =3D -1. Note that this ensures that jacobi(y(k'G)) =3D 1. Also you've sort of left it undefined what to do when k =3D 0. According t= o the current specification, you will produce an invalid signature. The expected result is that you should win a 1000 BTC prize. One solution is to let k =3D *1 + int(hash(bytes(d) || m)) mod (n-1)*. Alternatively you could let k' =3D 1 when k =3D 0. Or you could just make = a note that signature generation fails with this message and private key pair when this happens. Let *e =3D int(hash(bytes(x(R)) || bytes(dG) || m)) mod n*. > P =3D dG should probably be noted somewhere in the text. I.e. this signatu= re is generated for the public key P =3D dG. If the inputs to hash were reordered as *hash(bytes(dG) || bytes(x(R)) || m)* then there is an opportunity for SHA256 expander to be partially prefilled for a fixed public key. This could provide a little benefit, especially when multiple signatures for a single public key need to be generated and/or verified. If all things are otherwise equal, perhaps this alternate order is better. The signature is *bytes(x(R)) || bytes(k + ex mod n)*. You haven't defined `x`. I'm guessing you mean `d` instead. > Optimizations > > *Jacobian coordinates* > > - *oncurve(P)* can be implemented as *y2 =3D x3 + 7z6 mod p*. > > oncurve(P) requires that `P` be on the curve and not infinity. You need another condition here to ensure that `P` is not infinity. On Fri, Jul 6, 2018 at 2:08 PM, Pieter Wuille via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Hello everyone, > > Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures, > over the same curve as is currently used in ECDSA: > https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki > > It is simply a draft specification of the signature scheme itself. It > does not concern consensus rules, aggregation, or any other > integration into Bitcoin - those things are left for other proposals, > which can refer to this scheme if desirable. Standardizing the > signature scheme is a first step towards that, and as it may be useful > in other contexts to have a common Schnorr scheme available, it is its > own informational BIP. > > If accepted, we'll work on more production-ready reference > implementations and tests. > > This is joint work with several people listed in the document. > > Cheers, > > -- > Pieter > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --000000000000beb71905705b0518 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Some quick comments:

Signing

To sign:
  • Let k =3D int(hash(bytes(d) || m)) mod n[8].
  • Let R = =3D kG.
  • If jacobi(y(R)) =E2=89=A0 1, let k =3D n - k<= /i>.
  • Let e =3D int(hash(bytes(x(R)) || bytes(dG) || m)) mod n.
  • The signature is bytes(x(R)) || bytes(k + ex mod n).
    • =
Can we avoid mutable variables in these specificatio= n?=C2=A0 I know this is commonly done in RFCs, but I think it is fairly con= fusing to have `k` defined in two different ways within a single specificat= ion.
Let's let k' =3D k when jacobi(y(R)) =3D 1 and l= et k' =3D n - k when jacobi(y(R)) =3D -1.=C2=A0 Note that this ensures = that jacobi(y(k'G)) =3D 1.

Also you've sort of le= ft it undefined what to do when k =3D 0.=C2=A0 According to the current spe= cification, you will produce an invalid signature.=C2=A0 The expected resul= t is that you should win a 1000 BTC prize.

One solution i= s to let k =3D 1 + int(hash(bytes(d) || m)) mod (n-1).=C2=A0 Alterna= tively you could let k' =3D 1 when k =3D 0.=C2=A0 Or you could just mak= e a note that signature generation fails with this message and private key = pair when this happens.

Let e =3D int(hash(bytes(x(R)) || bytes(dG) || m)) mod = n.

P =3D dG should probably be note= d somewhere in the text.=C2=A0 I.e. this signature is generated for the pub= lic key P =3D dG.

If the inputs to hash were reordered as= hash(bytes(dG) || bytes(x(R)) || m) then there is an opportu= nity for SHA256 expander to be partially prefilled for a fixed public key.= =C2=A0 This could provide a little benefit, especially when multiple signat= ures for a single public key need to be generated and/or verified.=C2=A0 If= all things are otherwise equal, perhaps this alternate order is better.

=C2=A0The sign= ature is bytes(x(R)) || bytes(k + ex mod n).

You haven't defined `x`.=C2=A0 I'm guessing you mean `d` i= nstead.

Optimizati= ons

Jacobian coordinates

  • oncurve(P) ca= n be implemented as y2 =3D x3 + 7z6 mod= p.
oncurve(P) requires that `P` be on the c= urve and not infinity.=C2=A0 You need another condition here to ensure that= `P` is not infinity.
=C2=A0

On Fri, Jul 6, 2018 at 2:0= 8 PM, Pieter Wuille via bitcoin-dev <bitcoin-dev@lists= .linuxfoundation.org> wrote:
https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

It is simply a draft specification of the signature scheme itself. It
does not concern consensus rules, aggregation, or any other
integration into Bitcoin - those things are left for other proposals,
which can refer to this scheme if desirable. Standardizing the
signature scheme is a first step towards that, and as it may be useful
in other contexts to have a common Schnorr scheme available, it is its
own informational BIP.

If accepted, we'll work on more production-ready reference
implementations and tests.

This is joint work with several people listed in the document.

Cheers,

--
Pieter
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev

--000000000000beb71905705b0518--