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
|
Return-Path: <apoelstra@wpsoftware.net>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id E626771F
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 10 May 2017 07:55:44 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mail.wpsoftware.net (wpsoftware.net [96.53.77.134])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id 47DE214E
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 10 May 2017 07:55:44 +0000 (UTC)
Received: from boulet.lan (boulot.lan [192.168.0.193])
by mail.wpsoftware.net (Postfix) with ESMTPSA id 227C9400FB;
Wed, 10 May 2017 07:55:42 +0000 (UTC)
Date: Wed, 10 May 2017 07:55:42 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Russell O'Connor <roconnor@blockstream.io>
Message-ID: <20170510075542.GZ10783@boulet.lan>
References: <CAKEeUhh3Rj3Dh8ab5FFR6dGKc2Ojm5Z0uyWtAtrPrh=7dvj-GA@mail.gmail.com>
<CAMZUoK=iXXYkN64+T-haK=vXrd=L7eqbo3P-MOhrj6p35uaW0A@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="ICgY9hOMOIj3tkv0"
Content-Disposition: inline
In-Reply-To: <CAMZUoK=iXXYkN64+T-haK=vXrd=L7eqbo3P-MOhrj6p35uaW0A@mail.gmail.com>
User-Agent: Mutt/1.7.1 (2016-10-04)
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD
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] Per-block non-interactive Schnorr signature
aggregation
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: Wed, 10 May 2017 07:55:45 -0000
--ICgY9hOMOIj3tkv0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Tue, May 09, 2017 at 09:59:06PM -0400, Russell O'Connor via bitcoin-dev =
wrote:
> I'm a bit amateur at this sort of thing, but let me try to argue that this
> proposal is in fact horribly broken ;)
>=20
> Suppose Alice has some UTXO with some money Bob wants to steal. Grant me
> that the public key P0 protecting Alice's UTXO is public (say because the
> public key has been reused elsewhere).
>=20
> Bob going to spend Alice's UTXO by generating random values s0, k0 and R0
> :=3D k0*G and thus creating a random signature for it, [R0, s0]. Now cle=
arly
> this signature isn't going to be valid by itself because it is just rando=
m.
> Bob's goal will be to make a transaction with other inputs such that, whi=
le
> the individual signatures are not valid, the aggregated signature will be
> valid.
>
If you seed the randomization with every R value (which would come for free
if you used, say, the witness root) then Wagner's attack no longer applies.
The idea is that no aggregation occurs until a miner produces a block. You
have a bunch of independent Schnorr sigs (s_i, R_i). Then the _miner_ multi=
ples
each s_i by H(witness root || index) or whatever, sums up the s_i's, and co=
mmits
the sum somewhere where it doesn't affect the root.
Verifiers then multiply each R_i by the same multiplying factors and are ab=
le
to do a batch verification of them.
Verifiers who have seen a signature before and cached it as valid can save
themselves a bit of time by subtracting H(witness root || index)*s_i from
the summed s-value and then skipping R_i in the above step. These are scalar
operations and are extremely cheap.
They can recognize the signature given only the transaction it signs and R_=
i,
which uniquely determine a valid signature.
I believe this is what Tadge was referring to when he mentioned a talk of m=
ine.
It's roughly what I've had in mind whenever I talk about non-interactive Sc=
hnorr
aggregation.
Cheers
Andrew
--=20
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
"A goose alone, I suppose, can know the loneliness of geese
who can never find their peace,
whether north or south or west or east"
--Joanna Newsom
--ICgY9hOMOIj3tkv0
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJZEsd8AAoJEMWI1jzkG5fBmGcIAJFpS5Vs0Ch3JQAe3odBrixc
fS4TwGeORAjiXWmwvOeq+4ff4xpcOXCAR/BYwVojfLmCfTf4LvdCXX2mwq6uwvEl
7NGINe7kIWHulZVnn1zBb+5w3MGpjdQ7qGf9vuJG39jWIuo9tMvzHfI72RfZeHTe
kYwhHx1Twf44Iw6Fay1l1ug3rhO+T+w0ZsMfw5WvKh52joyGsiVVHOZkutOB9Rah
sOwFfj932MCYvPFf7Br6uoAVmTdtM5p/3mrp0c8k4tA4mMlCuSP1F3huFIbotSAh
XD/hT+zT3m3V/uPLV9bgF1/zUH4tW5WK8LoZD04vxui7G1BdOk2LLz1Ty5DOYbc=
=DLxO
-----END PGP SIGNATURE-----
--ICgY9hOMOIj3tkv0--
|
