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
159
160
161
162
163
164
165
166
167
168
|
Return-Path: <dave@dtrt.org>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 50D91C0001
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 16 Mar 2021 00:25:35 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp3.osuosl.org (Postfix) with ESMTP id 371B46F5D8
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 16 Mar 2021 00:25:35 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: 1.1
X-Spam-Level: *
X-Spam-Status: No, score=1.1 tagged_above=-999 required=5 tests=[BAYES_50=0.8,
DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1,
DKIM_VALID_EF=-0.1, PDS_BTC_ID=0.499, PDS_BTC_MSGID=0.001,
SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Authentication-Results: smtp3.osuosl.org (amavisd-new);
dkim=pass (1024-bit key) header.d=dtrt.org
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 TjiBQYgxorX6
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 16 Mar 2021 00:25:33 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.8.0
Received: from newmail.dtrt.org (newmail.dtrt.org
[IPv6:2600:3c03::f03c:91ff:fe7b:78d1])
by smtp3.osuosl.org (Postfix) with ESMTPS id C5EA26F55F
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 16 Mar 2021 00:25:33 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=dtrt.org;
s=20201208; h=In-Reply-To:Content-Type:MIME-Version:References:Message-ID:
Subject:To:From:Date:Sender:Reply-To:Cc:Content-Transfer-Encoding:Content-ID:
Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc
:Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe:
List-Post:List-Owner:List-Archive;
bh=vYRGaTQwPUM/wPS9fBWcwaeYm3SsYVMA/Z9CMqC9nsU=; b=ieRihRAdp3MCd4UqYXaZEE5tb6
RcQDKt4OPTgusZHxo9CXZGAdWWCEQiQAZVGJedRdN/idlK66tWmUGd7LYdfhaVbxkthEQGlZDIW4g
YhhJ3U0sXgQ8z+OQ5DyFfB2E65p2HR9PGZ3ElDxb++9i8kEZLleKF/0ZWIyDjNqRTNAE=;
Received: from harding by newmail.dtrt.org with local (Exim 4.92)
(envelope-from <dave@dtrt.org>)
id 1lLxWd-0004Qi-Qz; Mon, 15 Mar 2021 14:25:31 -1000
Date: Mon, 15 Mar 2021 14:24:01 -1000
From: "David A. Harding" <dave@dtrt.org>
To: Luke Dashjr <luke@dashjr.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20210316002401.zlfbc3y2s7vbrh35@ganymede>
References: <202103152148.15477.luke@dashjr.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
protocol="application/pgp-signature"; boundary="qhw546z5jk5oahgs"
Content-Disposition: inline
In-Reply-To: <202103152148.15477.luke@dashjr.org>
User-Agent: NeoMutt/20180716
Subject: Re: [bitcoin-dev] PSA: Taproot loss of quantum protections
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: Tue, 16 Mar 2021 00:25:35 -0000
--qhw546z5jk5oahgs
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
On Mon, Mar 15, 2021 at 09:48:15PM +0000, Luke Dashjr via bitcoin-dev wrote:
> Note that in all circumstances, Bitcoin is endangered when QC becomes
> a reality [...] it could very well become an unrecoverable situation
> if QC go online prior to having a full quantum-safe solution.
The main concern seems to be someone developing, in secret, a quantum
computer with enough capacity to compromise millions of keys and then
deciding to use the most powerful and (probably) expensive computer ever
developed to steal coins that will almost immediately lose most or all
of their value.
That's certainly a threat we should consider, but like other "movie
plot" threats, I think we should weigh its unlikeliness in comparison
to the people who are losing smaller amounts of money on a regular basis
right now because we don't already have taproot---people who don't use
multisig, or contracts with threshold reduction timeout clauses, or
certain types of covenants because the contingencies these types of
scripts protect against come at too great a cost in fees for the typical
case where no contingencies are needed.
We have many ideas about how to mitigate the risk of effective quantum
computing attacks, from emergency protection to long-term solutions, so
it seems to me that the real risk in the movie plot scenario comes
entirely from *secret advances* in quantum computing. Other similar
risks for Bitcoin exist, such as secret discoveries about how to
compromise the hash functions Bitcoin depends on. One way to help
control those risks is to pay a public bounty to anyone who provably and
publicly discloses the secret advance (ideally while allowing the leaker
to remain anonymous). Several years ago, Peter Todd created a series of
Bitcoin addresses that does exactly that.[1]
For example, if you pay 35Snmmy3uhaer2gTboc81ayCip4m9DT4ko, then
anyone[2] who can prove a collision attack against Bitcoin's primary
hash function, SHA256, will be able to claim the bitcoins you and other
people sent to that address. Their claim of the funds will publicly
demonstrate that someone can create a SHA256 collision, which is an
attack we currently believe to be impractical. This system was
demonstrated to work about four years ago[3] when the collision bounty
for the much weaker SHA1 function was claimed.[4]
We can already create an output script with a Nothing Up My Sleeve
(NUMS) point that would provide a trustless bounty to anyone proving the
capability to steal any P2PK-style output with secp256k1's 128-bit
security. I curious about whether anyone informed about ECC and QC
knows how to create output scripts with lower difficulty that could be
used to measure the progress of QC-based EC key cracking. E.g.,
NUMS-based ECDSA- or taproot-compatible scripts with a security strength
equivalent to 80, 96, and 112 bit security.
That way the people and businesses concerned about QC advances could
send a few BTC to those addresses to create a QC early warning system
that would allow us to continue confidently working on EC-based
protocols for now but also objectively alert us to when we need to shift
to working on post-QC protocols for the future.
Thank you,
-Dave
[1] https://bitcointalk.org/index.php?topic=293382.0
[2] Anyone claiming the reward may need to mine their own transaction to
protect it against rewriting. In the worst case, they may need to
mine at a depth of several blocks or share their reward with miners
to prevent sniping reorgs.
[3] https://blockstream.info/tx/8d31992805518fd62daa3bdd2a5c4fd2cd3054c9b3dca1d78055e9528cff6adc
[4] To the best of my knowledge, nothing in Bitcoin ever depended
significantly on SHA1, and especially not on SHA1 collision
resistance, which was known to be weak even in 2009 when Nakamoto
first published the Bitcoin software.
--qhw546z5jk5oahgs
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQIzBAEBCgAdFiEEgxUkqkMp0LnoXjCr2dtBqWwiadMFAmBP+qEACgkQ2dtBqWwi
adOOGg//ckjfCJ/YDyhdwNBs0ai2UBvzAhA0dMDH0Oto79zG7b96Jzy6Tg+RxOtx
6G8fI42+j/IVbdur92lvxSgtEnelH31eURwE4kKd47rxws6kCyojieeIjOX1PXPv
XVylC2HKxDKUIAorkClQZcj1hxILwIsGoe/QPRzH/z4OyMBiikmsaTdMmNN/6usn
paHYahgqZZSOFkPmnSlnhbyqs+poerGcvW9V2eQ35e5AiFOd0sJ4mLJlP+USP8hG
nmipnl/uNZNBKqdG7b2k/8BMbBEjZvUrOEzICKduOhv1LDO7PhfI7XjEJZbikyd8
rbE1FBu6GOy+/sjQz2uE3JbPFdJuaoaOcm/dMQkszM5DgSta5SL3NQ78mFCRWT9G
QpXbzQqsADkFlMnJRta2u9QwacYrlpUfb5eMoaCtaOz1iuDg59qlBHbuWdO4m2dN
W1qfbuVvYfRhyFoz6dhrnFUEoHoCOmAAKTq9PgcHZXiEz3nKvXtGuW19PNm7KMRy
FOshO6B0591YSfVd/OQfvmgknQMNz6qb0UZOlCw/ZzvGpUIUz6dzauRLoQfAWjYe
Len8V4gtX6aDfbE/MhYRdSqO3rgiiXvQOo/5nkvrGByD0jZzz2c2iVFTeDJnNpeG
wedDydCUFJrbiGcXQEUDrwx7ewsXVvIuJcPmhaxvJJdkr5ZDjC4=
=ieJ0
-----END PGP SIGNATURE-----
--qhw546z5jk5oahgs--
|
