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
|
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 DB0BB273
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jun 2015 17:47:24 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wg0-f49.google.com (mail-wg0-f49.google.com [74.125.82.49])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 16B71A8
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jun 2015 17:47:24 +0000 (UTC)
Received: by wgck11 with SMTP id k11so124181973wgc.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jun 2015 10:47:22 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:date:message-id:subject:from:to:cc
:content-type:content-transfer-encoding;
bh=Vl0l3KkP358Z4C5HrqrV2buAKT3EKnpCgIt06yogaVI=;
b=GMTR/86F0CQ3ghoSKdHSkDLjznKS1Ny9pwRLb2KjAv5Gc2SGT4UCr0w69dJEh/7Wgr
bDCaAC09CoVQsHkzDPGI8lT+CVSIKzjtsCru+17o1neQsLMw7g4CSxyla8fgt+2qPoZg
xLdEzOEE6DeydF0zSSbhxLGinIQMl7of8mgf1FLuP1tDwi4SaZBGMry19+odmShlMNKC
k5/LpzqcNboFMyE7Br7LvpWp3R/8GJJyPYp0UiCSUsCrKLdjoP4zN7t6AfEqVSPUcSuD
5zfpt/vn2GeLG20wPYWDeE4STM6yGlt2/Z9LdcUJ9Tluww91mKHccjTO0eMwA6KHT7DT
0Kew==
X-Gm-Message-State: ALoCoQlG8ICaZZTElRy001SNZdJFDLyrQ1dWWdp/8cwp98tfLv916Xq3sfK0zEkSXQJ9mTU+b+Ed
MIME-Version: 1.0
X-Received: by 10.180.88.201 with SMTP id bi9mr15426479wib.58.1435513642708;
Sun, 28 Jun 2015 10:47:22 -0700 (PDT)
Received: by 10.194.95.168 with HTTP; Sun, 28 Jun 2015 10:47:22 -0700 (PDT)
Date: Sun, 28 Jun 2015 19:47:22 +0200
Message-ID: <CABm2gDpLDs9WN2E67O_0OuVGiE7HBhtBnhQchpDaoAM7rZjn_w@mail.gmail.com>
From: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= <jtimon@jtimon.cc>
To: Mark Friedenbach <mark@friedenbach.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW,
URIBL_BLACK autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: [bitcoin-dev] TXO + STXO vs UTXO Re: Original Vision
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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: Sun, 28 Jun 2015 17:47:25 -0000
On Sun, Jun 28, 2015 at 6:15 PM, Mark Friedenbach <mark@friedenbach.org> wr=
ote:
> Assuming randomly-picked outputs, it's actually worse. The slowdown facto=
r
> has to do with the depth of the tree, and TXO and STXO trees are always
> growing. It's still complexity O(log N), but with TXO/STXO N is the size =
of
> the entire block chain history, whereas with UTXO it's just the set of
> unspent transaction outputs.
But you can prune them.
> But it is not the case that TXO/STXO gives you constant time updates. The
> append-only TXO tree might be close to that, but you'd still need the spe=
nt
> or unspent tree which is not insertion ordered. There are alternatives li=
ke
> updating the TXO tree and requiring blocks and transactions to carry proo=
fs
> with them (so validators can be stateless), but that pushes the same (wor=
se,
> actually) problem to whoever generated or assembled the proof. It may be =
a
> tradeoff worth making, but it's not an easy answer...
No, no.
You don't need a non-constant update of any spent flag (because
there's none), that's the whole point of having 2 separated trees for
everything on one side, and only spent outputs on the other side.
This proposal is not useful for SPV wallets but it lets you build the
UTXO at any height from the committed txo + stxo trees and update it
yourself from there. You could have a fast synchronization mode in
which you're not really a full node from the beginning but you end up
validating the older blocks later, when you have time after
synchronizing to the tip of the chain.
For the SPV use case you would need a committed UTXO (or the TXO with
a fIsSpent bit) but that seems to be more complicated and can be done
separately later.
> On Sun, Jun 28, 2015 at 8:51 AM, Jorge Tim=C3=B3n <jtimon@jtimon.cc> wrot=
e:
>>
>> On Sun, Jun 28, 2015 at 5:23 PM, Mark Friedenbach <mark@friedenbach.org>
>> wrote:
>> > UTXO commitments are the nominal solution here. You commit the validat=
or
>> > state in each block, and then you can prove things like a negative by
>> > referencing that state commitment. The trouble is this requires mainta=
ining
>> > a hash tree commitment over validator state, which turns out to be ins=
anely
>> > expensive. With the UTXO commitment scheme (the others are not better)=
that
>> > ends up requiring 15 - 22x more I/O during block validation. And I/O i=
s
>> > presently a limiter to block validation speed. So if you thought 8MB w=
as
>> > what bitcoin today could handle, and you also want this commitment sch=
eme
>> > for fraud proofs, then you should be arguing for a block size limit de=
crease
>> > (to 500kB), not increase.
>>
>> What about a TXO and a STXO O(1)-append commitment? That shouldn't
>> cause that much overhead and you can build UTXO from TXO - STXO.
>> I know it's not so efficient in some respects but it scales better I
>> think.
>
>
|
