Re: [bitcoin-dev] BIP Proposal: Inhibiting a covert optimization on the Bitcoin POW function
Hi, 1 comment below On Fri, 7 Apr 2017 17:52:17 -0300 Sergio Demian Lerner via bitcoin-devwrote: > > 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 >
[bitcoin-dev] BIP Proposal: Inhibiting a covert optimization on the Bitcoin POW function
BIP: TBD Layer: Consensus Title: Inhibiting a covert optimization on the Bitcoin POW function Author: Sergio Demian LernerStatus: 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