From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 61F684A3 for ; 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 ; 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 To: "Russell O'Connor" Message-ID: <20170528082624.GA14552@fedora-23-dvm> References: MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="liOOAslEiF7prFVr" Content-Disposition: inline In-Reply-To: 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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--