From: Peter Todd <pete@petertodd•org>
To: bitcoin-dev@lists•linuxfoundation.org
Subject: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork
Date: Thu, 7 Jun 2018 13:13:11 -0400 [thread overview]
Message-ID: <20180607171311.6qdjohfuuy3ufriv@petertodd.org> (raw)
[-- Attachment #1: Type: text/plain, Size: 3008 bytes --]
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 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 = CTransaction([CTxIn(COutPoint(b'\xaa'*32,0xbbbbbbbb),nSequence=0xcccccccc)],[CTxOut(2**44-1,CScript([b'\xdd\xdd\xdd']))],nLockTime=2**31-1)
If we serialize it, the last 32 bytes are:
aaaaaaaaaa bbbbbbbb 00 cccccccc 01 ffffffffff0f0000 04 03dddddd ffffff7f
↳prevhash↲ ↳ n ↲ ↳ seq ↲ ↳ nValue ↲ ↳ pubk ↲ ↳lockt ↲
↳ sig_len ↳num_txouts ↳scriptPubKey_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=1 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 → 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 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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
next reply other threads:[~2018-06-07 17:13 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-06-07 17:13 Peter Todd [this message]
2018-06-07 21:15 ` Bram Cohen
2018-06-07 22:20 ` Peter Todd
2018-06-09 3:29 ` Bram Cohen
2018-06-09 11:03 ` Sergio Demian Lerner
2018-06-09 12:21 ` Sergio Demian Lerner
2018-06-09 12:24 ` Sergio Demian Lerner
2018-06-09 12:45 ` Peter Todd
2018-06-09 12:51 ` Sergio Demian Lerner
2018-06-09 13:02 ` Peter Todd
2018-06-09 12:50 ` Peter Todd
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180607171311.6qdjohfuuy3ufriv@petertodd.org \
--to=pete@petertodd$(echo .)org \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox