BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

Summary:

In a draft proposal for discussion titled "Inhibiting a covert attack on the Bitcoin POW function", author Greg Maxwell explains how the Bitcoin Proof of Work (POW) function has a potential vulnerability which allows miners to save up to 30% of their energy costs. The vulnerability is exploited through ASICBOOST, a patented technology marketed by Timo Hanke and Sergio Demian Lerner. While there exists an overt way of exploiting the vulnerability which is highly detectable, there also exists a covert method that has significant interaction and potential interference with the Bitcoin protocol. The protocol interactions of the covert method can block the implementation of virtuous improvements such as segregated witness. Reverse engineering of a mining ASIC from a major manufacturer revealed that it contained an undocumented, undisclosed ability to make use of this attack.A new proposal has been made to add a new consensus rule to prevent a covert attack on the SHA2-256 function used in Bitcoin mining. The attack involves reusing computation of initial expansion for multiple trials by preparing block headers with multiple distinct first 64-byte chunks but identical 16-byte second chunks. This reduces power consumption, and there are two broad ways of making use of this attack: trying candidates with different version numbers or finding multiple candidate root values which have the same final 32-bit. To find multiple roots with the same trailing 32-bits, miners can use efficient collision finding mechanisms 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 computation. An obvious way to generate different candidates is to grind the coinbase extra-nonce but for non-empty blocks each attempt will require 13 or so additional sha2 runs which is very 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 sqrt number of candidates of the right side of the tree using transaction permutation or substitution of a small number of transactions. All combinations of the left and right side are then combined with only a single hashing operation virtually eliminating 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 the >2^28 operations that would be required for extra-nonce grinding which would substantially erode the benefit of the attack. It is this final optimization which this proposal blocks.The proposed new consensus rule states that beginning block X and until block Y, the coinbase transaction of each block must either contain a BIP-141 segwit commitment or a correct WTXID commitment with ID 0xaa21a9ef. The commitment in the left side of the tree to all transactions in the right side completely prevents the final sqrt speedup. A stronger inhibition of the covert attack would be requiring the least significant bits of the block timestamp to be equal to a hash of the first 64-bytes of the header, which would increase the collision space from 32 to 40 or more bits. The root value could be required to meet a specific hash prefix requirement in order to increase the computational work required to try candidate roots. These changes would be more disruptive and there is no reason to believe that it is currently necessary.The proposed rule automatically sunsets, and if it is no longer needed due to the introduction of stronger rules or the acceptance of the version-grinding form then there would be no reason to continue with this requirement. If it is still useful at the expiration time the rule can simply be extended with a new softfork that sets longer date ranges. This sun-setting avoids the accumulation of technical debt due to retaining enforcement of this rule when it is no longer needed without requiring a hard fork to remove it. The non-covert form can be trivially blocked by requiring that the header version match the coinbase transaction version.

Updated on: 2023-05-20T01:51:00.465410+00:00