path: root/6f/abcac3a82d1e142d7c8a9aa309299af40d96df

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 3179B3EE
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 16 Jun 2016 01:16:48 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-io0-f172.google.com (mail-io0-f172.google.com
	[209.85.223.172])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1BACE1A9
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 16 Jun 2016 01:16:47 +0000 (UTC)
Received: by mail-io0-f172.google.com with SMTP id t74so29257755ioi.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 15 Jun 2016 18:16:47 -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=NUdX1KXK2I97NEdBImHYkxrqiMe3Hwt38qF52PCe2Gk=;
	b=nf42RPTmOglNDnrNrJGkT+nALA8CFN9+rmaoXsHBWWDDMYoAwqN0ZKDOVx7lvtcFXt
	19AVwuwFNzFfT8isR5UfP8IVPqHfQprj+C5jKkSngTW2tsiduesznP6A4kuwLa0wyZtq
	0GS92yPDICU0ygw+03V1YSgj0HV0fdMhP/FzoV62+y3Klgd/3ZvNtKQqQ/tEU40plwFt
	VfExL7ing/ZNnbX4kTgPXfTEhz0gOBfxyvMPjeFq1W2jr7sjICHdTlRvpezF7kJWJt4r
	erpCn8yTauJmsCxtCJS4mtNtyBRn+L3IQwMs6RwqgmvL1DB1c644CR3mWwcWUx3ZZ0NZ
	D8Hw==
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=NUdX1KXK2I97NEdBImHYkxrqiMe3Hwt38qF52PCe2Gk=;
	b=CsPGz3NowC6qf5AvM2Cb5uFokPN7ckdtwQBLjZRhoSgGN6Rf8hGGa4pEIcBvfoD5Y+
	Mm1Au7+vtl17sOpQMMg5jnbzAU/FYlwOYGu18ZvGgebrl1++SU+li81qpI37BJuTeZ/r
	dFLHQwQLD+XTKxChYnSXb4gl3gMe2jo8Lh4azPHkrhpUi/pMIBqbHJ0nLz5iD9G3PiL/
	gI0+xmVbPAsruri99yyFMupkL+fN5Z5eUTDR3RMz09f1UYM/7XleFXRtmPD6lyGsohcF
	kecshBWqw+3zTvgHHlRedB5hSgAAEmrBXPm9pmtDaNslIhPi64/UUpX6gjLJak74RQ76
	i20g==
X-Gm-Message-State: ALyK8tKahI8X6p4gpcJuTzJttBzD7EcP1CK6sSMcepuqoprU/RFnmaYgNCmHbfYS0hwidZBpW9+NWwkNavTNyrHe
X-Received: by 10.107.205.8 with SMTP id d8mr3648697iog.113.1466039806307;
	Wed, 15 Jun 2016 18:16:46 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.36.134.68 with HTTP; Wed, 15 Jun 2016 18:16:26 -0700 (PDT)
In-Reply-To: <20160616001040.GA5026@fedora-21-dvm>
References: <CA+KqGkosGrWQ2Lpg3Ptc+UyidK7H4_HLQ_QWx2DOAFRmLkv4zQ@mail.gmail.com>
	<20160616001040.GA5026@fedora-21-dvm>
From: Bram Cohen <bram@bittorrent.com>
Date: Wed, 15 Jun 2016 18:16:26 -0700
Message-ID: <CA+KqGkqAHcU2PzEX6OmorXRBQ22eF_QBYYqUDS1v_ZvevhLCuQ@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=94eb2c1880dce1cb0805355afde8
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 01:16:48 -0000

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

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

> On Tue, Jun 14, 2016 at 05:14:23PM -0700, Bram Cohen via bitcoin-dev wrote:
> >
> > Peter proposes that there should be both UTXO and STXO commitments, and
>
> No, that's incorrect - I'm only proposing TXO commitments, not UTXO nor
> STXO
> commitments.
>

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.

When I say 'merkle tree' what I mean is a patricia trie. What I assume is
meant by a merkle mountain range is a series of patricia tries of
decreasing size each of which is an addition to the previous one, and
they're periodically consolidated into larger tries so the old ones can go
away. This data structure has the nice property that it's both in sorted
order and has less than one cache miss per operation because the
consolidation operations can be batched and done linearly. There are a
number of different things you could be describing if I misunderstood.


> I'm not proposing STXO commitments precisely because the set of _spent_
> transactions grows without bound.


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.


> > Now I'm going to go out on a limb. My thesis is that usage of a mountain
> > range is unnecessary, and that a merkle tree in the raw can be made
> > serviceable by sprinkling magic pixie dust on the performance problem.
>
> It'd help if you specified exactly what type of merkle tree you're talking
> about here; remember that the certificate transparency RFC appears to have
> reinvented merkle mountain ranges, and they call them "merkle trees".
> Bitcoin
> meanwhile uses a so-called "merkle tree" that's broken, and Zcash uses a
> partially filled fixed-sized perfect tree.
>

What I'm making is a patricia trie. Its byte level definition is very
similar to the one in your MMR codebase.

Each level of the tree has a single metadata byte and followed by two
hashes. The hashes are truncated by one byte and the hash function is a
non-padding variant of sha256 (right now it's just using regular sha256,
but that's a nice optimization which allows everything to fit in a single
block).

The possible metadata values are: TERM0, TERM1, TERMBOTH, ONLY0, ONLY1,
MIDDLE. They mean:

TERM0, TERM1: There is a single thing in the tree on the specified side.
The thing hashed on that side is that thing verbatim. The other side has
more than one thing and the hash of it is the root of everything below.

TERMBOTH: There are exactly two things below and they're included inline.
Note that two things is a special case, if there are more you sometimes
have ONLY0 or ONLY1.

ONLY0, ONLY1: There are more than two things below and they're all on the
same side. This makes proofs of inclusion and exclusion simpler, and makes
some implementation details easier, for example there's always something at
every level with perfect memory positioning. It doesn't cause much extra
memory usage because of the TERMBOTH exception for exactly two things.

MIDDLE: There two or more things on both sides.

There's also a SINGLETON special case for a tree which contains only one
thing, and an EMPTY special value for tree which doesn't contain anything.

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.


>
> > There are two causes of performance problems for merkle trees: hashing
> > operations and memory cache misses. For hashing functions, the difference
> > between a mountain range and a straight merkle tree is roughly that in a
> > mountain range there's one operation for each new update times the number
> > of times that thing will get merged into larger hills. If there are fewer
> > levels of hills the number of operations is less but the expense of proof
> > of inclusion will be larger. For raw merkle trees the number of
> operations
> > per thing added is the log base 2 of the number of levels in the tree,
> > minus the log base 2 of the number of things added at once since you can
> do
> > lazy evaluation. For practical Bitcoin there are (very roughly) a million
> > things stored, or 20 levels, and there are (even more roughly) about a
> > thousand things stored per block, so each thing forces about 20 - 10 = 10
> > operations. If you follow the fairly reasonable guideline of mountain
> range
> > hills go up by factors of four, you instead have 20/2 = 10 operations per
> > thing added amortized. Depending on details this comparison can go either
> > way but it's roughly a wash and the complexity of a mountain range is
> > clearly not worth it at least from the point of view of CPU costs.
>
> I'm having a hard time understanding this paragraph; could you explain
> what you
> think is happening when things are "merged into larger hills"?
>

I'm talking about the recalculation of mountain tips, assuming we're on the
same page about what 'MMR' means.


> As UTXO/STXO/TXO sets are all enormously larger than L1/L2 cache, it's
> impossible to get CPU cache misses below one for update operations. The
> closest
> thing to an exception is MMR's, which due to their insertion-ordering could
> have good cache locality for appends, in the sense that the mountain tips
> required to recalculate the MMR tip digest will already be in cache from
> the
> previous append. But that's not sufficient, as you also need to modify old
> TXO's further back in the tree to mark them as spent - that data is going
> to be
> far larger than L1/L2 cache.
>

This makes me think we're talking about subtly different things for MMRs.
The ones I described above have sub-1 cache miss per update due to the
amortized merging together of old mountains.

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.

--94eb2c1880dce1cb0805355afde8
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 5:10 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"">On Tue, Jun 14,=
 2016 at 05:14:23PM -0700, Bram Cohen via bitcoin-dev wrote:<br>&gt;<br>
&gt; Peter proposes that there should be both UTXO and STXO commitments, an=
d<br>
<br>
</span>No, that&#39;s incorrect - I&#39;m only proposing TXO commitments, n=
ot UTXO nor STXO<br>
commitments.<br></blockquote><div><br></div><div>What do you mean by TXO co=
mmitments? If you mean that it only records insertions rather than deletion=
s, 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&#39;d like=
 to provide.</div><div><br></div><div>When I say &#39;merkle tree&#39; what=
 I mean is a patricia trie. What I assume is meant by a merkle mountain ran=
ge is a series of patricia tries of decreasing size each of which is an add=
ition to the previous one, and they&#39;re periodically consolidated into l=
arger tries so the old ones can go away. This data structure has the nice p=
roperty that it&#39;s both in sorted order and has less than one cache miss=
 per operation because the consolidation operations can be batched and done=
 linearly. There are a number of different things you could be describing i=
f I misunderstood.</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">I&#=
39;m not proposing STXO commitments precisely because the set of _spent_<br=
>
transactions grows without bound. </blockquote><div><br></div><div>I&#39;m =
worried that once there&#39;s real transaction fees everyone might stop con=
solidating dust and the set of unspent transactions might grow without boun=
d as well, but that&#39;s a topic for another day.</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; Now I&#39;m going to go =
out on a limb. My thesis is that usage of a mountain<br>
&gt; range is unnecessary, and that a merkle tree in the raw can be made<br=
>
&gt; serviceable by sprinkling magic pixie dust on the performance problem.=
<br>
<br>
</span>It&#39;d help if you specified exactly what type of merkle tree you&=
#39;re talking<br>
about here; remember that the certificate transparency RFC appears to have<=
br>
reinvented merkle mountain ranges, and they call them &quot;merkle trees&qu=
ot;.=C2=A0 Bitcoin<br>
meanwhile uses a so-called &quot;merkle tree&quot; that&#39;s broken, and Z=
cash uses a<br>
partially filled fixed-sized perfect tree.<br></blockquote><div><br></div><=
div>What I&#39;m making is a patricia trie. Its byte level definition is ve=
ry similar to the one in your MMR codebase.</div><div><br></div><div>Each l=
evel of the tree has a single metadata byte and followed by two hashes. The=
 hashes are truncated by one byte and the hash function is a non-padding va=
riant of sha256 (right now it&#39;s just using regular sha256, but that&#39=
;s a nice optimization which allows everything to fit in a single block).</=
div><div><br></div><div>The possible metadata values are: TERM0, TERM1, TER=
MBOTH, ONLY0, ONLY1, MIDDLE. They mean:</div><div><br></div><div>TERM0, TER=
M1: There is a single thing in the tree on the specified side. The thing ha=
shed on that side is that thing verbatim. The other side has more than one =
thing and the hash of it is the root of everything below.</div><div><br></d=
iv><div>TERMBOTH: There are exactly two things below and they&#39;re includ=
ed inline. Note that two things is a special case, if there are more you so=
metimes have ONLY0 or ONLY1.</div><div><br></div><div>ONLY0, ONLY1: There a=
re more than two things below and they&#39;re all on the same side. This ma=
kes proofs of inclusion and exclusion simpler, and makes some implementatio=
n details easier, for example there&#39;s always something at every level w=
ith perfect memory positioning. It doesn&#39;t cause much extra memory usag=
e because of the TERMBOTH exception for exactly two things.</div><div><br><=
/div><div>MIDDLE: There two or more things on both sides.</div><div><br></d=
iv><div>There&#39;s also a SINGLETON special case for a tree which contains=
 only one thing, and an EMPTY special value for tree which doesn&#39;t cont=
ain anything.</div><div><br></div><div>The main differences to your patrici=
a trie are the non-padding sha256 and that each level doesn&#39;t hash in a=
 record of its depth and the usage of ONLY0 and ONLY1.</div><div>=C2=A0</di=
v><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:=
1px #ccc solid;padding-left:1ex">
<span class=3D""><br>
&gt; There are two causes of performance problems for merkle trees: hashing=
<br>
&gt; operations and memory cache misses. For hashing functions, the differe=
nce<br>
&gt; between a mountain range and a straight merkle tree is roughly that in=
 a<br>
&gt; mountain range there&#39;s one operation for each new update times the=
 number<br>
&gt; of times that thing will get merged into larger hills. If there are fe=
wer<br>
&gt; levels of hills the number of operations is less but the expense of pr=
oof<br>
&gt; of inclusion will be larger. For raw merkle trees the number of operat=
ions<br>
&gt; per thing added is the log base 2 of the number of levels in the tree,=
<br>
&gt; minus the log base 2 of the number of things added at once since you c=
an do<br>
&gt; lazy evaluation. For practical Bitcoin there are (very roughly) a mill=
ion<br>
&gt; things stored, or 20 levels, and there are (even more roughly) about a=
<br>
&gt; thousand things stored per block, so each thing forces about 20 - 10 =
=3D 10<br>
&gt; operations. If you follow the fairly reasonable guideline of mountain =
range<br>
&gt; hills go up by factors of four, you instead have 20/2 =3D 10 operation=
s per<br>
&gt; thing added amortized. Depending on details this comparison can go eit=
her<br>
&gt; way but it&#39;s roughly a wash and the complexity of a mountain range=
 is<br>
&gt; clearly not worth it at least from the point of view of CPU costs.<br>
<br>
</span>I&#39;m having a hard time understanding this paragraph; could you e=
xplain what you<br>
think is happening when things are &quot;merged into larger hills&quot;?<br=
></blockquote><div><br></div><div>I&#39;m talking about the recalculation o=
f mountain tips, assuming we&#39;re on the same page about what &#39;MMR&#3=
9; means.<br></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">As UTXO/=
STXO/TXO sets are all enormously larger than L1/L2 cache, it&#39;s<br>
impossible to get CPU cache misses below one for update operations. The clo=
sest<br>
thing to an exception is MMR&#39;s, which due to their insertion-ordering c=
ould<br>
have good cache locality for appends, in the sense that the mountain tips<b=
r>
required to recalculate the MMR tip digest will already be in cache from th=
e<br>
previous append. But that&#39;s not sufficient, as you also need to modify =
old<br>
TXO&#39;s further back in the tree to mark them as spent - that data is goi=
ng to be<br>
far larger than L1/L2 cache.<br></blockquote><div><br></div><div>This makes=
 me think we&#39;re talking about subtly different things for MMRs. The one=
s I described above have sub-1 cache miss per update due to the amortized m=
erging together of old mountains.</div><div><br></div><div>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 on=
e l2 cache miss per update, but not a lot less.</div></div></div></div>

--94eb2c1880dce1cb0805355afde8--