summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPeter Todd <pete@petertodd.org>2017-05-28 04:26:24 -0400
committerbitcoindev <bitcoindev@gnusha.org>2017-05-28 08:26:36 +0000
commit7419c1604b4f64e40d95b760d2a98a7eec76db3b (patch)
tree5af70fe516496fe543fd5089bd2048768ef36efd
parentcd6a06f8a5bf8103bd93a6bf7645a64614b4e9e2 (diff)
downloadpi-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/5e7818b35a89c0dcf5c51a171b49c4a56bfb59111
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--
+