Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 080B42C for ; Sat, 27 May 2017 22:07:10 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ua0-f173.google.com (mail-ua0-f173.google.com [209.85.217.173]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4D3AEE4 for ; Sat, 27 May 2017 22:07:09 +0000 (UTC) Received: by mail-ua0-f173.google.com with SMTP id u10so20882377uaf.1 for ; Sat, 27 May 2017 15:07:09 -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; bh=+KLbk+pyKKoIMEDqGUTba48W5YNnlp6fC8xpOheUfcw=; b=s/OSyLgubgTBUVcxsBG95ZFonyOIEyofT1HwXGQK3vAV/3e7NQoUzfeJ5Z6o/VPh/b 4tPvMH/2JQM1uFbKXsBhfu8d61rE2rEQkcL6gAorubrRKdORLbKASK8kXuAZYKW69osR 4v5SewkerTUv6kNkXANhGjuH1A+oTFMIPebRaqztQQ1giayn9qz1lO+VtEk4Zwq8+ZPl h6KGChIJrnalHoeITKxKob5XwgFRWum2LXbzwJvow8ytK3gcPpp8HqqicoUtlhHUAoCM neuntqr06g3A8BDOSnyCnTOb480gEvNmpBK7xV01GYcpVqlTssakJIwiREHWQpcsfiXq rNLg== 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; bh=+KLbk+pyKKoIMEDqGUTba48W5YNnlp6fC8xpOheUfcw=; b=V2rHgzNKJ4rsl+xxA/c0WTbjvCnX23oJIFoqCZV29c5vn7G/QBTj8CNBSAzVlxERbc q6a99FvwIw8igih+POHUl7lP7AVTU8y5CLQyXJ9v4pXJa4hij6UmW2YN2PcSHiWvv0z4 04omr3xcETkS+J8cn+bwpoD5qNK2+rZ1poZ9CVa8WZGzHRIhVEVvUt5NQ5xJkMnxLzy7 UR2L+EMNk0GrVX7pKHFll+imfqF8SKxiLU2TO5xRiH8WNy+lHgXLzXYCmwvbx40QW577 ZlMNCBsuc6P5NX4/3HiYfw1FuzfgSmlpkJ3nq0w4DhQ88odYy2rc03HcCvqYNsl1NdDH a1jg== X-Gm-Message-State: AODbwcDgyuB50Lx9eYkPQiDPYNVcsBSJQb0IpFukWv0NGhu0vk0E6gih 0MSOnvMEC6ln/ltbGPPNYsXbnYWrCHTFfhA= X-Received: by 10.159.41.130 with SMTP id s2mr4255386uas.44.1495922828412; Sat, 27 May 2017 15:07:08 -0700 (PDT) MIME-Version: 1.0 Received: by 10.176.95.90 with HTTP; Sat, 27 May 2017 15:07:07 -0700 (PDT) Received: by 10.176.95.90 with HTTP; Sat, 27 May 2017 15:07:07 -0700 (PDT) In-Reply-To: References: <20170522140548.GA17732@fedora-23-dvm> <20170527174138.GA7610@fedora-23-dvm> From: "Russell O'Connor" Date: Sat, 27 May 2017 18:07:07 -0400 Message-ID: To: Peter Todd , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="001a114c1e92cc98da055088ac4d" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 27 May 2017 22:07:10 -0000 --001a114c1e92cc98da055088ac4d Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On May 28, 2017 06:09, "Russell O'Connor" wrote: On May 28, 2017 03:16, "Peter Todd" wrote: On Mon, May 22, 2017 at 06:32:38PM -0400, Russell O'Connor wrote: > On May 22, 2017 23:05, "Peter Todd" wrote: > > On Mon, May 22, 2017 at 03:05:49AM -0400, Russell O'Connor via bitcoin-de= v > wrote: > > MerkleRoot :=3D SHA256(SHA256(LeftRoot =E2=8B=85 RightRoot)) > > sha256Compress : Word256 =C3=97 Word512 -> Word256 > > To be clear, what math operations do you mean by "=E2=8B=85" and "=C3=97"= ? > > > By "=E2=8B=85", I usually mean concatenation (though I also use it for fu= nction > composition in one instance). By "=C3=97", I mean the Cartesian product= . Cartesian product can mean a lot of things. What specifically do you mean by "cartesian product" here? Oops, I forgot to reply all. Below is my reply. Given two types A and B, then A =C3=97 B is the type of pairs of A and B in= the sense of type theory as used in Standard ML or Haskell or other typed languages. To follow up, by "sha256Compress : Word256 =C3=97 Word512 -> Word256" I mea= n that sha256Compress is a function that takes two arguments, the first being a 256 bit word and the second being a 512 bit word, and returns a 256 bit word (or equivalently sha256Compress is a function that takes a pair as input, the first component being a 256 bit word and the second component being a 512 bit word, and returns a 256 bit word). sha256Compress is meant to be the compression function defined by the SHA256 standard, though nothing here depends on anything more that its type signature. --001a114c1e92cc98da055088ac4d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


On May 28, 2017 06:09, "Russell O'Connor" <roconnor@blockstrea= m.io> wrote:


On= May 28, 2017 03:16, "Peter Todd" <pete@petertodd.org> wrote:
On= Mon, May 22, 2017 at 06:32:38PM -0400, Russell O'Connor wrote:
> On May 22, 2017 23:05, "Peter Todd" <pete@petertodd.org> wrote:
>
> On Mon, May 22, 2017 at 03:05:49AM -0400, Russell O'Connor via bit= coin-dev
> wrote:
> >=C2=A0 =C2=A0 =C2=A0MerkleRoot :=3D SHA256(SHA256(LeftRoot =E2=8B= =85 RightRoot))
> >=C2=A0 =C2=A0 =C2=A0sha256Compress : Word256 =C3=97 Word512 -> = Word256
>
> To be clear, what math operations do you mean by "=E2=8B=85"= and "=C3=97"?
>
>
> By "=E2=8B=85", I usually mean concatenation (though I also = use it for function
> composition in one instance).=C2=A0 =C2=A0By "=C3=97", I mea= n the Cartesian product.

Cartesian product can mean a lot of things.

What specifically do you mean by "cartesian product" here?

Oops, I forgot to reply all.=C2=A0 Be= low is my reply.

Given two types A and= B, then A=C2=A0=C3=97 B is the type= of pairs of A and B in the sense of type theory as used in Standard ML or = Haskell or other typed languages.

To follow up, by &quo= t;sha256Compress : Word256 =C3=97 Wo= rd512 -> Word256" I mean that sha256Compress is a function that tak= es two arguments, the first being a 256 bit word and the second being a 512= bit word, and returns a 256 bit word (or equivalently sha256Compress is a = function that takes a pair as input, the first component being a 256 bit wo= rd and the second component being a 512 bit word, and returns a 256 bit wor= d).
sha256Compress i= s meant to be the compression function defined by the SHA256 standard, thou= gh nothing here depends on anything more that its type signature.
--001a114c1e92cc98da055088ac4d--