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
|
Return-Path: <bram@bittorrent.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id DF124B7E
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 31 Mar 2017 22:05:09 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f47.google.com (mail-it0-f47.google.com
[209.85.214.47])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D9018172
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 31 Mar 2017 22:05:08 +0000 (UTC)
Received: by mail-it0-f47.google.com with SMTP id 68so7802878itx.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 31 Mar 2017 15:05:08 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=bittorrent-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:from:date:message-id:subject:to;
bh=zoaCtHs3Y1Xaum+4bAjR4RBg6G6hCwPXH5MUlGgAxPc=;
b=RlIX0k3pA6X+5wPAFSLHspzhsYIASdll6MWwYA9BUG8o4XYp4DccDCGowTSDzDFpKK
1Bu74gZeZtMlZLeBt+cx7jUlzikGk8kmZxN6DKVKBJTETv1/d1BiRowpzB8KvgDAMl/I
uTcnHfHuX31jgtp+btnHBJBRoUPVvaUu5ZjI2z6FDpxz8RcxvE0nA1Nf6jWGYoe2uVfg
UIDq57R+KZTo3AJ41q2uWb7NLQT/W053XCpDm9XnCT5gTYklwyKnwch/xps4XYRCX9HL
okERy4+csTh2AUdzwIF62JlJiKRj9hwFHLejL1x8dhMZV5vQ4iPCK52q6fMpdR1svjcy
KCHg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=zoaCtHs3Y1Xaum+4bAjR4RBg6G6hCwPXH5MUlGgAxPc=;
b=qvrZyy/dML3ZaNJBcxCx1mvvnYIYzHuyqdsfTbEykW9uL3kOWXMhQLl00ivY/LnlY0
OHnjfx09VvlDkjO98JRzhfKiUlITyV7czsSkjakJVWnLnNtrCI/xwT1NUBxzxtWvMd58
O4fAs9UxTIY13+CKE64K4VhZmEnrr7kgvbKeJE+U1Vyv7ld+V2jX8Ej1eMTMBZH7YTab
m80KFR4p/+aNBGLQkSPDNws/pCgvoLseG2ERPG8yV7ytzhlLSeflWgCJ8exJrYv+5nEY
w/3LwZNnr+yBfW0eBDmrDL8yTP4pZ/E+KlZH2HSzHBHZQD+2hFFDeR095km3oSK4Er2j
zxFQ==
X-Gm-Message-State: AFeK/H0Qfg9k3Qb6Dco92auNDs4YZxcm4x0qV04RkCuZpbb+RdYQLDKAKWUaF2k+aTxj05k3ThV/aNzcDqX3G34X
X-Received: by 10.36.188.129 with SMTP id n123mr6062091ite.65.1490997908012;
Fri, 31 Mar 2017 15:05:08 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.36.184.70 with HTTP; Fri, 31 Mar 2017 15:05:07 -0700 (PDT)
From: Bram Cohen <bram@bittorrent.com>
Date: Fri, 31 Mar 2017 15:05:07 -0700
Message-ID: <CA+KqGkpa0=O-ob6SsxST6bHwHu9hTnS16wnpNusrbc8nXVEouA@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=94eb2c114564ab1933054c0e00f9
X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, 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: [bitcoin-dev] The TXO bitfield
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: Fri, 31 Mar 2017 22:05:10 -0000
--94eb2c114564ab1933054c0e00f9
Content-Type: text/plain; charset=UTF-8
Looking forward in node scaling we can envision a future in which blocks
are required to come with proofs of their validity and nodes can be run
entirely in memory and never have to hit disk. Ideally we'd like for proofs
to be able to be stored in client wallets which plan to spend their utxos
later, or at least be able to have a full node make a single not terribly
expensive disk access to form the proof which can then be passed along to
other peers.
Such proofs will probably be significantly larger than the blocks they
prove (this is merkle root stuff, not zero knowledge stuff), but if we
accept that as a given then this should be doable, although the details of
how to do it aren't obvious.
This vision can be implemented simply and efficiently by playing some games
with the semantics of the term 'proof'. A proof is a thing which convinces
someone of something. What we've discussed in the past for such proofs
mostly has to do with maintaining a hash root of everything and having
proofs lead to that. This is an extrema of complexity of the proof and
simplicity of the checker, at the expense of forcing the root to be
maintained at all times and the proof to be reasonably fresh. Some tricks
can be applied to keep that problem under control, but there's an
alternative approach where the amount of data necessary to do validation is
much larger but still entirely reasonable to keep in memory, and the sizes
of proofs and their required freshness is much smaller.
In the previous discussion on Merkle sets I commented that insertion
ordering's main practical utility may be that it allows for compression. It
turns out that a constant factor of 256 makes a big difference. Since
there's only really one bit stored for each txo (stored or not) once you
have an insertion ordering you can simply store a bitfield of all txos so
far, which is entirely reasonable to hold in memory, and can be made even
more reasonable by compactifying down the older, mostly spent portions of
it (how best to compress a bitfield while maintaining random access is an
interesting problem but entirely doable).
This approach meets all the design goals, even allowing wallets to remember
their own 'proofs', which are just proofs of insertion ordering. Those
don't even change once the risk of reorgs has passed, so they can be stored
for years without being maintained.
Proofs of insertion ordering can be made by having a canonical way of
calculating a root of position commitments for each block, and nodes
calculate those roots when evaluating the block history and store them all
in memory. A proof of position is a path to one of those roots.
I've intentionally skipped over most of the details here, because it's
probably best to have a high level discussion of this as a general approach
before getting lost in the weeds.
--94eb2c114564ab1933054c0e00f9
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Looking forward in node scaling we can envision a future i=
n which blocks are required to come with proofs of their validity and nodes=
can be run entirely in memory and never have to hit disk. Ideally we'd=
like for proofs to be able to be stored in client wallets which plan to sp=
end their utxos later, or at least be able to have a full node make a singl=
e not terribly expensive disk access to form the proof which can then be pa=
ssed along to other peers.<div><br></div><div>Such proofs will probably be =
significantly larger than the blocks they prove (this is merkle root stuff,=
not zero knowledge stuff), but if we accept that as a given then this shou=
ld be doable, although the details of how to do it aren't obvious.</div=
><div><br></div><div>This vision can be implemented simply and efficiently =
by playing some games with the semantics of the term 'proof'. A pro=
of is a thing which convinces someone of something. What we've discusse=
d in the past for such proofs mostly has to do with maintaining a hash root=
of everything and having proofs lead to that. This is an extrema of comple=
xity of the proof and simplicity of the checker, at the expense of forcing =
the root to be maintained at all times and the proof to be reasonably fresh=
. Some tricks can be applied to keep that problem under control, but there&=
#39;s an alternative approach where the amount of data necessary to do vali=
dation is much larger but still entirely reasonable to keep in memory, and =
the sizes of proofs and their required freshness is much smaller.</div><div=
><br></div><div>In the previous discussion on Merkle sets I commented that =
insertion ordering's main practical utility may be that it allows for c=
ompression. It turns out that a constant factor of 256 makes a big differen=
ce. Since there's only really one bit stored for each txo (stored or no=
t) once you have an insertion ordering you can simply store a bitfield of a=
ll txos so far, which is entirely reasonable to hold in memory, and can be =
made even more reasonable by compactifying down the older, mostly spent por=
tions of it (how best to compress a bitfield while maintaining random acces=
s is an interesting problem but entirely doable).</div><div><br></div><div>=
This approach meets all the design goals, even allowing wallets to remember=
their own 'proofs', which are just proofs of insertion ordering. T=
hose don't even change once the risk of reorgs has passed, so they can =
be stored for years without being maintained.</div><div><br></div><div>Proo=
fs of insertion ordering can be made by having a canonical way of calculati=
ng a root of position commitments for each block, and nodes calculate those=
roots when evaluating the block history and store them all in memory. A pr=
oof of position is a path to one of those roots.</div><div><br></div><div>I=
've intentionally skipped over most of the details here, because it'=
;s probably best to have a high level discussion of this as a general appro=
ach before getting lost in the weeds.</div></div>
--94eb2c114564ab1933054c0e00f9--
|
