path: root/4e/1b0b67281869c59147b41a94c5ed7e1a06acaa

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 949B6956
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 16 Jun 2016 09:07:47 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f41.google.com (mail-it0-f41.google.com
	[209.85.214.41])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 78FB913D
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 16 Jun 2016 09:07:46 +0000 (UTC)
Received: by mail-it0-f41.google.com with SMTP id i6so23415713ith.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 16 Jun 2016 02:07:46 -0700 (PDT)
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
	:cc; bh=SovlNT4hmdV9ABy7nTHLWRFiy18y0D8pxvv+UUQN+pE=;
	b=yhiD4gFuwwOr4Ua6phhoItq2EUWcfVTAzYPjHe8VE3kyYMZSfB2JijI8BB6FNJAv+8
	X2JLA3HCEVUdnqnshYG95mDL94gjppD4UQ7sLQCcsCZxwKxqrxdTZRh0gM7qQB0DW40W
	4dp1qn7EaZBOxrbXjOJkcTkWNK1VnuhIbX1Vn3gwr9y6xdz8hsx8D4pFp1NUO6qBaO/x
	SGeroBxhOVWQ/mM9tnxuFJGh1iEEiKK1uYshX5OcLuaqiQbMfry8owfSIbquAXw5Bas1
	PxFJx3oDrN18x30+GlEyPRJWqJ3ED1b88FIMe8pfwo1yqjg8M4BbE8FcisT2vfpAoRId
	TGaQ==
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;
	bh=SovlNT4hmdV9ABy7nTHLWRFiy18y0D8pxvv+UUQN+pE=;
	b=Lb16REWI6nmQZWjJa/BLZum2L31i9kUCAn6viCSmJWRh5ZVUvrAFnSvuvLgl84X367
	2UDJNZqdF5ocx2SyOax6KWMKLc9mTeIYu06fzEkcU8w92efqvZFoYr4VX4G0eC7N1E+l
	oEnuUrIC9VQm4nnfgyxzBw8nTmCMr8UWS/MNruEpGJ2OYCmpdeci9r5nr0KpgxOPqZGb
	DRZuMImxMMnk/XrkSq5kRRsz3un7XTENp2Mao/PACmnuy0J2xvvxV4/TuDXdhizIXWJp
	S3PWg44vIsb3oCiat3Vnt/CPf3hHfR6vkE3dgzTmpNL8oMS0mVt1L19g8CCMtYO3yjjH
	YFqQ==
X-Gm-Message-State: ALyK8tLXkvUC+ZQU1xISLvvECokTZ80Yxy2orqQNv+fwcL8MMSL2Hi/I/1CQo9p6X4ziYj8/trRntuLqLXbMoslA
X-Received: by 10.36.149.215 with SMTP id m206mr6178133itd.20.1466068065706;
	Thu, 16 Jun 2016 02:07:45 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.36.134.68 with HTTP; Thu, 16 Jun 2016 02:07:26 -0700 (PDT)
In-Reply-To: <20160616032612.GA7792@fedora-21-dvm>
References: <CA+KqGkosGrWQ2Lpg3Ptc+UyidK7H4_HLQ_QWx2DOAFRmLkv4zQ@mail.gmail.com>
	<20160616001040.GA5026@fedora-21-dvm>
	<CA+KqGkqAHcU2PzEX6OmorXRBQ22eF_QBYYqUDS1v_ZvevhLCuQ@mail.gmail.com>
	<20160616032612.GA7792@fedora-21-dvm>
From: Bram Cohen <bram@bittorrent.com>
Date: Thu, 16 Jun 2016 02:07:26 -0700
Message-ID: <CA+KqGkqA2WnvBEck3kv6p2no-9wzNVCTNA-MGw=Jg=gMGfrxUQ@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=94eb2c05e21a4614a8053561923b
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,HTML_MESSAGE,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkle trees and mountain ranges
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: Thu, 16 Jun 2016 09:07:47 -0000

--94eb2c05e21a4614a8053561923b
Content-Type: text/plain; charset=UTF-8

On Wed, Jun 15, 2016 at 8:26 PM, Peter Todd <pete@petertodd.org> wrote:

> >
> > What do you mean by TXO commitments? If you mean that it only records
> > insertions rather than deletions, then that can do many of the same
> proofs
> > but has no way of proving that something is currently in the UTXO set,
> > which is functionality I'd like to provide.
>
> I think you need to re-read my original post on TXO commitments,
> specifically
> where I say:
>
>     # TXO Commitments
>
>     A merkle tree committing to the state of __all transaction outputs,
> both spent
>     and unspent__, we can provide a method of compactly proving the
> current state of
>     an output.
>
>
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html


Okay, clearly my assumptions about the parts of that post I didn't read
carefully were way off. I'll have to look through it carefully to be able
to make coherent apples to apples comparisons.

> I'm worried that once there's real transaction fees everyone might stop
> > consolidating dust and the set of unspent transactions might grow without
> > bound as well, but that's a topic for another day.
>
> Ok, but then if you're concerned about that risk, why introduce a data
> structure - the STXO set - that's _guaranteed_ to grow without bound?
>

I'm not proposing STXO set commitments either. My point was that there
should be incentives for collecting dust. That has nothing to do with this
thread though and should be discussed separately (also I don't feel like
discussing it because I don't have a good proposal).


> > What I'm making is a patricia trie. Its byte level definition is very
> > similar to the one in your MMR codebase.
>
> Which codebase exactly? I have both a insertion-ordered list (MMR) and a
> key:value mapping (referred to as a "merbinner tree" in the codebase) in
> the
> proofchains codebase. They're very different data structures.
>

I'm talking about your merbinner trees. I read through that part of your
codebase carefully and got the impression that the MMR tree section used it
as a building block.


> > The main differences to your patricia trie are the non-padding sha256 and
> > that each level doesn't hash in a record of its depth and the usage of
> > ONLY0 and ONLY1.
>
> I'm rather confused, as the above sounds nothing like what I've
> implemented,
> which only has leaf nodes, inner nodes, and the special empty node
> singleton,
> for both the MMR and merbinner trees.
>

It's quite a bit like merbinner trees. I've basically taken the leaf nodes
and smushed them into the inner nodes above them, thus saving a hashing
operation and some memory. They're both binary radix trees.

> Technically even a patricia trie utxo commitment can have sub-1 cache
> > misses per update if some of the updates in a single block are close to
> > each other in memory. I think I can get practical Bitcoin updates down
> to a
> > little bit less than one l2 cache miss per update, but not a lot less.
>
> I'm very confused as to why you think that's possible. When you say
> "practical
> Bitcoin updates", what exactly is the data structure you're proposing to
> update? How is it indexed?


My calculations are: a Bitcoin block contains about 2000 updates. The l2
cache is about 256 kilobytes, and if an update is about 32 bytes times two
for the parents, grandparents, etc. then an l2 cache can contain about 4000
values. If the current utxo size is about 2000 * 4000 = 8,000,000 in size
then about half the pages which contain a transaction will contain a second
one. I think the utxo set is currently about an order of magnitude greater
than that, so the number of such collisions will be fairly mall, hence my
'less than one but not a lot less' comment.

As for how it's indexed, at a crypto definition level it's just a binary
radix tree. In terms of how it's indexed in memory, that involves some
optimizations to avoid cache misses. Memory is allocated into blocks of
about the size of an 12 cache (or maybe an l1 cache, it will require some
testing and optimization). Blocks are either branch blocks, which keep
everything in fixed positions, or leaf blocks, which contain fixed size
entries for nodes plus indexes within the same leaf block of their
children. Branch blocks can have many children which can be either branch
blocks or leaf blocks, but typically are either all branch blocks or all
leaf blocks. Branch blocks always have exactly one parent. Leaf blocks
always have all their inputs come from a single branch block, but there can
be multiple ones of those. When a branch block overflows it first tries to
put stuff into the last leaf block it used, and if there's no more room it
allocates a new one. It's fairly common for branches to have just a few
leaf children, but they also could have a lot, depending on whether the
base 2 log of the number of things currently in the set modulo the number
levels in a branch is a small number.

Usually when an update is done it consists of first checking the
appropriate output of the root block (it's jumped to directly to avoid
unnecessary memory lookups. If there's nothing there the algorithm will
walk back until it finds something.) That leads directly to (usually)
another branch whose output is jumped to directly again. At Bitcoin utxo
set sizes that will usually lead to a leaf block, which is then walked down
manually to find the actual terminal node, which is then updated, and the
parent, grandparent, etc. is then marked invalid until something which was
already marked invalid is hit, and it exits. Calculation of hash values is
done lazily.

--94eb2c05e21a4614a8053561923b
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 W=
ed, Jun 15, 2016 at 8:26 PM, Peter Todd <span dir=3D"ltr">&lt;<a href=3D"ma=
ilto:pete@petertodd.org" target=3D"_blank">pete@petertodd.org</a>&gt;</span=
> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo=
rder-left:1px #ccc solid;padding-left:1ex"><span class=3D"">&gt;<br>
&gt; What do you mean by TXO commitments? If you mean that it only records<=
br>
&gt; insertions rather than deletions, then that can do many of the same pr=
oofs<br>
&gt; but has no way of proving that something is currently in the UTXO set,=
<br>
&gt; which is functionality I&#39;d like to provide.<br>
<br>
</span>I think you need to re-read my original post on TXO commitments, spe=
cifically<br>
where I say:<br>
<br>
=C2=A0 =C2=A0 # TXO Commitments<br>
<br>
=C2=A0 =C2=A0 A merkle tree committing to the state of __all transaction ou=
tputs, both spent<br>
=C2=A0 =C2=A0 and unspent__, we can provide a method of compactly proving t=
he current state of<br>
=C2=A0 =C2=A0 an output.<br>
<br>
<a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May=
/012715.html" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfound=
ation.org/pipermail/bitcoin-dev/2016-May/012715.html</a></blockquote><div><=
br></div><div>Okay, clearly my assumptions about the parts of that post I d=
idn&#39;t read carefully were way off. I&#39;ll have to look through it car=
efully to be able to make coherent apples to apples comparisons.</div><div>=
<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bord=
er-left:1px #ccc solid;padding-left:1ex"><span class=3D"">&gt; I&#39;m worr=
ied that once there&#39;s real transaction fees everyone might stop<br>
&gt; consolidating dust and the set of unspent transactions might grow with=
out<br>
&gt; bound as well, but that&#39;s a topic for another day.<br>
<br>
</span>Ok, but then if you&#39;re concerned about that risk, why introduce =
a data<br>
structure - the STXO set - that&#39;s _guaranteed_ to grow without bound?<b=
r></blockquote><div><br></div><div>I&#39;m not proposing STXO set commitmen=
ts either. My point was that there should be incentives for collecting dust=
. That has nothing to do with this thread though and should be discussed se=
parately (also I don&#39;t feel like discussing it because I don&#39;t have=
 a good proposal).</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" =
style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><sp=
an class=3D"">&gt; What I&#39;m making is a patricia trie. Its byte level d=
efinition is very<br>
&gt; similar to the one in your MMR codebase.<br>
<br>
</span>Which codebase exactly? I have both a insertion-ordered list (MMR) a=
nd a<br>
key:value mapping (referred to as a &quot;merbinner tree&quot; in the codeb=
ase) in the<br>
proofchains codebase. They&#39;re very different data structures.<br></bloc=
kquote><div><br></div><div>I&#39;m talking about your merbinner trees. I re=
ad through that part of your codebase carefully and got the impression that=
 the MMR tree section used it as a building block.</div><div>=C2=A0</div><b=
lockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px =
#ccc solid;padding-left:1ex"><span class=3D"">&gt; The main differences to =
your patricia trie are the non-padding sha256 and<br>
&gt; that each level doesn&#39;t hash in a record of its depth and the usag=
e of<br>
&gt; ONLY0 and ONLY1.<br>
<br>
</span>I&#39;m rather confused, as the above sounds nothing like what I&#39=
;ve implemented,<br>
which only has leaf nodes, inner nodes, and the special empty node singleto=
n,<br>
for both the MMR and merbinner trees.<br></blockquote><div><br></div><div>I=
t&#39;s quite a bit like merbinner trees. I&#39;ve basically taken the leaf=
 nodes and smushed them into the inner nodes above them, thus saving a hash=
ing operation and some memory. They&#39;re both binary radix trees.</div><d=
iv><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;b=
order-left:1px #ccc solid;padding-left:1ex"><span class=3D"">&gt; Technical=
ly even a patricia trie utxo commitment can have sub-1 cache<br>
&gt; misses per update if some of the updates in a single block are close t=
o<br>
&gt; each other in memory. I think I can get practical Bitcoin updates down=
 to a<br>
&gt; little bit less than one l2 cache miss per update, but not a lot less.=
<br>
<br>
</span>I&#39;m very confused as to why you think that&#39;s possible. When =
you say &quot;practical<br>
Bitcoin updates&quot;, what exactly is the data structure you&#39;re propos=
ing to<br>
update? How is it indexed?</blockquote><div><br></div><div>My calculations =
are: a Bitcoin block contains about 2000 updates. The l2 cache is about 256=
 kilobytes, and if an update is about 32 bytes times two for the parents, g=
randparents, etc. then an l2 cache can contain about 4000 values. If the cu=
rrent utxo size is about 2000 * 4000 =3D 8,000,000 in size then about half =
the pages which contain a transaction will contain a second one. I think th=
e utxo set is currently about an order of magnitude greater than that, so t=
he number of such collisions will be fairly mall, hence my &#39;less than o=
ne but not a lot less&#39; comment.</div><div><br></div><div>As for how it&=
#39;s indexed, at a crypto definition level it&#39;s just a binary radix tr=
ee. In terms of how it&#39;s indexed in memory, that involves some optimiza=
tions to avoid cache misses. Memory is allocated into blocks of about the s=
ize of an 12 cache (or maybe an l1 cache, it will require some testing and =
optimization). Blocks are either branch blocks, which keep everything in fi=
xed positions, or leaf blocks, which contain fixed size entries for nodes p=
lus indexes within the same leaf block of their children. Branch blocks can=
 have many children which can be either branch blocks or leaf blocks, but t=
ypically are either all branch blocks or all leaf blocks. Branch blocks alw=
ays have exactly one parent. Leaf blocks always have all their inputs come =
from a single branch block, but there can be multiple ones of those. When a=
 branch block overflows it first tries to put stuff into the last leaf bloc=
k it used, and if there&#39;s no more room it allocates a new one. It&#39;s=
 fairly common for branches to have just a few leaf children, but they also=
 could have a lot, depending on whether the base 2 log of the number of thi=
ngs currently in the set modulo the number levels in a branch is a small nu=
mber.</div><div><br></div><div>Usually when an update is done it consists o=
f first checking the appropriate output of the root block (it&#39;s jumped =
to directly to avoid unnecessary memory lookups. If there&#39;s nothing the=
re the algorithm will walk back until it finds something.) That leads direc=
tly to (usually) another branch whose output is jumped to directly again. A=
t Bitcoin utxo set sizes that will usually lead to a leaf block, which is t=
hen walked down manually to find the actual terminal node, which is then up=
dated, and the parent, grandparent, etc. is then marked invalid until somet=
hing which was already marked invalid is hit, and it exits. Calculation of =
hash values is done lazily.</div><div><br></div><div>=C2=A0</div></div></di=
v></div>

--94eb2c05e21a4614a8053561923b--