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.ler...@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 <g...@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.ca...@braiins.cz http://braiins.cz http://slushpool.com _______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev