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
|
Return-Path: <jonasdnick@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 9F05CC002D
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 8 Jul 2022 15:50:34 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp3.osuosl.org (Postfix) with ESMTP id 6AFC8613D3
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 8 Jul 2022 15:50:34 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 6AFC8613D3
Authentication-Results: smtp3.osuosl.org;
dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
header.a=rsa-sha256 header.s=20210112 header.b=hFNmN3lA
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Received: from smtp3.osuosl.org ([127.0.0.1])
by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id Kgt89aAkH0st
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 8 Jul 2022 15:50:33 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 64C0C6138C
Received: from mail-ed1-x536.google.com (mail-ed1-x536.google.com
[IPv6:2a00:1450:4864:20::536])
by smtp3.osuosl.org (Postfix) with ESMTPS id 64C0C6138C
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 8 Jul 2022 15:50:33 +0000 (UTC)
Received: by mail-ed1-x536.google.com with SMTP id fd6so27349962edb.5
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 08 Jul 2022 08:50:33 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
h=from:message-id:date:mime-version:user-agent:content-language:to
:subject:content-transfer-encoding;
bh=SQeJxenr3FOEnBM6tRTc8E+0N1cBQuka/MKE5EFD+eQ=;
b=hFNmN3lArU922r/VetrmUH4Xyus6J9UqX81xidvjBv/knc7GLpEM/UGUgUWvQ8Fz7J
9AKrOeH7A/10kGdW5UMx/uxbu3hD5YZH/wqanFL1zTcbuylJiisKVbxCtx0Mx79zRRn7
Xo4EdOKfTVAuJF/NIh2zC3yOmyhMcZO/LH14ppp/uCVanohkuauFpY4Uu5EmvG6TD/qj
0WbmUvyhjcH8U7Pn6Wcyw+Cu1MbKK5N2s+I26uUsTW7+kah/I8HoKnqkae9wEmX6tNmh
As+9Nx7mnvbOX/iQ4OgRcQp+1cLmVtB4JN/iZJ1SuGisXdRPhSMjn+idgodC0yFzHJfB
5E3w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20210112;
h=x-gm-message-state:from:message-id:date:mime-version:user-agent
:content-language:to:subject:content-transfer-encoding;
bh=SQeJxenr3FOEnBM6tRTc8E+0N1cBQuka/MKE5EFD+eQ=;
b=J77dDORPbKYiuXwWpho50ms3pvl3Hg3u3cBTQyO+2C03wschwxhnp+YEI/Pxfs1NpG
Fyrva2jJlX2v9ZP0WJH2WBnhnB4awyTe92UwUkioYXII7eyqqrFkfz+SZDSkDOQfq07H
IvnkuZEzhqzQw6GKn2VxVbOAVwLgjGWL6h9bUwTtdShFVrq5u0cItS3pZOwk0ZokgPTG
q+/aJuI4eYena0Jhy6ZzsUt191/fIKfO+dAv1p4J1PkIzhTAlmpN+GFXc1ULWLV2CkGX
VULZdChcnaHI4aU/nTzUACn5BB3SsES2riZljfbFfo6ZHgo8DK0VHhevu9cM5pFnqVVv
Bnzw==
X-Gm-Message-State: AJIora9ZisGSKbd0qgV4yayDKkG3xXVvPxQ4BH9YEPi1JmoD6gybOKEq
R9p1Etwmzty+VgH79esQekvIgh4iY0iHFQ==
X-Google-Smtp-Source: AGRyM1vJxvtze5i+2OyQaP9vLN/qjKF2dhLBM7W0hpq6bWYCtjoOoxOtDf7Es/jMp5QW/13QR6plbg==
X-Received: by 2002:a05:6402:448c:b0:435:9dcc:b8a5 with SMTP id
er12-20020a056402448c00b004359dccb8a5mr5697850edb.287.1657295431596;
Fri, 08 Jul 2022 08:50:31 -0700 (PDT)
Received: from [10.11.10.13] (179-129-067-156.ip-addr.inexio.net.
[156.67.129.179]) by smtp.googlemail.com with ESMTPSA id
eg37-20020a05640228a500b0043a587eb95dsm11653714edb.5.2022.07.08.08.50.30
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Fri, 08 Jul 2022 08:50:30 -0700 (PDT)
From: Jonas Nick <jonasdnick@gmail.com>
X-Google-Original-From: Jonas Nick <jonasd.nick@gmail.com>
Message-ID: <33f275c2-06b1-4b4a-2a75-cafe36836503@gmail.com>
Date: Fri, 8 Jul 2022 15:53:06 +0000
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
Thunderbird/91.11.0
Content-Language: en-US-large
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Mailman-Approved-At: Fri, 08 Jul 2022 17:32:37 +0000
Subject: [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: Fri, 08 Jul 2022 15:50:34 -0000
Half-aggregation has been mentioned several times on this list in various
contexts. To have a solid basis for discussing applications of half-aggregation,
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/half-aggregation.mediawiki
Similar to BIP-340, this BIP draft specifies only the cryptographic scheme and
does not prescribe specific applications. It has not received an extensive
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 aggregation"
which allows aggregating additional BIP-340 signatures into an existing
half-aggregate signature.
While BIP-340 has a pseudocode specification and a reference implementation in
python, this BIP draft has a formal specification written in hacspec [0] and
auxiliary pseudocode. The formal specification is a mathematically precise
description of the scheme, which paves the way for computer-aided formal proofs.
Software tools ("proof assistants") allow proving properties about the formal
specification ("no integer overflow") and apply formal software verification
("implementation is behaviorally equivalent to the spec"). I don't have concrete
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 Bitcoin
ecosystem's robustness significantly and has little downside. Since hacspec's
syntax is a subset of Rust's syntax, one can use the standard rust toolchain 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
|
