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 714AFB44 for ; Tue, 23 May 2017 06:06:10 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f48.google.com (mail-wm0-f48.google.com [74.125.82.48]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CAFC6AD for ; Tue, 23 May 2017 06:06:09 +0000 (UTC) Received: by mail-wm0-f48.google.com with SMTP id 7so12637677wmo.1 for ; Mon, 22 May 2017 23:06:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bittorrent-com.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=Q6/qBtuGOQYic7dBfbowIgcycFalUxE35/T+rCeNGS8=; b=g/8mo/VPDND8oRswle8gBAZQHtqqbQP3F2iVneWbpv/NuX2DmHlsKYFP9FXrDro7T2 yssKDi/n6I97jQemH5jeX8vFNZIsdrw00LuMujWeu9JJsgw0w7oWr7nNnYqF92XzbROX S3gguaqB5klZP849Q78KkVFp2fCtib9ljRG2x0Qh5/G4aNJtzS1vnQ/54ZL0UU9uXfhF MWLb+fHF72UO2YG6hsKtHUgPLsN1JCZMnFcX2mVIV74wXdAJUDEPr/P1F1henrOgk9pY lPbALlYf+l02X9mk3FMLM1kZbgurjLnnywg7LIqw5997yIZO7TlMv4puVIiTj0FZtKVL jf2w== 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=Q6/qBtuGOQYic7dBfbowIgcycFalUxE35/T+rCeNGS8=; b=cR/5fFKLNC9TzIO6+g2gLg8zs/0hT5j2tPJV6sMa5STDlBzaNycc3FS1OC6EbYKdJH 0810MzyTS7oB+elg75tN2bubWShHy/2Ke5WVPG/bgvBd/Y/wliaG88cYbCJ6Qojpd3tG 6Hz3yhvQ5HeHQI9pK8jgVi+B1aRTme0DTT9mhHQ7/cxv3nFZxitpbtlPV032dVmxUnjU n21Zcvk6yWJdIpfx3F4lRfvRDhFSXRr6PQiuk29g+Twd6KuJJss8BaMxEh/zRtBCTIBl pb4uFI+CGub8Q9MLK8MaDs0jIkVfnOfnA0bhbC/go0inpqohEfMVeQxZdgfGWlbIfaXu nWFQ== X-Gm-Message-State: AODbwcCBWmtd9YnQYbHVe4lhcITYlwLbJpRH7j4q9rJEt7H/Xbf3unf0 Zj8anJ/0PU6UDkJUwj7vip6yiuQTkkDm X-Received: by 10.28.109.29 with SMTP id i29mr804522wmc.113.1495519568420; Mon, 22 May 2017 23:06:08 -0700 (PDT) MIME-Version: 1.0 Received: by 10.223.170.201 with HTTP; Mon, 22 May 2017 23:06:07 -0700 (PDT) In-Reply-To: References: From: Bram Cohen Date: Mon, 22 May 2017 23:06:07 -0700 Message-ID: To: "Russell O'Connor" Content-Type: multipart/alternative; boundary="001a11478866a181f505502ac810" X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=no 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: Tue, 23 May 2017 06:06:10 -0000 --001a11478866a181f505502ac810 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Mon, May 22, 2017 at 12:05 AM, Russell O'Connor via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > The SHA256 compression function takes two inputs: > > 1. A 256-bit value for the previous chunk in a chain, or an initial vecto= r > in the case of the first chunk. > 2. A 512-bit chunk of data. > > sha256Compress : Word256 =C3=97 Word512 -> Word256 > > In total, the SHA256 compression function compresses 768-bits into > 256-bits. The Merkle roots of two branches occupy 512 bits, and this > leaves another 256-bits of space available for tags. > Ya know, when you're building a Merkle Trie that's exactly the primitive you need. In my own construction the assumption is that the values are already hashed down to 256 bits when they're passed in, and the tags (which are currently done by sacrificing bits instead of using tags, that needs to be fixed) include three states for either side: empty, unary, or middle. Three of those possibilities are unreachable (empty/empty, empty/unary, unary/empty) so there are 6 possible tags needed. This approach essentially skips doing the unary hashes, a further performance improvement. There doesn't appear to be any downside in leveraging this trick as long as tags are cheap. --001a11478866a181f505502ac810 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On M= on, May 22, 2017 at 12:05 AM, Russell O'Connor via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
The SHA256 compression fu= nction takes two inputs:

1. A 256-bit value for the previous chunk i= n a chain, or an initial vector in the case of the first chunk.
2. A 512= -bit chunk of data.

= =C2=A0=C2=A0=C2=A0 sha256Compress : Word256 =C3=97 Word512 -> Word256
In total, the SHA256 compression function compresses 768-bits i= nto 256-bits.=C2=A0 The Merkle roots of two branches occupy 512 bits, and t= his leaves another 256-bits of space available for tags.

Ya know, when you're building a Merkle Trie tha= t's exactly the primitive you need.

In my own = construction the assumption is that the values are already hashed down to 2= 56 bits when they're passed in, and the tags (which are currently done = by sacrificing bits instead of using tags, that needs to be fixed) include = three states for either side: empty, unary, or middle. Three of those possi= bilities are unreachable (empty/empty, empty/unary, unary/empty) so there a= re 6 possible tags needed. This approach essentially skips doing the unary = hashes, a further performance improvement. There doesn't appear to be a= ny downside in leveraging this trick as long as tags are cheap.
= =C2=A0
--001a11478866a181f505502ac810--