Return-Path: <jl2012@xbt.hk>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id CBF84955
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 12 Sep 2017 11:45:00 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from sender-of-o52.zoho.com (sender-of-o52.zoho.com [135.84.80.217])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 31253113
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 12 Sep 2017 11:45:00 +0000 (UTC)
Received: from [192.168.1.139] (137.189.135.167 [137.189.135.167]) by
	mx.zohomail.com with SMTPS id 1505216694069290.6603069124434;
	Tue, 12 Sep 2017 04:44:54 -0700 (PDT)
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
From: Johnson Lau <jl2012@xbt.hk>
In-Reply-To: <40D6F502-3380-4B64-BCD9-80D361EED35C@friedenbach.org>
Date: Tue, 12 Sep 2017 19:44:48 +0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <14F84E09-5B25-4604-B210-A5CC2271C78C@xbt.hk>
References: <CAMZUoKmD4v4vn9L=kdyJNk-km3XHpNVkD_tmS+SseMsf6YaVPg@mail.gmail.com>
	<F1D041D0-FC5A-425C-835D-37E7A9C0CFC5@friedenbach.org>
	<CAMZUoKmhN=m4TFwJi7u1bibLJ6mYvpnkddWTZZWdHn7+mVcJvw@mail.gmail.com>
	<EB804508-715A-4CD6-9B87-09845368DAC0@friedenbach.org>
	<CAMZUoKk7dHy6urnGRzAB2UG_fkwXmQrRHDfFYOHa0sTStr=yAQ@mail.gmail.com>
	<40D6F502-3380-4B64-BCD9-80D361EED35C@friedenbach.org>
To: Mark Friedenbach <mark@friedenbach.org>,
	bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
X-Mailer: Apple Mail (2.3273)
X-ZohoMailClient: External
X-Spam-Status: No, score=0.0 required=5.0 tests=RCVD_IN_DNSWL_NONE
	autolearn=disabled version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Fast Merkle Trees
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 12 Sep 2017 11:45:00 -0000


> On 8 Sep 2017, at 4:04 AM, Mark Friedenbach via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> 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:
>=20
>     <fake-pubkey> CHECKSIGVERIFY HASH160 <preimage> EQUAL
>=20
> 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:
>=20
>     DUP HASH160 <fake-pubkey-hash> EQUALVERIFY CHECKSIGVERIFY HASH160 =
<preimage> EQUAL
>=20
> This is 46 bytes, but requires grinding 96 bits, which is a bit less
> plausible.
>=20
> 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.
>=20

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.