Re: [bitcoin-dev] BIP Proposal: Inhibiting a covert optimization on the Bitcoin POW function

["Jan Čapek" <jan.capek@braiins.cz>]

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