MIME-Version: 1.0
In-Reply-To: <20170223011506.GC905@savin.petertodd.org>
References: <20170223011506.GC905@savin.petertodd.org>
From: Bram Cohen <bram@bittorrent.com>
Date: Wed, 22 Feb 2017 19:07:08 -0800
Message-ID: <CA+KqGkqXmWgyU+4ZaR9w7e3xVBUyWwAixVAEzT9hT8V_1kwnuw@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=001a114401829b44c9054929e8d0
Subject: Re: [bitcoin-dev] A Better MMR Definition
Precedence: list

--001a114401829b44c9054929e8d0
Content-Type: text/plain; charset=UTF-8

On Wed, Feb 22, 2017 at 5:15 PM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> With that, notice how proving the soundness of the proofs becomes trivial:
> if
> validation is deterministic, it is obviously impossible to construct two
> different proofs that prove contradictory statements, because a proof is
> simply
> part of the data structure itself. Contradiction would imply that the two
> proofs are different, but that's easily rejected by simply checking the
> hash of
> the data.
>

My code works this way. Proofs are serialization of a subset of the tree,
and to validate a proof you ask a single function whether a particular
value is included in that tree subset, and it answers yes or no, so
obviously it's impossible for a single value to both validate and not
validate. The proof code was quite terrifying before I made this change
(which I did on your suggestion), and it's much cleaner and simpler now. It
also in principle supports compact proofs of multiple inclusions and
exclusions in the same serialization of a subset of the tree because the
upper branches won't have to be repeated. I haven't written code for
generating those, but the validation code will happily accept them.

I'm not sure what you mean by MMRs though. Are you talking about MMRs where
each mountain is a set of diffs to the old things and are periodically
consolidated? Or do later mountains refer to internals of earlier ones? Or
do they have 'maybe' values which mean that the earlier mountain should be
referred to? Are these patricia tries or something flatter and more fixed
depth?

My code doesn't keep track of tree size, by the way. It would be trivial to
add that functionality to the library, and including it in the hashing
creates complexity and doesn't seem to have any benefit over sending that
data in a side channel.

--001a114401829b44c9054929e8d0
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, Feb 22, 2017 at 5:15 PM, Peter Todd via bitcoin-dev <span dir=3D"ltr">&=
lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blan=
k">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wrote:<br><blockquo=
te class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc so=
lid;padding-left:1ex"><br>
With that, notice how proving the soundness of the proofs becomes trivial: =
if<br>
validation is deterministic, it is obviously impossible to construct two<br=
>
different proofs that prove contradictory statements, because a proof is si=
mply<br>
part of the data structure itself. Contradiction would imply that the two<b=
r>
proofs are different, but that&#39;s easily rejected by simply checking the=
 hash of<br>
the data.<br></blockquote><div><br></div><div>My code works this way. Proof=
s are serialization of a subset of the tree, and to validate a proof you as=
k a single function whether a particular value is included in that tree sub=
set, and it answers yes or no, so obviously it&#39;s impossible for a singl=
e value to both validate and not validate. The proof code was quite terrify=
ing before I made this change (which I did on your suggestion), and it&#39;=
s much cleaner and simpler now. It also in principle supports compact proof=
s of multiple inclusions and exclusions in the same serialization of a subs=
et of the tree because the upper branches won&#39;t have to be repeated. I =
haven&#39;t written code for generating those, but the validation code will=
 happily accept them.</div><div><br></div><div>I&#39;m not sure what you me=
an by MMRs though. Are you talking about MMRs where each mountain is a set =
of diffs to the old things and are periodically consolidated? Or do later m=
ountains refer to internals of earlier ones? Or do they have &#39;maybe&#39=
; values which mean that the earlier mountain should be referred to? Are th=
ese patricia tries or something flatter and more fixed depth?</div><div><br=
></div><div>My code doesn&#39;t keep track of tree size, by the way. It wou=
ld be trivial to add that functionality to the library, and including it in=
 the hashing creates complexity and doesn&#39;t seem to have any benefit ov=
er sending that data in a side channel.</div></div></div></div>

--001a114401829b44c9054929e8d0--