[bitcoin-dev] Fast Merkle Trees

[Johnson Lau]

> On 8 Sep 2017, at 4:04 AM, Mark Friedenbach via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> 
> If I understand the revised attack description correctly, then there
> is a small window in which the attacker can create a script less than
> 55 bytes in length, where nearly all of the first 32 bytes are
> selected by the attacker, yet nevertheless the script seems safe to
> the counter-party. The smallest such script I was able to construct
> was the following:
> 
>     <fake-pubkey> CHECKSIGVERIFY HASH160 <preimage> EQUAL
> 
> This is 56 bytes and requires only 7 bits of grinding in the fake
> pubkey. But 56 bytes is too large. Switching to secp256k1 serialized
> 32-byte pubkeys (in a script version upgrade, for example) would
> reduce this to the necessary 55 bytes with 0 bits of grinding. A
> smaller variant is possible:
> 
>     DUP HASH160 <fake-pubkey-hash> EQUALVERIFY CHECKSIGVERIFY HASH160 <preimage> EQUAL
> 
> This is 46 bytes, but requires grinding 96 bits, which is a bit less
> plausible.
> 
> Belts and suspenders are not so terrible together, however, and I
> think there is enough of a justification here to look into modifying
> the scheme to use a different IV for hash tree updates. This would
> prevent even the above implausible attacks.
> 

I think you overestimated the difficulty. Consider this MAST branch (an example in BIP114)

"Timestamp" CHECKLOCKTIMEVERIFY <fake-pubkey> CHECKSIGVERIFY

This requires just a few bytes of collision.