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 D1986486 for ; 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 ; Thu, 7 Sep 2017 02:20:08 +0000 (UTC) Received: by mail-pg0-f49.google.com with SMTP id 188so15160704pgb.2 for ; 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 X-Mailer: iPhone Mail (14G60) In-Reply-To: Date: Wed, 6 Sep 2017 19:20:06 -0700 Content-Transfer-Encoding: 7bit Message-Id: References: To: Russell O'Connor 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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 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
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?

On Sep 6, 2017, at 6:59 P= M, Russell O'Connor <roconnor@= blockstream.io> 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 v= alue, which should itself be the SHA-256 hash of some fixed string (e.g. the= string "BIP ???" or "Fash SHA-256").

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)= .

(I was schooled by Peter Todd by a similar issue in the past.= )

On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoi= n-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--