From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 8E1D03EE for ; Thu, 7 Jun 2018 17:13:18 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from outmail148107.authsmtp.com (outmail148107.authsmtp.com [62.13.148.107]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D1D575D3 for ; Thu, 7 Jun 2018 17:13:17 +0000 (UTC) Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247]) by punt21.authsmtp.com. (8.15.2/8.15.2) with ESMTP id w57HDFQN026171 for ; Thu, 7 Jun 2018 18:13:15 +0100 (BST) (envelope-from user@petertodd.org) Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com [52.5.185.120]) (authenticated bits=0) by mail.authsmtp.com (8.15.2/8.15.2) with ESMTPSA id w57HDDLF071270 (version=TLSv1.2 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO) for ; Thu, 7 Jun 2018 18:13:14 +0100 (BST) (envelope-from user@petertodd.org) Received: from [127.0.0.1] (localhost [127.0.0.1]) by petertodd.org (Postfix) with ESMTPSA id 32DBE400BF for ; Thu, 7 Jun 2018 17:13:13 +0000 (UTC) Received: by localhost (Postfix, from userid 1000) id 1E07522043; Thu, 7 Jun 2018 13:13:11 -0400 (EDT) Date: Thu, 7 Jun 2018 13:13:11 -0400 From: Peter Todd 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) X-Server-Quench: 107cf801-6a76-11e8-8791-0015176ca198 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZIVwkA IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd P1hyKltILEZaQVBf Ri5dBBEKBAw1ADwr dVUTOktdZVU0Glt1 UkhISkJTHA9pAhYA A1AbUAd3aQROfWBx Z0Z9XHVEXQo9cEEF NjooY20BZGVnaC4b VUdROQJUd1Acdh9E d1YuU3UQYGRSbmdo QF5qemhpZGgGd3pe S1hcfUQuW1sQAjMw DxUPBzYrEAUZXSg+ ZxArMkIcVEgWKA0p OFUsEU4Iex4UAQlD BEBKBmdBPV4GSTFj EgJGXUkDDHVUI29H BRM0ahFPGD86 X-Authentic-SMTP: 61633532353630.1038:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 52.5.185.120/25 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 07 Jun 2018 17:13:18 -0000 --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--