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: <michaelfolkson@protonmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
by lists.linuxfoundation.org (Postfix) with ESMTP id 95801C002D
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 17 Jul 2022 13:26:37 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp2.osuosl.org (Postfix) with ESMTP id 5B190409D3
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 17 Jul 2022 13:26:37 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 5B190409D3
Authentication-Results: smtp2.osuosl.org;
dkim=pass (2048-bit key) header.d=protonmail.com header.i=@protonmail.com
header.a=rsa-sha256 header.s=protonmail3 header.b=mVzEJajz
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -0.701
X-Spam-Level:
X-Spam-Status: No, score=-0.701 tagged_above=-999 required=5
tests=[BAYES_05=-0.5, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Received: from smtp2.osuosl.org ([127.0.0.1])
by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id rRa0neblqmYF
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 17 Jul 2022 13:26:35 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 500C7400DD
Received: from mail-40134.protonmail.ch (mail-40134.protonmail.ch
[185.70.40.134])
by smtp2.osuosl.org (Postfix) with ESMTPS id 500C7400DD
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 17 Jul 2022 13:26:35 +0000 (UTC)
Date: Sun, 17 Jul 2022 13:26:26 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
s=protonmail3; t=1658064393; x=1658323593;
bh=MPQgDoR43zA9x2xlOkslfK9yc6Ui9Xw3fYERjcyO9/E=;
h=Date:To:From:Reply-To:Subject:Message-ID:In-Reply-To:References:
Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID:
Message-ID;
b=mVzEJajz2ikH64txJP0+YNKftXVo1p12AD+knXXwfsKXuPnI9kY28qwzx5Bw9I721
KOKwpCl27tATGnWge9TEzk95K/o4n/ESLZ20sGrrY+K/VqtsSTfhMdJtqsymacqUMl
6qpx/nocHzO+905sQw8pk/66E+WppHUEnSVZhbo5HEwYhFjiBdLjNH4IeVWwR+Q5JK
qU1mAE89Mh1X6qII2DpWQXoul5/xp69mggZ/kJmdvTkNHrz7F+Sfgos6Bg1TvwABnt
TpyC1sqmYisJv3SmiDe5Zq8teW69G4C/vYfkrgLSQDZqwX8qy74gejoeTzbkTq76gl
N93iwnhfmWeDA==
To: Jonas Nick <jonasdnick@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: Michael Folkson <michaelfolkson@protonmail.com>
Reply-To: Michael Folkson <michaelfolkson@protonmail.com>
Message-ID: <uxodWlVSmJqvVHDuGevdDbsc5lXiyV6zONlNJtj6gDylkTXQzkPPokLXKJAVULMwPbduJJ7Fb-s0ZYKpduvIZ-LkCsfXClkDH5WhOFsTHts=@protonmail.com>
In-Reply-To: <33f275c2-06b1-4b4a-2a75-cafe36836503@gmail.com>
References: <33f275c2-06b1-4b4a-2a75-cafe36836503@gmail.com>
Feedback-ID: 27732268:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Mailman-Approved-At: Sun, 17 Jul 2022 18:10:41 +0000
Subject: Re: [bitcoin-dev] BIP draft: Half-Aggregation of BIP-340 Signatures
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
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: Sun, 17 Jul 2022 13:26:37 -0000
Thanks for this Jonas. One question that was asked on Telegram (credit: Ant=
oine D) and isn't clear to me skimming the blog post and the draft BIP is w=
hether half aggregation needs a new output type or not like we expect cross=
input signature aggregation (CISA) to [0]. My understanding is Schnorr sig=
nature batch verification (no aggregation of signatures) can be done today =
but half aggregation and CISA would need a soft fork and potentially a new =
output type in addition.
(I know this work is in its early stages and won't be proposed for a soft f=
ork anytime soon. A few of us are just trying to get a basic sketch in our =
heads of what they require and whether they could be enabled in the same up=
grade.)
[0]: https://bitcoin.stackexchange.com/questions/106240/will-cross-input-si=
gnature-aggregation-need-a-new-output-type/
--
Michael Folkson
Email: michaelfolkson at protonmail.com
Keybase: michaelfolkson
PGP: 43ED C999 9F85 1D40 EAF4 9835 92D6 0159 214C FEE3
------- Original Message -------
On Friday, July 8th, 2022 at 16:53, Jonas Nick via bitcoin-dev <bitcoin-dev=
@lists.linuxfoundation.org> wrote:
> Half-aggregation has been mentioned several times on this list in various
> contexts. To have a solid basis for discussing applications of half-aggre=
gation,
> I think it's helpful to have a concrete specification of the scheme and a=
place
> for collecting supplemental information like references to cryptographic
> security proofs. You can find the BIP draft at
>
> https://github.com/ElementsProject/cross-input-aggregation/blob/master/ha=
lf-aggregation.mediawiki
>
> Similar to BIP-340, this BIP draft specifies only the cryptographic schem=
e and
> does not prescribe specific applications. It has not received an extensiv=
e
> security review yet. Thanks to Elliott Jin and Tim Ruffing for the review=
so
> far. One new feature that the specified scheme has is "incremental aggreg=
ation"
> which allows aggregating additional BIP-340 signatures into an existing
> half-aggregate signature.
>
> While BIP-340 has a pseudocode specification and a reference implementati=
on in
> python, this BIP draft has a formal specification written in hacspec [0] =
and
> auxiliary pseudocode. The formal specification is a mathematically precis=
e
> description of the scheme, which paves the way for computer-aided formal =
proofs.
> Software tools ("proof assistants") allow proving properties about the fo=
rmal
> specification ("no integer overflow") and apply formal software verificat=
ion
> ("implementation is behaviorally equivalent to the spec"). I don't have c=
oncrete
> plans (nor the skillset) to use these techniques. Still, I think this is =
an
> exciting area to explore because it has the potential to increase the Bit=
coin
> ecosystem's robustness significantly and has little downside. Since hacsp=
ec's
> syntax is a subset of Rust's syntax, one can use the standard rust toolch=
ain to
> compile, execute and test the specification.
>
> You can find a blog post that gives a broader context at
> https://blog.blockstream.com/half-aggregation-of-bip-340-signatures/
>
> [0] https://github.com/hacspec/hacspec
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
|
