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
172
173
174
|
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 4E31B957
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 07:41:44 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail149084.authsmtp.net (outmail149084.authsmtp.net
[62.13.149.84])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id E7194F4
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 07:41:42 +0000 (UTC)
Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247])
by punt22.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1N7feoZ000873;
Thu, 23 Feb 2017 07:41:40 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 v1N7fcPZ054166
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
Thu, 23 Feb 2017 07:41:39 GMT
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 6F0C240576;
Thu, 23 Feb 2017 07:41:38 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id B298D20245; Thu, 23 Feb 2017 02:41:37 -0500 (EST)
Date: Thu, 23 Feb 2017 02:41:37 -0500
From: Peter Todd <pete@petertodd.org>
To: Bram Cohen <bram@bittorrent.com>
Message-ID: <20170223074137.GA3395@savin.petertodd.org>
References: <20170223011506.GC905@savin.petertodd.org>
<CA+KqGkqXmWgyU+4ZaR9w7e3xVBUyWwAixVAEzT9hT8V_1kwnuw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="4Ckj6UjgE2iN1+kY"
Content-Disposition: inline
In-Reply-To: <CA+KqGkqXmWgyU+4ZaR9w7e3xVBUyWwAixVAEzT9hT8V_1kwnuw@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: 836c82fa-f99b-11e6-bcdf-0015176ca198
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aAdMdAEUHlAWAgsB AmEbW1NeVFx7XWM7 bghPaBtcak9QXgdq
T0pMXVMcUgQWBkpS ZnQeVx1zcQMIeX5z bEAsVnNdD0x4Ixdg
FEddR3AHZDJmdTJM BBZFdwNVdQJNeEwU a1l3GhFYa3VsNCMk
FAgyOXU9MCtqYA0d aAwRMV8ICWMuJHYQ Sh4DGzQzHEoDLwAA
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] 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 07:41:44 -0000
--4Ckj6UjgE2iN1+kY
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Wed, Feb 22, 2017 at 07:07:08PM -0800, Bram Cohen wrote:
> On Wed, Feb 22, 2017 at 5:15 PM, Peter Todd via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> >
> > With that, notice how proving the soundness of the proofs becomes trivi=
al:
> > if
> > validation is deterministic, it is obviously impossible to construct two
> > different proofs that prove contradictory statements, because a proof is
> > simply
> > part of the data structure itself. Contradiction would imply that the t=
wo
> > proofs are different, but that's easily rejected by simply checking the
> > hash of
> > the data.
> >
>=20
> My code works this way. Proofs are serialization of a subset of the tree,
> and to validate a proof you ask a single function whether a particular
> value is included in that tree subset, and it answers yes or no, so
> obviously it's impossible for a single value to both validate and not
> validate. The proof code was quite terrifying before I made this change
> (which I did on your suggestion), and it's much cleaner and simpler now. =
It
> also in principle supports compact proofs of multiple inclusions and
> exclusions in the same serialization of a subset of the tree because the
> upper branches won't have to be repeated. I haven't written code for
> generating those, but the validation code will happily accept them.
That's an improvement, but I think we can do even better if we think of mis=
sing
pruned data as analogous to virtual memory: pruned data is the same as a pa=
ge
that has been swapped to disk, with the magical property that hashing allow=
s us
to swap it back in from an untrusted source.
Thus a proof should actually be whatever data we expect our counterparty to
have flushed, ranging from none at all, to 100% (modulo a root hash). An
implementation should then do operations as normal, using parts of the proo=
f on
an as-needed basis where pruned data is encountered.
Thus if you have a key-value map and do a get() operation, you'd expect the
proof to *not* be what the get operates on, but rather be a *context* argum=
ent
to the get() operation. The other way around is actually an example of doing
computations on untrusted data, and bad API design!
> I'm not sure what you mean by MMRs though. Are you talking about MMRs whe=
re
> each mountain is a set of diffs to the old things and are periodically
> consolidated? Or do later mountains refer to internals of earlier ones? Or
> do they have 'maybe' values which mean that the earlier mountain should be
> referred to? Are these patricia tries or something flatter and more fixed
> depth?
I'm talking about these MMR's: https://github.com/proofchains/python-proofm=
arshal/blob/master/proofmarshal/mmr.py
Notably I'm talking about an insertion ordered list, indexed by position, t=
hat
supports append and update operations, but *not* insertions; this is differ=
ent
than what you've recently published re: UTXO commitments. That's a full
key-value map, something MMR's are delibrately are not doing.
Draw out a MMR based on the formal definition you're replying too and you'll
see the new structure.
> My code doesn't keep track of tree size, by the way. It would be trivial =
to
> add that functionality to the library, and including it in the hashing
> creates complexity and doesn't seem to have any benefit over sending that
> data in a side channel.
Like I say above, you're solving a different problem than MMR's solve.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--4Ckj6UjgE2iN1+kY
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJYrpIsAAoJECSBQD2l8JH7rQ8IAIJmliLfyft94QZH4qr04L3i
IGQZAlJ545ZXXIaojIpPqUxEDA3+BzYcbtM83ToEdlAeBi1fy4X+mERzDkTV7sXm
741iX2g0a/IDxADYCxhubUAeHqmxrJuxZ3JbvoNruAOeCGhIpWXI4OwLbJCa03Kg
zaOEdIZzIkoq5tY1agyd5Fp+CbmrYOC2DUaDL0Y1HukxhmyiVztL663tSGyVVb8W
S2XjO8hDJPdo0VEZNPVJYpYVfhKsg2TAoo9UNm0b+OObQsEd9gwMslfxxa/ZkByi
2PYIrADOu0pJtO0q4N3stt+4qZeOFwS7a3Z3cp9NO4oiggrOUev8XRjmP7w727A=
=fW3l
-----END PGP SIGNATURE-----
--4Ckj6UjgE2iN1+kY--
|
