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
|
Return-Path: <bram@bittorrent.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 24F66B9E
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Feb 2017 02:50:13 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f44.google.com (mail-it0-f44.google.com
[209.85.214.44])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1F93C138
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Feb 2017 02:50:12 +0000 (UTC)
Received: by mail-it0-f44.google.com with SMTP id 203so8326367ith.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 18:50:11 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=bittorrent-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=fHcI2m7355y2NQkfiKT+XZJIHOpYtBMzHqL+5rnkeFs=;
b=WGMQxSoMLFS5SpJ//Q+VCwKKnHrIxMZEgpPxnSKVlyL3yo44B/isSIW7EXfsujQdUz
AP01KhEOmxkwrjU+ks7lM09/CsrzsUvyEsOaUW1cT4vsWoRt9yr3OwLAesSxbmXR2FoB
jnNXpkRjlEIHpFV6ge7zvHSmwSHYeVXI4ZNPswE2kHVXOnzpvwQwwkbUwjGyCTCbuIRL
wgBsAf1zq4La6zavnN8dOHGtLn+XntN3CJRXOf/gcODDy5UbB1a8bXB4jy1Aa4224VtZ
HpFOEhr+fKL/e2U3CZQgr/vQMJop0JacFkecErAbegb8TDVnE6slyC2dG/PHkAWBlTw2
M3fQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=fHcI2m7355y2NQkfiKT+XZJIHOpYtBMzHqL+5rnkeFs=;
b=hXBFP3ETR8utSskdncv7CzweW3GxKxKy69UTY9/qwWwWbVjGKT4tSpOezkLakfaFQ5
QO3600EYiRVgYEXwmnDNJ5aDzDRgqctATC9N+uo4pVCaCcLd5DBU5J11b4bZvadVVNxH
ZfYi5n5cDkr2+OZTEBzeFHZ8d5qv6i05AOF5Mi0CqvEVZNXZAZSAG7Mw6HG2jRQlR1Xe
m0hnOWW7scpsGIfq/Vng6SmJSNnPKCdlR+d8SXXR5kIPKd6u1qIOYqYE0ZlqIN+f31zx
Rqs8QS6DFMhP5vS8DGYxh9zJi4DxMmfhdP4LYxJpz+BjTwS8wI6RFGIC1FYqVMfjXe5i
MM/w==
X-Gm-Message-State: AMke39nQMskIuNAfXqJ7Pu5AvgoEU0P8qR9F055joVO5WDwDYjbcG/+QuhwpzHX8md41qhI2cPa2Bpzqx52JQfgf
X-Received: by 10.107.34.10 with SMTP id i10mr775033ioi.41.1487904611450; Thu,
23 Feb 2017 18:50:11 -0800 (PST)
MIME-Version: 1.0
Received: by 10.36.73.150 with HTTP; Thu, 23 Feb 2017 18:50:10 -0800 (PST)
In-Reply-To: <20170224010943.GA29218@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>
From: Bram Cohen <bram@bittorrent.com>
Date: Thu, 23 Feb 2017 18:50:10 -0800
Message-ID: <CA+KqGkrOK76S3ffPJmpqYcBwtSeKESqN16yZsrwzDR6JZZmwFA@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=001a1140ec68d358cb05493dc924
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_LOW,
RCVD_IN_SORBS_SPAM 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:50:13 -0000
--001a1140ec68d358cb05493dc924
Content-Type: text/plain; charset=UTF-8
On Thu, Feb 23, 2017 at 5:09 PM, Peter Todd <pete@petertodd.org> wrote:
> 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:
>
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.
--001a1140ec68d358cb05493dc924
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On T=
hu, Feb 23, 2017 at 5:09 PM, Peter Todd <span dir=3D"ltr"><<a href=3D"ma=
ilto:pete@petertodd.org" target=3D"_blank">pete@petertodd.org</a>></span=
> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo=
rder-left:1px #ccc solid;padding-left:1ex">I think you've misunderstood=
what TXO commitments are. From my article:<br>
<br>
"A merkle tree committing to the state of all transaction outputs, bot=
h spent<br>
and unspent, can provide a method of compactly proving the current state of=
an<br>
output."<br>
-<a href=3D"https://petertodd.org/2016/delayed-txo-commitments#txo-commitme=
nts" rel=3D"noreferrer" target=3D"_blank">https://petertodd.org/2016/<wbr>d=
elayed-txo-commitments#txo-<wbr>commitments</a>:<br></blockquote><div><br><=
/div><div>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 indic=
ate 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 d=
ata structure instead of a basic fundamental one.=C2=A0</div></div></div></=
div>
--001a1140ec68d358cb05493dc924--
|
