Date: Thu, 7 Jun 2018 13:13:11 -0400
From: Peter Todd <pete@petertodd.org>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <20180607171311.6qdjohfuuy3ufriv@petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="cwwghymfjg67cxcz"
Content-Disposition: inline
User-Agent: NeoMutt/20170113 (1.7.2)
Subject: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion
 proofs without a soft fork
Precedence: list


--cwwghymfjg67cxcz
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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 a=
re
hashed the same way. This potentially poses a problem for tx inclusion proo=
fs,
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 ha=
shed
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 pr=
ior
to pruning the block contents itself, this would allow for completely safe
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 to =
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 match
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 bil=
lion right now
pubk:      32 - fully brute-forcable if willing to lose BTC spent; all scri=
ptPubKeys 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 checking =
for
valid scriptSig/scriptPubKey combinations other than a zero-length scriptSi=
g;
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 transacti=
on.
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-curre=
ncies
for which this brute-force is much easier than it is on Bitcoin!

--=20
https://petertodd.org 'peter'[:-1]@petertodd.org

--cwwghymfjg67cxcz
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQEzBAEBCAAdFiEEFcyURjhyM68BBPYTJIFAPaXwkfsFAlsZZ6MACgkQJIFAPaXw
kftJAwgAh+pXU/jrq2dMOtiaUBCDldKgTaLErKb0ly3KVgXewS9x/SK/Dqn8XzTI
yG35IAPzW+m+J5N6PZDzoEqR5C7kU4kp35aq2owpxedCHWRyIZDX6Z3nGhnKZgf9
z0uSp/kNw2b1XVliM2rnJkkN6yDIo/+wGnHWq3czykh5wG0bmsjHG0m0dz3OK//O
BwPqlYtY7EFCR2IDikdtP41Jyii27Gh/DHuoSQoZyF1JdJXypyE0FwBjKS5HsxhJ
fQ8hKspr86qel8b8+8QiuntlS1A712cheELgXXS9Arul/fDlPkNX31nsZidRCZwe
FnQVwLRKrr2DAB1ImpqFi4yNM653SA==
=EEOR
-----END PGP SIGNATURE-----

--cwwghymfjg67cxcz--