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 AEA90305 for ; Fri, 18 Nov 2016 03:20:56 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-yw0-f170.google.com (mail-yw0-f170.google.com [209.85.161.170]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 906FDFE for ; Fri, 18 Nov 2016 03:20:55 +0000 (UTC) Received: by mail-yw0-f170.google.com with SMTP id r204so155991001ywb.0 for ; Thu, 17 Nov 2016 19:20:55 -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=/MbQyI2Y/914U7GPxArGP4sYwF9ikpzbM3VvAl73uDw=; b=R+TYb4veM2EqBJAAebzq3VoTTSJFQolVWSMmUSry+TLzRqU7Bk6OpPXchzes2lcOVs tPlEoF8vlS1o1mbmNpwXD2T8PWZoMShXLh+y7FmbXJkGrXOe0ycZEe4Q0BMapS/4uleN z1sEX3g/2iTUKx0azulHdMg7Sk8xqdi9uxIaX25pmLBWPc55onkdsrizIsSo4q6wzuHb sX0pGZUWH6/4fPKS6E1nehK4ItMN9NxFZAvdZ12Tr7IwLYiucFJFjsT+zUhLxgwmYc+L WPIqA9XBH3Equ8anZAeWkEvh7N6WYAY7WrXVA2Y95DjnqeejKuefKvs6Cu8UvjWYQ2sj j1gw== 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=/MbQyI2Y/914U7GPxArGP4sYwF9ikpzbM3VvAl73uDw=; b=WfZ4sA68mZCHTC9RLVaLfmJr/qJyu5Ft0Hd46jny1MsIhk54dwWQLKi+iMG9G4XzQ6 QaHPsffD9l965luSGzstcz9CB43ltWLWHJo97T2kzgcaK407VU+FKZiSaimKCcN3fSu8 D6ubDn7Yfk8fMHiHG+58RPBwB8WD3j76icC2hrXC06lzSdRO/h5oB5q22Gxl3icEg4aC y4Kvofu5jVNpSaRS+nT9cxpwHLYMe+VSxBTgqypNilG8yaHPg6nz1LL59dREB+Asa9bJ 1Wcayp3Ik6kFtjz7ZDUwGUH/oU20v9MI1YPDoWOnoSuQm50wGMDML2blQFUoAUNUa5xR 9ZuQ== X-Gm-Message-State: AKaTC01Fce/90q9IAcI/jKl26q1LL/sMq1DjE2+R+lKZwryppFHSW6UfW0OBK5mhdliQ7Q== X-Received: by 10.129.82.214 with SMTP id g205mr5426229ywb.73.1479439254558; Thu, 17 Nov 2016 19:20:54 -0800 (PST) Received: from [10.189.101.3] ([166.170.56.221]) by smtp.gmail.com with ESMTPSA id w184sm2197638ywe.16.2016.11.17.19.20.53 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 17 Nov 2016 19:20:53 -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: <6F2B3EA2-4245-4A0E-8E19-12D02A871815@xbt.hk> Date: Thu, 17 Nov 2016 22:20:52 -0500 Content-Transfer-Encoding: quoted-printable Message-Id: <11B3C69E-5F1B-4D25-86CE-E5F3B603266F@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> <59D27CC6-120C-4673-9F20-6B5E95EA60C6@voskuil.org> <6F2B3EA2-4245-4A0E-8E19-12D02A871815@xbt.hk> To: Johnson Lau X-Spam-Status: No, score=1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,MIME_QP_LONG_LINE,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_WEB autolearn=no version=3.3.1 X-Spam-Level: * X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Fri, 18 Nov 2016 03:26:32 +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: Fri, 18 Nov 2016 03:20:56 -0000 You are suggesting that, since a node implements a denial of service policy t= hat actually denies itself otherwise valid blocks, those blocks are conditio= nally invalid. And that, since the validity condition is based on order of a= rrival and therefore independently unverifiable, Bitcoin consensus is broken= in the face of a hash collision. I am aware of two other hash collision scenarios that cause Core to declare b= locks invalid based on ordering. The block hash duplicate check (it's not fo= rk-point relative) and signature verification caching. Like the "block banni= ng" issue above, the latter is related to an internal optimization. I would c= ategorize the former as a simple oversight that presumably goes way back. What then is the consequence of validity that is unverifiable? You believe t= his means that Bitcoin consensus is broken. This is incorrect. First underst= and that it is not possible for consensus rules to invalidate blocks based o= n order of arrival. As such any *implementation* that invalidates blocks bas= ed on order of arrival is broken. It is an error to claim that these behavio= rs are part of consensus, despite being implemented in the satoshi node(s). Validity must be verifiable independent of the state of other nodes. Consens= us is a function of block history and time alone. Time is presumed to be uni= versally consistent. To be a consensus rule all nodes must be able to indepe= ndently reach the same validity conclusion, given the same set of blocks, in= dependent of order. If this is not the case the behavior is not a consensus r= ule, it is simply a bug.=20 Deviating from such bugs is not a break with consensus, since such non-rules= cannot be part of consensus. One node implementation can behave determinist= ically while others are behaving non-deterministically, with the two nodes r= emaining consistent from a consensus standpoint (deterministic produces a su= bset of non-deterministic results). But, unlike arbitrary nodes, determinist= ic nodes will not cause disruption on the network. You imply that these determinism bugs are necessary, that there is no fix. T= his is also incorrect. The block banning hash collision bug is avoided by not using non-chain/clock= state to determine validity. Doing otherwise is clearly a bug. The hash of a= block is not the block itself, a logically-correct ban would be to compare t= he wire serialization of the block as opposed to the hash, or not maintain t= he feature at all. The signature verification caching hash collision bug is the same problem, a= n optimization based on an invalid assumption. A full serialization comparis= on (true identity), or elimination of the feature resolves the bug. The block hash check collision bug is trivially resolved by checking at the f= ork point as opposed to the tip. This prevents arbitrary (and irrational) in= validity based on conflict with irrelevant blocks that may or may not exist a= bove the fork point. Libbitcoin is deterministic in all three cases (although the third issue is n= ot made consistent until v3). I am not aware of any other non-determinism in= Core, but I don't spend a lot of time there. There is no need to study othe= r implementations to ensure determinism, as that can be verified independent= ly. Any situation in which a node cannot provide deterministic validation of uno= rdered blocks constitutes a non-consensus bug, as the behavior is not consis= tently verifiable by others under any conditions. Fixing/preventing these bu= gs is responsible development behavior, and does not require forks or BIPs, s= ince Bitcoin doesn't inherently contain any such bugs. They are the conseque= nce of incorrect implementation, and in two of the three cases above have re= sulted from supposed optimizations. But any code that creates non-determinis= m in exchange for speed, etc. is not an optimization, it's a bug. A node mus= t implement its optimizations in a manner that does not alter consensus. The BIP30 regression hard fork is not a case of non-determinism. This will p= roduce deterministic results (apart from the impact of unrelated bugs). Howe= ver the results are both a clear break from previous (and documented) consen= sus but also produce a very undesirable outcome - destruction of all unspent= outputs in the "replaced" transaction for starters. So this is a distinct c= ategory, not a determinism bug but a hard fork that produces undesired conse= quences. The BIP30 regression hard fork actually enables the various pathological sce= narios that you were describing, where no such issues existed in Bitcoin con= sensus previously. It is now possible to produce a block that mutates anothe= r arbitrarily deep block, and forces a reorg all the way back to the mutated= block. This was done to save microseconds per block. Despite the improbabil= ity of hash collisions, I find this deplorable and the lack of public discus= sion on the decision concerning. With respect to the original post, the point at issue is the introduction of= another hard fork, with some odd behaviors, but without any justification a= part from tidying up the small amount of necessary code. These issues are re= lated in that they are both consensus forks that have been introduced as sup= posed optimizations, with no public discussion prior to release (or at least= merging to master with the presumption of shipping in the latter case). Two= of the three hash collision issues above are also related in that they are b= ugs introduced by a desire to optimize internals. The engineering lesson here should be clear - watch out for developers beari= ng optimizations. A trade against correctness is not an optimization, it's a= break. Satoshi was clearly a fan of the premature optimization. FindAndDele= te is a howler. So this is a tradition in Bitcoin. My intent is not to sling= mud but to improve the situation. It is very possible to produce straightforward and deterministic code that a= bides consensus and materially outperforms Core, without any of the above op= timization breaks, even avoiding the utxo set optimization. Even the tx (mem= ory) and block (orphan) pools are complex store denormalizations implemented= as optimizations. Optimizing before producing a clean conceptual model arch= itecture and design is a software development anti-pattern (premature optimi= zation). The proposed fork is a premature optimization. There are much more s= ignificant opportunities to better organize code (and improve performance). I= cannot support the decision to advance it. I was unaware Core had regressed BIP30. Given that the behavior is catastrop= hic and that it introduces the *only* hash-collision consensus misbehavior (= unless we consider a deep reorg sans the otherwise necessary proof of work d= esirable behavior), I strongly recommend it be reverted, with a post-mortem B= IP. Finally I recommend people contemplate the difference between unlikely and i= mpossible. The chance of random collision is very small, but not zero. Colli= ding hashes is extremely difficult, but not impossible. But Bitcoin does not= rely on impossibility for correct behavior. It relies of difficulty. This i= s a subtle but important distinction that people are missing. Difficulty is a knowable quantity - a function of computing power. If hash o= perations remain difficult, Bitcoin is undeterred. Collisions will have no i= mpact, even if they happen with unexpected frequency (which would still be v= anishingly infrequent). If the difficulty of producing a collision is reduce= d to the point where people cannot rely on addresses (for example), then Bit= coin has a problem, as it has become a leaky ship (and then there's mining).= But with the unnecessary problems described above, a single hash collision c= an be catastrophic. Unlike difficulty, which is known, nobody can know when a= single collision will show up. Betting Bitcoin, and potentially the world's= money, on the unknowable is poor reasoning, especially given that the cost o= f not doing so is so very low. e > On Nov 17, 2016, at 10:08 AM, Johnson Lau wrote: >=20 > The fact that some implementations ban an invalid block hash and some do n= ot, suggests that it=E2=80=99s not a pure p2p protocol issue. A pure p2p spl= it should be unified by a bridge node. However, a bridge node is not helpful= in this case. Banning an invalid block hash is an implicit =E2=80=9Cfirst s= een=E2=80=9D consensus rule. >=20 > jl2012 >=20 >> On 18 Nov 2016, at 01:49, Eric Voskuil wrote: >>=20 >> Actually both possibilities were specifically covered in my description. S= orry if it wasn't clear. >>=20 >> If you create a new valid block out of an old one it's has potential to c= ause a reorg. The blocks that previously built on the original are still abl= e to do so but presumably cannot build forever on the *new* block as it has a= different tx. But other new blocks can. There is no chain split due to a di= fferent interpretation of valid, there are simply two valid competing chains= . >>=20 >> Note that this scenario requires not only block and tx validity with a tx= hash collision, but also that the tx be valid within the block. Pretty far t= o reach to not even get a chain split, but it could produce a deep reorg wit= h a very low chance of success. As I keep telling people, deep reorgs can ha= ppen, they are just unlikely, as is this scenario. >>=20 >> If you create a new invalid block it is discarded by everyone. That does n= ot invalidate the hash of that block. Permanent blocking as you describe it w= ould be a p2p protocol design choice, having nothing to do with consensus. L= ibbitcoin for example does not ban invalidated hashes at all. It just discar= ds the block and drops the peer. >>=20 >> e >=20 >=20