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 --]
prev parent 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 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$(echo .)com \
--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