diff options
| author | Russell O'Connor <roconnor@blockstream.io> | 2017-09-07 11:51:14 -0400 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2017-09-07 15:51:36 +0000 |
| commit | d8bd8d8b1ed836f0053f16c1c36fe63048419e6f (patch) | |
| tree | 30a68fb696aaee2f18a7ee2c186e8e60fd3df6ec | |
| parent | e776aa07bc4f9e45e8721ce0475bc852002c8af9 (diff) | |
| download | pi-bitcoindev-d8bd8d8b1ed836f0053f16c1c36fe63048419e6f.tar.gz pi-bitcoindev-d8bd8d8b1ed836f0053f16c1c36fe63048419e6f.zip | |
Re: [bitcoin-dev] Fast Merkle Trees
| -rw-r--r-- | 6e/3fad66c93aa090d11d361320891ea19b2299e3 | 138 |
1 files changed, 138 insertions, 0 deletions
diff --git a/6e/3fad66c93aa090d11d361320891ea19b2299e3 b/6e/3fad66c93aa090d11d361320891ea19b2299e3 new file mode 100644 index 000000000..ce15a95f3 --- /dev/null +++ b/6e/3fad66c93aa090d11d361320891ea19b2299e3 @@ -0,0 +1,138 @@ +Return-Path: <roconnor@blockstream.io> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 9C8148A1 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 7 Sep 2017 15:51:36 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.7.6 +Received: from mail-vk0-f45.google.com (mail-vk0-f45.google.com + [209.85.213.45]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 24ED3E5 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 7 Sep 2017 15:51:36 +0000 (UTC) +Received: by mail-vk0-f45.google.com with SMTP id v203so191037vkv.3 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 07 Sep 2017 08:51:36 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=blockstream-io.20150623.gappssmtp.com; s=20150623; + h=mime-version:in-reply-to:references:from:date:message-id:subject:to + :cc; bh=yhW5TkRJYpw1j14Klg4E2S8EKIs7dyXSIYXDdQa8Tyw=; + b=gr7EHSZban3HYW35uKd5nMGHceoHTEu3OhlHwfuFNV0yIG+IxztAD34Eym6AOUl+ra + RbPtP7cVuKREiCmh7yPlaaz3wz2pXjxuOeUi6vBbGHQPYwk4431uVoGL4nyKxBsCPvjc + ToIkb/DQC6VtD5B42ZykN48gH5iY/704xPHUKeaVEye3m5fI11U63i4DG8n4ClUe6ZN/ + XV0M/3H4LI3e9rClX/C9AysSH2b6oAI3eCFkjoBgoXfGnebk3Rs+K5B1cujnqwkeBmmL + DsVpUKYNZenTnCfnjGPhBUiErZSksX+R75tyinbJZVi77yB+3/KF3j1z8dzP7GIBXsX/ + XBIA== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20161025; + h=x-gm-message-state:mime-version:in-reply-to:references:from:date + :message-id:subject:to:cc; + bh=yhW5TkRJYpw1j14Klg4E2S8EKIs7dyXSIYXDdQa8Tyw=; + b=SRYKzX6vfw8MUZ1ZGKS7nQs/QYVoZEBkmk3edwE0GZcLPx8bsFrqxkzxrS/QMcAnwi + 0AvKZhMQs0KsAJLljh5O6+Vyms2x8zg3HbyuYLZ74nxRcdnB8sMqrQLWjfWuUt5jRTgD + d3qbxuvXoY1meF1Fty7ZV7mudZTiVYTztsCoz1qTBEWxFa7ykxYsWA6jPpzpw6TpME+B + Lj2MnwFitWDwyC2Sv9bb3RyhT4ZjpUeMX1A8aNfI79eNQW8jbjBlXzxEBT/KiYJyU18q + jha1lpwODb+L0bkaV+/EvSGHTLvRFFmEJGrjsV8HpCEZRoKoL7U2ifSsO4CnRz50XWt4 + rZYg== +X-Gm-Message-State: AHPjjUihMt9l3bfK8F3L41w7lY/OcAQKemFAFEBc9XYy3o2MAFPTscyw + o41JcM9DnYhyHp+AZiV+Y0VSBBKy+95c +X-Google-Smtp-Source: ADKCNb6xdL/3VZKGULfrz2sP1IDsdOXW++fvkCs3m+sHUCKfL8+n2woybs0eFm9GvhNbUPGqgDheVqUAIM32aa5Glw8= +X-Received: by 10.31.33.87 with SMTP id h84mr1761132vkh.105.1504799495236; + Thu, 07 Sep 2017 08:51:35 -0700 (PDT) +MIME-Version: 1.0 +Received: by 10.176.90.142 with HTTP; Thu, 7 Sep 2017 08:51:14 -0700 (PDT) +In-Reply-To: <20170907055557.GA12638@fedora-23-dvm> +References: <CAMZUoKmD4v4vn9L=kdyJNk-km3XHpNVkD_tmS+SseMsf6YaVPg@mail.gmail.com> + <20170907055557.GA12638@fedora-23-dvm> +From: "Russell O'Connor" <roconnor@blockstream.io> +Date: Thu, 7 Sep 2017 11:51:14 -0400 +Message-ID: <CAMZUoKk=00AJbtq602P=MWtGhWUY_7oCrWEUj+K7xp_+DOOTYg@mail.gmail.com> +To: Peter Todd <pete@petertodd.org> +Content-Type: multipart/alternative; boundary="001a11c000445f4b7b05589b6f38" +X-Spam-Status: No, score=0.5 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, + HTML_MESSAGE,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM autolearn=disabled + 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] Fast Merkle 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: Thu, 07 Sep 2017 15:51:36 -0000 + +--001a11c000445f4b7b05589b6f38 +Content-Type: text/plain; charset="UTF-8" + +On Thu, Sep 7, 2017 at 1:55 AM, Peter Todd <pete@petertodd.org> wrote: + +> On Wed, Sep 06, 2017 at 09:59:54PM -0400, Russell O'Connor via bitcoin-dev +> wrote: +> > The fast hash for internal nodes needs to use an IV that is not the +> > standard SHA-256 IV. Instead needs to use some other fixed value, which +> > should itself be the SHA-256 hash of some fixed string (e.g. the string +> > "BIP ???" or "Fash SHA-256"). +> +> Note that in general, designs should *not* create new hash functions by +> using +> custom IVs, but rather use bog-standard SHA256, and make a fixed first +> block. +> That allows unoptimised implementations to just hash a block with the +> second +> initialization value, and optimized implementations to start with the fixed +> midstate. + + +I 100% agree. + +With SHA256 every final state is also a valid midstate. Therefore, using a +custom IV of the SHA256 hash of some fixed string results in a hash of data +that is functionally equivalent to prefixing the data with the padded +version of the fixed string and using a regular SHA256 hash of the combined +data. This is important and I should have explicitly pointed it out. + +--001a11c000445f4b7b05589b6f38 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo= +te">On Thu, Sep 7, 2017 at 1:55 AM, Peter Todd <span dir=3D"ltr"><<a hre= +f=3D"mailto:pete@petertodd.org" target=3D"_blank">pete@petertodd.org</a>>= +;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 = +.8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=3D"">On Wed, = +Sep 06, 2017 at 09:59:54PM -0400, Russell O'Connor via bitcoin-dev wrot= +e:<br> +> The fast hash for internal nodes needs to use an IV that is not the<br= +> +> standard SHA-256 IV. Instead needs to use some other fixed value, whic= +h<br> +> should itself be the SHA-256 hash of some fixed string (e.g. the strin= +g<br> +> "BIP ???" or "Fash SHA-256").<br> +<br> +</span>Note that in general, designs should *not* create new hash functions= + by using<br> +custom IVs, but rather use bog-standard SHA256, and make a fixed first bloc= +k.<br> +That allows unoptimised implementations to just hash a block with the secon= +d<br> +initialization value, and optimized implementations to start with the fixed= +<br> +midstate.</blockquote><div><br></div><div>I 100% agree.</div><div><br></div= +><div>With SHA256 every final state is also a valid midstate.=C2=A0 Therefo= +re, using a custom IV of the SHA256 hash of some fixed string results in a = +hash of data that is functionally equivalent to prefixing the data with the= + padded version of the fixed string and using a regular SHA256 hash of the = +combined data.=C2=A0 This is important and I should have explicitly pointed= + it out.<br></div></div></div></div> + +--001a11c000445f4b7b05589b6f38-- + |