Re: [bitcoin-dev] Guessing the spentness status of the pruned relatives

[praxeology_guy <praxeology_guy@protonmail.com>]

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

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.

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