{"type":"rich","version":"1.0","author_name":"npub10vt6y7m6shn8hfuj83zjlwcga4fky38kv73qz6xlcvtj4q7fjt0sqmper0","author_url":"https://nostr.ae/npub10vt6y7m6shn8hfuj83zjlwcga4fky38kv73qz6xlcvtj4q7fjt0sqmper0","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2017-04-05\n📝 Original message:This seems to be a serious security problem.  Would it be possible to have\na flag-day softfork included in Bitcoin Core as soon as 0.14.1? I think that a trigger\n3-6 months from release should be sufficient for enough of the economy to upgrade,\ngiven the severity of the issue.\n\nBIP 141 says that the the commitment is optional if there are no SegWit transactions in\nthe block,  so will today's SegWit-ready miners always produce it even when optional\naccording to BIP 141, as required by this softfork?\n\nOn Wed, Apr 5, 2017, at 04:37 PM, Gregory Maxwell via bitcoin-dev wrote:\n\u003e A month ago I was explaining the attack on Bitcoin's SHA2 hashcash which\n\u003e is exploited by ASICBOOST and the various steps which could be used to\n\u003e block it in the network if it became a problem.\n\u003e \n\u003e While most discussion of ASICBOOST has focused on the overt method\n\u003e of implementing it, there also exists a covert method for using it.\n\u003e \n\u003e As I explained one of the approaches to inhibit covert ASICBOOST I\n\u003e realized that my words were pretty much also describing the SegWit\n\u003e commitment structure.\n\u003e \n\u003e The authors of the SegWit proposal made a specific effort to not be\n\u003e incompatible with any mining system and, in particular, changed the\n\u003e design at one point to accommodate mining chips with forced payout\n\u003e addresses.\n\u003e \n\u003e Had there been awareness of exploitation of this attack an effort\n\u003e would have been made to avoid incompatibility-- simply to separate\n\u003e concerns.  But the best methods of implementing the covert attack\n\u003e are significantly incompatible with virtually any method of\n\u003e extending Bitcoin's transaction capabilities; with the notable\n\u003e exception of extension blocks (which have their own problems).\n\u003e \n\u003e An incompatibility would go a long way to explain some of the\n\u003e more inexplicable behavior from some parties in the mining\n\u003e ecosystem so I began looking for supporting evidence.\n\u003e \n\u003e Reverse engineering of a particular mining chip has demonstrated\n\u003e conclusively that ASICBOOST has been implemented\n\u003e in hardware.\n\u003e \n\u003e On that basis, I offer the following BIP draft for discussion.\n\u003e This proposal does not prevent the attack in general, but only\n\u003e inhibits covert forms of it which are incompatible with\n\u003e improvements to the Bitcoin protocol.\n\u003e \n\u003e I hope that even those of us who would strongly prefer that\n\u003e ASICBOOST be blocked completely can come together to support\n\u003e a protective measure that separates concerns by inhibiting\n\u003e the covert use of it that potentially blocks protocol improvements.\n\u003e \n\u003e The specific activation height is something I currently don't have\n\u003e a strong opinion, so I've left it unspecified for the moment.\n\u003e \n\u003e \u003cpre\u003e\n\u003e   BIP: TBD\n\u003e   Layer: Consensus\n\u003e   Title: Inhibiting a covert attack on the Bitcoin POW function\n\u003e   Author: Greg Maxwell \u003cgreg at xiph.org\u003e\n\u003e   Status: Draft\n\u003e   Type: Standards Track\n\u003e   Created: 2016-04-05\n\u003e   License: PD\n\u003e \u003c/pre\u003e\n\u003e \n\u003e ==Abstract==\n\u003e \n\u003e This proposal inhibits the covert exploitation of a known\n\u003e vulnerability in Bitcoin Proof of Work function.\n\u003e \n\u003e The key words \"MUST\", \"MUST NOT\", \"REQUIRED\", \"SHALL\", \"SHALL NOT\",\n\u003e \"SHOULD\", \"SHOULD NOT\", \"RECOMMENDED\", \"MAY\", and \"OPTIONAL\" in this\n\u003e document are to be interpreted as described in RFC 2119.\n\u003e \n\u003e ==Motivation==\n\u003e \n\u003e Due to a design oversight the Bitcoin proof of work function has a potential\n\u003e attack which can allow an attacking miner to save up-to 30% of their energy\n\u003e costs (though closer to 20% is more likely due to implementation overheads).\n\u003e \n\u003e Timo Hanke and Sergio Demian Lerner claim to hold a patent on this attack,\n\u003e which they have so far not licensed for free and open use by the public.\n\u003e They have been marketing their patent licenses under the trade-name\n\u003e ASICBOOST.  The document takes no position on the validity or enforceability\n\u003e of the patent.\n\u003e \n\u003e There are two major ways of exploiting the underlying vulnerability: One\n\u003e obvious way which is highly detectable and is not in use on the network\n\u003e today and a covert way which has significant interaction and potential\n\u003e interference with the Bitcoin protocol.  The covert mechanism is not\n\u003e easily detected except through its interference with the protocol.\n\u003e \n\u003e In particular, the protocol interactions of the covert method can block the\n\u003e implementation of virtuous improvements such as segregated witness.\n\u003e \n\u003e Exploitation of this vulnerability could result in payoff of as much as\n\u003e $100 million USD per year at the time this was written (Assuming at\n\u003e 50% hash-power miner was gaining a 30% power advantage and that mining\n\u003e was otherwise at profit equilibrium).  This could have a phenomenal\n\u003e centralizing effect by pushing mining out of profitability for all\n\u003e other participants, and the income from secretly using this\n\u003e optimization could be abused to significantly distort the Bitcoin\n\u003e ecosystem in order to preserve the advantage.\n\u003e \n\u003e Reverse engineering of a mining ASIC from a major manufacture has\n\u003e revealed that it contains an undocumented, undisclosed ability\n\u003e to make use of this attack. (The parties claiming to hold a\n\u003e patent on this technique were completely unaware of this use.)\n\u003e \n\u003e On the above basis the potential for covert exploitation of this\n\u003e vulnerability and the resulting inequality in the mining process\n\u003e and interference with useful improvements presents a clear and\n\u003e present danger to the Bitcoin system which requires a response.\n\u003e \n\u003e ==Background==\n\u003e \n\u003e The general idea of this attack is that SHA2-256 is a merkle damgard hash\n\u003e function which consumes 64 bytes of data at a time.\n\u003e \n\u003e The Bitcoin mining process repeatedly hashes an 80-byte 'block header' while\n\u003e incriminating a 32-bit nonce which is at the end of this header data. This\n\u003e means that the processing of the header involves two runs of the compression\n\u003e function run-- one that consumes the first 64 bytes of the header and a\n\u003e second which processes the remaining 16 bytes and padding.\n\u003e \n\u003e The initial 'message expansion' operations in each step of the SHA2-256\n\u003e function operate exclusively on that step's 64-bytes of input with no\n\u003e influence from prior data that entered the hash.\n\u003e \n\u003e Because of this if a miner is able to prepare a block header with\n\u003e multiple distinct first 64-byte chunks but identical 16-byte\n\u003e second chunks they can reuse the computation of the initial\n\u003e expansion for multiple trials. This reduces power consumption.\n\u003e \n\u003e There are two broad ways of making use of this attack. The obvious\n\u003e way is to try candidates with different version numbers.  Beyond\n\u003e upsetting the soft-fork detection logic in Bitcoin nodes this has\n\u003e little negative effect but it is highly conspicuous and easily\n\u003e blocked.\n\u003e \n\u003e The other method is based on the fact that the merkle root\n\u003e committing to the transactions is contained in the first 64-bytes\n\u003e except for the last 4 bytes of it.  If the miner finds multiple\n\u003e candidate root values which have the same final 32-bit then they\n\u003e can use the attack.\n\u003e \n\u003e To find multiple roots with the same trailing 32-bits the miner can\n\u003e use efficient collision finding mechanism which will find a match\n\u003e with as little as 2^16 candidate roots expected, 2^24 operations to\n\u003e find a 4-way hit, though low memory approaches require more\n\u003e computation.\n\u003e \n\u003e An obvious way to generate different candidates is to grind the\n\u003e coinbase extra-nonce but for non-empty blocks each attempt will\n\u003e require 13 or so additional sha2 runs which is very inefficient.\n\u003e \n\u003e This inefficiency can be avoided by computing a sqrt number of\n\u003e candidates of the left side of the hash tree (e.g. using extra\n\u003e nonce grinding) then an additional sqrt number of candidates of\n\u003e the right  side of the tree using transaction permutation or\n\u003e substitution of a small number of transactions.  All combinations\n\u003e of the left and right side are then combined with only a single\n\u003e hashing operation virtually eliminating all tree related\n\u003e overhead.\n\u003e \n\u003e With this final optimization finding a 4-way collision with a\n\u003e moderate amount of memory requires ~2^24 hashing operations\n\u003e instead of the \u003e2^28 operations that would be require for\n\u003e extra-nonce  grinding which would substantially erode the\n\u003e benefit of the attack.\n\u003e \n\u003e It is this final optimization which this proposal blocks.\n\u003e \n\u003e ==New consensus rule==\n\u003e \n\u003e Beginning block X and until block Y the coinbase transaction of\n\u003e each block MUST either contain a BIP-141 segwit commitment or a\n\u003e correct WTXID commitment with ID 0xaa21a9ef.\n\u003e \n\u003e (See BIP-141 \"Commitment structure\" for details)\n\u003e \n\u003e Existing segwit using miners are automatically compatible with\n\u003e this proposal. Non-segwit miners can become compatible by simply\n\u003e including an additional output matching a default commitment\n\u003e value returned as part of getblocktemplate.\n\u003e \n\u003e Miners SHOULD NOT automatically discontinue the commitment\n\u003e at the expiration height.\n\u003e \n\u003e ==Discussion==\n\u003e \n\u003e The commitment in the left side of the tree to all transactions\n\u003e in the right side completely prevents the final sqrt speedup.\n\u003e \n\u003e A stronger inhibition of the covert attack in the form of\n\u003e requiring the least significant bits of the block timestamp\n\u003e to be equal to a hash of the first 64-bytes of the header. This\n\u003e would increase the collision space from 32 to 40 or more bits.\n\u003e The root value could be required to meet a specific hash prefix\n\u003e requirement in order to increase the computational work required\n\u003e to try candidate roots. These change would be more disruptive and\n\u003e there is no reason to believe that it is currently necessary.\n\u003e \n\u003e The proposed rule automatically sunsets. If it is no longer needed\n\u003e due to the introduction of stronger rules or the acceptance of the\n\u003e version-grinding form then there would be no reason to continue\n\u003e with this requirement.  If it is still useful at the expiration\n\u003e time the rule can simply be extended with a new softfork that\n\u003e sets longer date ranges.\n\u003e \n\u003e This sun-setting avoids the accumulation of technical debt due\n\u003e to retaining enforcement of this rule when it is no longer needed\n\u003e without requiring a hard fork to remove it.\n\u003e \n\u003e == Overt attack ==\n\u003e \n\u003e The non-covert form can be trivially blocked by requiring that\n\u003e the header version match the coinbase transaction version.\n\u003e \n\u003e This proposal does not include this block because this method\n\u003e may become generally available without restriction in the future,\n\u003e does not generally interfere with improvements in the protocol,\n\u003e and because it is so easily detected that it could be blocked if\n\u003e it becomes an issue in the future.\n\u003e \n\u003e ==Backward compatibility==\n\u003e \n\u003e \n\u003e ==Implementation==\n\u003e \n\u003e \n\u003e ==Acknowledgments==\n\u003e \n\u003e \n\u003e ==Copyright==\n\u003e \n\u003e This document is placed in the public domain.\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev"}