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 D5D06B8C for ; Fri, 7 Apr 2017 22:48:21 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f68.google.com (mail-wm0-f68.google.com [74.125.82.68]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 94C83F3 for ; Fri, 7 Apr 2017 22:48:17 +0000 (UTC) Received: by mail-wm0-f68.google.com with SMTP id d79so489242wmi.2 for ; Fri, 07 Apr 2017 15:48:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braiins-cz.20150623.gappssmtp.com; s=20150623; h=date:from:to:subject:message-id:in-reply-to:references:organization :mime-version:content-transfer-encoding; bh=IjBq0idjxJcbB5G3JBn81njJt9PGLWaFF1M1rY5Jmhs=; b=RVujPbttv6H3RFkIa2qfQEHKiWlaMIdSqRdzWotRPySAu4aGASIENfgqpe1vRic15l L0dnxrMQ8SHodEC6GUlY15HVEqJj26HtoQEbm1A2UAnNMqInVudRV5wgVGO8LPaAJ7te unfj2KVOoclhjBD/QRk6eKBCOAt4zogtnPiq/xY2NtFZMJquhwSnguafH0c7ag9Orx1S EYSqGug5fUFGJIqCGiXVIZ4IGyZBBOgfxc2oxgKuE7kEcwOLBNluw1idkHWBclv1iVsv lFzNWnnm2M4/TipWKWbnvBgUuwZNcS7l6Wx5NZmUiXEk2M9IuOjO+smW4E/cvDOFq8XH RcWw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:subject:message-id:in-reply-to :references:organization:mime-version:content-transfer-encoding; bh=IjBq0idjxJcbB5G3JBn81njJt9PGLWaFF1M1rY5Jmhs=; b=NbC/bAc8EPXV91HdNGjuGoD1ux/iR6fXuotUqHtED+dVu47qAABIzaghR6/xVQPi0Y YCooAYH1iaNDHmOkv5yiP+zkv8jJj46pBmUArS5SqGEHOAnafxNykH2tGyqi3wJY2fTo CuaHLfViMVRwLWX9ED80aGAavRoFvoJySQo2PiFK/97PSxkjJ2i3eLBSo85DLpOnvrlD OFyzH2qXw0PZVeIgMhVwBCiFcshk2t1/hF+pTrtqUqEIy9jLIFzOzi8hv7exWzQSTl/f 6Qiqr8UZp+7aHiIgZYEfYgPMos3r0EUNAl2AucdbrdOrc4Nj2LpFCvigFX7qY9O2Arsh 48cg== X-Gm-Message-State: AN3rC/5gfuI8WbiBfhT+Q3jyGGQKBbETQ5tukA7Q8bFzxqsOG36K6WtQ CSQLt6uKjYLHcn1k X-Received: by 10.28.40.198 with SMTP id o189mr1309471wmo.108.1491605295256; Fri, 07 Apr 2017 15:48:15 -0700 (PDT) Received: from glum ([185.112.167.79]) by smtp.gmail.com with ESMTPSA id l90sm453112wmi.25.2017.04.07.15.48.14 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 07 Apr 2017 15:48:15 -0700 (PDT) Date: Sat, 8 Apr 2017 00:48:11 +0200 From: Jan =?UTF-8?B?xIxhcGVr?= To: Sergio Demian Lerner via bitcoin-dev Message-ID: <20170408004811.2a0c2b9e@glum> In-Reply-To: References: Organization: braiins X-Mailer: Claws Mail 3.13.2 (GTK+ 2.24.30; x86_64-pc-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Fri, 07 Apr 2017 22:51:47 +0000 Subject: Re: [bitcoin-dev] BIP Proposal: Inhibiting a covert optimization on the Bitcoin POW function 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, 07 Apr 2017 22:48:21 -0000 Hi, 1 comment below On Fri, 7 Apr 2017 17:52:17 -0300 Sergio Demian Lerner via bitcoin-dev wrote: > 
>   BIP: TBD
>   Layer: Consensus
>   Title: Inhibiting a covert optimization on the Bitcoin POW function
>   Author: Sergio Demian Lerner 
>   Status: Draft
>   Type: Standards Track
>   Created: 2016-04-07
>   License: PD
>
> > ==Abstract== > > This proposal inhibits the covert use of a known optimization in > Bitcoin Proof of Work function. > > The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", > "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this > document are to be interpreted as described in RFC 2119. > > ==Motivation== > > Due to a design oversight the Bitcoin proof of work function has a > potential optimization which can allow a rational miner to save up-to > 30% of their energy > costs (though closer to 20% is more likely due to implementation > overheads). > > Timo Hanke and Sergio Demian Lerner applied for a patent on this > optimization. The company "Sunrise Tech Group, Llc" has offered to > license it to any interested party in the past. Sunrise Tech Group > has been marketing their patent licenses under the trade-name > ASICBOOST. The document takes no position on the validity or > enforceability of the patent. > > There are two major ways of taking advantage of this optimization, as > described > by the patent: > One way which is highly detectable and is not in use on the network > today and a covert way which has significant interaction and potential > interference with the Bitcoin protocol. The covert mechanism is not > easily detected except through its interference with the protocol. > > In particular, the protocol interactions of the covert method can > block the implementation of virtuous improvements such as segregated > witness. > > The use of this optimization could result in a big payoff, but the > actual sum depends on the degree of research, investment and effort > put into designing > the improved cores. > > On the above basis the potential for covert use of this optimization > in the covert form and interference with useful improvements presents > a danger to the Bitcoin system. > > ==Background== > > The general idea of this optimization is that SHA2-256 is a merkle > damgard hash > function which consumes 64 bytes of data at a time. > > The Bitcoin mining process repeatedly hashes an 80-byte 'block > header' while incriminating a 32-bit nonce which is at the end of > this header data. This means that the processing of the header > involves two runs of the compression function run-- one that consumes > the first 64 bytes of the header and a second which processes the > remaining 16 bytes and padding. > > The initial 'message expansion' operations in each step of the > SHA2-256 function operate exclusively on that step's 64-bytes of > input with no influence from prior data that entered the hash. > > Because of this if a miner is able to prepare a block header with > multiple distinct first 64-byte chunks but identical 16-byte > second chunks they can reuse the computation of the initial > expansion for multiple trials. This reduces power consumption. > > There are two broad ways of making use of this optimization. The > obvious way is to try candidates with different version numbers. > Beyond upsetting the soft-fork detection logic in Bitcoin nodes this > has little negative effect but it is highly conspicuous and easily > blocked. > > The other method is based on the fact that the merkle root > committing to the transactions is contained in the first 64-bytes > except for the last 4 bytes of it. If the miner finds multiple > candidate root values which have the same final 32-bit then they > can use the optimization. > > To find multiple roots with the same trailing 32-bits the miner can > use efficient collision finding mechanism which will find a match > with as little as 2^16 candidate roots expected, 2^24 operations to > find a 4-way hit, though low memory approaches require more > computation. > > An obvious way to generate different candidates is to grind the > coinbase extra-nonce but for non-empty blocks each attempt will > require 13 or so additional sha2 runs which is very inefficient. > > This inefficiency can be avoided by computing a sqrt number of > candidates of the left side of the hash tree (e.g. using extra > nonce grinding) then an additional sqrt number of candidates of > the right side of the tree using transaction permutation or > substitution of a small number of transactions. All combinations > of the left and right side are then combined with only a single > hashing operation virtually eliminating all tree related > overhead. > > With this final optimization finding a 4-way collision with a > moderate amount of memory requires ~2^24 hashing operations > instead of the >2^28 operations that would be require for > extra-nonce grinding which would substantially erode the > benefit of the optimization. > > It is this final optimization which this proposal blocks. > > ==New consensus rule== > > Beginning block X and until block Y the coinbase transaction of > each block MUST either contain a BIP-141 segwit commitment or a > correct WTXID commitment with ID 0xaa21a9ef. > > (See BIP-141 "Commitment structure" for details) > > Existing segwit using miners are automatically compatible with > this proposal. Non-segwit miners can become compatible by simply > including an additional output matching a default commitment > value returned as part of getblocktemplate. > > Miners SHOULD NOT automatically discontinue the commitment > at the expiration height. > > ==Discussion== > > The commitment in the left side of the tree to all transactions > in the right side completely prevents the final sqrt speedup. > > A stronger inhibition of the covert optimization in the form of > requiring the least significant bits of the block timestamp > to be equal to a hash of the first 64-bytes of the header. This > would increase the collision space from 32 to 40 or more bits. > The root value could be required to meet a specific hash prefix > requirement in order to increase the computational work required > to try candidate roots. Root value pow - Does this mean that every miner would be penalized in this way regardless of the actual number of transactions in the block? > These change would be more disruptive and > there is no reason to believe that it is currently necessary. > > The proposed rule automatically sunsets. If it is no longer needed > due to the introduction of stronger rules or the acceptance of the > version-grinding form then there would be no reason to continue > with this requirement. If it is still useful at the expiration > time the rule can simply be extended with a new softfork that > sets longer date ranges. > > This sun-setting avoids the accumulation of technical debt due > to retaining enforcement of this rule when it is no longer needed > without requiring a hard fork to remove it. > > == Overt optimization == > > A BIP for avoiding erroneous warning messages when miners use the > overt version > of the optimization was proposed several years ago, in order to deter > the covert > use of the optimization. But that BIP was rejected. > However, in light of the current discoveries, that BIP could be > reconsidered. > > The over optimization does not generally interfere with improvements > in the protocol. > > ==Backward compatibility== > > > ==Implementation== > > > ==Acknowledgments== > > Greg Maxwell for the original report, which contained > several errors that were corrected in the present proposal. > > ==Copyright== > > This document is placed in the public domain. -- CEO Braiins Systems | Slushpool.com tel: +420 604 566 382 email: jan.capek@braiins.cz http://braiins.cz http://slushpool.com