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
|
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 D982BB90
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Feb 2017 02:58:17 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail149056.authsmtp.com (outmail149056.authsmtp.com
[62.13.149.56])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id 15988FC
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Feb 2017 02:58:16 +0000 (UTC)
Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232])
by punt21.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1O2wElR023764;
Fri, 24 Feb 2017 02:58:14 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 v1O2wCNw090019
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
Fri, 24 Feb 2017 02:58:13 GMT
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 598DA40576;
Fri, 24 Feb 2017 02:58:12 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id B249A204AB; Thu, 23 Feb 2017 21:58:11 -0500 (EST)
Date: Thu, 23 Feb 2017 21:58:11 -0500
From: Peter Todd <pete@petertodd.org>
To: Bram Cohen <bram@bittorrent.com>
Message-ID: <20170224025811.GA31911@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>
<20170223235105.GA28497@savin.petertodd.org>
<CA+KqGkowxEZeAFYa2JJchBDtRkg1p3YZNocivzu3fAtgRLDRBQ@mail.gmail.com>
<20170224010943.GA29218@savin.petertodd.org>
<CA+KqGkrOK76S3ffPJmpqYcBwtSeKESqN16yZsrwzDR6JZZmwFA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="HlL+5n6rz5pIUxbD"
Content-Disposition: inline
In-Reply-To: <CA+KqGkrOK76S3ffPJmpqYcBwtSeKESqN16yZsrwzDR6JZZmwFA@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: 156fbad2-fa3d-11e6-829f-00151795d556
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aQdMdAYUHlAWAgsB AmEbW1ZeVVV7WGc7 bghPaBtcak9QXgdq
T0pMXVMcUgQXA1ty eFkeWxlydgwIeX5z ZUMsX3VdChYrIURg
FB9XQXAHZDJmdWgd 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: Fri, 24 Feb 2017 02:58:18 -0000
--HlL+5n6rz5pIUxbD
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Thu, Feb 23, 2017 at 06:50:10PM -0800, Bram Cohen wrote:
> On Thu, Feb 23, 2017 at 5:09 PM, Peter Todd <pete@petertodd.org> wrote:
>=20
> > I think you've misunderstood what TXO commitments are. From my article:
> >
> > "A merkle tree committing to the state of all transaction outputs, both
> > spent
> > and unspent, can provide a method of compactly proving the current state
> > of an
> > output."
> > -https://petertodd.org/2016/delayed-txo-commitments#txo-commitments:
> >
>=20
> The proposal on that page is of a tree which does require random access
> updates, it just positions entries in the order they happened to be added
> instead of sorting by their hash. Once you start updating it to indicate
> spent status all the exact same issues of TXO size and cache coherence on
> updates show up again, but now you're using a more complex bespoke data
> structure instead of a basic fundamental one.
Sorry, but I was replying to your statement:
> What you can't do with MMRs or the blockchain is make a compact proof that
> something is still in the utxo set, which is the whole point of utxo
> commitments.
So to be clear, do you agree or disagree with me that you *can* extract a
compact proof from a MMR that a given output is unspent?
I just want to make sure we're on the same page here before we discuss
performance characteristics.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--HlL+5n6rz5pIUxbD
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJYr6FAAAoJECSBQD2l8JH7tmwIAK34ukxG2HFsKi7n1c87uam0
FcsxU1Kq7juomOxxVCdXuhvjspS32yx2yhMhQKZC8+fzICiPW4khfXAs4eqOUFDZ
Rhi7K02c5qEMQocH7t+rY5LBjy93rvosFEP6gbme8ezfC1TZDkaKwVAJs09VeP5X
MAJSdY5y7nIl1x5yC+bFhnnlajE0PyGoD0fZr/wuJ6YPaVFmEypBc5z5DK/oz5le
3UrV/VrjAtEhhpVbECjaWD2i/LpqcfB2r1973AYugkUpQQlv8z1xwwgIIeNqMHAc
hJXpZeT+E6rpatKcbjidU9fCclWkLTsfyFQ0QLvXdUn0bofsBfID8kzTcqjCqwU=
=0QRZ
-----END PGP SIGNATURE-----
--HlL+5n6rz5pIUxbD--
|
