š
Original date posted:2017-04-02
š Original message:TL;DR: using spentness bits scales linearly... vs swapping digest leafs with empties can scale with logorithmically increasing storage requirements. So if you are using a 32 byte hash and spentness bits, you are pretty much limited to only being able to prune 8 to 12 layers. This corresponds to an MMR proof length of 512 to 768 bytes.
===============
After doing some calculations:
Given that the spentness bit fields are 1 bit per txo, and markle hash size is 32 bytes... When using spentness bits in the merkle tree hashes instead of setting leaf nodes to empty, increasing the DLH_REQUIRED beyond 8 quickly has diminishing returns.
With DLH_REQUIRED = 8, the spentness bits take up 30% of the data structure's space. MMR proof size = 512 bytes.
With DLH_REQUIRED = 12, the spentness bits take up 87% of the data structure's space. MMR proof size = 768 bytes.
Using stats from blockchain.info (I know not very reliable)... I figure there would be about 12E6 delayed utxo only txos added to an MMR per year w/ the current block size. 200E6 txo/year added to the MMR per year if spent txos are added too.
Using DLH_REQUIRED = 12 (or 8)
With 12E6 txo/year added to the MMR, the MMR grows by about 1.5MB (or 5MB) per year.
With 200E6 txo/year added to the MMR, the MMR grows by about 27.5MB (or 80MB) per year.
Since the spentness bits are not in any way compressed by the MMR tree... this puts a hard limit on the potential gains by pruning more.
A growth rate of 27MB to 80MB per year for adding all txos to the MMR doesn't sound too bad. But if the block size is increased, we may soon decide we'd rather switch from using spentness bits to changing digest nodes to empty nodes. Only adding utxos at a delayed time gives more breathing room.
Cheers,
Praxeology Guy
P.S. This analysis also applies to Bram Cohen's "TXO bitfield". Instead of DLH_REQUIRED, his node with spendess bits would be at a block with about 4000 txos, which just happens to equal a DLH_REQUIRED = 12.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170402/44931f22/attachment-0001.html>;
praxeology_guy [ARCHIVE] /
npub1hzā¦7nzv7
2023-06-07 17:58:56
in reply to nevent1qā¦l4v6
Author Public Key
npub1hzkv59ax7ax80nv2fzvcgmveqyk3k5sg9gq695n48l9scenf5c9sa7nzv7Published at
2023-06-07 17:58:56Event JSON
{
"id": "b48223418aefb3ae53acb7cc8618f91e3d0ffcf2664a4f2937e66a818211fd42",
"pubkey": "b8acca17a6f74c77cd8a4899846d99012d1b52082a01a2d2753fcb0c6669a60b",
"created_at": 1686160736,
"kind": 1,
"tags": [
[
"e",
"56cde3ba45fdc2fd1de191987567d27ad54a1430fd971dd6fb1d3c51a3891d99",
"",
"root"
],
[
"e",
"a7141f2064f2a0e412796faf3d7603d62d7ca4a2e5bea79da475f8bfcf681403",
"",
"reply"
],
[
"p",
"b8acca17a6f74c77cd8a4899846d99012d1b52082a01a2d2753fcb0c6669a60b"
]
],
"content": "š
Original date posted:2017-04-02\nš Original message:TL;DR: using spentness bits scales linearly... vs swapping digest leafs with empties can scale with logorithmically increasing storage requirements. So if you are using a 32 byte hash and spentness bits, you are pretty much limited to only being able to prune 8 to 12 layers. This corresponds to an MMR proof length of 512 to 768 bytes.\n\n===============\n\nAfter doing some calculations:\nGiven that the spentness bit fields are 1 bit per txo, and markle hash size is 32 bytes... When using spentness bits in the merkle tree hashes instead of setting leaf nodes to empty, increasing the DLH_REQUIRED beyond 8 quickly has diminishing returns.\n\nWith DLH_REQUIRED = 8, the spentness bits take up 30% of the data structure's space. MMR proof size = 512 bytes.\n\nWith DLH_REQUIRED = 12, the spentness bits take up 87% of the data structure's space. MMR proof size = 768 bytes.\n\nUsing stats from blockchain.info (I know not very reliable)... I figure there would be about 12E6 delayed utxo only txos added to an MMR per year w/ the current block size. 200E6 txo/year added to the MMR per year if spent txos are added too.\n\nUsing DLH_REQUIRED = 12 (or 8)\nWith 12E6 txo/year added to the MMR, the MMR grows by about 1.5MB (or 5MB) per year.\nWith 200E6 txo/year added to the MMR, the MMR grows by about 27.5MB (or 80MB) per year.\n\nSince the spentness bits are not in any way compressed by the MMR tree... this puts a hard limit on the potential gains by pruning more.\n\nA growth rate of 27MB to 80MB per year for adding all txos to the MMR doesn't sound too bad. But if the block size is increased, we may soon decide we'd rather switch from using spentness bits to changing digest nodes to empty nodes. Only adding utxos at a delayed time gives more breathing room.\n\nCheers,\nPraxeology Guy\n\nP.S. This analysis also applies to Bram Cohen's \"TXO bitfield\". Instead of DLH_REQUIRED, his node with spendess bits would be at a block with about 4000 txos, which just happens to equal a DLH_REQUIRED = 12.\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170402/44931f22/attachment-0001.html\u003e",
"sig": "ad98f1aa35ab4641ff64adfbc8535e7b63c8c9bd9cd0aa45eda9c86d29b03ffd8a23c9bd3bb15a54421c8ac90cebd3e583e210b352434c518c67947c0291983b"
}