diff options
author | Peter Todd <pete@petertodd.org> | 2017-05-28 04:26:24 -0400 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2017-05-28 08:26:36 +0000 |
commit | 7419c1604b4f64e40d95b760d2a98a7eec76db3b (patch) | |
tree | 5af70fe516496fe543fd5089bd2048768ef36efd | |
parent | cd6a06f8a5bf8103bd93a6bf7645a64614b4e9e2 (diff) | |
download | pi-bitcoindev-7419c1604b4f64e40d95b760d2a98a7eec76db3b.tar.gz pi-bitcoindev-7419c1604b4f64e40d95b760d2a98a7eec76db3b.zip |
Re: [bitcoin-dev] A Method for Computing Merkle Roots of Annotated Binary Trees
-rw-r--r-- | f4/5e7818b35a89c0dcf5c51a171b49c4a56bfb59 | 111 |
1 files changed, 111 insertions, 0 deletions
diff --git a/f4/5e7818b35a89c0dcf5c51a171b49c4a56bfb59 b/f4/5e7818b35a89c0dcf5c51a171b49c4a56bfb59 new file mode 100644 index 000000000..a7de87f86 --- /dev/null +++ b/f4/5e7818b35a89c0dcf5c51a171b49c4a56bfb59 @@ -0,0 +1,111 @@ +Return-Path: <pete@petertodd.org> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 61F684A3 + for <bitcoin-dev@lists.linuxfoundation.org>; + Sun, 28 May 2017 08:26:36 +0000 (UTC) +X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 +Received: from outmail149056.authsmtp.com (outmail149056.authsmtp.com + [62.13.149.56]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9569079 + for <bitcoin-dev@lists.linuxfoundation.org>; + Sun, 28 May 2017 08:26:35 +0000 (UTC) +Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247]) + by punt21.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v4S8QXOk023568; + Sun, 28 May 2017 09:26:33 +0100 (BST) +Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com + [52.5.185.120]) (authenticated bits=0) + by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v4S8QUPX077703 + (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); + Sun, 28 May 2017 09:26:31 +0100 (BST) +Received: from [127.0.0.1] (localhost [127.0.0.1]) + by petertodd.org (Postfix) with ESMTPSA id 0A4C040098; + Sun, 28 May 2017 08:26:30 +0000 (UTC) +Received: by localhost (Postfix, from userid 1000) + id A811520611; Sun, 28 May 2017 04:26:24 -0400 (EDT) +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) +X-Server-Quench: 5ac4f0ce-437f-11e7-bcdf-0015176ca198 +X-AuthReport-Spam: If SPAM / abuse - report it at: + http://www.authsmtp.com/abuse +X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR + aAdMdAoUFVQNAgsB AmEbW11eUlt7WmE7 bghPaBtcak9QXgdq + T0pMXVMcUgELCX1k ZnYeVR51dwYIfXx1 bQhnDyNfCkQpIFt5 + QUkCCGwHMGB9OjNL Bl1YdwJRcQRMLU5E Y1gxNiYHcQ5VPz4z + GA41ejw8IwAXAWxw Tx0NKl5aT0ERVhU7 QggfATQpEgUgSj8w + KxFuEFkbAF1ZNUt6 GF0nXk4RLxIeaEV0 HkdEGj4RG0MMSjFD +X-Authentic-SMTP: 61633532353630.1038:706 +X-AuthFastPath: 0 (Was 255) +X-AuthSMTP-Origin: 52.5.185.120/25 +X-AuthVirus-Status: No virus detected - but ensure you scan with your own + anti-virus system. +X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW + autolearn=ham version=3.3.1 +X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on + smtp1.linux-foundation.org +Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +Subject: Re: [bitcoin-dev] A Method for Computing Merkle Roots of Annotated + Binary 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: Sun, 28 May 2017 08:26:36 -0000 + + +--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-- + |