<div dir="ltr"><div>&lt;pre&gt;</div><div>  BIP: TBD</div><div>  Layer: Consensus</div><div>  Title: Inhibiting a covert optimization on the Bitcoin POW function</div><div>  Author: Sergio Demian Lerner &lt;<a href="mailto:sergio.d.lerner@gmail.com">sergio.d.lerner@gmail.com</a>&gt;</div><div>  Status: Draft</div><div>  Type: Standards Track</div><div>  Created: 2016-04-07</div><div>  License: PD</div><div>&lt;/pre&gt;</div><div><br></div><div>==Abstract==</div><div><br></div><div>This proposal inhibits the covert use of a known optimization in Bitcoin Proof of Work function.</div><div><br></div><div>The key words &quot;MUST&quot;, &quot;MUST NOT&quot;, &quot;REQUIRED&quot;, &quot;SHALL&quot;, &quot;SHALL NOT&quot;,</div><div>&quot;SHOULD&quot;, &quot;SHOULD NOT&quot;, &quot;RECOMMENDED&quot;, &quot;MAY&quot;, and &quot;OPTIONAL&quot; in this document are to be interpreted as described in RFC 2119.</div><div><br></div><div>==Motivation==</div><div><br></div><div>Due to a design oversight the Bitcoin proof of work function has a potential</div><div>optimization which can allow a rational miner to save up-to 30% of their energy</div><div>costs (though closer to 20% is more likely due to implementation overheads).</div><div><br></div><div>Timo Hanke and Sergio Demian Lerner applied for a patent on this optimization. The company &quot;Sunrise Tech Group, Llc&quot; 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.</div><div><br></div><div>There are two major ways of taking advantage of this optimization, as described </div><div>by the patent: </div><div>One way which is highly detectable and is not in use on the network</div><div>today and a covert way which has significant interaction and potential</div><div>interference with the Bitcoin protocol.  The covert mechanism is not</div><div>easily detected except through its interference with the protocol.</div><div><br></div><div>In particular, the protocol interactions of the covert method can block the</div><div>implementation of virtuous improvements such as segregated witness.</div><div><br></div><div>The use of this optimization could result in a big payoff, but the actual</div><div>sum depends on the degree of research, investment and effort put into designing</div><div>the improved cores.  </div><div><br></div><div>On the above basis the potential for covert use of this optimization </div><div>in the covert form and interference with useful improvements presents a </div><div>danger to the Bitcoin system.</div><div><br></div><div>==Background==</div><div><br></div><div>The general idea of this optimization is that SHA2-256 is a merkle damgard hash</div><div>function which consumes 64 bytes of data at a time.</div><div><br></div><div>The Bitcoin mining process repeatedly hashes an 80-byte &#39;block header&#39; while</div><div>incriminating a 32-bit nonce which is at the end of this header data. This</div><div>means that the processing of the header involves two runs of the compression</div><div>function run-- one that consumes the first 64 bytes of the header and a</div><div>second which processes the remaining 16 bytes and padding.</div><div><br></div><div>The initial &#39;message expansion&#39; operations in each step of the SHA2-256</div><div>function operate exclusively on that step&#39;s 64-bytes of input with no</div><div>influence from prior data that entered the hash.</div><div><br></div><div>Because of this if a miner is able to prepare a block header with</div><div>multiple distinct first 64-byte chunks but identical 16-byte</div><div>second chunks they can reuse the computation of the initial</div><div>expansion for multiple trials. This reduces power consumption.</div><div><br></div><div>There are two broad ways of making use of this optimization. The obvious</div><div>way is to try candidates with different version numbers.  Beyond</div><div>upsetting the soft-fork detection logic in Bitcoin nodes this has</div><div>little negative effect but it is highly conspicuous and easily</div><div>blocked.</div><div><br></div><div>The other method is based on the fact that the merkle root</div><div>committing to the transactions is contained in the first 64-bytes</div><div>except for the last 4 bytes of it.  If the miner finds multiple</div><div>candidate root values which have the same final 32-bit then they</div><div>can use the optimization.</div><div><br></div><div>To find multiple roots with the same trailing 32-bits the miner can</div><div>use efficient collision finding mechanism which will find a match</div><div>with as little as 2^16 candidate roots expected, 2^24 operations to</div><div>find a 4-way hit, though low memory approaches require more</div><div>computation.</div><div><br></div><div>An obvious way to generate different candidates is to grind the</div><div>coinbase extra-nonce but for non-empty blocks each attempt will</div><div>require 13 or so additional sha2 runs which is very inefficient.</div><div><br></div><div>This inefficiency can be avoided by computing a sqrt number of</div><div>candidates of the left side of the hash tree (e.g. using extra</div><div>nonce grinding) then an additional sqrt number of candidates of</div><div>the right  side of the tree using transaction permutation or</div><div>substitution of a small number of transactions.  All combinations</div><div>of the left and right side are then combined with only a single</div><div>hashing operation virtually eliminating all tree related</div><div>overhead.</div><div><br></div><div>With this final optimization finding a 4-way collision with a</div><div>moderate amount of memory requires ~2^24 hashing operations</div><div>instead of the &gt;2^28 operations that would be require for</div><div>extra-nonce  grinding which would substantially erode the</div><div>benefit of the optimization.</div><div><br></div><div>It is this final optimization which this proposal blocks.</div><div><br></div><div>==New consensus rule==</div><div><br></div><div>Beginning block X and until block Y the coinbase transaction of</div><div>each block MUST either contain a BIP-141 segwit commitment or a</div><div>correct WTXID commitment with ID 0xaa21a9ef.</div><div><br></div><div>(See BIP-141 &quot;Commitment structure&quot; for details)</div><div><br></div><div>Existing segwit using miners are automatically compatible with</div><div>this proposal. Non-segwit miners can become compatible by simply</div><div>including an additional output matching a default commitment</div><div>value returned as part of getblocktemplate.</div><div><br></div><div>Miners SHOULD NOT automatically discontinue the commitment</div><div>at the expiration height.</div><div><br></div><div>==Discussion==</div><div><br></div><div>The commitment in the left side of the tree to all transactions</div><div>in the right side completely prevents the final sqrt speedup.</div><div><br></div><div>A stronger inhibition of the covert optimization in the form of</div><div>requiring the least significant bits of the block timestamp</div><div>to be equal to a hash of the first 64-bytes of the header. This</div><div>would increase the collision space from 32 to 40 or more bits.</div><div>The root value could be required to meet a specific hash prefix</div><div>requirement in order to increase the computational work required</div><div>to try candidate roots. These change would be more disruptive and</div><div>there is no reason to believe that it is currently necessary.</div><div><br></div><div>The proposed rule automatically sunsets. If it is no longer needed</div><div>due to the introduction of stronger rules or the acceptance of the</div><div>version-grinding form then there would be no reason to continue</div><div>with this requirement.  If it is still useful at the expiration</div><div>time the rule can simply be extended with a new softfork that</div><div>sets longer date ranges.</div><div><br></div><div>This sun-setting avoids the accumulation of technical debt due</div><div>to retaining enforcement of this rule when it is no longer needed</div><div>without requiring a hard fork to remove it.</div><div><br></div><div>== Overt optimization ==</div><div><br></div><div>A BIP for avoiding erroneous warning messages when miners use the overt version</div><div>of the optimization was proposed several years ago, in order to deter the covert</div><div>use of the optimization. But that BIP was rejected. </div><div>However, in light of the current discoveries, that BIP could be reconsidered.</div><div><br></div><div>The over optimization does not generally interfere with improvements in the protocol.</div><div><br></div><div>==Backward compatibility==</div><div><br></div><div><br></div><div>==Implementation==</div><div><br></div><div><br></div><div>==Acknowledgments==</div><div><br></div><div>Greg Maxwell &lt;<a href="mailto:greg@xiph.org">greg@xiph.org</a>&gt; for the original report, which contained several errors that were corrected in the present proposal.</div><div><br></div><div>==Copyright==</div><div><br></div><div>This document is placed in the public domain.</div></div>