10:53 AM
@Murch Re: "For reasons I don't fully understand, this commitment makes it 16 times harder to find matching Merkle roots and thus makes the covert application of ASICBOOST less feasible."
The covert form of ASICBoost requires finding colliding partial block headers by modifying parts of the block header merkle root.
The conceptually simple way to do that is to grind the coinbase transaction extranonce space, but each time you change the coinbase transaction, you have to re-hash it and every merkle tree pair above it up to the merkle root, which is 11 to 12 extra hashes for 2048 to 4096 transaction blocks and so 11 to 12 times slower than plain grinding (plus it's sha256d, so another 2x less efficient than sha256 grinding).
A less conceptually simple but more efficient way to accomplish the same result of obtaining a particular block header merkle root is to create one left side of the tree that contains a particular coinbase transaction and multiple right-sides of the tree, so all you need to do is one sha256d hash to combine the sides and see if you generated the desired block header merkle root.
In pracitice, you can generate multiple right side trees efficiently by simply combining multiple compatible candidate trees a few branches down from the merkle root in different ways (which is why naively-implemented covert-ASICBoost may have out-of-order transaction fees, unknown transactions, and never or rarely any ancestor/decendant transactions in the same block). This process is highly parallizable.
You can also do this the other way around and keep the right-side of the tree static while grinding the left side of the tree, although it's slightly less efficient owing to the coinbase transaction having a fixed place within the Merkle tree so the branches containing it can't be rearranged.
Segwit and the alternative segwit-like commitment in Maxwell's proposed BIP breaks this because it puts in the coinbase transaction a Merkle root commitment to all of other transactions in the order they appear in the block.
That means any time you update any transaction in a block (including rearranging the ordering of the transactions), the coinbase tranaction Merkle leaf is updated and the entire left side of the Merkle tree has to be updated---pushing you back to the same lower efficiency as the conceptually simple method described above.
Oh, I should note that the above is just my best guess based on what Maxwell said in his initial email; I haven't had time to dig in on ASICBoost yet.
