{"type":"rich","version":"1.0","author_name":"npub1m230cem2yh3mtdzkg32qhj73uytgkyg5ylxsu083n3tpjnajxx4qqa2np2","author_url":"https://nostr.ae/npub1m230cem2yh3mtdzkg32qhj73uytgkyg5ylxsu083n3tpjnajxx4qqa2np2","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2017-02-22\n📝 Original message:Reposting something that came up recently in a private discussion with some\nacademics:\n\nConcretely, let's define a prunable MMR with the following grammar. This\ndefinition is an improvement on whats in the python-proofmarshal by committing\nto the number of items in the tree implicitly; an obvious max-log2(n)-sized\nproof-of-tree-size can be obtained by following the right-most nodes:\n\n    Maybe(T) := UNPRUNED \u003cT\u003e | PRUNED \u003cCommitment(T)\u003e\n\n    FullNode(0) := \u003cValue\u003e\n    FullNode(n) := \u003cMaybe(FullNode(n-1)\u003e \u003cMaybe(FullNode(n-1))\u003e\n\n    PartialNode(0) := SOME \u003cFullNode(0)\u003e | NONE\n    PartialNode(n) := \u003cMaybe(FullNode(n-1))\u003e \u003cMaybe(PartialNode(n-1))\u003e\n\n    MMR := FULL \u003cN\u003e \u003cFullNode(n)\u003e | PARTIAL \u003cN\u003e \u003cPartialNode(n)\u003e\n\nBasically we define it in four parts. First we define Maybe(T) to represent\npruned and unpruned (hash only) data. Secondly we define full nodes within 2^n\nsized trees. Third we define partial nodes. And finally we define the MMR\nitself as being either a full or partial node.\n\nFirst of all, with pruning we can define a rule that if any operation (other\nthan checking commitment hashes) attempts to access pruned data, it should\nimmediately fail. In particular, no operation should be able to determine if\ndata is or isn't pruned. Equally, note how an implementation can keep track of\nwhat data was accessed during any given operation, and prune the rest, which\nmeans a proof is just the parts of the data structure accessed during one or\nmore operations.\n\nWith that, notice how proving the soundness of the proofs becomes trivial: if\nvalidation is deterministic, it is obviously impossible to construct two\ndifferent proofs that prove contradictory statements, because a proof is simply\npart of the data structure itself. Contradiction would imply that the two\nproofs are different, but that's easily rejected by simply checking the hash of\nthe data.\n\n-- \nhttps://petertodd.org 'peter'[:-1]@petertodd.org\n-------------- next part --------------\nA non-text attachment was scrubbed...\nName: signature.asc\nType: application/pgp-signature\nSize: 455 bytes\nDesc: Digital signature\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170222/1412af52/attachment.sig\u003e"}