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
|
Return-Path: <pieter.wuille@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 90F00259
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Feb 2017 23:24:31 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr0-f175.google.com (mail-wr0-f175.google.com
[209.85.128.175])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 344B0139
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Feb 2017 23:24:30 +0000 (UTC)
Received: by mail-wr0-f175.google.com with SMTP id u108so18971448wrb.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Feb 2017 15:24:30 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=2VqlDuUbaL6ciAwgrEGvbxmQ7Og0G0hCa8zY7Ni1u08=;
b=MR3kFdBLdOMqKIgEmTRNLueW+Ng4fTHtgL/ugF8bqmCwY78kLrOxrQtuPp+XXIS101
eBAvOTZEGCJybT49zVW0bzlCPe7ok/LjnQ5rehRdxOpC4IqwvAgCymDTbGGZWCZFXrjs
Kyfkj6x9aR4jlWyLe7Z6fZzsCoO3vn5xtWYz2M2WjYkBg1rFPN3WcNCQd2d3CyBHJpmo
zf+m4wjL19dHxp9Ky2pxgm5Sjd76gyxzcKPuql8VO82Oe7hNJZrhWeXh36nSn97aBs+z
cWZdEEa4yNFcgqSRZpjiRRygL+6zx/JKzN4WbmknPT9AceQ5af4Wy85rEl45RIkaBWd9
UjYw==
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=2VqlDuUbaL6ciAwgrEGvbxmQ7Og0G0hCa8zY7Ni1u08=;
b=F+i/BO5efb0M4xc0Jd8DKqKni5bFFS7raDy4Zt6j2uxkMUPso6U3t/TpFcvPYZdzSV
G4T83zMaGMFcHEupptYrLuPrBehMnia4GxQZJ5OLAC86F5daSZYHHPAkxkviIF6iAK50
z2cq+1O/9V/cpBN8J5e2TCdGoqY/lTtJYzjnGW0DlxJem6wjelGCKrdpHsYGmZ0phhMT
cxEqaiI0135i+fTsT/lswRDBgfOv39cqYfQ/wmz5cpVFy4apFd/Vz1n2MBkFdoC04EGm
taJGyIpUCPbUCp6EA7xTeGPrejRJYQV6tblsf76hAo6UilQg18HmxL3KV6MaPBMlQQI9
D/mw==
X-Gm-Message-State: AMke39nYcxB3q2xTx+wAZR8CFZB8eCCZ8bLAbXsyyebGDuwE+SxEwHlhRK8DGr64xMR14/4KWvyJ57Tpg26ILQ==
X-Received: by 10.223.136.82 with SMTP id e18mr4358235wre.28.1488324268768;
Tue, 28 Feb 2017 15:24:28 -0800 (PST)
MIME-Version: 1.0
Received: by 10.80.153.212 with HTTP; Tue, 28 Feb 2017 15:24:28 -0800 (PST)
Received: by 10.80.153.212 with HTTP; Tue, 28 Feb 2017 15:24:28 -0800 (PST)
In-Reply-To: <CA+KqGkrNDEUB8yzkX+ya1ikb46zmKA6Bt4-skqUgLzo=nnNtUw@mail.gmail.com>
References: <20170223235105.GA28497@savin.petertodd.org>
<CA+KqGkowxEZeAFYa2JJchBDtRkg1p3YZNocivzu3fAtgRLDRBQ@mail.gmail.com>
<20170224010943.GA29218@savin.petertodd.org>
<CA+KqGkrOK76S3ffPJmpqYcBwtSeKESqN16yZsrwzDR6JZZmwFA@mail.gmail.com>
<20170224025811.GA31911@savin.petertodd.org>
<CA+KqGkq7gavAnAk-tcA+gxL2sWpv3ENhEmHrQHaPdyAsKrLjGg@mail.gmail.com>
<20170224031531.GA32118@savin.petertodd.org>
<CA+KqGkrfhg3GnbWwvKXHQ2NWuCnfzYyTPUxRhzYMuDBiNQR4eA@mail.gmail.com>
<20170224043613.GA32502@savin.petertodd.org>
<CA+KqGkpi4GvgU-K6vt-U5ZN4AkpjZ0rruzddoJS4-V0TcnyqUQ@mail.gmail.com>
<20170225041202.GA11152@savin.petertodd.org>
<CA+KqGkqs8F1hK6y-JnLFRpqhQ5i8i+MXVmtGUQBYmE5d1OCAAg@mail.gmail.com>
<CAHUwRvtseXUx_ShfHd9r9LW1_8cJYcofQ4s1vEpkpKJEniDTzA@mail.gmail.com>
<CA+KqGkrNDEUB8yzkX+ya1ikb46zmKA6Bt4-skqUgLzo=nnNtUw@mail.gmail.com>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Tue, 28 Feb 2017 15:24:28 -0800
Message-ID: <CAPg+sBgyToj8NcYSFJ376WNLGXO7aSwpZRvd0zuFeB=rF14rfg@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>,
Bram Cohen <bram@bittorrent.com>
Content-Type: multipart/alternative; boundary=001a1146060e59d0fe05499f7f61
X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE,
RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.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: Tue, 28 Feb 2017 23:24:31 -0000
--001a1146060e59d0fe05499f7f61
Content-Type: text/plain; charset=UTF-8
On Feb 28, 2017 15:10, "Bram Cohen via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:
On Tue, Feb 28, 2017 at 8:43 AM, G. Andrew Stone <g.andrew.stone@gmail.com>
wrote:
>
> But since transactions' prevouts are not specified by [block height, tx
> index, output index] or by TXO index, I don't understand how an insertion
> ordered TXO tree can result in efficient lookups. Can you help me
> understand this?
>
You have to have a lookup table going from prevouts to txo index. Lookups
on that are relatively fast because looking up things in a hashtable is a
single cache miss, while looking up things in a tree is logarithmic cache
misses.
I'm wondering if there is some confusion here.
Yes, someone needs to have a lookup table from prevouts to TXO tree
positions. But because an insertion-ordered TXO tree does not rebalance,
that table can be maintained by wallets or service providers for just their
own coins, instead of by every full node and miner individually for
everyone's coins.
In the simplest committed TXO model, full nodes simply maintain the TXO
root hash, and every transaction/block comes with a proof that its inputs
are in the TXO tree, and the necessary information to update the root after
spending the inputs and adding the outputs.
--
Pieter
--001a1146060e59d0fe05499f7f61
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto"><div class=3D"gmail_extra" dir=3D"auto"><div class=3D"gma=
il_quote">On Feb 28, 2017 15:10, "Bram Cohen via bitcoin-dev" <=
;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists=
.linuxfoundation.org</a>> wrote:<br type=3D"attribution"><blockquote cla=
ss=3D"quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-=
left:1ex"><div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_q=
uote"><div class=3D"quoted-text">On Tue, Feb 28, 2017 at 8:43 AM, G. Andrew=
Stone <span dir=3D"ltr"><<a href=3D"mailto:g.andrew.stone@gmail.com" ta=
rget=3D"_blank">g.andrew.stone@gmail.com</a>></span> wrote:<br><blockquo=
te class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc so=
lid;padding-left:1ex"><div dir=3D"ltr"><div><div><div><br></div>But since t=
ransactions' prevouts are not specified by [block height, tx index, out=
put index] or by TXO index, I don't understand how an insertion ordered=
TXO tree can result in efficient lookups.=C2=A0 Can you help me understand=
this?<br></div></div></div></blockquote><div><br></div></div><div>You have=
to have a lookup table going from prevouts to txo index. Lookups on that a=
re relatively fast because looking up things in a hashtable is a single cac=
he miss, while looking up things in a tree is logarithmic cache misses.</di=
v></div></div></div></blockquote></div></div><div dir=3D"auto"><br></div><d=
iv dir=3D"auto">I'm wondering if there is some confusion here.</div><di=
v dir=3D"auto"><br></div><div dir=3D"auto">Yes, someone needs to have a loo=
kup table from prevouts to TXO tree positions. But because an insertion-ord=
ered TXO tree does not rebalance, that table can be maintained by wallets o=
r service providers for just their own coins, instead of by every full node=
and miner individually for everyone's coins.</div><div dir=3D"auto"><b=
r></div><div dir=3D"auto">In the simplest committed TXO model, full nodes s=
imply maintain the TXO root hash, and every transaction/block comes with a =
proof that its inputs are in the TXO tree, and the necessary information to=
update the root after spending the inputs and adding the outputs.</div><di=
v dir=3D"auto"><br></div><div dir=3D"auto">--=C2=A0</div><div dir=3D"auto">=
Pieter</div><div dir=3D"auto"><br></div><div class=3D"gmail_extra" dir=3D"a=
uto"></div></div>
--001a1146060e59d0fe05499f7f61--
|
