path: root/36/190fc3f5ef61336a0267f100e78e5e36a0bc36

Return-Path: <jan.capek@braiins.cz>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id D5D06B8C
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  7 Apr 2017 22:48:17 +0000 (UTC)
Received: by mail-wm0-f68.google.com with SMTP id d79so489242wmi.2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>
	(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?= <jan.capek@braiins.cz>
To: Sergio Demian Lerner via bitcoin-dev
	<bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20170408004811.2a0c2b9e@glum>
In-Reply-To: <CAKzdR-rzb6oBq01DQM530pdgNUjzc79yjtYp_HAyF5GZpBPnFw@mail.gmail.com>
References: <CAKzdR-rzb6oBq01DQM530pdgNUjzc79yjtYp_HAyF5GZpBPnFw@mail.gmail.com>
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 <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: 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
<bitcoin-dev@lists.linuxfoundation.org> wrote:

> <pre>
>   BIP: TBD
>   Layer: Consensus
>   Title: Inhibiting a covert optimization on the Bitcoin POW function
>   Author: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
>   Status: Draft
>   Type: Standards Track
>   Created: 2016-04-07
>   License: PD
> </pre>
> 
> ==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 <greg@xiph.org> 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