From: Peter Todd <pete@petertodd•org>
To: bitcoin-dev@lists•linuxfoundation.org
Subject: [bitcoin-dev] A Better MMR Definition
Date: Wed, 22 Feb 2017 20:15:06 -0500 [thread overview]
Message-ID: <20170223011506.GC905@savin.petertodd.org> (raw)
[-- Attachment #1: Type: text/plain, Size: 1966 bytes --]
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
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]
next reply other threads:[~2017-02-23 1:15 UTC|newest]
Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-02-23 1:15 Peter Todd [this message]
2017-02-23 3:07 ` Bram Cohen
2017-02-23 7:41 ` Peter Todd
2017-02-23 17:53 ` Chris Priest
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=20170223011506.GC905@savin.petertodd.org \
--to=pete@petertodd$(echo .)org \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.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