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 28B48BD3 for ; 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 ; Thu, 17 Nov 2016 17:49:47 +0000 (UTC) Received: by mail-it0-f42.google.com with SMTP id y23so66080469itc.0 for ; 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 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: <5ef23296-5909-a350-ab11-e717f8fffc41@voskuil.org> <34949746-c0c9-7f14-0e92-69d5a7d44b04@voskuil.org> <8d92ae05-ac6a-30b7-5ef3-f7aa1298e46d@voskuil.org> <632B36D5-74AF-41E2-8E21-359F02645066@xbt.hk> To: Johnson Lau 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 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: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 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 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