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
|
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 5F11C360
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 18 May 2016 11:15:01 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-vk0-f48.google.com (mail-vk0-f48.google.com
[209.85.213.48])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CC4781B4
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 18 May 2016 11:15:00 +0000 (UTC)
Received: by mail-vk0-f48.google.com with SMTP id f66so56493234vkh.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 18 May 2016 04:15:00 -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;
bh=TvVCn8Km/J8464W3I2pQJYa6E9m1Ceh8pJHdu7BX2Bc=;
b=s9aecJs1eaHGFWV2a6qOWhEwm2v+xXeiDzeo2wFmEvtsBOb9fxV4h1JGLL1Yee7oR/
br5Ouirl4J20u9SOAjzqhpxTWCAg0q6pM9e9q0qIOz+kNFlinZBRru2kjMmijPdw/Rm1
FJGl/8uLtyod4DPrNWZ4zrWA5VYd8OKMMruuJeEdUcCGeectg6EnEq8kBr002mCROBwO
aXs99iSBexklQIxDmZ60pgjCEx/gWc4gWOQQ4Em9cUB2Dq7kJX+U5nK8xLaHPnZZoA0D
lCqKKFbMFRwD/dcYkp+gGmzjVqvyI2SvqwSDyPYBhLQgrSrVuZnIcEEDjq/gSBcR7XWH
a2Mw==
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;
bh=TvVCn8Km/J8464W3I2pQJYa6E9m1Ceh8pJHdu7BX2Bc=;
b=G16Cq8A/Q9rGs610RQ/XLms7rmeLDi+ViIqgPKWNQ+k7kChGyttwvSCo8auD5DDCDT
VrBwn0p9N+HqTw5brSKd3j/2Wq6pPMLVr1WJT/CxyPu11cseRNtmq1n1ATtF5Rd1xshr
JoQH/4YUzKi3CZov7GU6eXYlA3kufmMqFETDqye5+Pa77RiOfZ8lCvhlPQMuE51c1KYI
ft1BS82fDhKlkCRGa0R6kbp6hUN5GBzI17fjjWY5Hnn1DDRNJP2qEfzC3UpdCr8GQF2j
8pjx4WQn1fkxCURKI2ybX9disSPfn4uzwUyWJ8gbLYSoyVi4BEJ5M/6hnds4V6nrLuYR
u9Lw==
X-Gm-Message-State: AOPr4FVhhfuWMU/lqwDW4GbsJrWgd/u8JG+bdfNthk8/HCf2KuptX0Q2sfwYq2AVanebTJ43cuOQT/s6B4EACQ==
MIME-Version: 1.0
X-Received: by 10.159.40.99 with SMTP id c90mr3650263uac.85.1463570099779;
Wed, 18 May 2016 04:14:59 -0700 (PDT)
Received: by 10.31.141.73 with HTTP; Wed, 18 May 2016 04:14:59 -0700 (PDT)
Received: by 10.31.141.73 with HTTP; Wed, 18 May 2016 04:14:59 -0700 (PDT)
In-Reply-To: <CABm2gDqMQanaY0Eo4QAnx2MrKCSP+v31R6J80jSVx+jOwsVsVw@mail.gmail.com>
References: <20160517132311.GA21656@fedora-21-dvm>
<CABm2gDoj=6CimHm2C0H_qa=o5SRqWr0ZTGamf-qT-kUjt5WXTA@mail.gmail.com>
<CABm2gDqMQanaY0Eo4QAnx2MrKCSP+v31R6J80jSVx+jOwsVsVw@mail.gmail.com>
Date: Wed, 18 May 2016 13:14:59 +0200
Message-ID: <CABm2gDp9NLKS=+2BhtS3tT2aZjV0sGHUkVV-+n_90w4Ud9Aakw@mail.gmail.com>
From: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= <jtimon@jtimon.cc>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>,
Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=94eb2c048618e6d3d605331bf7eb
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
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: Wed, 18 May 2016 11:15:01 -0000
--94eb2c048618e6d3d605331bf7eb
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On May 17, 2016 15:23, "Peter Todd via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> # TXO Commitments
>
> Specifically TXO commitments proposes a Merkle Mountain Range=C2=B9 (MMR)=
, a
> type of deterministic, indexable, insertion ordered merkle tree, which
allows
> new items to be cheaply appended to the tree with minimal storage
requirements,
> just log2(n) "mountain tips". Once an output is added to the TXO MMR it i=
s
> never removed; if an output is spent its status is updated in place. Both
the
> state of a specific item in the MMR, as well the validity of changes to
items
> in the MMR, can be proven with log2(n) sized proofs consisting of a
merkle path
> to the tip of the tree.
How expensive it is to update a leaf from this tree from unspent to spent?
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")=
?
--94eb2c048618e6d3d605331bf7eb
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<p dir=3D"ltr"><br>
On May 17, 2016 15:23, "Peter Todd via bitcoin-dev" <<a href=
=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfo=
undation.org</a>> wrote:<br>
> # TXO Commitments<br>
></p>
<p dir=3D"ltr">> Specifically TXO commitments proposes a Merkle Mountain=
Range=C2=B9 (MMR), a<br>
> type of deterministic, indexable, insertion ordered merkle tree, which=
allows<br>
> new items to be cheaply appended to the tree with minimal storage requ=
irements,<br>
> just log2(n) "mountain tips". Once an output is added to the=
TXO MMR it is<br>
> never removed; if an output is spent its status is updated in place. B=
oth the<br>
> state of a specific item in the MMR, as well the validity of changes t=
o items<br>
> in the MMR, can be proven with log2(n) sized proofs consisting of a me=
rkle path<br>
> to the tip of the tree.</p>
<p dir=3D"ltr">How expensive it is to update a leaf from this tree from uns=
pent to spent?</p>
<p dir=3D"ltr">Wouldn't it be better to have both an append-only TXO an=
d an append-only STXO (with all spent outputs, not only the latest ones lik=
e in your "STXO")?</p>
--94eb2c048618e6d3d605331bf7eb--
|