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
|
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 8A9EF86D
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Jun 2018 22:20:36 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from outmail148095.authsmtp.com (outmail148095.authsmtp.com
[62.13.148.95])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D49C270D
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Jun 2018 22:20:35 +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 w57MKXEM021838;
Thu, 7 Jun 2018 23:20:33 +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 w57MKUhE030682
(version=TLSv1.2 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO);
Thu, 7 Jun 2018 23:20:31 +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 8F0A3400B0;
Thu, 7 Jun 2018 22:20:30 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id 6CCD922043; Thu, 7 Jun 2018 18:20:28 -0400 (EDT)
Date: Thu, 7 Jun 2018 18:20:28 -0400
From: Peter Todd <pete@petertodd.org>
To: Bram Cohen <bram@chia.net>
Message-ID: <20180607222028.zbva4vrv64dzrmxy@petertodd.org>
References: <20180607171311.6qdjohfuuy3ufriv@petertodd.org>
<CAHUJnBB7UL3mH6SixP_M4yooMVP3DgZa+5hiQOmF=AiqfdpfOg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="lvorui2qu73lvhyc"
Content-Disposition: inline
In-Reply-To: <CAHUJnBB7UL3mH6SixP_M4yooMVP3DgZa+5hiQOmF=AiqfdpfOg@mail.gmail.com>
User-Agent: NeoMutt/20170113 (1.7.2)
X-Server-Quench: fde045a1-6aa0-11e8-8791-0015176ca198
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZIVwkA IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aAdMdgUUEkAaAgsB Am4bWVdeUl17WmE7 bghPaBtcak9QXgdq
T0pMXVMcUwBvfGdk XmseURl0fwcIfnZ5 ZQg0CiVbWEErdFt7
Ex9UCGwHMG99YGcW UV1YdwJRcQRMLU5E Y1gxNiYHcQ5VPz4z
GA41ejw8IwAXFD5I WR0AIRoXTFwIGjN0 WwoPEH0jEFUZR209
KAZuMVcSEQ4NIg0z N1AlREkZNBlwQhVE GEZDG2dGJkUBQDc3
RQoSRkkQDHVTRj1f agAA
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
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [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 22:20:36 -0000
--lvorui2qu73lvhyc
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Thu, Jun 07, 2018 at 02:15:35PM -0700, Bram Cohen wrote:
> 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? Th=
at
> sounds like a good idea.
>=20
> On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> > It's well known that the Bitcoin merkle tree algorithm fails to disting=
uish
> > between inner nodes and 64 byte transactions, as both txs and inner nod=
es
> > 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 s=
afe
> > verification of tx inclusion proofs, without a soft-fork; storing this
^^^^^^^^^^^^^^^^^^^
Re-read my post: I specifically said you do not need a soft-fork to impleme=
nt
this. In fact, I think you can argue that this is an accidental feature, no=
t a
bug, as it further encourages the use of safe full verifiaction rather than
unsafe lite clients.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--lvorui2qu73lvhyc
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQEzBAEBCAAdFiEEFcyURjhyM68BBPYTJIFAPaXwkfsFAlsZr6oACgkQJIFAPaXw
kftYFwf8DuI6w/F2TNWTpB148T8D+76lYlk08wAWVaVZy4b1MCBtIOVbs7xRA+k4
RWQSML1Zhpo1Gi3JwBAeGFRHKQa/XWG7PRj76FgJlvNtaHVaFMszqbOTGsPXMtX3
f+iVubCxBHNBgCXaAkcuPi7IwVwELGCPP51aq5F1iTiayQPUPnnIFgc1X82jG/Y+
6t/fEWqO/ZbDk7apzx4zZYD+YndWA1VnjDVbtaL5AmqTfgE6MrVIlmfaDWWoRJlW
HWJEGY2iHC1+EXn657hpjEQ7zUF70B+U/Dz5whVsEaAOU2Hwvqwo63jL0yu7clbk
m9C4aS3Cfmfha9AhvvTGsZkbncAyYQ==
=sog5
-----END PGP SIGNATURE-----
--lvorui2qu73lvhyc--
|
