From: praxeology_guy <praxeology_guy@protonmail•com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Guessing the spentness status of the pruned relatives
Date: Sun, 02 Apr 2017 16:43:40 -0400 [thread overview]
Message-ID: <slZ23d145uIKHr0zGoApsczTN3MNPSMtYbNmZV3Nk7F9YrgY8XaXTZ4BPvgIGGIdHBEf5V7c_ugY4RQVWeYYQW57ZQtfkUlHwOQZC7ANGjk=@protonmail.com> (raw)
In-Reply-To: <h-i4wv8tgd-htJYGNv1FsgBOs0CJbU2CVhit0gj1JqGp6qnCB6_Lvqt-pFNQxD_cuM-Z8Bu6e-YImZkPv8LYOAaVJHmNsSJIeLV-qiGpUHc=@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 --]
next prev parent reply other threads:[~2017-04-02 20:43 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-04-01 20:04 praxeology_guy
2017-04-01 23:38 ` bfd
2017-04-02 1:10 ` praxeology_guy
2017-04-02 1:27 ` Bram Cohen
2017-04-02 1:58 ` praxeology_guy
2017-04-02 2:18 ` Bram Cohen
2017-04-02 3:37 ` praxeology_guy
2017-04-02 20:43 ` praxeology_guy [this message]
2017-04-03 3:13 ` Bram Cohen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='slZ23d145uIKHr0zGoApsczTN3MNPSMtYbNmZV3Nk7F9YrgY8XaXTZ4BPvgIGGIdHBEf5V7c_ugY4RQVWeYYQW57ZQtfkUlHwOQZC7ANGjk=@protonmail.com' \
--to=praxeology_guy@protonmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox