From: "Russell O'Connor" <roconnor@blockstream•io>
To: Peter Todd <pete@petertodd•org>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Method for Computing Merkle Roots of Annotated Binary Trees
Date: Mon, 29 May 2017 10:55:37 -0400 [thread overview]
Message-ID: <CAMZUoK=8xaVp2Qoc7kvx8FdPbpY0rEpSba8kQVRQGjX4p0haxg@mail.gmail.com> (raw)
In-Reply-To: <20170528082624.GA14552@fedora-23-dvm>
[-- Attachment #1: Type: text/plain, Size: 2264 bytes --]
On Sun, May 28, 2017 at 4:26 AM, Peter Todd <pete@petertodd•org> wrote:
> On Mon, May 22, 2017 at 03:05:49AM -0400, Russell O'Connor via bitcoin-dev
> wrote:
> > Not all of the inputs to the SHA256 compression function are created
> > equal. Only the second argument, the chunk data, is applied to the
> SHA256
> > expander. `merkleRoot` is designed to ensure that the first argument of
> > the SHA256 compression function is only fed some output of the SHA256
> > compression function. In fact, we can prove that the output of the
> > `merkleRoot` function is always the midstate of some SHA256 hash. To see
> > this, let us explicitly separate the `sha256` function into the padding
> > step, `sha256Pad`, and the recursive hashing step, `unpaddedSha256`.
>
> This doesn't hold true in the case of pruned trees, as for the pruning to
> be
> useful, you don't know what produced the left merkleRoot, and thus you
> can't
> guarantee it is in fact a midstate of a genuine SHA256 hash.
>
Thanks for the review Peter. This does seem like a serious issue that I
hadn't considered yet. As far as I understand, we have no reason to think
that the SHA-256 compression function will be secure with chosen initial
values.
Some of this proposal can be salvaged, I think, by putting the hash of the
tags into Sha256Compress's first argument:
merkleRoot : Tree BitString -> Word256
merkleRoot (Leaf (t)) := sha256Compress(sha256(t),
0b0^512)
merkleRoot (Unary (t, child)) := sha256Compress(sha256(t),
merkleRoot(child) ⋅ 0b0^256)
merkleRoot (Binary (t, left, right)) := sha256Compress(sha256(t),
merkleRoot(left) ⋅ merkleRoot(right))
The Merkle--Damgård property will still hold under the same conditions
about tags determining the type of node (Leaf, Unary, or Binary) while
avoiding the need for SHA256's padding. If you have a small number of
tags, then you can pre-compute their hashes so that you only end up with
one call to SHA256 compress per node. If you have tags with a large amount
of data, you were going to be hashing them anyways.
Unfortunately we lose the ability to cleverly avoid collisions between the
Sha256 and MerkleRoot functions by using safe tags.
[-- Attachment #2: Type: text/html, Size: 3337 bytes --]
next prev parent reply other threads:[~2017-05-29 14:55 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-05-22 7:05 Russell O'Connor
2017-05-22 14:05 ` Peter Todd
2017-05-22 22:32 ` Russell O'Connor
2017-05-27 17:41 ` Peter Todd
[not found] ` <CAMZUoKkS8azx7Gooo3D+H_gdGdTNiNtwwNVbvU0u7HzOfdUSBg@mail.gmail.com>
2017-05-27 22:07 ` Russell O'Connor
2017-05-23 6:06 ` Bram Cohen
2017-05-28 8:26 ` Peter Todd
2017-05-29 14:55 ` Russell O'Connor [this message]
2017-05-29 16:10 ` Peter Todd
2017-06-01 15:10 ` Russell O'Connor
2017-06-27 4:13 ` Peter Todd
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='CAMZUoK=8xaVp2Qoc7kvx8FdPbpY0rEpSba8kQVRQGjX4p0haxg@mail.gmail.com' \
--to=roconnor@blockstream$(echo .)io \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=pete@petertodd$(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