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
|
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 98EF8959
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 8 Mar 2017 01:55:20 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f44.google.com (mail-it0-f44.google.com
[209.85.214.44])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 07E9F139
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 8 Mar 2017 01:55:19 +0000 (UTC)
Received: by mail-it0-f44.google.com with SMTP id m27so17727363iti.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 07 Mar 2017 17:55:19 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=bittorrent-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to;
bh=x2zsrJoRwmQc+BpFaZR6Ke48oN/EO621E1Gh5LJqSfA=;
b=Qv8g01q2R2V7gr/DD7T5mR+QOk0dWNXMpqo5pQUOyikPnuU0X+T2PzXfnbzfBayn5t
jz3p7kCiIqo3UJ1etNjfEx1Jl++Bm3I7OIJgIrHIPknqTdBgfeE3FfvcRkFEOYWg6v9m
BnwtiMZBuRhhvneivjW53g/5ZPq2lhSZ2dpXZf5bMT6lsVHFV0T11/Mr+k1RRFwIHZ6I
+Xqa8m/RMZcOei7+Pr4P4uBS3irK3ZJMIlVVVxV6Xn9CHFC5MlSV0z71LO31/VQBCcEA
oW7cXVb7S7ntoc4QKty0bfGZeyyrwLn2GIbJYT+DAA9K0/sFiueGsn8dm5FnazKYsO2K
j2pA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to;
bh=x2zsrJoRwmQc+BpFaZR6Ke48oN/EO621E1Gh5LJqSfA=;
b=jLVm73uavZiJ4qGJzqhV6tepMeAXzsAB8rgL010sMb7U82UFzz6ai6RO5WHjIIIEzc
5Ot1W26WCyGWgMIGN1NXLftxJT2kmhTMkR8RQzzALR0JCaRSaIBnjp/8m+n9TKmgPSPl
X1a7mx37UBEj05p441GVnVWDJPqzXlDRGsu+DxcsBltKa8ThdcsWBAhz/ZryxpVc0swQ
gc9ddU9CI/zdrhkFEEwrlQ6bIeTjOBareaky+LxOh75Eg9m3TrzcNdX3hSW9KGnefuza
3vHsWv/dYRDfD4dTg+zSN+bUpUCFtkAZNILZfX5gzelysGvvpDMUnQSpjYndzcDwZ8FS
ayiw==
X-Gm-Message-State: AMke39nhC8BOu8mE71fK75X9SLp6/zk+sIkOkeJGEHgVIs76fXT7l+oB/vsdMfes4hVl4wuBNgcpKV7FcNVHCjak
X-Received: by 10.36.196.8 with SMTP id v8mr23422130itf.115.1488938119362;
Tue, 07 Mar 2017 17:55:19 -0800 (PST)
MIME-Version: 1.0
Received: by 10.36.254.132 with HTTP; Tue, 7 Mar 2017 17:55:18 -0800 (PST)
In-Reply-To: <_Z0S6yfN2uS1b0SYoZzU9LMo3QQ967dyn0e12ep_aXJ8cNw8wTovQWED6mKg3PH0hb2yKEG-5Cv0xH3IC2cG5rczP5qo-xLtrjJMXW1uCss=@protonmail.com>
References: <_Z0S6yfN2uS1b0SYoZzU9LMo3QQ967dyn0e12ep_aXJ8cNw8wTovQWED6mKg3PH0hb2yKEG-5Cv0xH3IC2cG5rczP5qo-xLtrjJMXW1uCss=@protonmail.com>
From: Bram Cohen <bram@bittorrent.com>
Date: Tue, 7 Mar 2017 17:55:18 -0800
Message-ID: <CA+KqGkp7hLDNFjzWUTU7_FSCnHBAw+79SURAFo8V62BaMpdzhQ@mail.gmail.com>
To: praxeology_guy <praxeology_guy@protonmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=94eb2c05d0d4b2abc9054a2e6b75
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_LOW,
RCVD_IN_SORBS_SPAM 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] A Commitment-suitable UTXO set "Balances" file
data structure
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, 08 Mar 2017 01:55:20 -0000
--94eb2c05d0d4b2abc9054a2e6b75
Content-Type: text/plain; charset=UTF-8
On Tue, Mar 7, 2017 at 1:28 PM, praxeology_guy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> merkle tree hashes:
> - array of "piece count" leaf hashes, hashing the balance pieces
> - array of "(child layer count + 1)/2" node hashes, hashing pairs of child
> hashes, or copying up if only one child
> - repeat ^ until the root hash is written
> ... except reverse the layer order. In other words, it should be breadth
> first.
>
A big yuck on that format. It should be something based on a patricia trie
to support incremental updates. Also if the things being stored are output
transaction + output number then those two can be hashed together to make a
consistent size identifier and be put into the merkle set format I
proposed, which is exactly the intended usage:
https://github.com/bramcohen/MerkleSet
- We could make BCP 4383 blocks, which would be 12 times per year, given
> block period was exactly 10 minutes. But since block period is not exactly
> 10 minutes, and file names generated with period 4283 are much less
> comprehensible than file names generated with period 5000... I propose
> 5000.
>
If it's of that order it should be synched up with the work difficulty
reset interval of 2016. If the format supports incremental updates it would
of course be possible to require them more frequently later.
> - Having a shorter BCP period would result in more frequent checks on UTXO
> set integrity, and permit new pruning nodes to start synching closer to the
> tip. But it may require nodes to keep more copies of the balances file to
> satisfy the same backup period, and require more background work of
> creating more balances files.
>
With a patricia based format it would be possible to make much more common
utxo commitments, possibly as often as every block only trailing by a few,
and the cost of updating wouldn't be onerous and reorgs could be handled by
simply undoing the last few transactions in the set and and then rolling
forward.
--94eb2c05d0d4b2abc9054a2e6b75
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On T=
ue, Mar 7, 2017 at 1:28 PM, praxeology_guy via bitcoin-dev <span dir=3D"ltr=
"><<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_b=
lank">bitcoin-dev@lists.linuxfoundation.org</a>></span> wrote:<br><block=
quote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1=
px solid rgb(204,204,204);padding-left:1ex"><div><br></div><div>merkle tree=
hashes:<br></div><div>- array of "piece count" leaf hashes, hash=
ing the balance pieces<br></div><div>- array of "(child layer count + =
1)/2" node hashes, hashing pairs of child hashes, or copying up if onl=
y one child<br></div><div>- repeat ^ until the root hash is written<br></di=
v><div>... except reverse the layer order. In other words, it should be bre=
adth first.<br></div></blockquote><div><br></div><div>A big yuck on that fo=
rmat. It should be something based on a patricia trie to support incrementa=
l updates. Also if the things being stored are output transaction + output =
number then those two can be hashed together to make a consistent size iden=
tifier and be put into the merkle set format I proposed, which is exactly t=
he intended usage: <a href=3D"https://github.com/bramcohen/MerkleSet">https=
://github.com/bramcohen/MerkleSet</a></div><div><br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex"><div>- We could make BCP 4383 blocks, whic=
h would be 12 times per year, given block period was exactly 10 minutes.=C2=
=A0 But since block period is not exactly 10 minutes, and file names genera=
ted with period 4283 are much less comprehensible than file names generated=
with period 5000...=C2=A0 I propose 5000.<br></div></blockquote><div><br><=
/div><div>If it's of that order it should be synched up with the work d=
ifficulty reset interval of 2016. If the format supports incremental update=
s it would of course be possible to require them more frequently later.</di=
v><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0p=
x 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><=
/div><div>- Having a shorter BCP period would result in more frequent check=
s on UTXO set integrity, and permit new pruning nodes to start synching clo=
ser to the tip.=C2=A0 But it may require nodes to keep more copies of the b=
alances file to satisfy the same backup period, and require more background=
work of creating more balances files.<br></div></blockquote><div><br></div=
><div><div>With a patricia based format it would be possible to make much m=
ore common utxo commitments, possibly as often as every block only trailing=
by a few, and the cost of updating wouldn't be onerous and reorgs coul=
d be handled by simply undoing the last few transactions in the set and and=
then rolling forward.</div><div><br></div></div></div></div></div>
--94eb2c05d0d4b2abc9054a2e6b75--
|
