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
|
Return-Path: <mark@friedenbach.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 308E683D
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jun 2015 16:15:49 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ig0-f170.google.com (mail-ig0-f170.google.com
[209.85.213.170])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 79F3BF2
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jun 2015 16:15:48 +0000 (UTC)
Received: by igblr2 with SMTP id lr2so39348618igb.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jun 2015 09:15:48 -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:in-reply-to:references:from:date
:message-id:subject:to:cc:content-type;
bh=gZ8DkLIzbHXxoX0KyhO2Ux4OhMk7/U1P1xQbiAl/7g4=;
b=Qu9X/ew+DcyvwiPoWaY4HrBDZKQ3FVmQkrpooUacbznRRm994/b9Ml6X8G/CNDdrFn
nnjia3CiTfB1271xOu2TXcWgebAEi8hZ84onno3qY4MwVv6AkztGzLEA3aUa10gz0UX2
3vpJX9nBB6X9SKLDI4DqZyw/vyo0vDSxsyOGYi686J3oUsWp96Ni6oHWRvzPPezkaLpM
AHnyQ7yogInVrF2IejDObRCmfIq+CrXlqKY72zP08JhXWxN2a+WD/scn3vWxEHpYzgzR
vdF6/39OEWqJQ1GLmngEWCITnG56NKC/jLwUa4J5KQnB8uAQOMeHGmpwPbvGI+hb24oU
mrCA==
X-Gm-Message-State: ALoCoQkrz/Fk3GvcCLvJ12Ob+xhmxDZ+CcPU4grPCy69+6bpXI+rBa+urA3eayXo59UWzr0wO1Y9
X-Received: by 10.107.3.227 with SMTP id e96mr14941939ioi.50.1435508147921;
Sun, 28 Jun 2015 09:15:47 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.107.149.20 with HTTP; Sun, 28 Jun 2015 09:15:28 -0700 (PDT)
X-Originating-IP: [50.0.37.37]
In-Reply-To: <CABm2gDq31doL62a2HwY8kSuB1zPMhz6OPR0Qa9X7thbZBdNTOQ@mail.gmail.com>
References: <1164261435450448@web14h.yandex.ru> <558F583C.1000500@gmail.com>
<2A94BDF7-F265-4D36-B438-DC4F432E1C67@gmail.com>
<558F8634.90904@gmail.com>
<38C2E2A1-EB6C-48EB-8FA1-7FAA97B3E911@gmail.com>
<CAOG=w-vQ+bCyT8mLNBvLDhhQzCHXxaRos-3VFDGkCsxvCiX3jA@mail.gmail.com>
<CABm2gDq31doL62a2HwY8kSuB1zPMhz6OPR0Qa9X7thbZBdNTOQ@mail.gmail.com>
From: Mark Friedenbach <mark@friedenbach.org>
Date: Sun, 28 Jun 2015 09:15:28 -0700
Message-ID: <CAOG=w-u4UVuuV=+9-8u+ZHLgf7CCqZ17wosQBit4CZiG738JFQ@mail.gmail.com>
To: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= <jtimon@jtimon.cc>
Content-Type: multipart/alternative; boundary=001a113f0c5a3abad105199649cd
X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,HTML_MESSAGE,
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: Re: [bitcoin-dev] 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 16:15:49 -0000
--001a113f0c5a3abad105199649cd
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Assuming randomly-picked outputs, it's actually worse. The slowdown factor
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.
Of course that's not a fair assumption since in an insertion-ordered tree
using the Merkle mountain range data structure would have significantly
shorter paths for recent outputs. But the average case might be about the
same, and it comes with a slew of other tradeoffs that make it hard to
compare head-to-head in the abstract. Ultimately both need to be written
and benchmarked.
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 spent
or unspent tree which is not insertion ordered. There are alternatives like
updating the TXO tree and requiring blocks and transactions to carry proofs
with them (so validators can be stateless), but that pushes the same
(worse, actually) problem to whoever generated or assembled the proof. It
may be a tradeoff worth making, but it's not an easy answer...
On Sun, Jun 28, 2015 at 8:51 AM, Jorge Tim=C3=B3n <jtimon@jtimon.cc> wrote:
> 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 validato=
r
> state in each block, and then you can prove things like a negative by
> referencing that state commitment. The trouble is this requires maintaini=
ng
> a hash tree commitment over validator state, which turns out to be insane=
ly
> expensive. With the UTXO commitment scheme (the others are not better) th=
at
> ends up requiring 15 - 22x more I/O during block validation. And I/O is
> presently a limiter to block validation speed. So if you thought 8MB was
> what bitcoin today could handle, and you also want this commitment scheme
> for fraud proofs, then you should be arguing for a block size limit
> decrease (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 thin=
k.
>
--001a113f0c5a3abad105199649cd
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div><div>Assuming randomly-picked outputs, it's actua=
lly worse. The slowdown factor has to do with the depth of the tree, and TX=
O and STXO trees are always growing. It's still complexity O(log N), bu=
t with TXO/STXO N is the size of the entire block chain history, whereas wi=
th UTXO it's just the set of unspent transaction outputs.<br><br></div>=
Of course that's not a fair assumption since in an insertion-ordered tr=
ee using the Merkle mountain range data structure would have significantly =
shorter paths for recent outputs. But the average case might be about the s=
ame, and it comes with a slew of other tradeoffs that make it hard to compa=
re head-to-head in the abstract. Ultimately both need to be written and ben=
chmarked.<br><br></div>But it is not the case that TXO/STXO gives you const=
ant time updates. The append-only TXO tree might be close to that, but you&=
#39;d still need the spent or unspent tree which is not insertion ordered. =
There are alternatives like updating the TXO tree and requiring blocks and =
transactions to carry proofs with them (so validators can be stateless), bu=
t that pushes the same (worse, actually) problem to whoever generated or as=
sembled the proof. It may be a tradeoff worth making, but it's not an e=
asy answer...<br></div><div class=3D"gmail_extra"><br><div class=3D"gmail_q=
uote">On Sun, Jun 28, 2015 at 8:51 AM, Jorge Tim=C3=B3n <span dir=3D"ltr">&=
lt;<a href=3D"mailto:jtimon@jtimon.cc" target=3D"_blank">jtimon@jtimon.cc</=
a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0=
0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=3D"">On =
Sun, Jun 28, 2015 at 5:23 PM, Mark Friedenbach <<a href=3D"mailto:mark@f=
riedenbach.org">mark@friedenbach.org</a>> wrote:<br>
> 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 re=
ferencing that state commitment. The trouble is this requires maintaining a=
hash tree commitment over validator state, which turns out to be insanely =
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 is pr=
esently a limiter to block validation speed. So if you thought 8MB was what=
bitcoin today could handle, and you also want this commitment scheme for f=
raud proofs, then you should be arguing for a block size limit decrease (to=
500kB), not increase.<br>
<br>
</span>What about a TXO and a STXO O(1)-append commitment? That shouldn'=
;t<br>
cause that much overhead and you can build UTXO from TXO - STXO.<br>
I know it's not so efficient in some respects but it scales better I th=
ink.<br>
</blockquote></div><br></div>
--001a113f0c5a3abad105199649cd--
|
