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
|
Return-Path: <crypto@timruffing.de>
Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138])
by lists.linuxfoundation.org (Postfix) with ESMTP id 7712CC0177
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 12 Mar 2020 17:04:57 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by whitealder.osuosl.org (Postfix) with ESMTP id 62F2F88307
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 12 Mar 2020 17:04:57 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from whitealder.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id p29FiWcUU7BP
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 12 Mar 2020 17:04:55 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mout-p-101.mailbox.org (mout-p-101.mailbox.org [80.241.56.151])
by whitealder.osuosl.org (Postfix) with ESMTPS id 1247A881D7
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 12 Mar 2020 17:04:54 +0000 (UTC)
Received: from smtp1.mailbox.org (smtp1.mailbox.org
[IPv6:2001:67c:2050:105:465:1:1:0])
(using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits))
(No client certificate requested)
by mout-p-101.mailbox.org (Postfix) with ESMTPS id 48dZv81V16zKmQX;
Thu, 12 Mar 2020 18:04:52 +0100 (CET)
X-Virus-Scanned: amavisd-new at heinlein-support.de
Received: from smtp1.mailbox.org ([80.241.60.240])
by spamfilter06.heinlein-hosting.de (spamfilter06.heinlein-hosting.de
[80.241.56.125]) (amavisd-new, port 10030)
with ESMTP id P1Ym3Wg08LxA; Thu, 12 Mar 2020 18:04:48 +0100 (CET)
Message-ID: <3e5b438ce1487412d203387d6c0e8f53cfdb7449.camel@timruffing.de>
From: Tim Ruffing <crypto@timruffing.de>
To: Lloyd Fournier <lloyd.fourn@gmail.com>, Bitcoin Protocol Discussion
<bitcoin-dev@lists.linuxfoundation.org>
Date: Thu, 12 Mar 2020 18:04:47 +0100
In-Reply-To: <CAH5Bsr2m3+kN67h0Dd+60-i3WCnCRXr_ywzub5_OV=UxxzN3hQ@mail.gmail.com>
References: <CAH5Bsr2m3+kN67h0Dd+60-i3WCnCRXr_ywzub5_OV=UxxzN3hQ@mail.gmail.com>
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
X-Mailman-Approved-At: Thu, 12 Mar 2020 17:06:06 +0000
Subject: Re: [bitcoin-dev] Hash function requirements for Taproot
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: Thu, 12 Mar 2020 17:04:57 -0000
Hi Lloyd,
This is great research, thanks for this effort!
Here are some comments:
On Wed, 2020-03-04 at 18:10 +1100, Lloyd Fournier via bitcoin-dev
wrote:
>
> Property (2) is more difficult to argue as it depends on the multi-
> party key generation protocol. Case in point: Taproot is completely
> broken when combined with a proof of knowledge key generation
> protocol where along with their public keys each party provides a
> proof of knowledge of the secret key. Where X_1 is the key of the
> honest party, the malicious party can choose their key X_2 to be
> G*H(X_1 || m) where m is a malicious Merkle root. Clearly the
> malicious party has a covert Taproot for X = X_1 + X_2 and can
> produce a proof of knowledge for X_2.
I mean, the good thing is that there's a general method to defend
against this, namely always adding a Merkle root on top. Maybe it's
useful to make the warning here a litte bit more drastic:
https://github.com/sipa/bips/blob/bip-taproot/bip-0341.mediawiki#cite_ref-22-0
Maybe we could actually mention this in BIP340, too, when we talk about
key generation,
>
> Poelstra presented a proof in the ROM for the security of Taproot
> [3]. It frames Taproot as a way of combining two signature schemes
> into one public key (in our case Schnorr and Tapscript). He uses a
> similar line of reasoning to what I have just presented in his proof
> (Lemma 1, step 3) but this approach brings in many other
> considerations that I think can be avoided by modelling it as a
> commitment scheme. Note that this proof only shows that Taproot
> forgeries are hard i.e. property (1).
I agree that modeling it as a commitment scheme is more natural. But I
think an optimal model would capture both worlds, and would give the
attacker signing oracles for the inner and the outer key, and an
commitment opening oracle That is, it would capture that
* the ability to obtain signatures for the inner key does not help you
to forge for the outer key
* the ability to obtain signatures for the outer key does not help you
to open the commitment, and --- if already opened --- do not help
you to forge for the inner key
* the ability to obtain an opening does not help you to forge for
either key...
* etc
I believe that all these properties hold, and I believe this even
without a formal proof.
Still, it would be great to have one. The problem here is really that
things get complex so quickly. For example, how do you model key
generation in the game(s) that I sketched above? The traditional way or
with MuSig. The reality is that we want to have everything combined:
* BIP32
* MuSig (and variants of it)
* Taproot (with scripts that refer to the inner key)
* sign-to-contract stuff (e.g., to prevent covert channels with
hardware wallets)
* scriptless scrips
* blind signatures
* threshold signtures
* whatever you can imagine on top of this
It's very cumbersome to come up with a formal model that includes all
of this. One common approach to protocols that are getting too complex
is to switch to simpler models, e.g., symbolic models/Dolev-Yao models
but that's hard here given that we don't have clear layering. Things
would be easier to analyze if Taproot was really just a commitment to
a verification key. But it's more, it's something that's both a
verification and a commitment. Taproot interferes with Schnorr
signatures on an algebraic level (not at all black-box), and that's
actually the reason why it's so powerful and efficient. The same is
true for almost everything in the list above, and this puts Taproot
outside the scope of proof assistants for cryptographic protocols that
work on a symbolic level of abstraction. I really wonder how we can
handle this better. This would improve our understanding of the
interplay between various crypto components better, and make it easier
to judge future proposals on all levels, from consensus changes to new
multi-signature protocols, etc.
>
> In my opinion, the cost of Taproot is mostly borne by theoreticians.
> They can no longer treat a a public key ideally but have to consider
> the implications of it also being a commitment. For the user and
> Bitcoin as a whole it seems to offer an overwhelming benefit. In
> exchange for the complexity it adds to making security claims in the
> GGM (if using Taprscript and MuSig), it offers exciting new
> opportunities for non-interactivity and fungibility over what just
> what Schnorr would provide.
I agree with this overall statement. I'm confident in Taproot, and I
guess what say above really applies to the cost for theoreticians.
(Let's just make sure that we don't forget how theory is relevant to
security in practice.)
Tim
|
