summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMark Friedenbach <mark@friedenbach.org>2017-09-06 19:20:06 -0700
committerbitcoindev <bitcoindev@gnusha.org>2017-09-07 02:20:08 +0000
commit9d628679303b1795b9877b3d99c9bfc181124f2d (patch)
tree9536eb0099c2e42a024216f4d6b630dbc839ee56
parent70f1b820ba92c064acb1e80cd086c79c6aa4893f (diff)
downloadpi-bitcoindev-9d628679303b1795b9877b3d99c9bfc181124f2d.tar.gz
pi-bitcoindev-9d628679303b1795b9877b3d99c9bfc181124f2d.zip
Re: [bitcoin-dev] Fast Merkle Trees
-rw-r--r--87/2ec6fc70e999c56ede044756c1d281ba957fad148
1 files changed, 148 insertions, 0 deletions
diff --git a/87/2ec6fc70e999c56ede044756c1d281ba957fad b/87/2ec6fc70e999c56ede044756c1d281ba957fad
new file mode 100644
index 000000000..62a06a31e
--- /dev/null
+++ b/87/2ec6fc70e999c56ede044756c1d281ba957fad
@@ -0,0 +1,148 @@
+Return-Path: <mark@friedenbach.org>
+Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
+ [172.17.192.35])
+ by mail.linuxfoundation.org (Postfix) with ESMTPS id D1986486
+ for <bitcoin-dev@lists.linuxfoundation.org>;
+ Thu, 7 Sep 2017 02:20:08 +0000 (UTC)
+X-Greylist: whitelisted by SQLgrey-1.7.6
+Received: from mail-pg0-f49.google.com (mail-pg0-f49.google.com [74.125.83.49])
+ by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 50C3B1E5
+ for <bitcoin-dev@lists.linuxfoundation.org>;
+ Thu, 7 Sep 2017 02:20:08 +0000 (UTC)
+Received: by mail-pg0-f49.google.com with SMTP id 188so15160704pgb.2
+ for <bitcoin-dev@lists.linuxfoundation.org>;
+ Wed, 06 Sep 2017 19:20:08 -0700 (PDT)
+DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
+ d=friedenbach-org.20150623.gappssmtp.com; s=20150623;
+ h=mime-version:subject:from:in-reply-to:date:cc
+ :content-transfer-encoding:message-id:references:to;
+ bh=O99owo4VeAG8qGCck0PX8f7UNn60b2znQ2XeDqHaeZk=;
+ b=kst5S6SGpMa41QWwqy04OF+UL59HX2LSLo6kB3Ep/Me8S4Rm/HRohBLVxj1BYRPM+w
+ HKNzGFuO9J1HVOMKhjKwDgJ3U0RBHS/WEBcQGeruvF5L+UBkj1pug9WA1FyHchJxWv4i
+ FYLbiNVQEC9OpXoJckGL0VcS+ZskHCBaBHitUMQm94cEmys5diVGym6eGKiZKfO4bbxb
+ 6niCY8nQiggQ0dJNiYbB4/lc18CekjypV2hv/GIyjURZPacwBi/iQoSloD200kmtuFSj
+ 6HDRdip0uDlGaipnlvchyRg0cg+4a76qDp+1LL7qFtIww/ivw1+hQ0UTXx43lgXcJ8HW
+ YU/A==
+X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
+ d=1e100.net; s=20161025;
+ h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc
+ :content-transfer-encoding:message-id:references:to;
+ bh=O99owo4VeAG8qGCck0PX8f7UNn60b2znQ2XeDqHaeZk=;
+ b=IxLkafmiLvKzwqfOnxtyTaNEwnlAx+zsB7Ol6PZWJ1cKILbtC2GMciEWjBtBdfJ1F0
+ LBnisElrJnuN6o0fWs9Eu+miPQKDFO15nqmMVDytpGkdJhy52jWTVfSp6y6x74dErufk
+ TJRYE+dTSk5+pHUU6z4Y4zIy8QjNQrSg2nltiTPT1THmfAqCsxU54X2R5f+HD/IUnYOe
+ RUPSABMPGFuc8n5RyRgeG3ZNNCTbSa6PG2TkIjOJ4y+Co/x6x0gCabH+3dVYV2WwaJ0B
+ CBgbIBIm6yGXbSR3wMVKAiRzJZKuxJubFh9hipqRcVtsKSFlz6DgqwHOUkMZHjgGprVf
+ wYXw==
+X-Gm-Message-State: AHPjjUhtJFvTHNB7tZdUjJlqc9OEy0/dWUdfTSo1V8X7fL60CTWaNz4h
+ PJSXlkdSyU1IPO7YWBvFSA==
+X-Google-Smtp-Source: ADKCNb5mjegnFJ6zJIttXxlC0WDzrQCOyeo4KAlKrBQ/RWD/+dVdNnBy+XGTQ/upRWBlmVJ90AhEQQ==
+X-Received: by 10.98.17.156 with SMTP id 28mr1155647pfr.83.1504750807670;
+ Wed, 06 Sep 2017 19:20:07 -0700 (PDT)
+Received: from ?IPv6:2601:646:8080:1291:9c8f:a514:978d:a19a?
+ ([2601:646:8080:1291:9c8f:a514:978d:a19a])
+ by smtp.gmail.com with ESMTPSA id
+ x28sm1162743pgc.91.2017.09.06.19.20.06
+ (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
+ Wed, 06 Sep 2017 19:20:06 -0700 (PDT)
+Content-Type: multipart/alternative;
+ boundary=Apple-Mail-6D4C8F99-E208-40D8-86E3-84CAF12792B7
+Mime-Version: 1.0 (1.0)
+From: Mark Friedenbach <mark@friedenbach.org>
+X-Mailer: iPhone Mail (14G60)
+In-Reply-To: <CAMZUoKmD4v4vn9L=kdyJNk-km3XHpNVkD_tmS+SseMsf6YaVPg@mail.gmail.com>
+Date: Wed, 6 Sep 2017 19:20:06 -0700
+Content-Transfer-Encoding: 7bit
+Message-Id: <F1D041D0-FC5A-425C-835D-37E7A9C0CFC5@friedenbach.org>
+References: <CAMZUoKmD4v4vn9L=kdyJNk-km3XHpNVkD_tmS+SseMsf6YaVPg@mail.gmail.com>
+To: Russell O'Connor <roconnor@blockstream.io>
+X-Spam-Status: No, score=0.0 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
+ HTML_MESSAGE,MIME_QP_LONG_LINE,RCVD_IN_DNSWL_NONE autolearn=disabled
+ version=3.3.1
+X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
+ smtp1.linux-foundation.org
+X-Mailman-Approved-At: Thu, 07 Sep 2017 05:24:13 +0000
+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 02:20:08 -0000
+
+
+--Apple-Mail-6D4C8F99-E208-40D8-86E3-84CAF12792B7
+Content-Type: text/plain;
+ charset=us-ascii
+Content-Transfer-Encoding: quoted-printable
+
+This design purposefully does not distinguish leaf nodes from internal nodes=
+. That way it chained invocations can be used to validate paths longer than 3=
+2 branches. Do you see a vulnerability due to this lack of distinction?
+
+> On Sep 6, 2017, at 6:59 PM, Russell O'Connor <roconnor@blockstream.io> wro=
+te:
+>=20
+> The fast hash for internal nodes needs to use an IV that is not the standa=
+rd SHA-256 IV. Instead needs to use some other fixed value, which should its=
+elf be the SHA-256 hash of some fixed string (e.g. the string "BIP ???" or "=
+Fash SHA-256").
+>=20
+> As it stands, I believe someone can claim a leaf node as an internal node b=
+y creating a proof that provides a phony right-hand branch claiming to have h=
+ash 0x80000..0000100 (which is really the padding value for the second half o=
+f a double SHA-256 hash).
+>=20
+> (I was schooled by Peter Todd by a similar issue in the past.)
+>=20
+>> On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev <bitcoin=
+-dev@lists.linuxfoundation.org> wrote:
+>> Fast Merkle Trees
+>> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
+>> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
+
+--Apple-Mail-6D4C8F99-E208-40D8-86E3-84CAF12792B7
+Content-Type: text/html;
+ charset=utf-8
+Content-Transfer-Encoding: quoted-printable
+
+<html><head><meta http-equiv=3D"content-type" content=3D"text/html; charset=3D=
+utf-8"></head><body dir=3D"auto"><div>This design purposefully does not dist=
+inguish leaf nodes from internal nodes. That way it chained invocations can b=
+e used to validate paths longer than 32 branches. Do you see a vulnerability=
+ due to this lack of distinction?<br></div><div><br>On Sep 6, 2017, at 6:59 P=
+M, Russell O'Connor &lt;<a href=3D"mailto:roconnor@blockstream.io">roconnor@=
+blockstream.io</a>&gt; wrote:<br><br></div><blockquote type=3D"cite"><div><d=
+iv dir=3D"ltr"><div><div>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 v=
+alue, which should itself be the SHA-256 hash of some fixed string (e.g. the=
+ string "BIP ???" or "Fash SHA-256").<br><br></div>As it stands, I believe s=
+omeone can claim a leaf node as an internal node by creating a proof that pr=
+ovides a phony right-hand branch claiming to have hash 0x80000..0000100 (whi=
+ch is really the padding value for the second half of a double SHA-256 hash)=
+.<br><br></div>(I was schooled by Peter Todd by a similar issue in the past.=
+)<br><div><div><div><div><div><div><div class=3D"gmail_extra"><br><div class=
+=3D"gmail_quote">On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoi=
+n-dev <span dir=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundat=
+ion.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</sp=
+an> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;b=
+order-left:1px #ccc solid;padding-left:1ex">
+Fast Merkle Trees<br>
+BIP: <a href=3D"https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee=
+0a" rel=3D"noreferrer" target=3D"_blank">https://gist.github.com/maaku/<wbr>=
+41b0054de0731321d23e9da90ba4ee<wbr>0a</a><br>
+Code: <a href=3D"https://github.com/maaku/bitcoin/tree/fast-merkle-tree" rel=
+=3D"noreferrer" target=3D"_blank">https://github.com/maaku/<wbr>bitcoin/tree=
+/fast-merkle-tree</a><br></blockquote></div></div></div></div></div></div></=
+div></div></div>
+</div></blockquote></body></html>=
+
+--Apple-Mail-6D4C8F99-E208-40D8-86E3-84CAF12792B7--
+