<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Arial,Helvetica,sans-serif;" dir="ltr">
<p>Just to add on to the ethical issue of blocking this.</p>
<p><br>
</p>
<p>If blocking the covert form of ASICBOOST is seen as unethical, then the same can be said about
<span>libsecp256k1, various client optimisations, Compactblocks.&nbsp;</span></p>
<p><span>All of which seek to reduce the efficacy&nbsp;of large miners and selfish mining.</span></p>
<p><span><br>
</span></p>
<p><span>I also find it very ironic that the author of the Selfish Mining paper who rang alarm bells about miner centralisation in 2013 is now opposing attempts to reduce miner centralisation.</span></p>
<br>
<br>
<div style="color: rgb(0, 0, 0);">
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>From:</b> bitcoin-dev-bounces@lists.linuxfoundation.org &lt;bitcoin-dev-bounces@lists.linuxfoundation.org&gt; on behalf of Luv Khemani via bitcoin-dev &lt;bitcoin-dev@lists.linuxfoundation.org&gt;<br>
<b>Sent:</b> Thursday, April 6, 2017 8:02 PM<br>
<b>To:</b> Gregory Maxwell; Bitcoin Protocol Discussion<br>
<b>Subject:</b> Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function</font>
<div>&nbsp;</div>
</div>
<div>
<div id="divtagdefaultwrapper" dir="ltr" style="font-size:12pt; color:#000000; font-family:Calibri,Arial,Helvetica,sans-serif">
<p>Hi Greg</p>
<p><br>
</p>
<p>Great work in discovering this!</p>
<p><br>
</p>
<p>&gt;&nbsp;<span style="font-family:Calibri,Arial,Helvetica,sans-serif,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols; font-size:13.3333px">A month ago I was explaining the attack on Bitcoin's SHA2 hashcash which</span><br style="font-family:Calibri,Arial,Helvetica,sans-serif,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols; font-size:13.3333px">
<span style="font-family:Calibri,Arial,Helvetica,sans-serif,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols; font-size:13.3333px">is exploited by ASICBOOST and the various steps which could be used to</span><br style="font-family:Calibri,Arial,Helvetica,sans-serif,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols; font-size:13.3333px">
<span style="font-family:Calibri,Arial,Helvetica,sans-serif,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols; font-size:13.3333px">block it in the network if it became a problem.</span></p>
<p><span style="font-family:Calibri,Arial,Helvetica,sans-serif,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols; font-size:13.3333px"><br>
</span></p>
<p><span style="font-family:Calibri,Arial,Helvetica,sans-serif,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols; font-size:16px">Could you elaborate on why you consider ASICBOOST to be an attack? Attack here
 implies ill-intent by the practitioner&nbsp;towards the network as a primary motivating factor.</span><br>
</p>
<p><span style="font-family:Calibri,Arial,Helvetica,sans-serif,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols; font-size:16px">Personally, i see this as a miner acting in his self-interest and had i been a
 miner and knew about the covert method, i would use it too.</span></p>
<p>So while i'm no fan of Bitmain/Jihan, i do not condone the vilification he has received over the use of ASICBOOST to gain an edge.</p>
<p>I know i'm griping over semantics, but in the current political climate, they can be amplified by some to cause more drama than is healthy.</p>
<p><br>
</p>
<p>Other thoughts:</p>
<p><br>
</p>
Several people have commented that blocking the use of this covert technique is unethical or &quot;wrong&quot;.
<div>To quote Emin:</div>
<div><br>
</div>
<div><i></i><span><i>&gt;Taking action to block this is similar to the government taking measures to block Elon Musk's more efficient electric cars. Specifically prosecuting a chosen miner, in the current political climate, would send a terrible message of absolute
 centralization in the hands of one particular developer group, and it would severely damage Bitcoin mining and the coin's security.</i></span><br>
<br>
This is a poor analogy and extremely misleading&nbsp;as the the basis for blocking has nothing to do with efficiency and more to do with the following:</div>
<div><br>
</div>
<div>1) Blocking upgrades to the protocol that are deemed by the vast majority of the technical community/Bitcoin&nbsp;Businesses as being the best way forward</div>
<div><br>
</div>
<div>2) An advantage by a miner/group, especially one with majority hashrate is a threat to decentralisation and security of the network and it is entirely justifiable for devs to nullify such an advantage.</div>
<div>You can see&nbsp;it as&nbsp;an arms race where miners are always finding ways to gain an edge and devs trying to discover such edges and nullify them to level the playing field.&nbsp;</div>
<div>This is how the game works and it should not be viewed in a political angle or taken personally by either party. Miners are acting in their self-interest and Devs are trying to secure the network and increase decentralisation.</div>
<div>Both are doing their job.</div>
<div><br>
</div>
<div>Just by revealing the info, you have effectively ensured the&nbsp;nullification of any edge enjoyed by miners&nbsp;using&nbsp;the covert technique in the medium to long term.</div>
<div>Either miners not using the technique will all start signalling for SegWit to nullify their competitors&nbsp;edge or they will procure hardware which has the edge.&nbsp;</div>
<div><br>
</div>
<div>Given the threat to decentralisation, i also believe UASF will gain more momentum as users seek to protect the network from further miner centralisation.</div>
<div><br>
</div>
<div><br>
<div style="color:rgb(0,0,0)">
<div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="x_divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>From:</b> bitcoin-dev-bounces@lists.linuxfoundation.org &lt;bitcoin-dev-bounces@lists.linuxfoundation.org&gt; on behalf of Gregory Maxwell via bitcoin-dev
 &lt;bitcoin-dev@lists.linuxfoundation.org&gt;<br>
<b>Sent:</b> Thursday, April 6, 2017 5:37 AM<br>
<b>To:</b> Bitcoin Dev<br>
<b>Subject:</b> [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function</font>
<div>&nbsp;</div>
</div>
</div>
<font size="2"><span style="font-size:10pt">
<div class="PlainText">A month ago I was explaining the attack on Bitcoin's SHA2 hashcash which<br>
is exploited by ASICBOOST and the various steps which could be used to<br>
block it in the network if it became a problem.<br>
<br>
While most discussion of ASICBOOST has focused on the overt method<br>
of implementing it, there also exists a covert method for using it.<br>
<br>
As I explained one of the approaches to inhibit covert ASICBOOST I<br>
realized that my words were pretty much also describing the SegWit<br>
commitment structure.<br>
<br>
The authors of the SegWit proposal made a specific effort to not be<br>
incompatible with any mining system and, in particular, changed the<br>
design at one point to accommodate mining chips with forced payout<br>
addresses.<br>
<br>
Had there been awareness of exploitation of this attack an effort<br>
would have been made to avoid incompatibility-- simply to separate<br>
concerns.&nbsp; But the best methods of implementing the covert attack<br>
are significantly incompatible with virtually any method of<br>
extending Bitcoin's transaction capabilities; with the notable<br>
exception of extension blocks (which have their own problems).<br>
<br>
An incompatibility would go a long way to explain some of the<br>
more inexplicable behavior from some parties in the mining<br>
ecosystem so I began looking for supporting evidence.<br>
<br>
Reverse engineering of a particular mining chip has demonstrated<br>
conclusively that ASICBOOST has been implemented<br>
in hardware.<br>
<br>
On that basis, I offer the following BIP draft for discussion.<br>
This proposal does not prevent the attack in general, but only<br>
inhibits covert forms of it which are incompatible with<br>
improvements to the Bitcoin protocol.<br>
<br>
I hope that even those of us who would strongly prefer that<br>
ASICBOOST be blocked completely can come together to support<br>
a protective measure that separates concerns by inhibiting<br>
the covert use of it that potentially blocks protocol improvements.<br>
<br>
The specific activation height is something I currently don't have<br>
a strong opinion, so I've left it unspecified for the moment.<br>
<br>
&lt;pre&gt;<br>
&nbsp; BIP: TBD<br>
&nbsp; Layer: Consensus<br>
&nbsp; Title: Inhibiting a covert attack on the Bitcoin POW function<br>
&nbsp; Author: Greg Maxwell &lt;greg@xiph.org&gt;<br>
&nbsp; Status: Draft<br>
&nbsp; Type: Standards Track<br>
&nbsp; Created: 2016-04-05<br>
&nbsp; License: PD<br>
&lt;/pre&gt;<br>
<br>
==Abstract==<br>
<br>
This proposal inhibits the covert exploitation of a known<br>
vulnerability in Bitcoin Proof of Work function.<br>
<br>
The key words &quot;MUST&quot;, &quot;MUST NOT&quot;, &quot;REQUIRED&quot;, &quot;SHALL&quot;, &quot;SHALL NOT&quot;,<br>
&quot;SHOULD&quot;, &quot;SHOULD NOT&quot;, &quot;RECOMMENDED&quot;, &quot;MAY&quot;, and &quot;OPTIONAL&quot; in this<br>
document are to be interpreted as described in RFC 2119.<br>
<br>
==Motivation==<br>
<br>
Due to a design oversight the Bitcoin proof of work function has a potential<br>
attack which can allow an attacking miner to save up-to 30% of their energy<br>
costs (though closer to 20% is more likely due to implementation overheads).<br>
<br>
Timo Hanke and Sergio Demian Lerner claim to hold a patent on this attack,<br>
which they have so far not licensed for free and open use by the public.<br>
They have been marketing their patent licenses under the trade-name<br>
ASICBOOST.&nbsp; The document takes no position on the validity or enforceability<br>
of the patent.<br>
<br>
There are two major ways of exploiting the underlying vulnerability: One<br>
obvious way which is highly detectable and is not in use on the network<br>
today and a covert way which has significant interaction and potential<br>
interference with the Bitcoin protocol.&nbsp; The covert mechanism is not<br>
easily detected except through its interference with the protocol.<br>
<br>
In particular, the protocol interactions of the covert method can block the<br>
implementation of virtuous improvements such as segregated witness.<br>
<br>
Exploitation of this vulnerability could result in payoff of as much as<br>
$100 million USD per year at the time this was written (Assuming at<br>
50% hash-power miner was gaining a 30% power advantage and that mining<br>
was otherwise at profit equilibrium).&nbsp; This could have a phenomenal<br>
centralizing effect by pushing mining out of profitability for all<br>
other participants, and the income from secretly using this<br>
optimization could be abused to significantly distort the Bitcoin<br>
ecosystem in order to preserve the advantage.<br>
<br>
Reverse engineering of a mining ASIC from a major manufacture has<br>
revealed that it contains an undocumented, undisclosed ability<br>
to make use of this attack. (The parties claiming to hold a<br>
patent on this technique were completely unaware of this use.)<br>
<br>
On the above basis the potential for covert exploitation of this<br>
vulnerability and the resulting inequality in the mining process<br>
and interference with useful improvements presents a clear and<br>
present danger to the Bitcoin system which requires a response.<br>
<br>
==Background==<br>
<br>
The general idea of this attack is that SHA2-256 is a merkle damgard hash<br>
function which consumes 64 bytes of data at a time.<br>
<br>
The Bitcoin mining process repeatedly hashes an 80-byte 'block header' while<br>
incriminating a 32-bit nonce which is at the end of this header data. This<br>
means that the processing of the header involves two runs of the compression<br>
function run-- one that consumes the first 64 bytes of the header and a<br>
second which processes the remaining 16 bytes and padding.<br>
<br>
The initial 'message expansion' operations in each step of the SHA2-256<br>
function operate exclusively on that step's 64-bytes of input with no<br>
influence from prior data that entered the hash.<br>
<br>
Because of this if a miner is able to prepare a block header with<br>
multiple distinct first 64-byte chunks but identical 16-byte<br>
second chunks they can reuse the computation of the initial<br>
expansion for multiple trials. This reduces power consumption.<br>
<br>
There are two broad ways of making use of this attack. The obvious<br>
way is to try candidates with different version numbers.&nbsp; Beyond<br>
upsetting the soft-fork detection logic in Bitcoin nodes this has<br>
little negative effect but it is highly conspicuous and easily<br>
blocked.<br>
<br>
The other method is based on the fact that the merkle root<br>
committing to the transactions is contained in the first 64-bytes<br>
except for the last 4 bytes of it.&nbsp; If the miner finds multiple<br>
candidate root values which have the same final 32-bit then they<br>
can use the attack.<br>
<br>
To find multiple roots with the same trailing 32-bits the miner can<br>
use efficient collision finding mechanism which will find a match<br>
with as little as 2^16 candidate roots expected, 2^24 operations to<br>
find a 4-way hit, though low memory approaches require more<br>
computation.<br>
<br>
An obvious way to generate different candidates is to grind the<br>
coinbase extra-nonce but for non-empty blocks each attempt will<br>
require 13 or so additional sha2 runs which is very inefficient.<br>
<br>
This inefficiency can be avoided by computing a sqrt number of<br>
candidates of the left side of the hash tree (e.g. using extra<br>
nonce grinding) then an additional sqrt number of candidates of<br>
the right&nbsp; side of the tree using transaction permutation or<br>
substitution of a small number of transactions.&nbsp; All combinations<br>
of the left and right side are then combined with only a single<br>
hashing operation virtually eliminating all tree related<br>
overhead.<br>
<br>
With this final optimization finding a 4-way collision with a<br>
moderate amount of memory requires ~2^24 hashing operations<br>
instead of the &gt;2^28 operations that would be require for<br>
extra-nonce&nbsp; grinding which would substantially erode the<br>
benefit of the attack.<br>
<br>
It is this final optimization which this proposal blocks.<br>
<br>
==New consensus rule==<br>
<br>
Beginning block X and until block Y the coinbase transaction of<br>
each block MUST either contain a BIP-141 segwit commitment or a<br>
correct WTXID commitment with ID 0xaa21a9ef.<br>
<br>
(See BIP-141 &quot;Commitment structure&quot; for details)<br>
<br>
Existing segwit using miners are automatically compatible with<br>
this proposal. Non-segwit miners can become compatible by simply<br>
including an additional output matching a default commitment<br>
value returned as part of getblocktemplate.<br>
<br>
Miners SHOULD NOT automatically discontinue the commitment<br>
at the expiration height.<br>
<br>
==Discussion==<br>
<br>
The commitment in the left side of the tree to all transactions<br>
in the right side completely prevents the final sqrt speedup.<br>
<br>
A stronger inhibition of the covert attack in the form of<br>
requiring the least significant bits of the block timestamp<br>
to be equal to a hash of the first 64-bytes of the header. This<br>
would increase the collision space from 32 to 40 or more bits.<br>
The root value could be required to meet a specific hash prefix<br>
requirement in order to increase the computational work required<br>
to try candidate roots. These change would be more disruptive and<br>
there is no reason to believe that it is currently necessary.<br>
<br>
The proposed rule automatically sunsets. If it is no longer needed<br>
due to the introduction of stronger rules or the acceptance of the<br>
version-grinding form then there would be no reason to continue<br>
with this requirement.&nbsp; If it is still useful at the expiration<br>
time the rule can simply be extended with a new softfork that<br>
sets longer date ranges.<br>
<br>
This sun-setting avoids the accumulation of technical debt due<br>
to retaining enforcement of this rule when it is no longer needed<br>
without requiring a hard fork to remove it.<br>
<br>
== Overt attack ==<br>
<br>
The non-covert form can be trivially blocked by requiring that<br>
the header version match the coinbase transaction version.<br>
<br>
This proposal does not include this block because this method<br>
may become generally available without restriction in the future,<br>
does not generally interfere with improvements in the protocol,<br>
and because it is so easily detected that it could be blocked if<br>
it becomes an issue in the future.<br>
<br>
==Backward compatibility==<br>
<br>
<br>
==Implementation==<br>
<br>
<br>
==Acknowledgments==<br>
<br>
<br>
==Copyright==<br>
<br>
This document is placed in the public domain.<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
bitcoin-dev@lists.linuxfoundation.org<br>
<a href="https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" id="LPlnk519544" previewremoved="true">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev</a>
<div id="LPBorder_GT_14914779708460.1275889041172491" style="margin-bottom:20px; overflow:auto; width:100%; text-indent:0px">
<table id="LPContainer_14914779708430.6391837727881977" cellspacing="0" style="width:90%; background-color:rgb(255,255,255); overflow:auto; padding-top:20px; padding-bottom:20px; margin-top:20px; border-top:1px dotted rgb(200,200,200); border-bottom:1px dotted rgb(200,200,200)">
<tbody>
<tr valign="top" style="border-spacing:0px">
<td id="TextCell_14914779708440.3747157755215689" colspan="2" style="vertical-align: top; padding: 0px; display: table-cell; position: relative;">
<div id="LPRemovePreviewContainer_14914779708440.6010049460283657"></div>
<div id="LPTitle_14914779708440.5364067327594058" style="top:0px; color:rgb(0,120,215); font-weight:normal; font-size:21px; font-family:wf_segoe-ui_light,&quot;Segoe UI Light&quot;,&quot;Segoe WP Light&quot;,&quot;Segoe UI&quot;,&quot;Segoe WP&quot;,Tahoma,Arial,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols,sans-serif; line-height:21px">
<a id="LPUrlAnchor_14914779708450.35914654150375735" href="https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" target="_blank" style="text-decoration:none">bitcoin-dev -- Bitcoin Protocol Discussion - Linux Foundation</a></div>
<div id="LPMetadata_14914779708450.7480051946749007" style="margin:10px 0px 16px; color:rgb(102,102,102); font-weight:normal; font-family:wf_segoe-ui_normal,&quot;Segoe UI&quot;,&quot;Segoe WP&quot;,Tahoma,Arial,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols,sans-serif; font-size:14px; line-height:14px">
lists.linuxfoundation.org</div>
<div id="LPDescription_14914779708450.8262054407680588" style="display:block; color:rgb(102,102,102); font-weight:normal; font-family:wf_segoe-ui_normal,&quot;Segoe UI&quot;,&quot;Segoe WP&quot;,Tahoma,Arial,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;,NotoColorEmoji,&quot;Segoe UI Symbol&quot;,&quot;Android Emoji&quot;,EmojiSymbols,sans-serif; font-size:14px; line-height:20px; max-height:100px; overflow:hidden">
Bitcoin development and protocol discussion. This list is lightly moderated. - No offensive posts, no personal attacks. - Posts must concern development of bitcoin ...</div>
</td>
</tr>
</tbody>
</table>
</div>
<br>
<br>
</div>
</span></font></div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>