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

In particular, the protocol interactions of the covert method can = block the

implementation of virtuous improvements such as segrega= ted witness.

The use of this optimization could re= sult in a big payoff, but the actual

sum depends on the degree of= research, investment and effort put into designing

the improved = cores. =C2=A0

On the above basis the potential for= covert use of this optimization=C2=A0

in the covert form and int= erference with useful improvements presents a=C2=A0

danger to the= Bitcoin system.

=3D=3DBackground=3D=3D

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 hashe= s an 80-byte 'block header' while

incriminating a 32-bit = nonce which is at the end of this header data. This

means that th= e processing of the header involves two runs of the compression

f= unction 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 s= tep of the SHA2-256

function operate exclusively on that step'= ;s 64-bytes of input with no

influence from prior data that enter= ed the hash.

Because of this if a miner is able to= prepare a block header with

multiple distinct first 64-byte chun= ks but identical 16-byte

second chunks they can reuse the computa= tion of the initial

expansion for multiple trials. This reduces p= ower consumption.

There are two broad ways of maki= ng use of this optimization. The obvious

way is to try candidates= with different version numbers.=C2=A0 Beyond

upsetting the soft-= fork detection logic in Bitcoin nodes this has

little negative ef= fect but it is highly conspicuous and easily

blocked.

<= br>

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.=C2=A0 If the miner finds multip= le

candidate root values which have the same final 32-bit then th= ey

can use the optimization.

To find mul= tiple roots with the same trailing 32-bits the miner can

use effi= cient 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

computati= on.

An obvious way to generate different candidate= s is to grind the

coinbase extra-nonce but for non-empty blocks e= ach attempt will

require 13 or so additional sha2 runs which is v= ery 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 sq= rt number of candidates of

the right =C2=A0side of the tree using= transaction permutation or

substitution of a small number of tra= nsactions.=C2=A0 All combinations

of the left and right side are = then combined with only a single

hashing operation virtually elim= inating 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 th= e >2^28 operations that would be require for

extra-nonce =C2= =A0grinding which would substantially erode the

benefit of the op= timization.

It is this final optimization which th= is proposal blocks.

=3D=3DNew consensus rule=3D=3D=

Beginning block X and until block Y the coinbase = transaction of

each block MUST either contain a BIP-141 segwit co= mmitment or a

correct WTXID commitment with ID 0xaa21a9ef.

<= div>

(See BIP-141 "Commitment structure" for detail= s)

Existing segwit using miners are automatically = compatible with

this proposal. Non-segwit miners can become compa= tible by simply

including an additional output matching a default= commitment

value returned as part of getblocktemplate.

Miners SHOULD NOT automatically discontinue the commitment<= /div>

at the expiration height.

=3D=3DDiscussi= on=3D=3D

The commitment in the left side of the tr= ee to all transactions

in the right side completely prevents the = final sqrt speedup.

A stronger inhibition of the c= overt optimization in the form of

requiring the least significant= bits of the block timestamp

to be equal to a hash of the first 6= 4-bytes of the header. This

would increase the collision space fr= om 32 to 40 or more bits.

The root value could be required to mee= t a specific hash prefix

requirement in order to increase the com= putational work required

to try candidate roots. These change wou= ld be more disruptive and

there is no reason to believe that it i= s currently necessary.

The proposed rule automatic= ally sunsets. If it is no longer needed

due to the introduction o= f stronger rules or the acceptance of the

version-grinding form t= hen there would be no reason to continue

with this requirement.= =C2=A0 If it is still useful at the expiration

time the rule can = simply be extended with a new softfork that

sets longer date rang= es.

This sun-setting avoids the accumulation of te= chnical debt due

to retaining enforcement of this rule when it is= no longer needed

without requiring a hard fork to remove it.

=3D=3D Overt optimization =3D=3D

A BIP for avoiding erroneous warning messages when miners use the over= t version

of the optimization was proposed several years ago, in = order to deter the covert

use of the optimization. But that BIP w= as rejected.=C2=A0

However, in light of the current discoveries, = that BIP could be reconsidered.

The over optimizat= ion does not generally interfere with improvements in the protocol.

=3D=3DBackward compatibility=3D=3D

=3D=3DImplementation=3D=3D

<= /div>

=3D=3DAcknowledgments=3D=3D

Greg Maxwell= <greg@xiph.org> for the origina= l report, which contained several errors that were corrected in the present= proposal.

=3D=3DCopyright=3D=3D

This document is placed in the public domain.

--001a11c000ae7132d1054c99cffb--