Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 4516EBAD for ; Sat, 14 Jul 2018 21:20:50 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-oi0-f48.google.com (mail-oi0-f48.google.com [209.85.218.48]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B75934FA for ; Sat, 14 Jul 2018 21:20:49 +0000 (UTC) Received: by mail-oi0-f48.google.com with SMTP id n84-v6so68291816oib.9 for ; Sat, 14 Jul 2018 14:20:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=efcoYfbzrMYUe24hrfQRxp1ZHFBntzXNGsXu5LJ0Is8=; b=si14N9R4dr+Hb3gLmhj//AX3e42rFHQcQHbrd/knBobqnnGAZ3rY1GmtATjdWRQ/x3 80C6mcrpa9qJMY+laibzLABL68+faPE/NR4B8plq+XibmGhmtI5u+s6U0wArLnw1lBmx 5zVaMorhG3n9MwehN/riXYXE1HgiZ1G2MdaiCmTJXeUJhM+Tr0iH2R76AWrCvqDcanzb gK60t9RCRIO767SJ2DPXZh0Kt1Rt4wy/BneVDFv7BVqL7i57GM9mx6BPIaPMF28R9ujg CZX9YQ5L64gEinL7l0uHhcECGKkpqf/DxsEK1PY0sM/o4cmDocSDvE6pornyihG1W5rb 7tLQ== 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:cc:content-transfer-encoding; bh=efcoYfbzrMYUe24hrfQRxp1ZHFBntzXNGsXu5LJ0Is8=; b=DwhQPEeB+MZZ8wG4Dm139UpfTXGSNZe3ARiZ/xxionMFOtvOuQYO6o8yCwMw0AWkW7 51WkUCSCJOh25RD/8EydnAPXpo+30efXh5tOdNZvbN1JdZ3fTW6h3+r4RF2Yie17jEEJ KIMLksyBeqSN6sl3gixQlkoDcLaepNPPF6XLUQKdJKyRG5wyvPbBQXkp28s1MGCxE99j oT9NMfucZq/ZcVwC6rAWjc6Ypls8C+doq65h1cmQPyk8/05BjajLR7MJX1RJnAeN5kZC JPQxzGsAzKY35qJ6GOBuvOoqT75yJ1MuKfbsTW6brXhgDZwq+FI1M4Uigmt/MqNHiChJ yjyQ== X-Gm-Message-State: AOUpUlH44I4PRWh9eKMVkZtBH92hdtPKYZYAOp2GkK9gcQvmj/xlghDF 4aCCF5hXmFsmYY4Duc3maOUMPvshnO9qC256F0SZiA== X-Google-Smtp-Source: AAOMgpc9ON4u87s/LmyQKmvuHH1wKZpxXeaP96AEF2PLGbnP2IqPUiLbszBNYkqWbKI+KC1hBcsXf8O8s7POgtKRNg4= X-Received: by 2002:aca:5545:: with SMTP id j66-v6mr13207446oib.291.1531603248786; Sat, 14 Jul 2018 14:20:48 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:a4a:4e02:0:0:0:0:0 with HTTP; Sat, 14 Jul 2018 14:20:48 -0700 (PDT) In-Reply-To: References: From: Pieter Wuille Date: Sat, 14 Jul 2018 14:20:48 -0700 Message-ID: To: Sjors Provoost Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, 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 Cc: Bitcoin Protocol Discussion 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, 14 Jul 2018 21:20:50 -0000 On Sat, Jul 14, 2018 at 8:42 AM, Sjors Provoost wrote: > Questions: > > Regarding verification: why does bytes(P) use compressed key serializatio= n rather than the implicit Y coordinate used for signing? I understand spac= e savings don't matter since these values don't end up on the blockchain. I= s it just easier to implement or is it faster? Following the design decision to use key-prefixed Schnorr, the signature must commit to the entire public key, including its Y coordinate. It would be possible to only permit public keys whose Y coordinates are even, or quadratic residues (like the signature internally uses for the R point), but that would mean changing what public keys are acceptable. Not doing so has significant practical advantages, like not breaking existing key generation mechanisms (like BIP32 and derivatives). So if we're going to serialize the public key into the hash, in full, the easiest choice seems to be to use the encoding everyone already uses for public keys. > Regarding rationale for choosing (e,s) vs. (R,s), you say that (e,s) "avo= ids the difficulty of encoding a point R in the signature". But since e =3D= H(sG - eP || m) also involves converting a point to some byte encoding in = order to hash it, how much difficulty is actually avoided? Is that, like fo= r previous question, because you could get away with compressed keys rather= than implicit Y coordinates? This is mostly a historical argument. When Schnorr is applied to an integer multiplication group rather than an elliptic curve group, serializing a group element is many times larger than serializing a hash. For elliptic curve based Schnorr, there is hardly any benefit for choosing the (e,s) form over (R,s). > Regarding batch verification: "randomly generated independently for each = batch of verifications" - by whom? I assume randomly picked by the verifier= ? Randomly picked by the verifier, yes. The randomization factors are there so that an attacker cannot choose signatures which cancel out other invalid signatures within the same batch. > Regarding random number used for signing. The suggested (?) deterministic= algorithm to derive secret key ''k'' from the private key ''d'' seems sim= ilar to RFC6979. Maybe it's useful to briefly explain the difference, as we= ll as your rationale for not making it mandatory (presumably the same as wh= y RFC6979 isn't mandatory although most (?) wallets use it). What would "mandatory" mean? To follow the BIP, signers must sign using nonces generated deterministically following the provided method. That's as far as mandatory can go. However, it is not possible to enforce (by a verifier) than nonces were generated in a specific way. To do so, the verifier would need to know the nonce, which implies learning the private key. So the nonce choosing algorithm cannot be enforced by the verifier. This implies that it is possible to generate valid (and secure) nonces in a way that does not follow the BIP. > * Motivation: "signatures ... These are standardized", but the "standardi= zed" link points to the secp256k1 curve parameters, not to anything signatu= re related afaik There are two documents on the site linked to. One describes the ECDSA signing algorithm and serializations, the other specifies the curve parameter. I could link to both. > * "message m: an array of 32 bytes", maybe add "typically the sha256 hash= of the transaction components commited to by SIGHASH_TYPE=E2=80=9D Ok. > * I left a few even smaller nits as a PR: https://github.com/sipa/bips/pu= ll/10 Thanks for your comments, will review. Cheers, --=20 Pieter