path: root/08/2c43e35ed0ddd4cd25b878b6dbc0f0ac00461f

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