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
|
Return-Path: <pete@petertodd.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 9EA399BA
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:15:11 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail149058.authsmtp.co.uk (outmail149058.authsmtp.co.uk
[62.13.149.58])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id BCF441C9
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:15:10 +0000 (UTC)
Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232])
by punt20.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1N1F9Y8035469
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:15:09 GMT
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.14.2/8.14.2/) with ESMTP id v1N1F7NQ037890
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO)
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:15:08 GMT
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 4964140123
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:15:07 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id 81ED820245; Wed, 22 Feb 2017 20:15:06 -0500 (EST)
Date: Wed, 22 Feb 2017 20:15:06 -0500
From: Peter Todd <pete@petertodd.org>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <20170223011506.GC905@savin.petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="rQ2U398070+RC21q"
Content-Disposition: inline
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: 84365579-f965-11e6-829f-00151795d556
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd
P1hyKltILEZaQVBf Ri5dBBEKBAw1ADwr dVUTOktfYVU4Cld1
UkhIRUJSFQ9pBBYB DlAbUAd3aQROfWBx Z0Z9XHVEXQo8dDh8
NEkqdG0FYm9paC4c U0lYOQtQcwVPexhM dwZ2UnYQYGRSYGdo
RV49emhpZGgGd3UI TlxQc0Q7CWwGAiIx XVgnOA9nMUALRiMy Mx0hLDYB
X-Authentic-SMTP: 61633532353630.1037: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] A Better MMR Definition
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, 23 Feb 2017 01:15:11 -0000
--rQ2U398070+RC21q
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
Reposting something that came up recently in a private discussion with some
academics:
Concretely, let's define a prunable MMR with the following grammar. This
definition is an improvement on whats in the python-proofmarshal by committ=
ing
to the number of items in the tree implicitly; an obvious max-log2(n)-sized
proof-of-tree-size can be obtained by following the right-most nodes:
Maybe(T) :=3D UNPRUNED <T> | PRUNED <Commitment(T)>
FullNode(0) :=3D <Value>
FullNode(n) :=3D <Maybe(FullNode(n-1)> <Maybe(FullNode(n-1))>
PartialNode(0) :=3D SOME <FullNode(0)> | NONE
PartialNode(n) :=3D <Maybe(FullNode(n-1))> <Maybe(PartialNode(n-1))>
MMR :=3D FULL <N> <FullNode(n)> | PARTIAL <N> <PartialNode(n)>
Basically we define it in four parts. First we define Maybe(T) to represent
pruned and unpruned (hash only) data. Secondly we define full nodes within =
2^n
sized trees. Third we define partial nodes. And finally we define the MMR
itself as being either a full or partial node.
First of all, with pruning we can define a rule that if any operation (other
than checking commitment hashes) attempts to access pruned data, it should
immediately fail. In particular, no operation should be able to determine if
data is or isn't pruned. Equally, note how an implementation can keep track=
of
what data was accessed during any given operation, and prune the rest, which
means a proof is just the parts of the data structure accessed during one or
more operations.
With that, notice how proving the soundness of the proofs becomes trivial: =
if
validation is deterministic, it is obviously impossible to construct two
different proofs that prove contradictory statements, because a proof is si=
mply
part of the data structure itself. Contradiction would imply that the two
proofs are different, but that's easily rejected by simply checking the has=
h of
the data.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--rQ2U398070+RC21q
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJYrjeWAAoJECSBQD2l8JH7yJkH/2TvMGw/B6pEhka8mKmZyYUk
z6DNnnss+Bc9Cy0Euxm5T+sWLlP/h+G4mdGsq0l1yn2MKEceVvOJIoirl/qrcbZ0
c5xRnPd/L6BUFmy+1gTo+HfW2i3l4X1RaU+v8m7t8clwSvqb1DSbumPr3H/AqZoh
xUNFpLQCyLPCH5fEfgpGGRFy8qVm6jSHR9R5dGrqdLwk7Hc1Ip6m55a+8J6EMlHp
AtB9MZF2nMM0gpcjPdfA8UiNDyTWHVcw2wUqUtQ1Tbj4NP4DgR3ZvFxRYudV+1HJ
A1SATEb9DleYPjHuyL127hXyuilk3+1IukOeYcOrMhiGf/aerDTan3VXPQ1VD1I=
=sb/5
-----END PGP SIGNATURE-----
--rQ2U398070+RC21q--
|
