📅 Original date posted:2017-04-01
📝 Original message: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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170401/084274f5/attachment.html>;
praxeology_guy [ARCHIVE] /
npub1hz…7nzv7
2023-06-07 17:58:54
in reply to nevent1q…ty6t
Author Public Key
npub1hzkv59ax7ax80nv2fzvcgmveqyk3k5sg9gq695n48l9scenf5c9sa7nzv7Published at
2023-06-07 17:58:54Event JSON
{
"id": "09af417afde90ebd3c7421df9c3ca74901e94273c18ea5f4771185845ef1bd7f",
"pubkey": "b8acca17a6f74c77cd8a4899846d99012d1b52082a01a2d2753fcb0c6669a60b",
"created_at": 1686160734,
"kind": 1,
"tags": [
[
"e",
"5b3d5a8df03ec6e0348fd76cf6ad62396ca68a52d04260478e631bf7f7b9c56b",
"",
"root"
],
[
"e",
"5bba22b2a3d60524e38167021b0ece4003fc6a4e92bf9e823e6690035b259884",
"",
"reply"
],
[
"p",
"b8acca17a6f74c77cd8a4899846d99012d1b52082a01a2d2753fcb0c6669a60b"
]
],
"content": "📅 Original date posted:2017-04-01\n📝 Original message:gmaxwell told me that most nodes would keep a full copy of the top of the MMR tree.\n\nHere I am exploring how this could be policy-ized to solve two problems:\n- MMR proofs change over time\n- 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.\n\nDefine 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 \u003c 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 \u003c DLH_REQUIRED.\n\nGiven the above, If a wallet didn't want to be continuously concerned about updating their MMR proof for its coins, then for each coin:\n- 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\".\n- Pruned relative count = 2^DLH_REQUIRED -1\n- Guessing the spentness status of the pruned relatives would worst case take 2^(pruned relative count) guesses.\n- 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.\n- Any future information discovered about whether a pruned relative is spent would reduce the worst case guess count by a factor of 2.\n\nAs an example, in the case where DLH_REQUIRED = 3:\n- pruned relative count = 7\n- worst case spentness guess count = 128\n\nWallets 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.\n\nCheers,\nPraxeology Guy\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170401/084274f5/attachment.html\u003e",
"sig": "f3ab2b19e50ff662ad65b2ef4f5cbe81e10c7c6b93417c457b28819eb83fd0ad5d0adda2104a81222679d137544edb43b3786d508f9c13cd560557540b1e7732"
}