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
|
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 3EB12AB6
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 17 Nov 2016 17:01:21 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f48.google.com (mail-it0-f48.google.com
[209.85.214.48])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A63A9CD
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 17 Nov 2016 17:01:20 +0000 (UTC)
Received: by mail-it0-f48.google.com with SMTP id j191so62706770ita.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 17 Nov 2016 09:01:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=voskuil-org.20150623.gappssmtp.com; s=20150623;
h=subject:to:references:cc:from:message-id:date:user-agent
:mime-version:in-reply-to;
bh=grDhZCRNKFN24vw4DFquO1mcuugkL7pQ1Pt8RdZsiuw=;
b=n7FJGLkrwFQ9niWVrfsRa6xQe9qgd3ZXFHI8mA/Tic7NGpRlMtN9rIdD6yKkslnduw
Ck4N0AYylpGqFtSBxDdXhDWnxzFhwJfhTgBmqeP+pioZGYRF91HlNQiw6MAI0cdia3dR
+qMMi4OWQm9Rnw94+IJzrH/2PhNxQuAn3JZp/EvJSv2eX2PkNDusGE7dRt6Pgf/i+vku
StBnns2lgZYSKugxa1u+Yk8gCL78el7iiZX+v+QVJoUcySl6121fQLzzXc8+xgOIHrWp
SDNgWl3iQvfYoB3/X418Y0Dw4N8ZhvwN0OyORocXw74JgjcDP7DCOC2dnYDTtCO7jeSB
054w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:subject:to:references:cc:from:message-id:date
:user-agent:mime-version:in-reply-to;
bh=grDhZCRNKFN24vw4DFquO1mcuugkL7pQ1Pt8RdZsiuw=;
b=CfnpnPQoT1TCFCv/rx7TK5g3MF8xlnxQSSk8pxamL7AgZfFyCvOWJTwnuMEKK5lc7C
LEpUm013OPm/QxVewC1t+Fj6UKdahtZ5sHUUJVvbIaRfERYsMY6z0ZB5J+5edazAk08L
B+26/N4Vtw2B2pkxxHML/1CX6WG/XQ0KUBXzOi1iMrqNa86bmc4fBxs3ixTye2zGX40x
EOTJH++Y7ejz2ql1HLPRtnS6loar+bz0ixv879sK2JuFk55OuvUrZW7oZPgoVkXSoy4Y
St9mHXOjJkanLiqWGD+l5M0smMdtJKHYr6D6Vvd/k8igif+9bnrBfIFYD8jADB5Zeoj0
vgYA==
X-Gm-Message-State: ABUngvcsd1CcV1tcdsC/UqXhU49rrGzf2GYPmi6B+zOYWV9LY2w2k8WVo4ur282rR3cR9g==
X-Received: by 10.36.196.135 with SMTP id v129mr14076155itf.100.1479402079868;
Thu, 17 Nov 2016 09:01:19 -0800 (PST)
Received: from ?IPv6:2601:600:9000:d69e:8084:4206:2529:776d?
([2601:600:9000:d69e:8084:4206:2529:776d])
by smtp.gmail.com with ESMTPSA id
m128sm5276213itm.9.2016.11.17.09.01.18
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Thu, 17 Nov 2016 09:01:19 -0800 (PST)
To: Johnson Lau <jl2012@xbt.hk>,
bitcoin-dev <bitcoin-dev@lists.linuxfoundation.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>
From: Eric Voskuil <eric@voskuil.org>
X-Enigmail-Draft-Status: N0110
Message-ID: <8d92ae05-ac6a-30b7-5ef3-f7aa1298e46d@voskuil.org>
Date: Thu, 17 Nov 2016 09:01:20 -0800
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.3.0
MIME-Version: 1.0
In-Reply-To: <FA128F93-7E79-47FE-8270-225D07DD6FEF@xbt.hk>
Content-Type: multipart/signed; micalg=pgp-sha1;
protocol="application/pgp-signature";
boundary="ORMEO88QddbuhpdsH7emMN85nWf4V1ksk"
X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, RCVD_IN_DNSWL_NONE,
RCVD_IN_SORBS_SPAM autolearn=no 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 17:07:03 +0000
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:01:21 -0000
This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--ORMEO88QddbuhpdsH7emMN85nWf4V1ksk
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
On 11/17/2016 07:40 AM, Johnson Lau wrote:
>
>> On 17 Nov 2016, at 20:22, Eric Voskuil via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>> Given that hash collisions are unquestionably possible,
>
> Everything you said after this point is irrelevant.
So... you think hash collisions are not possible, or that it's moot
because Core has broken its ability to handle them.
> Having hash collision is **by definition** a consensus failure,
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.
> or a hardfork.
And those changes could definitely result in a chain split. So right
about that too.
> 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).
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).
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.
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.
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.
> 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**.
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).
> 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.
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.
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.
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=
=2E
e
--ORMEO88QddbuhpdsH7emMN85nWf4V1ksk
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (GNU/Linux)
iQEcBAEBAgAGBQJYLeJgAAoJEDzYwH8LXOFOBVwIAI/KcdbFy5eNqfkEktA486Ro
Z5MlC0st4kajEhGSGeunNmlUUdTHpYckiq1fmAxw0OdvYw3MeNfVrNFzY3ALNjZX
cioUUjprNdDgV/Q4cMXocoXBAqsUApzG7X9gpKamxyI44L76Ha9ZcMI5DlJBBWAa
n/OvV6OPOrOmPlnkCMJHUbwKjx2Pr2vcx/gL3ppreLhVuBJfv9z1DjyDGhXeZxG1
wOPYv1+1hmPvRorzW3UHrcIfQNdobsUgp4itF1nt1koFmRv+TvGzkvCmffK6oYFb
PbtwgoSIlwLrhQIiKwjKKMSlyTltY1G+cCUIf6kYm0CKCasUxoERE9D2GgNO+oM=
=iZUz
-----END PGP SIGNATURE-----
--ORMEO88QddbuhpdsH7emMN85nWf4V1ksk--
|
