From: Chris Priest <cp368202@ohiou•edu>
To: Peter Todd <pete@petertodd•org>,
Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Better MMR Definition
Date: Thu, 23 Feb 2017 09:53:58 -0800 [thread overview]
Message-ID: <CAAcC9ys5sUxVfOjogFiF3gzk51D_L=QQkOYevTH=qbh_RkA3Hw@mail.gmail.com> (raw)
In-Reply-To: <20170223011506.GC905@savin.petertodd.org>
On 2/22/17, Peter Todd via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
> Reposting something that came up recently in a private discussion with some
> academics:
>
> Concretely, let's define a prunable MMR with the following grammar. This
> definition is an improvement on whats in the python-proofmarshal by
> committing
> to the number of items in the tree implicitly; an obvious max-log2(n)-sized
> proof-of-tree-size can be obtained by following the right-most nodes:
>
> Maybe(T) := UNPRUNED <T> | PRUNED <Commitment(T)>
>
> FullNode(0) := <Value>
> FullNode(n) := <Maybe(FullNode(n-1)> <Maybe(FullNode(n-1))>
>
> PartialNode(0) := SOME <FullNode(0)> | NONE
> PartialNode(n) := <Maybe(FullNode(n-1))> <Maybe(PartialNode(n-1))>
>
> MMR := FULL <N> <FullNode(n)> | PARTIAL <N> <PartialNode(n)>
>
> Basically we define it in four parts. First we define Maybe(T) to represent
> pruned and unpruned (hash only) data. Secondly we define full nodes within
> 2^n
> sized trees. Third we define partial nodes. And finally we define the MMR
> itself as being either a full or partial node.
>
> First of all, with pruning we can define a rule that if any operation
> (other
> than checking commitment hashes) attempts to access pruned data, it should
> immediately fail. In particular, no operation should be able to determine
> if
> data is or isn't pruned. Equally, note how an implementation can keep track
> of
> what data was accessed during any given operation, and prune the rest,
> which
> means a proof is just the parts of the data structure accessed during one
> or
> more operations.
>
> 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.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
What problem does this try to solve, and what does it have to do with bitcoin?
next prev parent reply other threads:[~2017-02-23 17:54 UTC|newest]
Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-02-23 1:15 Peter Todd
2017-02-23 3:07 ` Bram Cohen
2017-02-23 7:41 ` Peter Todd
2017-02-23 17:53 ` Chris Priest [this message]
2017-02-23 18:19 ` Peter Todd
2017-02-23 18:28 ` G. Andrew Stone
2017-02-23 18:31 ` Peter Todd
2017-02-23 23:13 ` Bram Cohen
2017-02-23 23:51 ` Peter Todd
2017-02-24 0:49 ` Bram Cohen
2017-02-24 1:09 ` Peter Todd
2017-02-24 2:50 ` Bram Cohen
2017-02-24 2:58 ` Peter Todd
2017-02-24 3:02 ` Bram Cohen
2017-02-24 3:15 ` Peter Todd
2017-02-24 3:32 ` Bram Cohen
2017-02-24 4:36 ` Peter Todd
2017-02-24 22:20 ` Bram Cohen
2017-02-25 4:12 ` Peter Todd
2017-02-25 6:23 ` Bram Cohen
2017-02-28 16:43 ` G. Andrew Stone
2017-02-28 23:10 ` Bram Cohen
2017-02-28 23:24 ` Pieter Wuille
2017-03-01 1:47 ` Bram Cohen
2017-03-01 1:56 ` Peter Todd
2017-03-01 22:31 ` Peter Todd
2017-03-31 20:38 ` Bram Cohen
2017-04-01 10:18 ` praxeology_guy
2017-04-01 19:46 ` praxeology_guy
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAAcC9ys5sUxVfOjogFiF3gzk51D_L=QQkOYevTH=qbh_RkA3Hw@mail.gmail.com' \
--to=cp368202@ohiou$(echo .)edu \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=pete@petertodd$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox