1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
Return-Path: <user@petertodd.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 8E1D03EE
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <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)
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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--
|
