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
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
