Content-Type: text/plain;
	charset=utf-8
Mime-Version: 1.0 (1.0)
From: Eric Voskuil <eric@voskuil.org>
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>
Cc: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP30 and BIP34 interaction (was Re: [BIP
	Proposal] Buried Deployments)
Precedence: list

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