From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id CBF84955 for ; 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 ; 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 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: <40D6F502-3380-4B64-BCD9-80D361EED35C@friedenbach.org> To: Mark Friedenbach , bitcoin-dev 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 = 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 > CHECKSIGVERIFY HASH160 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 EQUALVERIFY CHECKSIGVERIFY HASH160 = 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 CHECKSIGVERIFY This requires just a few bytes of collision.