MIME-Version: 1.0
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: Fri, 17 Jun 2016 20:22:04 -0700
Message-ID: <CA+KqGko2jW9999A9vkkBrM3EPb5OXYe4OPu0_Ot=fGnc7Cge-Q@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=001a113f970ad5eda4053584fa92
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkle trees and mountain ranges
Precedence: list

--001a113f970ad5eda4053584fa92
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:
>
> > The fundamental approach to handling the latency problem is to have the
> > utxo commitments trail a bit. Computing utxo commitments takes a certain
> > amount of time, too much to hold up block propagation but still hopefully
> > vastly less than the average amount of time between blocks. Trailing by a
> > single block is probably a bad idea because you sometimes get blocks back
> > to back, but you never get blocks back to back to back to back. Having
> the
> > utxo set be trailing by a fixed amount - five blocks is probably
> excessive
> > - would do a perfectly good job of keeping latency from every becoming an
> > issue. Smaller commitments for the utxos added and removed in each block
> > alone could be added without any significant performance penalty. That
> way
> > all blocks would have sufficient commitments for a completely up to date
> > proofs of inclusion and exclusion. This is not a controversial approach.
>
> Agreed - regardless of approach adding latency to commitment calculations
> of
> all kinds is something I think we all agree can work in principle, although
> obviously it should be a last resort technique when optimization fails.
>

An important point: Adding latency to utxo commitments does not imply
latency to proofs of inclusion and exclusion! If roots of what's added and
deleted in each block are added as well, then a proof of inclusion can be
done by having a proof of inclusion of the trailing utxo set followed by a
proof of exclusion from all the following deletion sets, or a proof of
inclusion in one of the single block addition sets followed by proofs of
exclusion from all the more recent deletion sets. Likewise a proof of
exclusion can be a proof of exclusion from the utxo set followed by proofs
of exclusion from all the more recent addition sets or a single proof of
inclusion in a recent deletion set.

This does make proofs larger (except in the case of recent deletions and
maybe recent additions) and adds complexity, so it shouldn't be done unless
necessary. But validation before block propagation needs to be extremely
fast, so for utxo roots this trick is probably both necessary and
sufficient.

--001a113f970ad5eda4053584fa92
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></span><spa=
n class=3D""><br>
&gt; The fundamental approach to handling the latency problem is to have th=
e<br>
&gt; utxo commitments trail a bit. Computing utxo commitments takes a certa=
in<br>
&gt; amount of time, too much to hold up block propagation but still hopefu=
lly<br>
&gt; vastly less than the average amount of time between blocks. Trailing b=
y a<br>
&gt; single block is probably a bad idea because you sometimes get blocks b=
ack<br>
&gt; to back, but you never get blocks back to back to back to back. Having=
 the<br>
&gt; utxo set be trailing by a fixed amount - five blocks is probably exces=
sive<br>
&gt; - would do a perfectly good job of keeping latency from every becoming=
 an<br>
&gt; issue. Smaller commitments for the utxos added and removed in each blo=
ck<br>
&gt; alone could be added without any significant performance penalty. That=
 way<br>
&gt; all blocks would have sufficient commitments for a completely up to da=
te<br>
&gt; proofs of inclusion and exclusion. This is not a controversial approac=
h.<br>
<br>
</span>Agreed - regardless of approach adding latency to commitment calcula=
tions of<br>
all kinds is something I think we all agree can work in principle, although=
<br>
obviously it should be a last resort technique when optimization fails.<br>=
</blockquote><div><br></div><div>An important point: Adding latency to utxo=
 commitments does not imply latency to proofs of inclusion and exclusion! I=
f roots of what&#39;s added and deleted in each block are added as well, th=
en a proof of inclusion can be done by having a proof of inclusion of the t=
railing utxo set followed by a proof of exclusion from all the following de=
letion sets, or a proof of inclusion in one of the single block addition se=
ts followed by proofs of exclusion from all the more recent deletion sets. =
Likewise a proof of exclusion can be a proof of exclusion from the utxo set=
 followed by proofs of exclusion from all the more recent addition sets or =
a single proof of inclusion in a recent deletion set.</div><div><br></div><=
div>This does make proofs larger (except in the case of recent deletions an=
d maybe recent additions) and adds complexity, so it shouldn&#39;t be done =
unless necessary. But validation before block propagation needs to be extre=
mely fast, so for utxo roots this trick is probably both necessary and suff=
icient.</div><div><br></div></div></div></div>

--001a113f970ad5eda4053584fa92--