<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. 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.