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>
In-Reply-To: <CAHUJnBCj8wnjP1=jobfpg7jkfjkX9iSBLeeAOyQCpobh6-AhUA@mail.gmail.com>
From: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
Date: Sat, 9 Jun 2018 13:03:53 +0200
Message-ID: <CAKzdR-paqYgOxToikaVD=0GMsCjHBaynX3WgB-CN6Sn7B7kRXw@mail.gmail.com>
To: bram@chia.net, bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000000d757e056e337b00"
Subject: Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion
 proofs without a soft fork
Precedence: list

--0000000000000d757e056e337b00
Content-Type: text/plain; charset="UTF-8"

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
>

--0000000000000d757e056e337b00
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi Peter,<div>We reported this as CVE-2017-12842, although=
 it may have been known by developers before us.=C2=A0</div><div>There are=
=C2=A0hundreds of SPV wallets out there, without even considering other mor=
e sensitive systems relying on SPV proofs.=C2=A0</div><div>As I said we, at=
 RSK, discovered this problem in 2017. For RSK it&#39;s very important this=
 is fixed because our SPV bridge uses SPV proofs.</div><div>I urge all peop=
le 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.</div><=
div><br></div><div>My suggestion is to use in the version bits 4 bits indic=
ating 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 &lt;<a href=
=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfo=
undation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div di=
r=3D"ltr">So are you saying that if fully validating nodes wish to prune th=
ey can maintain the ability to validate old transactions by cacheing the nu=
mber of transactions in each previous block?</div><div class=3D"gmail_extra=
"><br><div class=3D"gmail_quote">On Thu, Jun 7, 2018 at 3:20 PM, Peter Todd=
 <span dir=3D"ltr">&lt;<a href=3D"mailto:pete@petertodd.org" target=3D"_bla=
nk">pete@petertodd.org</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_=
quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1=
ex"><span>On Thu, Jun 07, 2018 at 02:15:35PM -0700, Bram Cohen wrote:<br>
&gt; Are you proposing a soft fork to include the number of transactions in=
 a<br>
&gt; block in the block headers to compensate for the broken Merkle format?=
 That<br>
&gt; sounds like a good idea.<br>
&gt; <br>
&gt; On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev &lt;<br>
&gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bl=
ank">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br>
&gt; <br>
&gt; &gt; It&#39;s well known that the Bitcoin merkle tree algorithm fails =
to distinguish<br>
&gt; &gt; between inner nodes and 64 byte transactions, as both txs and inn=
er nodes<br>
&gt; &gt; are<br>
&gt; &gt; hashed the same way. This potentially poses a problem for tx incl=
usion<br>
&gt; &gt; proofs,<br>
&gt; &gt; as a miner could (with ~60 bits of brute forcing) create a transa=
ction that<br>
&gt; &gt; committed to a transaction that was not in fact in the blockchain=
.<br>
&gt; &gt;<br>
&gt; &gt; Since odd-numbered inner/leaf nodes are concatenated with themsel=
ves and<br>
&gt; &gt; hashed<br>
&gt; &gt; twice, the depth of all leaves (txs) in the tree is fixed.<br>
&gt; &gt;<br>
&gt; &gt; It occured to me that if the depth of the merkle tree is known, t=
his<br>
&gt; &gt; vulnerability can be trivially avoided by simply comparing the le=
ngth of<br>
&gt; &gt; the<br>
&gt; &gt; merkle path to that known depth. For pruned nodes, if the depth i=
s saved<br>
&gt; &gt; prior<br>
&gt; &gt; to pruning the block contents itself, this would allow for comple=
tely safe<br>
&gt; &gt; 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_-1263791027191071155HOEnZb"><div class=3D"m_-12637910271910=
71155h5"><br>
-- <br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> &#39;peter&#39;[:-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>

--0000000000000d757e056e337b00--