From: Johnson Lau <jl2012@xbt•hk>
To: Mark Friedenbach <mark@friedenbach•org>,
bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fast Merkle Trees
Date: Tue, 12 Sep 2017 19:44:48 +0800 [thread overview]
Message-ID: <14F84E09-5B25-4604-B210-A5CC2271C78C@xbt.hk> (raw)
In-Reply-To: <40D6F502-3380-4B64-BCD9-80D361EED35C@friedenbach.org>
> On 8 Sep 2017, at 4:04 AM, Mark Friedenbach via bitcoin-dev <bitcoin-dev@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.
next prev parent reply other threads:[~2017-09-12 11:45 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-09-07 1:59 Russell O'Connor
2017-09-07 2:20 ` Mark Friedenbach
2017-09-07 15:43 ` Russell O'Connor
2017-09-07 17:42 ` Mark Friedenbach
2017-09-07 18:55 ` Russell O'Connor
2017-09-07 20:04 ` Mark Friedenbach
2017-09-12 11:44 ` Johnson Lau [this message]
2017-09-07 5:55 ` Peter Todd
2017-09-07 15:51 ` Russell O'Connor
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=14F84E09-5B25-4604-B210-A5CC2271C78C@xbt.hk \
--to=jl2012@xbt$(echo .)hk \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=mark@friedenbach$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox