Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 9.3 \(3124\))
From: Johnson Lau <jl2012@xbt.hk>
In-Reply-To: <8d92ae05-ac6a-30b7-5ef3-f7aa1298e46d@voskuil.org>
Date: Fri, 18 Nov 2016 01:22:56 +0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <632B36D5-74AF-41E2-8E21-359F02645066@xbt.hk>
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>
To: Eric Voskuil <eric@voskuil.org>
Cc: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP30 and BIP34 interaction (was Re: [BIP
	Proposal] Buried Deployments)
Precedence: list

I=E2=80=99m not sure if you really understand what you and I am talking. =
It has nothing to do with BIP30, 34, nor any other BIPs.

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 replace tx1 with tx2 in block X and the block is still perfectly =
valid. Anyone trying to download the blockchain from the beginning may =
end up with a different ledger. The consensus is irrevocably broken as =
soon as tx1 or tx2 is spent.

Or, alternatively, an attacker finds an invalid tx3 which (tx1 !=3D tx3) =
and (SHA256(tx1) =3D=3D SHA256(tx3)). Now he could replace tx1 with tx3 =
in block X. Anyone trying to download the blockchain from the beginning =
will permanently 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.

jl2012


> 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