MIME-Version: 1.0
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
Subject: Re: [bitcoin-dev] A Commitment-suitable UTXO set "Balances" file
	data structure
Precedence: list

--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=
">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_b=
lank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</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 &quot;piece count&quot; leaf hashes, hash=
ing the balance pieces<br></div><div>- array of &quot;(child layer count + =
1)/2&quot; 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&#39;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&#39;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--