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