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
|
Return-Path: <rx@awsomnet.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id C7A02BA4
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 10 May 2017 14:59:10 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f50.google.com (mail-it0-f50.google.com
[209.85.214.50])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 430F61A0
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 10 May 2017 14:59:10 +0000 (UTC)
Received: by mail-it0-f50.google.com with SMTP id o5so26429592ith.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 10 May 2017 07:59:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=awsomnet-org.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to;
bh=lFKilqIF4KABwfBl1keT8pzX4uMHSxpPbShJ1kkBaZs=;
b=RPV2iAZlIus4xHrltK28DjmGwYWj7Nz+18QrjIH7W0Dkn+0U/u7TNfUCmiCjUUUw7r
P89vG1wy3U45IevrFd1/kPwMgXG/ytpkPQfr7b8m5/m1Y8jsCKKt7dMVr+V57UmaaOxq
mEQXyND8W4cifLGnEFmHt7T+IZtP8n0Z4eupu3N/kWxJw5RwbFYh1Dk67Kiku8VGMwqz
jwizgSiDLKXMDbUDnWaTXQXvpEQ0TtSUUPx+BWKC8WT7MTVHre4Lt5UyNfYeGmptQpIv
S7roPuh+MBORk1cxWu1Zp5Q+GKpOqySVNFlMz6nNYYoB0oFc+4mqnZxqz3G5rWVugmQ8
PDYA==
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=lFKilqIF4KABwfBl1keT8pzX4uMHSxpPbShJ1kkBaZs=;
b=KmS0VwRtUiNVNkZmJHmStIT2IaZeeUIxZqgIJ5RhPeu62MgrdVKU0zqbnFSa2qc/gp
ShlKCmfaRc6pHpKolnimmL3IGXLeokPdIR/bXuZft4yDkNBsgXPdtXmjJ96NvGlS7YA3
KgKSVwEp2jc2SwZR1vgqYaQN8kGgjy2PTmFlVdspexgfI+dX1nNnGaF/AUKv6ysAPjo/
RlavQTrXz3Enq/F33vKRK+2sakXKFBDYDi53RASgVx8Lqe+kqY2uK1kQDu5jKNiZA/kj
tbLdHcnm34EvZEAGB1K3hV3flGRAMW4DYG5PxlJeEiAlwxA+5UIBVOfI5zwiThG2gRwV
geVw==
X-Gm-Message-State: AODbwcAXncw9+s/PGjIDgMiVtKuka9xeyrfhnW/qlHOu5uXrJaKR+WWc
zGeNvzbr5ZhqDx28jKbaZjcSyMAtGRdK
X-Received: by 10.36.37.17 with SMTP id g17mr1830859itg.101.1494428349406;
Wed, 10 May 2017 07:59:09 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.36.47.68 with HTTP; Wed, 10 May 2017 07:59:08 -0700 (PDT)
X-Originating-IP: [18.85.34.36]
In-Reply-To: <20170510075542.GZ10783@boulet.lan>
References: <CAKEeUhh3Rj3Dh8ab5FFR6dGKc2Ojm5Z0uyWtAtrPrh=7dvj-GA@mail.gmail.com>
<CAMZUoK=iXXYkN64+T-haK=vXrd=L7eqbo3P-MOhrj6p35uaW0A@mail.gmail.com>
<20170510075542.GZ10783@boulet.lan>
From: adiabat <rx@awsomnet.org>
Date: Wed, 10 May 2017 10:59:08 -0400
Message-ID: <CAKEeUhhPpCVG5Y7Upp5SXm1g3aXgm4ggNNT6C=_Pcj46vKVc7w@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,RCVD_IN_DNSWL_LOW 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] 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 14:59:10 -0000
I messed up and only replied to Russel O'Connor; my response is copied below.
And then there's a bit more.
-----
Aha, Wagner's generalized birthday attack, the bane of all clever tricks!
I didn't realize it applied in this case but looks like it in fact does.
applies to this case. It would have to be a miner performing the
attack as the s-value would only be aggregated in the coinbase tx, but
that's hardly an impediment.
In fact, sketching it out, it doesn't look like the need to know m1,
m2... m_n is a big problem. Even if the m's are fixed after being
chosen based on the P1... Pn's, (in bitcoin, m always commits to P so
not sure why it's needed in the hash) there is still freedom to
collide the hashes. The R values can be anything, so getting h(m1,
R1, P1) + h(m2, R2, P2)... to equal -h(m0, R0, P0) is doable with
Wagner's attack by varying R1, R2... to get different hashes.
I *think* there is a viable defense against this attack, but it does
make the whole aggregation setup less attractive. The miner who
calculates s-aggregate could also aggregate all the public keys from
all the aggregated signatures in the block (P0, P1...), sort them and
hash the concatenated list of pubkeys. They could then multiply s by
this combo-pubkey hash (call it h(c)). Then when nodes verify the
aggregate signature, they need to go through all the pubkeys in the
block, create the same combo-pubkey hash, and multiply s by the
multiplicative inverse of the h(c) they calculate, then verify s. I
believe this breaks the Wagner generalized birthday attack because
every h(m_i, R_i, P_i)*h(c) included or omitted affects the c part of
h(m0, R0, P0)*h(c).
I'm not sure how badly this impacts the verification speed. It might
not be too bad for verification as it's amortized over the whole
block. For the miner doing the aggregation it's a bit slower as they
need to re-sort and hash all the pubkeys every time a new signature is
added. Might not be too slow.
I'm not super confident that this actually prevents the generalized
birthday attack though. I missed that attack in the previous post so
I'm 0 for 1 against Wagner so far :)
-----
Andrew: Right, commiting to all the R values would also work; is there
an advantage to using the R's instead of the P's? At first glance it
seems about the same.
Another possible optimization: instead of sorting, concatenate all the
R's or P's in the order they appear in the block. Then have the miner
commit to s*h(c)^1, the multiplicative inverse of the hash of all
those values. Then when nodes are verifying in IBD, they can just
multiply by h(c) and they don't have to compute the inverse. A bit
more work for the miner and a bit less for the nodes.
-Tadge
|
