public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: praxeology_guy <praxeology_guy@protonmail.com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Better MMR Definition
Date: Sat, 01 Apr 2017 15:46:12 -0400	[thread overview]
Message-ID: <sg1WY50VjVRyYpa-2svzLhpSqj4NyFTASjsnebr0lY9ofjYLwMOzS_aRWszEeXvKi6s4tHFfJvx-x875Nl80gxBhHiLqLfCtCLd0xYaNmhc=@protonmail.com> (raw)
In-Reply-To: <U7XfjmkXVYYN0dL44eOIu9O0W7p6nd_BjIKkPW3Eiu2ADYbwsdQWt-JEWxdg-DOhde9pp9NKbkQIJr8ZEoJQp1WORMn6USprETs7RXgwgUk=@protonmail.com>

[-- Attachment #1: Type: text/plain, Size: 2043 bytes --]

gmaxwell told me that most nodes would keep a full copy of the top of the MMR tree.

Here I am exploring how this could be policy-ized to solve two problems:
- MMR proofs change over time
- How to coordinate nodes to get them to keep different portions of the MMR, so that everyone can prune most of the structure, but the entire network still retains multiple copies of the full MMR.

Define deltaLeafHeight as the number of tree layers between a node and the leaves in the MMR data structure. We make it a policy that nodes are expected to have all nodes above deltaLeafHeight = DLH_REQUIRED, but that nodes are free to prune any nodes with a deltaLeafHeight < DLH_REQUIRED. Of course a node could prune at DLH_REQUIRED or higher, but what I am proposing is that messages and proofs by default would only include nodes at deltaLeafHeight < DLH_REQUIRED.

Given the above, If a wallet didn't want to be continuously concerned about updating their MMR proof for its coins, then for each coin:
- store the set of utxo digests that are children of the "root nearest" node that is at deltaLeafHeight = DLH_REQUIRED. Call such a set of utxo digests the "pruned relatives".
- Pruned relative count = 2^DLH_REQUIRED -1
- Guessing the spentness status of the pruned relatives would worst case take 2^(pruned relative count) guesses.
- in the case where the MMR holds all txos (not just utxos at addition time)... the wallet should also keep record of which of the pruned relatives were utxos.
- Any future information discovered about whether a pruned relative is spent would reduce the worst case guess count by a factor of 2.

As an example, in the case where DLH_REQUIRED = 3:
- pruned relative count = 7
- worst case spentness guess count = 128

Wallets storing the digests of pruned relatives could also help the entire network be able to discover otherwise lost portions of the MMR. If wallets stored not just the pruned relatives digests, but also their corresponding utxos, they could help other nodes find lost coins.

Cheers,
Praxeology Guy

[-- Attachment #2: Type: text/html, Size: 2399 bytes --]

      reply	other threads:[~2017-04-01 19:46 UTC|newest]

Thread overview: 29+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-02-23  1:15 [bitcoin-dev] A Better MMR Definition Peter Todd
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 [this message]

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='sg1WY50VjVRyYpa-2svzLhpSqj4NyFTASjsnebr0lY9ofjYLwMOzS_aRWszEeXvKi6s4tHFfJvx-x875Nl80gxBhHiLqLfCtCLd0xYaNmhc=@protonmail.com' \
    --to=praxeology_guy@protonmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
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