diff options
| author | Bram Cohen <bram@chia.net> | 2018-06-08 20:29:30 -0700 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2018-06-09 03:29:33 +0000 |
| commit | 3841ca6154ebb86423bfedf09d4919889907bce4 (patch) | |
| tree | 84880f0a38e6d65a3a65463762f55d477febb910 | |
| parent | 50a459c94b2bfc1a09724b9072c59efef68876ce (diff) | |
| download | pi-bitcoindev-3841ca6154ebb86423bfedf09d4919889907bce4.tar.gz pi-bitcoindev-3841ca6154ebb86423bfedf09d4919889907bce4.zip | |
Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork
| -rw-r--r-- | 2a/9712e4631e68c0b09335e77de3610e2719d607 | 204 |
1 files changed, 204 insertions, 0 deletions
diff --git a/2a/9712e4631e68c0b09335e77de3610e2719d607 b/2a/9712e4631e68c0b09335e77de3610e2719d607 new file mode 100644 index 000000000..2f3833f93 --- /dev/null +++ b/2a/9712e4631e68c0b09335e77de3610e2719d607 @@ -0,0 +1,204 @@ +Return-Path: <bram@chia.net> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 9871C9E2 + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 9 Jun 2018 03:29:33 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.7.6 +Received: from mail-wm0-f52.google.com (mail-wm0-f52.google.com [74.125.82.52]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id E4D885C2 + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 9 Jun 2018 03:29:32 +0000 (UTC) +Received: by mail-wm0-f52.google.com with SMTP id 69-v6so6880799wmf.3 + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 08 Jun 2018 20:29:32 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=chia-net.20150623.gappssmtp.com; s=20150623; + h=mime-version:in-reply-to:references:from:date:message-id:subject:to + :cc; bh=VXbsYwcyEwRHSqvdlngzaTlNrwwzUqi5AStJRp8Yrug=; + b=Xy1k8rN9ugYQ5JSytDV55/FPx+c/k/O//AUceHKXsAsZgHbzXs9ktE4aknHHzTBKU9 + fyb1aQFyhH0Sy+1b7RYw0nmQlT/CHNZ3qTFVgZJHJFagY+mMhiyR3YvZ5gZtM+WOh52q + fxWSAze49bTdAubP/JOmqlkehlCPRgdC7Pu7tm6dDTTVw4CFflvqMlnsejwIjhpVcmym + DVnwGJbNvEovf/VYotuLj/Rq63fw04B92vu5YWzJOwgjjlcZ1d6+jHpDOYrzb7Tknsp7 + F1XI/sAtmp/EQAajJfN37N8PsGBa5Oop/mcNrLk0DiydH6wet+FvJ+hUbTKyU0r0/C/q + L/6A== +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=VXbsYwcyEwRHSqvdlngzaTlNrwwzUqi5AStJRp8Yrug=; + b=fnEmaZDW1QeaEIoy8LW4h5EAyRtQXK0MDe92ulPtUKZuJ4+C1kjrHrCUypV3TVXu4h + Bwu2srcMb6j2Qqis2UJAS0DkpPZzAqNf/36r6X3QZ2vbLpUZkN8MmWHjf3HLnW7B9ALu + 0QtmgdarDwrdkgccXoio8HcjEhM+9wix3jjbj9fZKe6h+1MrFcmBCL1l3/ku0CIbDpRr + itG2pDA/bka30fX0RZSCtBcDw0j2h+5lt2zcbwHPpsK1ZbsWZsxVwMMj1/DZag4wkepa + yC3mfwIaBGzsx5nXwwgqpm2oolnMIw7UK1aCVygKjXpt9ZXbVsIYWa/S+JtP533000IV + ahgQ== +X-Gm-Message-State: APt69E3zS0dK1w1qs4xwm5q9xmaiYj/ZIf96I+c2TJC9OcZ8uSWhVk5E + AS+NPPtwEO4C4ukLlcwIzacqNKDXGKRVlQV481rwmHxi +X-Google-Smtp-Source: ADUXVKKrHNSYS4U8We/wUsNWjZLOjjJ4f/RYaL5F+8fI+NhH6rucDQlg67sZu5rk2o5rJ+t+ikblgl1gCdcN9xfMqaA= +X-Received: by 2002:a1c:9f06:: with SMTP id i6-v6mr2783041wme.73.1528514971454; + Fri, 08 Jun 2018 20:29:31 -0700 (PDT) +MIME-Version: 1.0 +Received: by 2002:a1c:b984:0:0:0:0:0 with HTTP; + Fri, 8 Jun 2018 20:29:30 -0700 (PDT) +X-Originating-IP: [65.200.105.218] +In-Reply-To: <20180607222028.zbva4vrv64dzrmxy@petertodd.org> +References: <20180607171311.6qdjohfuuy3ufriv@petertodd.org> + <CAHUJnBB7UL3mH6SixP_M4yooMVP3DgZa+5hiQOmF=AiqfdpfOg@mail.gmail.com> + <20180607222028.zbva4vrv64dzrmxy@petertodd.org> +From: Bram Cohen <bram@chia.net> +Date: Fri, 8 Jun 2018 20:29:30 -0700 +Message-ID: <CAHUJnBCj8wnjP1=jobfpg7jkfjkX9iSBLeeAOyQCpobh6-AhUA@mail.gmail.com> +To: Peter Todd <pete@petertodd.org> +Content-Type: multipart/alternative; boundary="000000000000e85efc056e2d1f66" +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 +X-Mailman-Approved-At: Sat, 09 Jun 2018 03:30:45 +0000 +Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +Subject: Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion + proofs without a soft fork +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: Sat, 09 Jun 2018 03:29:33 -0000 + +--000000000000e85efc056e2d1f66 +Content-Type: text/plain; charset="UTF-8" + +So are you saying that if fully validating nodes wish to prune they can +maintain the ability to validate old transactions by cacheing the number of +transactions in each previous block? + +On Thu, Jun 7, 2018 at 3:20 PM, Peter Todd <pete@petertodd.org> wrote: + +> On Thu, Jun 07, 2018 at 02:15:35PM -0700, Bram Cohen wrote: +> > Are you proposing a soft fork to include the number of transactions in a +> > block in the block headers to compensate for the broken Merkle format? +> That +> > sounds like a good idea. +> > +> > On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev < +> > bitcoin-dev@lists.linuxfoundation.org> wrote: +> > +> > > It's well known that the Bitcoin merkle tree algorithm fails to +> distinguish +> > > between inner nodes and 64 byte transactions, as both txs and inner +> nodes +> > > are +> > > hashed the same way. This potentially poses a problem for tx inclusion +> > > proofs, +> > > as a miner could (with ~60 bits of brute forcing) create a transaction +> that +> > > committed to a transaction that was not in fact in the blockchain. +> > > +> > > Since odd-numbered inner/leaf nodes are concatenated with themselves +> and +> > > hashed +> > > twice, the depth of all leaves (txs) in the tree is fixed. +> > > +> > > It occured to me that if the depth of the merkle tree is known, this +> > > vulnerability can be trivially avoided by simply comparing the length +> of +> > > the +> > > merkle path to that known depth. For pruned nodes, if the depth is +> saved +> > > prior +> > > to pruning the block contents itself, this would allow for completely +> safe +> > > verification of tx inclusion proofs, without a soft-fork; storing this +> ^^^^^^^^^^^^^^^^^^^ +> +> Re-read my post: I specifically said you do not need a soft-fork to +> implement +> this. In fact, I think you can argue that this is an accidental feature, +> not a +> bug, as it further encourages the use of safe full verifiaction rather than +> unsafe lite clients. +> +> -- +> https://petertodd.org 'peter'[:-1]@petertodd.org +> + +--000000000000e85efc056e2d1f66 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr">So are you saying that if fully validating nodes wish to p= +rune they can maintain the ability to validate old transactions by cacheing= + the number of transactions in each previous block?</div><div class=3D"gmai= +l_extra"><br><div class=3D"gmail_quote">On Thu, Jun 7, 2018 at 3:20 PM, Pet= +er Todd <span dir=3D"ltr"><<a href=3D"mailto:pete@petertodd.org" target= +=3D"_blank">pete@petertodd.org</a>></span> wrote:<br><blockquote class= +=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd= +ing-left:1ex"><span class=3D"">On Thu, Jun 07, 2018 at 02:15:35PM -0700, Br= +am Cohen wrote:<br> +> Are you proposing a soft fork to include the number of transactions in= + a<br> +> block in the block headers to compensate for the broken Merkle format?= + That<br> +> sounds like a good idea.<br> +> <br> +> On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev <<br> +> <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@l= +ists.<wbr>linuxfoundation.org</a>> wrote:<br> +> <br> +> > It's well known that the Bitcoin merkle tree algorithm fails = +to distinguish<br> +> > between inner nodes and 64 byte transactions, as both txs and inn= +er nodes<br> +> > are<br> +> > hashed the same way. This potentially poses a problem for tx incl= +usion<br> +> > proofs,<br> +> > as a miner could (with ~60 bits of brute forcing) create a transa= +ction that<br> +> > committed to a transaction that was not in fact in the blockchain= +.<br> +> ><br> +> > Since odd-numbered inner/leaf nodes are concatenated with themsel= +ves and<br> +> > hashed<br> +> > twice, the depth of all leaves (txs) in the tree is fixed.<br> +> ><br> +> > It occured to me that if the depth of the merkle tree is known, t= +his<br> +> > vulnerability can be trivially avoided by simply comparing the le= +ngth of<br> +> > the<br> +> > merkle path to that known depth. For pruned nodes, if the depth i= +s saved<br> +> > prior<br> +> > to pruning the block contents itself, this would allow for comple= +tely safe<br> +> > verification of tx inclusion proofs, without a soft-fork; storing= + this<br> +</span>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= +=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = +=C2=A0^^^^^^^^^^^^^^^^^^^<br> +<br> +Re-read my post: I specifically said you do not need a soft-fork to impleme= +nt<br> +this. In fact, I think you can argue that this is an accidental feature, no= +t a<br> +bug, as it further encourages the use of safe full verifiaction rather than= +<br> +unsafe lite clients.<br> +<div class=3D"HOEnZb"><div class=3D"h5"><br> +-- <br> +<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http= +s://petertodd.org</a> 'peter'[:-1]@<a href=3D"http://petertodd.org"= + rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br> +</div></div></blockquote></div><br></div> + +--000000000000e85efc056e2d1f66-- + |