1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
Return-Path: <pieter.wuille@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 4516EBAD
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 14 Jul 2018 21:20:49 +0000 (UTC)
Received: by mail-oi0-f48.google.com with SMTP id n84-v6so68291816oib.9
for <bitcoin-dev@lists.linuxfoundation.org>;
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: <A899D97B-5D47-4AB0-8A7F-57F91C58ADE1@sprovoost.nl>
References: <CAPg+sBj7f+=OYXuOMdNeJk3NBG67FSQSF8Xv3seFCvwxCWq69A@mail.gmail.com>
<A899D97B-5D47-4AB0-8A7F-57F91C58ADE1@sprovoost.nl>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Sat, 14 Jul 2018 14:20:48 -0700
Message-ID: <CAPg+sBg1WuG1MihC3zBHJpxVqC2Sys7Y52iWs6JXEMmnL_tE_w@mail.gmail.com>
To: Sjors Provoost <sjors@sprovoost.nl>
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 <bitcoin-dev@lists.linuxfoundation.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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Sat, 14 Jul 2018 21:20:50 -0000
On Sat, Jul 14, 2018 at 8:42 AM, Sjors Provoost <sjors@sprovoost.nl> 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
|
