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
|
Return-Path: <jtimon@jtimon.cc>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 4E7DF83D
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 19 May 2016 09:31:28 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-vk0-f44.google.com (mail-vk0-f44.google.com
[209.85.213.44])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8BD52195
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 19 May 2016 09:31:27 +0000 (UTC)
Received: by mail-vk0-f44.google.com with SMTP id y2so24594820vka.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 19 May 2016 02:31:27 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=jtimon-cc.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:cc; bh=9jL02jH43wRcaUVXTqiNiNmhy0+NeDinlhPP27X39VA=;
b=LtibAq6gFLA22VkFgj1pP2oiF74JxWtENJdoEm0l6kqU/fC982G7ZGNmDmrqsxJl8K
72zN+wd/H2lYvGL3p1T0eRAuXhBqsux5ZSm0M6piiNCIFx95BTve5HrpPnOyOEjAfJ1J
7WV6LnK5OtouB/7F1otg6RhXgz5s6ig2VnWW7xtwODLSnrbqa9HRuNSyc1NymHQJNJPp
UaqKMospviv3aGTbIPJso0Vp5t6/1joLEulPzM02Qsf+Fq0hq1aB+fKrC53GSsrMoP8T
vrbAReUzxKLKTjWmsN3ozw/MrE4V4Ng34ORF+dIYG5VOGc+bgqPnnYWWIEb7uqwgkfip
ArZA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:in-reply-to:references:date
:message-id:subject:from:to:cc;
bh=9jL02jH43wRcaUVXTqiNiNmhy0+NeDinlhPP27X39VA=;
b=OSBmK3PVAkMyBhFGVHudJHFK+tsUf2Z48U/0o6TJZB1XG9siRgEA8pwOLM25pFdcoi
6eIhhwWpGPv5sXbsgvQvIil1N30a+pU9q5b5crSjEllgncbltHGJCcyEcWRkeK5/3yZt
rJmG0J1ON8yVxTmGtEHF+A9EntGnEqM6tLLBLRbFgvXmyju3cEj7DVBjf36dt8XljN23
pBuHf+aC88seNYUSvoAPPSvQEIM5Z2aziTiPJKuACPxE7ZjiUT05GjqnzMQ70Ay5UoP0
kX79tQX4WhfJeyJVFurotsS2iFewWERkdYouShjLM41sKEWuFqb41aw8PfSt0tAs0o/j
24XQ==
X-Gm-Message-State: AOPr4FVxxCPJCCiGPDVBrbVAe8dqLvFrjAUHQkoaviZ6NUvFkSUNl2Spljw870ciKUSf/hRifUi42DlGhfHr9Q==
MIME-Version: 1.0
X-Received: by 10.31.230.197 with SMTP id d188mr6485183vkh.143.1463650286678;
Thu, 19 May 2016 02:31:26 -0700 (PDT)
Received: by 10.31.141.73 with HTTP; Thu, 19 May 2016 02:31:26 -0700 (PDT)
Received: by 10.31.141.73 with HTTP; Thu, 19 May 2016 02:31:26 -0700 (PDT)
In-Reply-To: <CABm2gDp9N3ZEZcmF28ESv3V7v_HqU5e5KHY69cSxcVm0t7BeDQ@mail.gmail.com>
References: <20160517132311.GA21656@fedora-21-dvm>
<CABm2gDoj=6CimHm2C0H_qa=o5SRqWr0ZTGamf-qT-kUjt5WXTA@mail.gmail.com>
<CABm2gDqMQanaY0Eo4QAnx2MrKCSP+v31R6J80jSVx+jOwsVsVw@mail.gmail.com>
<CABm2gDp9NLKS=+2BhtS3tT2aZjV0sGHUkVV-+n_90w4Ud9Aakw@mail.gmail.com>
<20160518235336.GA1358@fedora-21-dvm>
<CABm2gDrXjg_nSKr-ju0jdXxmMc4N=LQFRwaVU3ix1p-T8CVKdQ@mail.gmail.com>
<CABm2gDrmRf9wjddiMb-TTDE0xkBJ6yMz-bW_aTpDuBvNqrnHzQ@mail.gmail.com>
<CABm2gDqfZh0zOqJN5itVk8eP0nshBsydzT6uryrBdRTcYqyhyA@mail.gmail.com>
<CABm2gDr4ZKvGt3qRPpV+iPgGbpQ5cO66M_bPn2HJPn-eYcQMOg@mail.gmail.com>
<CABm2gDrijEMZW1dMjGTfG-32VGvLZvX-ujP1n5mxBeVLQSsL1Q@mail.gmail.com>
<CABm2gDp9N3ZEZcmF28ESv3V7v_HqU5e5KHY69cSxcVm0t7BeDQ@mail.gmail.com>
Date: Thu, 19 May 2016 11:31:26 +0200
Message-ID: <CABm2gDqcURsug5C21A7dmAMCgU7easbCs=u5sFZy_G4MfyY8mw@mail.gmail.com>
From: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= <jtimon@jtimon.cc>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=94eb2c094e5669cbbc05332ea3c0
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,HTML_MESSAGE,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 Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With
Low-Latency Delayed TXO Commitments
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, 19 May 2016 09:31:28 -0000
--94eb2c094e5669cbbc05332ea3c0
Content-Type: text/plain; charset=UTF-8
On May 19, 2016 01:53, "Peter Todd" <pete@petertodd.org> wrote:
tip of the tree.
> >
> > How expensive it is to update a leaf from this tree from unspent to
spent?
>
> log2(n) operations.
Updating a leaf is just as expensive as adding a new one?
That's not what I expected.
Or is adding a new one O (1) ?
Anyway, thanks, I'll read this in more detail.
> > Wouldn't it be better to have both an append-only TXO and an append-only
> > STXO (with all spent outputs, not only the latest ones like in your
"STXO")?
>
> Nope. The reason why this doesn't work is apparent when you ask how will
the
> STXO be indexed?
Just the same way the TXO is (you just stop updating the txo leafs from
unspent to spent.
> If it's indexed by outpoint - that is H(txid:n) - to update the STXO you
need
> he entire thing, as the position of any new STXO that you need to add to
the
> STXO tree is random.
>
> OTOH, if you index the STXO by txout creation order, with the first txout
ever
> created having position #0, the second #1, etc. the data you may need to
update
> the STXO later has predictable locality... but now you have something
that's
> basically identical to my proposed insertion-ordered TXO commitment
anyway.
Yeah, that's what I want. Like your append only TXO but for STXO (that way
we avoid ever updating leafs in the TXO, and I suspect there are other
advantages for fraud proofs).
> Incidentally, it's interesting how if a merbinner tree is insertion-order
> indexed you end up with a datastructure that's almost identical to a MMR.
No complain with MMR. My point is having 2 of them separated: one for the
TXO (entries unmutable) and one for the STXO (again, entries unmutable).
Maybe it doesn't make sense, but I would like to understand why.
--94eb2c094e5669cbbc05332ea3c0
Content-Type: text/html; charset=UTF-8
<p dir="ltr"><br>
On May 19, 2016 01:53, "Peter Todd" <<a href="mailto:pete@petertodd.org">pete@petertodd.org</a>> wrote:<br>
tip of the tree.<br>
> ><br>
> > How expensive it is to update a leaf from this tree from unspent to spent?<br>
><br>
> log2(n) operations.</p>
<p dir="ltr">Updating a leaf is just as expensive as adding a new one?<br>
That's not what I expected.<br>
Or is adding a new one O (1) ?</p>
<p dir="ltr">Anyway, thanks, I'll read this in more detail.</p>
<p dir="ltr">> > Wouldn't it be better to have both an append-only TXO and an append-only<br>
> > STXO (with all spent outputs, not only the latest ones like in your "STXO")?<br>
><br>
> Nope. The reason why this doesn't work is apparent when you ask how will the<br>
> STXO be indexed?</p>
<p dir="ltr">Just the same way the TXO is (you just stop updating the txo leafs from unspent to spent.</p>
<p dir="ltr">> If it's indexed by outpoint - that is H(txid:n) - to update the STXO you need<br>
> he entire thing, as the position of any new STXO that you need to add to the<br>
> STXO tree is random.<br>
><br>
> OTOH, if you index the STXO by txout creation order, with the first txout ever<br>
> created having position #0, the second #1, etc. the data you may need to update<br>
> the STXO later has predictable locality... but now you have something that's<br>
> basically identical to my proposed insertion-ordered TXO commitment anyway.</p>
<p dir="ltr">Yeah, that's what I want. Like your append only TXO but for STXO (that way we avoid ever updating leafs in the TXO, and I suspect there are other advantages for fraud proofs).</p>
<p dir="ltr">> Incidentally, it's interesting how if a merbinner tree is insertion-order<br>
> indexed you end up with a datastructure that's almost identical to a MMR.</p>
<p dir="ltr">No complain with MMR. My point is having 2 of them separated: one for the TXO (entries unmutable) and one for the STXO (again, entries unmutable).</p>
<p dir="ltr">Maybe it doesn't make sense, but I would like to understand why.<br>
</p>
--94eb2c094e5669cbbc05332ea3c0--
|
