Date: Sun, 28 May 2017 04:26:24 -0400
From: Peter Todd <pete@petertodd.org>
To: "Russell O'Connor" <roconnor@blockstream.io>
Message-ID: <20170528082624.GA14552@fedora-23-dvm>
References: <CAMZUoK=f3hXHkqJBDfiLGSrgXi_ppgyH6+XWD9W54EYFWLm1+Q@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="liOOAslEiF7prFVr"
Content-Disposition: inline
In-Reply-To: <CAMZUoK=f3hXHkqJBDfiLGSrgXi_ppgyH6+XWD9W54EYFWLm1+Q@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Method for Computing Merkle Roots of Annotated
 Binary Trees
Precedence: list


--liOOAslEiF7prFVr
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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.

--=20
https://petertodd.org 'peter'[:-1]@petertodd.org

--liOOAslEiF7prFVr
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----

iQEcBAEBCAAGBQJZKomuAAoJECSBQD2l8JH7WA8IAI7pd4ivXMKExULoDtaUMHcL
2vUYyzkVbyHwdx28yeGJWvjGi+aVd2KkmneN5OxMLf9kd4J8Wj47mPFb+coiKUCO
4+AJQ+A3plbXGIP8T9wyODvP3soS9XDQ1Wm+1srO4wl+Vv7zNftfLJZUU6bzx4+L
WwQBEwitZn6dhJec9Y2fbPHuKO3HSFDRf5jxa4k+sEdfX8555k35iyB3K6Qnl1tN
J2UmeMo4Y6NsiKlCQd44dqcw09qjBhj7xTj5ZULI+Acp95Y1qwl7ZkVH2HOQsplZ
uf0qU/Eoj1Zow/XrgDpiYFbUwzI/JvpGDpVM0VYDygRhxvbXf/rNtKHgPH2McoM=
=k9CE
-----END PGP SIGNATURE-----

--liOOAslEiF7prFVr--