MIME-Version: 1.0
In-Reply-To: <20180607171311.6qdjohfuuy3ufriv@petertodd.org>
References: <20180607171311.6qdjohfuuy3ufriv@petertodd.org>
From: Bram Cohen <bram@chia.net>
Date: Thu, 7 Jun 2018 14:15:35 -0700
Message-ID: <CAHUJnBB7UL3mH6SixP_M4yooMVP3DgZa+5hiQOmF=AiqfdpfOg@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000d62a6c056e13c852"
Subject: Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion
 proofs without a soft fork
Precedence: list

--000000000000d62a6c056e13c852
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 distingui=
sh
> 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 th=
at
> 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 saf=
e
> verification of tx inclusion proofs, without a soft-fork; storing this
> data in
> the block header database would be a simple thing to do.
>
> Lite client verification without a trusted source of known-valid headers =
is
> dangerous anyway, so this protection makes for a fairly simple addition t=
o
> any
> lite client protocol.
>
>
> # Brute Force Cost Assuming a Valid Tx
>
> Consider the following 64 byte transaction:
>
>     tx =3D CTransaction([CTxIn(COutPoint(b'\xaa'*32,0xbbbbbbbb),
> nSequence=3D0xcccccccc)],[CTxOut(2**44-1,CScript([b'\
> xdd\xdd\xdd']))],nLockTime=3D2**31-1)
>
> If we serialize it, the last 32 bytes are:
>
>     aaaaaaaaaa bbbbbbbb 00 cccccccc 01 ffffffffff0f0000 04 03dddddd
> ffffff7f
>     =E2=86=B3prevhash=E2=86=B2 =E2=86=B3 n    =E2=86=B2    =E2=86=B3 seq =
 =E2=86=B2    =E2=86=B3 nValue       =E2=86=B2    =E2=86=B3 pubk =E2=86=B2 =
=E2=86=B3lockt
> =E2=86=B2
>                         =E2=86=B3 sig_len   =E2=86=B3num_txouts         =
=E2=86=B3scriptPubKey_len
>
> Of those fields, we have free choice of the following bits:
>
> prevhash:  40 - prev tx fully brute-forcable, as tx can be created to mat=
ch
> prev_n:    16 - can create a tx with up to about 2^16 outputs
> seq:       32 - fully brute-forcable in nVersion=3D1 txs
> nValue:    44 - assuming attacker has access to 175,921 BTC, worth ~1.3
> billion right now
> pubk:      32 - fully brute-forcable if willing to lose BTC spent; all
> scriptPubKeys are valid
> nLockTime: 31 - valid time-based nLockTime
> Total: 195 bits free choice =E2=86=92 61 bits need to be brute-forced
>
> Additionally, this can be improved slightly by a few more bits by checkin=
g
> for
> valid scriptSig/scriptPubKey combinations other than a zero-length
> scriptSig;
> the attacker can also avoid creating an unspendable output this way, and
> recover their funds by spending it in the same block with a third
> transaction.
> An obvious implementation making use of this would be to check that the
> high
> bits of prevout.n are zero first, prior to doing more costly checks.
>
> Finally, if inflation is not controlled - and thus nValue can be set
> freely -
> note how the brute force is trivial. There may very well exist
> crypto-currencies
> for which this brute-force is much easier than it is on Bitcoin!
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

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

<div dir=3D"ltr">Are you proposing a soft fork to include the number of tra=
nsactions in a block in the block headers to compensate for the broken Merk=
le format? That sounds like a good idea.</div><div class=3D"gmail_extra"><b=
r><div class=3D"gmail_quote">On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd vi=
a bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.lin=
uxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.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:1ex">It&#39;s well known =
that the Bitcoin merkle tree algorithm fails to distinguish<br>
between inner nodes and 64 byte transactions, as both txs and inner nodes a=
re<br>
hashed the same way. This potentially poses a problem for tx inclusion proo=
fs,<br>
as a miner could (with ~60 bits of brute forcing) create a transaction 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 themselves and ha=
shed<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, this<br>
vulnerability can be trivially avoided by simply comparing the length of th=
e<br>
merkle path to that known depth. For pruned nodes, if the depth is saved pr=
ior<br>
to pruning the block contents itself, this would allow for completely safe<=
br>
verification of tx inclusion proofs, without a soft-fork; storing this data=
 in<br>
the block header database would be a simple thing to do.<br>
<br>
Lite client verification without a trusted source of known-valid headers is=
<br>
dangerous anyway, so this protection makes for a fairly simple addition to =
any<br>
lite client protocol.<br>
<br>
<br>
# Brute Force Cost Assuming a Valid Tx<br>
<br>
Consider the following 64 byte transaction:<br>
<br>
=C2=A0 =C2=A0 tx =3D CTransaction([CTxIn(COutPoint(<wbr>b&#39;\xaa&#39;*32,=
0xbbbbbbbb),<wbr>nSequence=3D0xcccccccc)],[<wbr>CTxOut(2**44-1,CScript([b&#=
39;\<wbr>xdd\xdd\xdd&#39;]))],nLockTime=3D2**<wbr>31-1)<br>
<br>
If we serialize it, the last 32 bytes are:<br>
<br>
=C2=A0 =C2=A0 aaaaaaaaaa bbbbbbbb 00 cccccccc 01 ffffffffff0f0000 04 03dddd=
dd ffffff7f<br>
=C2=A0 =C2=A0 =E2=86=B3prevhash=E2=86=B2 =E2=86=B3 n=C2=A0 =C2=A0 =E2=86=B2=
=C2=A0 =C2=A0 =E2=86=B3 seq=C2=A0 =E2=86=B2=C2=A0 =C2=A0 =E2=86=B3 nValue=
=C2=A0 =C2=A0 =C2=A0 =C2=A0=E2=86=B2=C2=A0 =C2=A0 =E2=86=B3 pubk =E2=86=B2 =
=E2=86=B3lockt =E2=86=B2<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =E2=86=B3 sig_len=C2=A0 =C2=A0=E2=86=B3num_txouts=C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0=E2=86=B3scriptPubKey_len<br>
<br>
Of those fields, we have free choice of the following bits:<br>
<br>
prevhash:=C2=A0 40 - prev tx fully brute-forcable, as tx can be created to =
match<br>
prev_n:=C2=A0 =C2=A0 16 - can create a tx with up to about 2^16 outputs<br>
seq:=C2=A0 =C2=A0 =C2=A0 =C2=A032 - fully brute-forcable in nVersion=3D1 tx=
s<br>
nValue:=C2=A0 =C2=A0 44 - assuming attacker has access to 175,921 BTC, wort=
h ~1.3 billion right now<br>
pubk:=C2=A0 =C2=A0 =C2=A0 32 - fully brute-forcable if willing to lose BTC =
spent; all scriptPubKeys are valid<br>
nLockTime: 31 - valid time-based nLockTime<br>
Total: 195 bits free choice =E2=86=92 61 bits need to be brute-forced<br>
<br>
Additionally, this can be improved slightly by a few more bits by checking =
for<br>
valid scriptSig/scriptPubKey combinations other than a zero-length scriptSi=
g;<br>
the attacker can also avoid creating an unspendable output this way, and<br=
>
recover their funds by spending it in the same block with a third transacti=
on.<br>
An obvious implementation making use of this would be to check that the hig=
h<br>
bits of prevout.n are zero first, prior to doing more costly checks.<br>
<br>
Finally, if inflation is not controlled - and thus nValue can be set freely=
 -<br>
note how the brute force is trivial. There may very well exist crypto-curre=
ncies<br>
for which this brute-force is much easier than it is on Bitcoin!<br>
<span class=3D"HOEnZb"><font color=3D"#888888"><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>
</font></span><br>______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br></blockquote></div><br></div>

--000000000000d62a6c056e13c852--