{"type":"rich","version":"1.0","author_name":"npub1f2nvlx49er5c7sqa43src6ssyp6snd4qwvtkwm5avc2l84cs84esecrwet","author_url":"https://nostr.ae/npub1f2nvlx49er5c7sqa43src6ssyp6snd4qwvtkwm5avc2l84cs84esecrwet","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2017-04-05\n📝 Original message:A month ago I was explaining the attack on Bitcoin's SHA2 hashcash which\nis exploited by ASICBOOST and the various steps which could be used to\nblock it in the network if it became a problem.\n\nWhile most discussion of ASICBOOST has focused on the overt method\nof implementing it, there also exists a covert method for using it.\n\nAs I explained one of the approaches to inhibit covert ASICBOOST I\nrealized that my words were pretty much also describing the SegWit\ncommitment structure.\n\nThe authors of the SegWit proposal made a specific effort to not be\nincompatible with any mining system and, in particular, changed the\ndesign at one point to accommodate mining chips with forced payout\naddresses.\n\nHad there been awareness of exploitation of this attack an effort\nwould have been made to avoid incompatibility-- simply to separate\nconcerns.  But the best methods of implementing the covert attack\nare significantly incompatible with virtually any method of\nextending Bitcoin's transaction capabilities; with the notable\nexception of extension blocks (which have their own problems).\n\nAn incompatibility would go a long way to explain some of the\nmore inexplicable behavior from some parties in the mining\necosystem so I began looking for supporting evidence.\n\nReverse engineering of a particular mining chip has demonstrated\nconclusively that ASICBOOST has been implemented\nin hardware.\n\nOn that basis, I offer the following BIP draft for discussion.\nThis proposal does not prevent the attack in general, but only\ninhibits covert forms of it which are incompatible with\nimprovements to the Bitcoin protocol.\n\nI hope that even those of us who would strongly prefer that\nASICBOOST be blocked completely can come together to support\na protective measure that separates concerns by inhibiting\nthe covert use of it that potentially blocks protocol improvements.\n\nThe specific activation height is something I currently don't have\na strong opinion, so I've left it unspecified for the moment.\n\n\u003cpre\u003e\n  BIP: TBD\n  Layer: Consensus\n  Title: Inhibiting a covert attack on the Bitcoin POW function\n  Author: Greg Maxwell \u003cgreg at xiph.org\u003e\n  Status: Draft\n  Type: Standards Track\n  Created: 2016-04-05\n  License: PD\n\u003c/pre\u003e\n\n==Abstract==\n\nThis proposal inhibits the covert exploitation of a known\nvulnerability in Bitcoin Proof of Work function.\n\nThe key words \"MUST\", \"MUST NOT\", \"REQUIRED\", \"SHALL\", \"SHALL NOT\",\n\"SHOULD\", \"SHOULD NOT\", \"RECOMMENDED\", \"MAY\", and \"OPTIONAL\" in this\ndocument are to be interpreted as described in RFC 2119.\n\n==Motivation==\n\nDue to a design oversight the Bitcoin proof of work function has a potential\nattack which can allow an attacking miner to save up-to 30% of their energy\ncosts (though closer to 20% is more likely due to implementation overheads).\n\nTimo Hanke and Sergio Demian Lerner claim to hold a patent on this attack,\nwhich they have so far not licensed for free and open use by the public.\nThey have been marketing their patent licenses under the trade-name\nASICBOOST.  The document takes no position on the validity or enforceability\nof the patent.\n\nThere are two major ways of exploiting the underlying vulnerability: One\nobvious way which is highly detectable and is not in use on the network\ntoday and a covert way which has significant interaction and potential\ninterference with the Bitcoin protocol.  The covert mechanism is not\neasily detected except through its interference with the protocol.\n\nIn particular, the protocol interactions of the covert method can block the\nimplementation of virtuous improvements such as segregated witness.\n\nExploitation of this vulnerability could result in payoff of as much as\n$100 million USD per year at the time this was written (Assuming at\n50% hash-power miner was gaining a 30% power advantage and that mining\nwas otherwise at profit equilibrium).  This could have a phenomenal\ncentralizing effect by pushing mining out of profitability for all\nother participants, and the income from secretly using this\noptimization could be abused to significantly distort the Bitcoin\necosystem in order to preserve the advantage.\n\nReverse engineering of a mining ASIC from a major manufacture has\nrevealed that it contains an undocumented, undisclosed ability\nto make use of this attack. (The parties claiming to hold a\npatent on this technique were completely unaware of this use.)\n\nOn the above basis the potential for covert exploitation of this\nvulnerability and the resulting inequality in the mining process\nand interference with useful improvements presents a clear and\npresent danger to the Bitcoin system which requires a response.\n\n==Background==\n\nThe general idea of this attack is that SHA2-256 is a merkle damgard hash\nfunction which consumes 64 bytes of data at a time.\n\nThe Bitcoin mining process repeatedly hashes an 80-byte 'block header' while\nincriminating a 32-bit nonce which is at the end of this header data. This\nmeans that the processing of the header involves two runs of the compression\nfunction run-- one that consumes the first 64 bytes of the header and a\nsecond which processes the remaining 16 bytes and padding.\n\nThe initial 'message expansion' operations in each step of the SHA2-256\nfunction operate exclusively on that step's 64-bytes of input with no\ninfluence from prior data that entered the hash.\n\nBecause of this if a miner is able to prepare a block header with\nmultiple distinct first 64-byte chunks but identical 16-byte\nsecond chunks they can reuse the computation of the initial\nexpansion for multiple trials. This reduces power consumption.\n\nThere are two broad ways of making use of this attack. The obvious\nway is to try candidates with different version numbers.  Beyond\nupsetting the soft-fork detection logic in Bitcoin nodes this has\nlittle negative effect but it is highly conspicuous and easily\nblocked.\n\nThe other method is based on the fact that the merkle root\ncommitting to the transactions is contained in the first 64-bytes\nexcept for the last 4 bytes of it.  If the miner finds multiple\ncandidate root values which have the same final 32-bit then they\ncan use the attack.\n\nTo find multiple roots with the same trailing 32-bits the miner can\nuse efficient collision finding mechanism which will find a match\nwith as little as 2^16 candidate roots expected, 2^24 operations to\nfind a 4-way hit, though low memory approaches require more\ncomputation.\n\nAn obvious way to generate different candidates is to grind the\ncoinbase extra-nonce but for non-empty blocks each attempt will\nrequire 13 or so additional sha2 runs which is very inefficient.\n\nThis inefficiency can be avoided by computing a sqrt number of\ncandidates of the left side of the hash tree (e.g. using extra\nnonce grinding) then an additional sqrt number of candidates of\nthe right  side of the tree using transaction permutation or\nsubstitution of a small number of transactions.  All combinations\nof the left and right side are then combined with only a single\nhashing operation virtually eliminating all tree related\noverhead.\n\nWith this final optimization finding a 4-way collision with a\nmoderate amount of memory requires ~2^24 hashing operations\ninstead of the \u003e2^28 operations that would be require for\nextra-nonce  grinding which would substantially erode the\nbenefit of the attack.\n\nIt is this final optimization which this proposal blocks.\n\n==New consensus rule==\n\nBeginning block X and until block Y the coinbase transaction of\neach block MUST either contain a BIP-141 segwit commitment or a\ncorrect WTXID commitment with ID 0xaa21a9ef.\n\n(See BIP-141 \"Commitment structure\" for details)\n\nExisting segwit using miners are automatically compatible with\nthis proposal. Non-segwit miners can become compatible by simply\nincluding an additional output matching a default commitment\nvalue returned as part of getblocktemplate.\n\nMiners SHOULD NOT automatically discontinue the commitment\nat the expiration height.\n\n==Discussion==\n\nThe commitment in the left side of the tree to all transactions\nin the right side completely prevents the final sqrt speedup.\n\nA stronger inhibition of the covert attack in the form of\nrequiring the least significant bits of the block timestamp\nto be equal to a hash of the first 64-bytes of the header. This\nwould increase the collision space from 32 to 40 or more bits.\nThe root value could be required to meet a specific hash prefix\nrequirement in order to increase the computational work required\nto try candidate roots. These change would be more disruptive and\nthere is no reason to believe that it is currently necessary.\n\nThe proposed rule automatically sunsets. If it is no longer needed\ndue to the introduction of stronger rules or the acceptance of the\nversion-grinding form then there would be no reason to continue\nwith this requirement.  If it is still useful at the expiration\ntime the rule can simply be extended with a new softfork that\nsets longer date ranges.\n\nThis sun-setting avoids the accumulation of technical debt due\nto retaining enforcement of this rule when it is no longer needed\nwithout requiring a hard fork to remove it.\n\n== Overt attack ==\n\nThe non-covert form can be trivially blocked by requiring that\nthe header version match the coinbase transaction version.\n\nThis proposal does not include this block because this method\nmay become generally available without restriction in the future,\ndoes not generally interfere with improvements in the protocol,\nand because it is so easily detected that it could be blocked if\nit becomes an issue in the future.\n\n==Backward compatibility==\n\n\n==Implementation==\n\n\n==Acknowledgments==\n\n\n==Copyright==\n\nThis document is placed in the public domain."}