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
|
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 0663EC1D
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 23:51:12 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail148161.authsmtp.com (outmail148161.authsmtp.com
[62.13.148.161])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id E4ACD176
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 23:51:10 +0000 (UTC)
Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232])
by punt24.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1NNp8fC082001;
Thu, 23 Feb 2017 23:51:08 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 v1NNp711075267
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
Thu, 23 Feb 2017 23:51:08 GMT
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 8AFDB40576;
Thu, 23 Feb 2017 23:51:06 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id C6057204AB; Thu, 23 Feb 2017 18:51:05 -0500 (EST)
Date: Thu, 23 Feb 2017 18:51:05 -0500
From: Peter Todd <pete@petertodd.org>
To: Bram Cohen <bram@bittorrent.com>
Message-ID: <20170223235105.GA28497@savin.petertodd.org>
References: <20170223011506.GC905@savin.petertodd.org>
<CAAcC9ys5sUxVfOjogFiF3gzk51D_L=QQkOYevTH=qbh_RkA3Hw@mail.gmail.com>
<CA+KqGkrUneGe4yORi=JAAWzoO0UftMUuJm3S-__W5sBh-+T1vQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="Dxnq1zWXvFF0Q93v"
Content-Disposition: inline
In-Reply-To: <CA+KqGkrUneGe4yORi=JAAWzoO0UftMUuJm3S-__W5sBh-+T1vQ@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: f267c0ba-fa22-11e6-829f-00151795d556
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aQdMdAEUHlAWAgsB AmEbWVdeVVx7WWs7 bghPaBtcak9QXgdq
T0pMXVMcUgQWf1wG Bx8eVRxwcQIIeXpx YUMsCHJdWxd6Jxdg
FB9WF3AHZDJmdWgd WRZFdwNVdQJNdxoR b1V5GhFYa3VsNCMk
FAgyOXU9MCtqYA0d aAwRMV8ICWMuJHYQ Sh4DGzQzHEoDLwAA
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
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 23:51:12 -0000
--Dxnq1zWXvFF0Q93v
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Thu, Feb 23, 2017 at 03:13:43PM -0800, Bram Cohen wrote:
> On Thu, Feb 23, 2017 at 9:53 AM, Chris Priest via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> >
> > What problem does this try to solve, and what does it have to do with
> > bitcoin?
> >
>=20
> I can't speak to MMRs (they look a bit redundant with the actual blockcha=
in
> history to my eye) but circling back to utxo commitments, the benefits are
In what way do you see MMRs as redundant?
Remember that with UTXO commitments because access patterns are uniform, yo=
u'll
over time have a lot more "redundancy" in the form of lost-coins evenly spr=
ead
out across the whole keyspace.
> that it enables actual proofs of non-fraud: You can prove the validity of=
a
> block based on just the previous block (and maybe some previous headers
> because of mining rewards) and can prove to a light node that a utxo hasn=
't
> been spent yet.
>
> A major factor in the way of getting utxo commitments in blocks is
> performance. The txo set is of course vastly larger and more unwieldy. If
That statement is incorrect with pruning: you can maintain a commitment to =
the
TXO set, without actually storing the entire TXO set, because you don't nee=
d to
store anything for nodes that have already been spent.
Concretely, this can be done with nothing more than adding a FullySpent node
type to the MMR definition I published earlier, with the rule being that on=
ly a
left or right child of an inner node be a FullySpent node, not both; if both
sides are spent, the inner node itself becomes FullySpent. Equally, I think=
you
can re-use the Empty node for this, but I need to think a little about the
implications re: partial inner nodes.
Regardless, with a generalized commitment scheme, the serialization/commitm=
ent
to an Empty node is simply '0', the encoding of an unspent txout surrounded=
by
spent txouts will be similar in size to a position integer followed by the
txout...
A subtlety of this construction is that you can only prove that a specific
txout # is unspent, but that's actually sufficient, as you can also prove w=
hat
# a txout txid corresponds too with a previous version of the MMR.
> you make the utxo commitments trail by a small fixed number of blocks
> (between 2 and 5) their latency problems shouldn't be a big deal as long =
as
> the overall performance is good enough. My thesis is that with appropriate
> format and implementation tricks it's possible to get performance good
> enough to no longer be a gating factor to deployment.
>=20
> Disappointingly there hasn't been any feedback about my implementation,
> just discussion about merkle sets generally.
Well, I think at this point there's still discussion over whether or not a =
UTXO
set commitment is the right approach to begin with; if it's not your
implementation isn't relevant.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--Dxnq1zWXvFF0Q93v
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJYr3VmAAoJECSBQD2l8JH7+UIH/0SpeZNLujsPjE2iac/hXgM0
0ba5XHB9aGEosO+Q/NpttNPswi3KpHfz251yWQ0nCPBA+8xL8V/nQZy1KfbxAFel
5KKVN0E9lymN7RF9KaTB4uv31/8HhfUomAS/RB6PTewKuy4lN1QMqkkI3KwmXh4O
oeBvdZRaR38Kx532KV1+XisuTpBOxZ0gL6kjsWWXk8UpZRA/1ZDbVz7hG03Hu/TO
9DzXli+bumuUZmcMxbVoGM7nvtz4Yt+32CEYDpwccgS+uOTO8gwod9UN4HpQPiNo
XMZbm2j3XsYp4LSiM98Oj5C917ExWp58QF4uUY7N9OArxE9T054iEbD4wCRUmyE=
=5VXW
-----END PGP SIGNATURE-----
--Dxnq1zWXvFF0Q93v--
|
