public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Bram Cohen <bram@bittorrent.com>
To: "Russell O'Connor" <roconnor@blockstream.io>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Method for Computing Merkle Roots of Annotated Binary Trees
Date: Mon, 22 May 2017 23:06:07 -0700	[thread overview]
Message-ID: <CA+KqGkprA9XvaymW5VcpkcBQDp8s_M37r1K_9mbYScxMpV7cfQ@mail.gmail.com> (raw)
In-Reply-To: <CAMZUoK=f3hXHkqJBDfiLGSrgXi_ppgyH6+XWD9W54EYFWLm1+Q@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 1269 bytes --]

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 vector
> in the case of the first chunk.
> 2. A 512-bit chunk of data.
>
>     sha256Compress : Word256 × 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.

[-- Attachment #2: Type: text/html, Size: 1712 bytes --]

  parent reply	other threads:[~2017-05-23  6:06 UTC|newest]

Thread overview: 11+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-05-22  7:05 [bitcoin-dev] A Method for Computing Merkle Roots of Annotated Binary Trees Russell O'Connor
2017-05-22 14:05 ` Peter Todd
2017-05-22 22:32   ` Russell O'Connor
2017-05-27 17:41     ` Peter Todd
     [not found]       ` <CAMZUoKkS8azx7Gooo3D+H_gdGdTNiNtwwNVbvU0u7HzOfdUSBg@mail.gmail.com>
2017-05-27 22:07         ` Russell O'Connor
2017-05-23  6:06 ` Bram Cohen [this message]
2017-05-28  8:26 ` Peter Todd
2017-05-29 14:55   ` Russell O'Connor
2017-05-29 16:10     ` Peter Todd
2017-06-01 15:10       ` Russell O'Connor
2017-06-27  4:13     ` Peter Todd

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CA+KqGkprA9XvaymW5VcpkcBQDp8s_M37r1K_9mbYScxMpV7cfQ@mail.gmail.com \
    --to=bram@bittorrent.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=roconnor@blockstream.io \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox