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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
|
Return-Path: <eric@voskuil.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 28B48BD3
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 17 Nov 2016 17:49:49 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f42.google.com (mail-it0-f42.google.com
[209.85.214.42])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 0E388144
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 17 Nov 2016 17:49:47 +0000 (UTC)
Received: by mail-it0-f42.google.com with SMTP id y23so66080469itc.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 17 Nov 2016 09:49:47 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=voskuil-org.20150623.gappssmtp.com; s=20150623;
h=mime-version:subject:from:in-reply-to:date:cc
:content-transfer-encoding:message-id:references:to;
bh=iT+8VBmMLmeyt+r8f+rePNqsAn5LWPjCUO+quIs+upQ=;
b=P7oOKmOGrqtK1iHR8HzTTad6y5bxCmGV7WeHJkli93ToOP74R5yzAQglKJKzUPKglN
ZQj8BYI+Tqd+rOBpVxJfB/DhVuTnuviZqvZomPq88pVV9mgB8S2w2qPbGr2Q4eMKuI2Q
XFGWrDIE04vWSfD+OW7xFl1IrOarhZPDknWeqy0Upv7jVtZxIc+5dCwmiywQdXegt36v
hfiL8L06CZA6HL14cBkpmvAYB+TDvGwa8XJPAZ2DbNLtTu9jxwGRACfKj9Zz+p6nGzjT
M8RljQSZ3+x7JtqI4foICUOxtre6J2TpZ2CmpZaaddNTjpi5ela7OeSbljA1PMgE8PMu
MAJg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc
:content-transfer-encoding:message-id:references:to;
bh=iT+8VBmMLmeyt+r8f+rePNqsAn5LWPjCUO+quIs+upQ=;
b=Jsq3u4agWlfTV1KpmAZxyRYgEoCHmquGiFhI1tcHYxmB2rMNwRGM3i3hE6J+6H/8k0
zAGNi9GXocnI4n0RvEzaUjqRJ+p/VBz4aS7p+p2cMeufIdKvEKxaSK0KUlTElUT7GJHW
9yJTE27kp68k4SZo13NXsKQH82YdbzJKQ7p01+dentxhJS72m3xdcOmWQ+rkpXJ7H+7G
crth1r6X7p2j6XjT92XopxWhvgH4AgDbskJUPH/Du6sNOHSujxcWfqWlHmhGrxUW/g3L
ajPUw2nzLA9YQYDsGmHtPepKgoncqGfijrRUj6dpvGF+a5bzqzMANpJPaZHAugl6EHQN
L8AQ==
X-Gm-Message-State: AKaTC02lT7quJbOio1NXlpjC0jmcOEmkZRjOdCIMOVPST//5jte/gUDtQgF1BfgpkIQbrg==
X-Received: by 10.107.8.105 with SMTP id 102mr4138209ioi.154.1479404987298;
Thu, 17 Nov 2016 09:49:47 -0800 (PST)
Received: from [10.0.1.14] (c-24-19-229-46.hsd1.wa.comcast.net. [24.19.229.46])
by smtp.gmail.com with ESMTPSA id 145sm5367157itg.7.2016.11.17.09.49.46
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Thu, 17 Nov 2016 09:49:46 -0800 (PST)
Content-Type: text/plain;
charset=utf-8
Mime-Version: 1.0 (1.0)
From: Eric Voskuil <eric@voskuil.org>
X-Mailer: iPhone Mail (14B100)
In-Reply-To: <632B36D5-74AF-41E2-8E21-359F02645066@xbt.hk>
Date: Thu, 17 Nov 2016 09:49:45 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <59D27CC6-120C-4673-9F20-6B5E95EA60C6@voskuil.org>
References: <CABm2gDr2-MCiaFFjgUFP5Xc0fQfuqJ3=ZkrzjHqmOiwRZ50CBw@mail.gmail.com>
<d58ee114-00fd-23c8-9ca7-9a4b28c26f27@voskuil.org>
<CAE-z3OX5vak25UWcmBSe63OmoOVoGB394WmwyWwUcSxWeDOLhw@mail.gmail.com>
<e0e6679f-aec6-a579-667d-b5b58ea2360b@voskuil.org>
<CAE-z3OXfJa3Lewtrafm25bdfPa=eiarOAXBNbgc3ccTi7Qoe6A@mail.gmail.com>
<5ef23296-5909-a350-ab11-e717f8fffc41@voskuil.org>
<CAPWm=eW9X77+qQZGHkAOjN-k7KFwq06gKS6HOVOTE1+SmYBhWA@mail.gmail.com>
<34949746-c0c9-7f14-0e92-69d5a7d44b04@voskuil.org>
<FA128F93-7E79-47FE-8270-225D07DD6FEF@xbt.hk>
<8d92ae05-ac6a-30b7-5ef3-f7aa1298e46d@voskuil.org>
<632B36D5-74AF-41E2-8E21-359F02645066@xbt.hk>
To: Johnson Lau <jl2012@xbt.hk>
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, MIME_QP_LONG_LINE,
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
X-Mailman-Approved-At: Thu, 17 Nov 2016 18:08:58 +0000
Cc: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP30 and BIP34 interaction (was Re: [BIP
Proposal] Buried Deployments)
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, 17 Nov 2016 17:49:49 -0000
Actually both possibilities were specifically covered in my description. Sor=
ry if it wasn't clear.
If you create a new valid block out of an old one it's has potential to caus=
e a reorg. The blocks that previously built on the original are still able t=
o do so but presumably cannot build forever on the *new* block as it has a d=
ifferent tx. But other new blocks can. There is no chain split due to a diff=
erent interpretation of valid, there are simply two valid competing chains.
Note that this scenario requires not only block and tx validity with a tx ha=
sh collision, but also that the tx be valid within the block. Pretty far to r=
each to not even get a chain split, but it could produce a deep reorg with a=
very low chance of success. As I keep telling people, deep reorgs can happe=
n, they are just unlikely, as is this scenario.
If you create a new invalid block it is discarded by everyone. That does not=
invalidate the hash of that block. Permanent blocking as you describe it wo=
uld be a p2p protocol design choice, having nothing to do with consensus. Li=
bbitcoin for example does not ban invalidated hashes at all. It just discard=
s the block and drops the peer.
e
> On Nov 17, 2016, at 9:22 AM, Johnson Lau <jl2012@xbt.hk> wrote:
>=20
> I=E2=80=99m not sure if you really understand what you and I am talking. I=
t has nothing to do with BIP30, 34, nor any other BIPs.
>=20
> Say tx1 is confirmed 3 years ago in block X. An attacker finds a valid tx2=
which (tx1 !=3D tx2) and (SHA256(tx1) =3D=3D SHA256(tx2)). Now he could rep=
lace tx1 with tx2 in block X and the block is still perfectly valid. Anyone t=
rying to download the blockchain from the beginning may end up with a differ=
ent ledger. The consensus is irrevocably broken as soon as tx1 or tx2 is spe=
nt.
>=20
> Or, alternatively, an attacker finds an invalid tx3 which (tx1 !=3D tx3) a=
nd (SHA256(tx1) =3D=3D SHA256(tx3)). Now he could replace tx1 with tx3 in bl=
ock X. Anyone trying to download the blockchain from the beginning will perm=
anently reject the hash of block X. They will instead accept a fork built on=
top of block X-1. The chain will be permanently forked.
>=20
> jl2012
>=20
>=20
>> On 18 Nov 2016, at 01:01, Eric Voskuil <eric@voskuil.org> wrote:
>>=20
>> On 11/17/2016 07:40 AM, Johnson Lau wrote:
>>>=20
>>>> On 17 Nov 2016, at 20:22, Eric Voskuil via bitcoin-dev
>> <bitcoin-dev@lists.linuxfoundation.org> wrote:
>>>>=20
>>>> Given that hash collisions are unquestionably possible,
>>>=20
>>> Everything you said after this point is irrelevant.
>>=20
>> So... you think hash collisions are not possible, or that it's moot
>> because Core has broken its ability to handle them.
>>=20
>>=20
>>> Having hash collision is **by definition** a consensus failure,
>>=20
>> I suppose if you take fairly recent un-BIPped consensus changes in Core
>> to be the definition of consensus, you would be right about that.
>>=20
>>=20
>>> or a hardfork.
>>=20
>> And those changes could definitely result in a chain split. So right
>> about that too.
>>=20
>>=20
>>> You could replace the already-on-chain tx with the collision and
>> create 2 different versions of UTXOs (if the colliding tx is valid), or
>> make some nodes to accept a fork with less PoW (if the colliding tx is
>> invalid, or making the block invalid, such as being to big).
>>=20
>>=20
>> Not in accordance with BIP30 and not according to the implementation of
>> it that existed in Core until Nov 2015. A tx was only valid as a
>> "replacement" if it did not collide with the hash of an existing tx with
>> unspent outputs. The collision would have been rejected. And an invalid
>> colliding tx would not be accepted in any case (since nodes presumably
>> validate blocks and don't rely on checkpoints as a security measure).
>>=20
>> A transaction duplicating the hash of another and taking its place in a
>> block would not only have to collide the hash, but it would have to be
>> fully valid in the context of the block you are suggesting it is
>> substituted into. In that case it's simply a fully valid block. This is
>> not just the case of a hash collision, this is the case of a hash
>> collision where both transactions are fully valid in the context of the
>> same block parent. Even if that unlikely event did occur, it's not a
>> hard fork, it's a reorg. The chain that builds on this block will be
>> valid to all nodes but necessarily deviates from the other block's valid
>> chain. This is true whether the magical block is assembled via compact
>> blocks or otherwise.
>>=20
>> Transaction "replacement" is an implementation detail of Core. Once Core
>> accepted a replacement of a previously spent transaction it would be
>> unable to provide the previous block/spent-tx, but that would be a
>> wallet failure and an inability to provide valid historical blocks, not
>> a consensus/validation failure. The previously spent outputs no longer
>> contribute to validation, unless there is a reorg back to before the
>> original tx's block, and at that point it would be moot, since neither
>> transaction is on the chain.
>>=20
>> You are referring to the *current* behavior ("replacement" without
>> concern for collision). That was an unpublished hard fork, and is the
>> very source of the problems you are describing.
>>=20
>>> To put it simply, the Bitcoin protocol is broken. So with no doubt,
>> Bitcoin Core and any implementation of the Bitcoin protocol should
>> assume SHA256 collision is unquestionably **impossible**.
>>=20
>> I'm not disagreeing with you that it is broken. I'm pointing out that it
>> was broken by code that was merged recently - an undocumented hard fork
>> that reverted the documented BIP30 behavior that was previously
>> implemented correctly, based on the assumption that hash collisions
>> cannot occur, for the modest performance boost of not having to check
>> for unspent duplicates (sounds sort of familiar).
>>=20
>>> If some refuse to make such assumption, they should have introduced an
>> alternative hash algorithm and somehow run it in parallel with SHA256 to
>> prevent the consensus failure.
>>=20
>> No hash algorithm can prevent hash collisions, including one that is
>> just two running in parallel. A better resolution would be to fix the
>> problem.
>>=20
>> There is no need to replace the BIP30 rule. That resolves the TX hash
>> collision problem from a consensus standpoint. In order to serve up
>> whole blocks in the circumstance requires a more robust store than I
>> believe is exists in Core, but that has nothing to do with validity.
>>=20
>> The block hash check and signature validation caching splits caused by
>> collision can easily be avoided, and doing so doesn't break with
>> consensus. I'm not aware of any other aspects of consensus that are
>> effected by an implementation assumption of non-colliding hashes. But in
>> any case I'm pretty sure there aren't any that are necessary to consensus=
.
>>=20
>> e
>=20
>=20
|