diff options
| author | Sergio Demian Lerner <sergio.d.lerner@gmail.com> | 2018-06-09 14:21:17 +0200 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2018-06-09 12:21:57 +0000 |
| commit | ed8a5a7d47d198026a56146de269a3db51e911ad (patch) | |
| tree | 207636d0ddaabf89be378de5955c3475dd9da039 | |
| parent | b074376545a12ec0870186ea1371a6644cf5b12b (diff) | |
| download | pi-bitcoindev-ed8a5a7d47d198026a56146de269a3db51e911ad.tar.gz pi-bitcoindev-ed8a5a7d47d198026a56146de269a3db51e911ad.zip | |
Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork
| -rw-r--r-- | 0e/2aa9341812747d42da34ee74fc2f2a4a4f362b | 294 |
1 files changed, 294 insertions, 0 deletions
diff --git a/0e/2aa9341812747d42da34ee74fc2f2a4a4f362b b/0e/2aa9341812747d42da34ee74fc2f2a4a4f362b new file mode 100644 index 000000000..2afdc896f --- /dev/null +++ b/0e/2aa9341812747d42da34ee74fc2f2a4a4f362b @@ -0,0 +1,294 @@ +Return-Path: <sergio.d.lerner@gmail.com> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 5C1291619 + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 9 Jun 2018 12:21:57 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.7.6 +Received: from mail-lf0-f52.google.com (mail-lf0-f52.google.com + [209.85.215.52]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4A9A7708 + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 9 Jun 2018 12:21:56 +0000 (UTC) +Received: by mail-lf0-f52.google.com with SMTP id d24-v6so23922823lfa.8 + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 09 Jun 2018 05:21:56 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; + h=mime-version:references:in-reply-to:from:date:message-id:subject:to + :cc; bh=KjUC/7GLxfyMOeYLkpS0qVIE5XFECvKF7X+dUdBEnLw=; + b=ZDx9JV0qAXkoDzii+K3rmtQjKef82Orr+pgUF8bPJx0eDy6GP738lpvbQG/We5oag2 + GqAGDOcoGW6YJAx2xE5IWxRE9BtrVsZzIbhAQjOt8GrKFDYO6nE568/kvBhmeRcfB5Nd + UlzuZws1vZ1SQzQ2lT/Q6nO3zAGkyyVJm2t8z/FFs7LROL7BygATzdnhyhKgY11DYKP3 + B0GuwEGAUdOyJGn+YD7BtED5ChHOKoM4qA2GX48CPraH13olWz9v4tN/Wv7P9/ixQ2T1 + hU0rgrYIn/LYER8g7LUSo4LgByNNJgxpQXwMk8az3uToS0S+5aJo0TLgaaF//HtWHH+M + EUGQ== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20161025; + h=x-gm-message-state:mime-version:references:in-reply-to:from:date + :message-id:subject:to:cc; + bh=KjUC/7GLxfyMOeYLkpS0qVIE5XFECvKF7X+dUdBEnLw=; + b=Yy/UaaQWzDCx16Qxbb7OUeKOkIhoOOWKWK+bLW2O2b4C5RwZfo/y0Fp3KzhzCXGh/y + MAr0mZkfR/EaOgoibXqaa2yzo+k4HNW3HO/pHuLQB+2WN5v0QlsIDfz4urQujSzwO+UJ + DVS17eNO4+3CkwZQL+H5Hmnl9Ph+OIJOcgIIrqxeMy1tsjyzq70XQozET94svgp0fko5 + ewENSoXCoOf+cyhL3jdDM81gSra6HsV+UBUi1hgNV7pCTyMPm7jtjukyqUSAzbFfM+XZ + 62HXzXtCG5cIZ4W+J2BKKfOczAtBZa2qjKVfG+Depfl3wLDVDgU3EJ3g8yMLDsxsSydM + rgqg== +X-Gm-Message-State: APt69E21peB7xU8MPQDIpqsIGZF4Ht4miLh89XT7ofcH/T6+0alErSrP + MiDPtvoIbEmrfl5y/xLrpbYcXvwcxpemxYlpmY0= +X-Google-Smtp-Source: ADUXVKIce1ttO/X2mFsctQiHaDZoGytbDnea79ff9A+7+16RQap5lpxXe7axI6gNvOLdOcizkDyWrwtMYjIssem9kTs= +X-Received: by 2002:a2e:6a07:: with SMTP id + f7-v6mr6842875ljc.109.1528546914690; + Sat, 09 Jun 2018 05:21:54 -0700 (PDT) +MIME-Version: 1.0 +References: <20180607171311.6qdjohfuuy3ufriv@petertodd.org> + <CAHUJnBB7UL3mH6SixP_M4yooMVP3DgZa+5hiQOmF=AiqfdpfOg@mail.gmail.com> + <20180607222028.zbva4vrv64dzrmxy@petertodd.org> + <CAHUJnBCj8wnjP1=jobfpg7jkfjkX9iSBLeeAOyQCpobh6-AhUA@mail.gmail.com> + <CAKzdR-paqYgOxToikaVD=0GMsCjHBaynX3WgB-CN6Sn7B7kRXw@mail.gmail.com> +In-Reply-To: <CAKzdR-paqYgOxToikaVD=0GMsCjHBaynX3WgB-CN6Sn7B7kRXw@mail.gmail.com> +From: Sergio Demian Lerner <sergio.d.lerner@gmail.com> +Date: Sat, 9 Jun 2018 14:21:17 +0200 +Message-ID: <CAKzdR-rz2-D5pbcoSw0CK9tR-UY46ybYaZDmUMYTjBgvkL6ugg@mail.gmail.com> +To: bram@chia.net, bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> +Content-Type: multipart/alternative; boundary="000000000000df6c04056e348f08" +X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, + DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,LOTS_OF_MONEY, + 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 14:58:55 +0000 +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 12:21:57 -0000 + +--000000000000df6c04056e348f08 +Content-Type: text/plain; charset="UTF-8" + +Also it must be noted that an attacker having only 1.3M USD that can +brute-force 72 bits (4 days of hashing on capable ASICs) can perform the +same attack, so the attack is entirely feasible and no person should accept +more than 1M USD using a SPV wallet. + +Also the attack can be repeated: once you create the "extension point" +block, you can attack more and more parties without any additional +computation. + + +On Sat, Jun 9, 2018 at 1:03 PM Sergio Demian Lerner < +sergio.d.lerner@gmail.com> wrote: + +> Hi Peter, +> We reported this as CVE-2017-12842, although it may have been known by +> developers before us. +> There are hundreds of SPV wallets out there, without even considering +> other more sensitive systems relying on SPV proofs. +> As I said we, at RSK, discovered this problem in 2017. For RSK it's very +> important this is fixed because our SPV bridge uses SPV proofs. +> I urge all people participating in this mailing list and the rest of the +> Bitcoin community to work on this issue for the security and clean-design +> of Bitcoin. +> +> My suggestion is to use in the version bits 4 bits indicating the tree +> depth (-1), as a soft-fork, so +> 00=1 depth, +> 0F = 16 depth (maximum 64K transactions). Very clean. +> +> The other option is to ban transaction with size lower or equal to 64. +> +> Best regards, +> Sergio. +> +> On Sat, Jun 9, 2018 at 5:31 AM Bram Cohen via bitcoin-dev < +> bitcoin-dev@lists.linuxfoundation.org> wrote: +> +>> 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 +>>> +>> +>> _______________________________________________ +>> bitcoin-dev mailing list +>> bitcoin-dev@lists.linuxfoundation.org +>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev +>> +> + +--000000000000df6c04056e348f08 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr">Also it must be noted that an attacker having only 1.3M US= +D that can brute-force 72 bits (4 days of hashing on capable ASICs) can per= +form the same attack, so the attack is entirely feasible and no person shou= +ld accept more than 1M USD using a SPV wallet.<div><br></div><div>Also the = +attack can be repeated: once you create the "extension point" blo= +ck, you can attack more and more parties without any additional computation= +.</div><div><br></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr"= +>On Sat, Jun 9, 2018 at 1:03 PM Sergio Demian Lerner <<a href=3D"mailto:= +sergio.d.lerner@gmail.com">sergio.d.lerner@gmail.com</a>> wrote:<br></di= +v><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:= +1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">Hi Peter,<div>We reported= + this as CVE-2017-12842, although it may have been known by developers befo= +re us.=C2=A0</div><div>There are=C2=A0hundreds of SPV wallets out there, wi= +thout even considering other more sensitive systems relying on SPV proofs.= +=C2=A0</div><div>As I said we, at RSK, discovered this problem in 2017. For= + RSK it's very important this is fixed because our SPV bridge uses SPV = +proofs.</div><div>I urge all people participating in this mailing list and = +the rest of the Bitcoin community to work on this issue for the security an= +d clean-design of Bitcoin.</div><div><br></div><div>My suggestion is to use= + in the version bits 4 bits indicating the tree depth (-1), as a soft-fork,= + so=C2=A0</div><div>00=3D1 depth,=C2=A0</div><div>0F =3D 16 depth (maximum = +64K transactions).=20 + +<span style=3D"background-color:rgb(255,255,255);text-decoration-style:init= +ial;text-decoration-color:initial;float:none;display:inline">Very clean.</s= +pan></div><div>=C2=A0</div><div>The other option is to ban transaction with= + size lower or equal to 64.=C2=A0</div><div><br></div><div>Best regards,</d= +iv><div>=C2=A0Sergio.</div></div><br><div class=3D"gmail_quote"><div dir=3D= +"ltr">On Sat, Jun 9, 2018 at 5:31 AM Bram Cohen via bitcoin-dev <<a href= +=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin= +-dev@lists.linuxfoundation.org</a>> wrote:<br></div><blockquote class=3D= +"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding= +-left:1ex"><div dir=3D"ltr">So are you saying that if fully validating node= +s wish to prune they can maintain the ability to validate old transactions = +by cacheing the number of transactions in each previous block?</div><div cl= +ass=3D"gmail_extra"><br><div class=3D"gmail_quote">On Thu, Jun 7, 2018 at 3= +:20 PM, Peter Todd <span dir=3D"ltr"><<a href=3D"mailto:pete@petertodd.o= +rg" target=3D"_blank">pete@petertodd.org</a>></span> wrote:<br><blockquo= +te class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc so= +lid;padding-left:1ex"><span>On Thu, Jun 07, 2018 at 02:15:35PM -0700, Bram = +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" target=3D"_bl= +ank">bitcoin-dev@lists.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"m_-7137015386548983706m_-1263791027191071155HOEnZb"><div clas= +s=3D"m_-7137015386548983706m_-1263791027191071155h5"><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> +_______________________________________________<br> +bitcoin-dev mailing list<br> +<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">= +bitcoin-dev@lists.linuxfoundation.org</a><br> +<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = +rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail= +man/listinfo/bitcoin-dev</a><br> +</blockquote></div> +</blockquote></div> + +--000000000000df6c04056e348f08-- + |