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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
Return-Path: <natanael.l@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id BB973FBF
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 15 Feb 2018 20:27:30 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f47.google.com (mail-wm0-f47.google.com [74.125.82.47])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 14F0AE6
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 15 Feb 2018 20:27:30 +0000 (UTC)
Received: by mail-wm0-f47.google.com with SMTP id t74so3141484wme.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 15 Feb 2018 12:27:29 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to;
bh=9xgeBXHdrAj3pOkiUkoAmPLKkXFQCeoRvHr4FAldj+s=;
b=U7YZEM+rDkaKLfReHrmN6TlujK1JI2xTOCX5nRCiDq0owhXuWMYUZFpVIi97o3nfMv
LN7FnkNnPIWWM946go4kclVDuamYd80La8Kw/n9LFWLrKN6HYhY62TsVkpKtrUbdaRpO
N9MguFsrB/ImBCS2JbwlUYVecSQtZL3uW1XQpgUaEKQdQKKLAF9x+PuvdWcgDtlUSMbb
f1uuRmf2UGCB3zhv+x+dAqvFeT4wLIb5I+BZStJVb0dmA83iKXikiO2rfi2TkBmwDNOb
JXXLG+EUR0P5KhLxGSIcblpKenhRDg/6ApnocicypBOdfNlJtnemW77Rsq9WjjGSfLhU
QSVQ==
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=9xgeBXHdrAj3pOkiUkoAmPLKkXFQCeoRvHr4FAldj+s=;
b=my3nwtf4xFGIZ8qFZS5Q3v6e/PAPfpqULwrNaAHi0YTDfLIOneQi/3ZkUTbOpjp3gb
fW3OoCLIX43Z0bWb57/Wy73M0Msj++fitp3Bnw1REgew40X3Gybq4XTLjJzdRHyRoSvV
b/y+NhpeDiAHBK5A/nw0UaoTiu4Wuu68Fvys1LRANk7fuwoLn1gQEWefsHL1k8tA+THg
sOtWJpDHEbtk1W6/+hSY29KOU6sbSr3PrQ8yBRyHi3PqvrsIFRz0vvOxBP3tktbP59aT
bCm8PlZI0nVkPCYuVACmLw6mDBDmWERoBS2sIv+Qji+0uuvGRleA3x6xqQIFIaxBSF61
w1QQ==
X-Gm-Message-State: APf1xPCqYov2k5x0cg0SKtFJQ4H2p78rKaV8l8uqTa265w46QrYaGhee
0QhzPsxvfrQFCTLqEyDLP7JU8CoHulpnhzschzs=
X-Google-Smtp-Source: AH8x224nGtfG9q2SVl99YGkwILLMmuayfqX/bCH9iVmW7zVWWO2Jbap2dZZXC68IH2Nwlw65Hajx/0BNCxeqgcCeiWE=
X-Received: by 10.80.208.135 with SMTP id v7mr4940638edd.182.1518726448628;
Thu, 15 Feb 2018 12:27:28 -0800 (PST)
MIME-Version: 1.0
Received: by 10.80.169.74 with HTTP; Thu, 15 Feb 2018 12:27:27 -0800 (PST)
Received: by 10.80.169.74 with HTTP; Thu, 15 Feb 2018 12:27:27 -0800 (PST)
In-Reply-To: <1518710367.3550.111.camel@mmci.uni-saarland.de>
References: <CAFEpHQHP7XXBYUP6CF1OeYoBpj0UwK+qpYG-14_zQZDX4Md7UA@mail.gmail.com>
<1518450650.7829.87.camel@mmci.uni-saarland.de>
<CAFEpHQHYdE3m2GUtN=ijvtYUudwtcG52rRxzH66VFbgO1KEihw@mail.gmail.com>
<1518504374.9878.24.camel@mmci.uni-saarland.de>
<882306fa-3ea0-99bd-61c6-f646d27c2ab6@gmail.com>
<1518710367.3550.111.camel@mmci.uni-saarland.de>
From: Natanael <natanael.l@gmail.com>
Date: Thu, 15 Feb 2018 21:27:27 +0100
Message-ID: <CAAt2M1-JtmcMH2WCx5T5U8B-B+Ob61WPSvX4JoOcWzYFCLSTmw@mail.gmail.com>
To: Tim Ruffing <tim.ruffing@mmci.uni-saarland.de>,
Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="94eb2c1cd0f27b48380565460ed5"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE 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] Transition to post-quantum
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: Thu, 15 Feb 2018 20:27:30 -0000
--94eb2c1cd0f27b48380565460ed5
Content-Type: text/plain; charset="UTF-8"
Den 15 feb. 2018 17:00 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org>:
Consensus rules
===============
A decommitment d = chal spends a UTXO with address H_addr(chal), if
there exists a commitment c in the blockchain which references the UTXO
and which is the first commitment (among all referencing the UTXO) in
the blockchain such that
1. k = KDF(chal) correctly decrypts Dec(k, c)
and
2. tx = Dec(k, c) is a valid transaction to spend UTXO
The UTXO is spent as described by tx.
Commitments never expire.
I addressed this partially before, and this is unfortunately incomplete.
Situation A: Regardless of expiration of commitments, we allow doubles. (Or
no doubles allowed, but commitments expire.)
If I can block your transaction from confirming (censorship), then I can
make my own commitment + transaction. The miners will see two commitments
referencing the same UTXO - but can see only one transaction which match a
valid challenge and spends them, which is mine. You gained nothing from the
commitment.
Situation B: We don't allow conflicting commitments, and they never expire.
I can now freeze everybody's funds trivially with invalid commitments,
because you can't validate a commitment without seeing a valid transaction
matching it - and exposing an uncommitted transaction breaks the security
promise of commitments.
Any additional data in the commitment but hash it the transaction is
pointless, because the security properties are the same. You can't freeze
an UTXO after only seeing a commitment, and for any two conflicting
transactions you may observe it does not matter at all if one references
UTXO:s or not since you already know both transactions' commitment ages
anyway. Oldest would win no matter the additional data.
Commitments work when the network can't easily be censored for long enough
to deploy the attack (at least for 2-3 blocks worth of time). They fail
when the attacker is capable of performing such an attack.
As I said previously, the only completely solid solution in all
circumstances is a quantum resistant Zero-knowledge proof algorithm, or
some equivalent method of proving knowledge of the key without revealing
any data that enables a quantum attack.
--94eb2c1cd0f27b48380565460ed5
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto"><div><br><div class=3D"gmail_extra"><br><div class=3D"gma=
il_quote">Den 15 feb. 2018 17:00 skrev "Tim Ruffing via bitcoin-dev&qu=
ot; <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-de=
v@lists.linuxfoundation.org</a>>:<br type=3D"attribution"><blockquote cl=
ass=3D"quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding=
-left:1ex"><br>
Consensus rules<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>
A decommitment d =3D chal spends a UTXO with address H_addr(chal), if<br>
there exists a commitment c in the blockchain which references the UTXO<br>
and which is the first commitment (among all referencing the UTXO) in<br>
the blockchain such that<br>
1. k =3D KDF(chal) correctly decrypts Dec(k, c)<br>
=C2=A0 =C2=A0 and<br>
2. tx =3D Dec(k, c) is a valid transaction to spend UTXO<br>
<br>
The UTXO is spent as described by tx.<br>
Commitments never expire.<br></blockquote></div></div></div><div dir=3D"aut=
o"><br></div><div dir=3D"auto">I addressed this partially before, and this =
is unfortunately incomplete.</div><div dir=3D"auto"><br></div><div dir=3D"a=
uto"><span style=3D"font-family:sans-serif">Situation A: Regardless of expi=
ration of commitments, we allow doubles. (Or no doubles allowed, but commit=
ments expire.)=C2=A0</span></div><div dir=3D"auto"><br></div><div dir=3D"au=
to">If I can block your transaction from confirming (censorship), then I ca=
n make my own commitment + transaction. The miners will see two commitments=
referencing the same UTXO - but can see only one transaction which match a=
valid challenge and spends them, which is mine. You gained nothing from th=
e commitment.=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">Situ=
ation B: We don't allow conflicting commitments, and they never expire.=
I can now freeze everybody's funds trivially with invalid commitments,=
because you can't validate a commitment without seeing a valid transac=
tion matching it - and exposing an uncommitted transaction breaks the secur=
ity promise of commitments.=C2=A0</div><div dir=3D"auto"><br></div><div dir=
=3D"auto">Any additional data in the commitment but hash it the transaction=
is pointless, because the security properties are the same. You can't =
freeze an UTXO after only seeing a commitment, and for any two conflicting =
transactions you may observe it does not matter at all if one references UT=
XO:s or not since you already know both transactions' commitment ages a=
nyway. Oldest would win no matter the additional data.=C2=A0=C2=A0</div><di=
v dir=3D"auto"><br></div><div dir=3D"auto">Commitments work when the networ=
k can't easily be censored for long enough to deploy the attack (at lea=
st for 2-3 blocks worth of time). They fail when the attacker is capable of=
performing such an attack.=C2=A0</div><div dir=3D"auto"><br></div><div dir=
=3D"auto">As I said previously, the only completely solid solution in all c=
ircumstances is a quantum resistant Zero-knowledge proof algorithm, or some=
equivalent method of proving knowledge of the key without revealing any da=
ta that enables a quantum attack.</div><div dir=3D"auto"><div class=3D"gmai=
l_extra"><div class=3D"gmail_quote"><blockquote class=3D"quote" style=3D"ma=
rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"></blockquote><=
/div></div></div></div>
--94eb2c1cd0f27b48380565460ed5--
|
