|
November 24, 2015, 05:05:58 PM |
|
I will add some reasoning about free start pre-image / collisions attacks that makes me think it is less of a problem for this particular use. These are the reasons:
1. The security of pre-image resistance of SHA-256 in bits is 256 bits. If SHA-256 were 100% secure, an attacker that wants to reuse the PoW of another merge-mined block will need to perform 2^256 operations. This attack will never be practical for SHA-256, even having a free start. There has be no successful practical pre-image attack to any of the once standardized hash functions (including MD5, SHA-1, etc.). The best theoretical pre-image attack to the broken MD5 requires 2^125 operations, which is much more than the current PoW difficulty.
2. A simpler attack is to first try to find two or more free-start collisions in the coinbase, and then create a merge-mined block. The collision resistance security of SHA-256 is 128 bits.
The best freestart attacks on SHA-1 requires around 2^60 operations and only produce a single collision (it does not extend to create multiple collisions). There is no known free start collision vulnerability in full SHA-256.
As an example, suppose that a full free start collision that requires 2^100 operations is found. That would be devastating for SHA-256, and everyone (including Bitcoin) will start to move away from SHA-256. However, it still won't affect this particular use.
We can assume the Bitcoin proof-of-work will not have more than 100 zero prefix bits for the next 50 years (assuming Moore's law stays true, and performance per watt keeps increasing exponentially, since currently Bitcoin PoW it has around 72 zero bits). And that would be a very positive scenario, as Bitcoin reward will be 4096 times lower, to keep up with the same amount of mining hashing power the Bitcoin will need to be 4096 times more valuable (1 BTC = 1.3M USD) or each block would need to be 400 GB to pay enough fees.
But the operations involved in finding a collision are not equivalent to PoW hash operations (SHA256D). There will be no pre-built optimized ASICs to execute such attack, and the attack will require the use of GPUs. So we can expect another 1000x performance ratio between them (10 bits). 3. Generally attacks start being unpractical and then they get slowly better over time, so when an initial vulnerability is found, there is plenty of time to hard-fork. Assuming the attack only produces a single collision, and a successful and immediate attack is found, the consequence would be a short period of very fast blocks (e.g. 1 per second), followed by a difficulty adjustment that will prevent the merged block-chain from growing without limit. That would give plenty of time for a hard-fork, rendering the attack useless.
4. Even if the attack could find many collisions at once, it would be very easy to prevent the reuse of Bitcoin headers by not allowing the repetition of the Bitcoin header in the last 100 mined blocks. Checking the timestamp of the Bitcoin block, and not allowing the use of an old header (e.g. the header timestamp must be not older than 1 hour, or the median timestamp of the last 10 blocks) can also help.
5. The attack would be immediately detected as the coinbase part presented would surely not be a valid coinbase transaction tail.
So I expect that using the mid-state for coinbase compression in merge-mining will not be a problem for the next 50 years.
|