From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id AC7D7BA6 for ; Thu, 17 Nov 2016 17:23:05 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from sender163-mail.zoho.com (sender163-mail.zoho.com [74.201.84.163]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id EB6321D0 for ; Thu, 17 Nov 2016 17:23:04 +0000 (UTC) Received: from [10.8.8.2] (119246245241.ctinets.com [119.246.245.241]) by mx.zohomail.com with SMTPS id 1479403379422954.6926223340656; Thu, 17 Nov 2016 09:22:59 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 9.3 \(3124\)) From: Johnson Lau 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: <5ef23296-5909-a350-ab11-e717f8fffc41@voskuil.org> <34949746-c0c9-7f14-0e92-69d5a7d44b04@voskuil.org> <8d92ae05-ac6a-30b7-5ef3-f7aa1298e46d@voskuil.org> To: Eric Voskuil X-Mailer: Apple Mail (2.3124) X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,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 Cc: bitcoin-dev 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 17 Nov 2016 17:23:05 -0000 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 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 > 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