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

[praxeology_guy via bitcoin-dev]

Bitcoin nodes could also keep a spentness status list, where each bit in the spentness status list corresponds to whether a txo in the MMR is spent. This could make it so that disconnected wallets didn't have to guess the pruned relative spentness status when it reconnects to the network... and help prevent DoS attacks.

Keeping such a bit list would consume considerably less space if stxos were never added to the MMR. Putting portions of such a list in the node at height DLH_REQUIRED would made R/W operations on the bit list more local to other data that is going to be R/W.

Cheers,
Praxeology Guy

[bfd--- via bitcoin-dev]

If a wallet is unaware of spends of its own coins (ie, transactions
were made it can't have known about), there's probably bigger problems
going on. You might enjoy the topic on this mailing list on committed
bloom filters however, as this solves a similar issue without needing
an ever-growing list of hundreds of millions of spent outputs.

Post by praxeology_guy via bitcoin-dev
Bitcoin nodes could also keep a spentness status list, where each bit
in the spentness status list corresponds to whether a txo in the MMR
is spent. This could make it so that disconnected wallets didn't have
to guess the pruned relative spentness status when it reconnects to
the network... and help prevent DoS attacks.

[praxeology_guy via bitcoin-dev]

Not sure if you are BFD or BF Trolling D, BFTD. But I will bite this time.

Sorry I mistakenly forgot to change the subject back to "A Better MMR Definition" when I decided to send the email to the dev list instead of directly to Peter. So then you made such a reply without knowing context.

With using the MMR data structure for txo commitments, its preferable that wallets only keep information pertinent to their own spendable coins. In previous communication we talked about how wallets could maintain the changing MMR proof for their old coins. Yes wallets know which of their own coins are spent. But with MMR proofs wallets also need to know the spentness status of close relatives in the MMR tree... in order to construct a valid MMR proof that their own coin is not spent.

Hope that... clears it up for you.

Cheers,
P. Guy

-------- Original Message --------
Subject: Re: [bitcoin-dev] Guessing the spentness status of the pruned relatives
Local Time: April 1, 2017 6:38 PM
UTC Time: April 1, 2017 11:38 PM
From: ***@cock.lu
To: praxeology_guy <***@protonmail.com>, Bitcoin Protocol Discussion <bitcoin-***@lists.linuxfoundation.org>

If a wallet is unaware of spends of its own coins (ie, transactions
were made it can't have known about), there's probably bigger problems
going on. You might enjoy the topic on this mailing list on committed
bloom filters however, as this solves a similar issue without needing
an ever-growing list of hundreds of millions of spent outputs.

Post by praxeology_guy via bitcoin-dev
Bitcoin nodes could also keep a spentness status list, where each bit
in the spentness status list corresponds to whether a txo in the MMR
is spent. This could make it so that disconnected wallets didn't have
to guess the pruned relative spentness status when it reconnects to
the network... and help prevent DoS attacks.

[Bram Cohen via bitcoin-dev]

On Sat, Apr 1, 2017 at 6:10 PM, praxeology_guy via bitcoin-dev <

Post by praxeology_guy via bitcoin-dev
With using the MMR data structure for txo commitments, its preferable that
wallets only keep information pertinent to their own spendable coins. In
previous communication we talked about how wallets could maintain the
changing MMR proof for their old coins. Yes wallets know which of their
own coins are spent. But with MMR proofs wallets also need to know the
spentness status of close relatives in the MMR tree... in order to
construct a valid MMR proof that their own coin is not spent.

Did you read the post that I made about the TXO bitfield yesterday? That
gives what I believe is a much better way of handling this whole issue,
allowing wallets to keep track of nothing other than the proof of position
of their txo, which never changes.

[praxeology_guy via bitcoin-dev]

Bram Cohen,

In R&D: First its appropriate to explore all interesting ideas, and help each other improve their ideas. Last, when there is a deadline that needs to be met, we compare various options and decide on which to go with.

I'm on the First step still.

If you really want to push me to saying it, I'm not a fan of the Patricia Tree for bitcoin txos. I think its too much work for everyone to do when other options are available. But I'm not trying to say that your design is bad or wont work... I'm just personally not interested in it at this time.

Cheers,
Praxeology Guy

[Bram Cohen via bitcoin-dev]

On Sat, Apr 1, 2017 at 6:58 PM, praxeology_guy <

Post by praxeology_guy via bitcoin-dev
Bram Cohen,
In R&D: First its appropriate to explore all interesting ideas, and help
each other improve their ideas. Last, when there is a deadline that needs
to be met, we compare various options and decide on which to go with.
I'm on the First step still.

In that case you should read my txo bitfield proposal, instead of taking my
postings yesterday as a prompt to respond to something completely unrelated.

Post by praxeology_guy via bitcoin-dev
If you really want to push me to saying it, I'm not a fan of the Patricia
Tree for bitcoin txos. I think its too much work for everyone to do when
other options are available. But I'm not trying to say that your design is
bad or wont work... I'm just personally not interested in it at this time.

My bitfield proposal is different from the patricia trie stuff. Also your
objection about patricia tries being 'too much work' is nonsensical because
they're quite a bit simpler than MMRs.

[praxeology_guy via bitcoin-dev]

Bram Cohen,

My apologies, I guess I glossed over your "The TXO bitfield" because by subject I thought it just had something to do with changing the txo's data structure.

Yes what you are proposing with "The TXO bitfield" is pretty much exactly the same as the MMR data structure... EXCEPT yours has the wonderful benefit of the MMR proofs not changing. Excellent idea!

Basically your idea is a change in how the MMR data is modified on spend... moving it from changing the leaf nodes to changing a node closer to the root... and particularly it seems you are making such a deltaLeaveHeight = block height... which might be a different height for each block, but not that big of a deal.

Which leads me to modifying the MMR structure so that the spentness bit array is actually part of the nodes at height DLH_REQUIRED's hash... and that the leaf nodes don't actually get changed to empty as Peter is proposing, instead the leaf nodes stay the same. This results in the same wonderful benefit of the MMR proofs not changing, just like in your "TXO bitfield" proposal.

I still like the MMR structure better, in the case that only utxos are added after a long delay. The delay and adding only utxos allows much fewer additions to the spentness bitfield and it's merkle tree. But if we are going to make commitments on the entire txo set instead of some policy of N blocks delayed utxos... your "TXO bitfield" idea looks great.

Say... one bad thing about only adding delayed utxos to the MMR, as I am proposing, is that the index changes/is created when the delayed addition happens. Verses with "txo bitfield" or adding all txos to the MMR, the index is created when the block is first made.

Thank you so much for your TXO bitfield idea... and harping on me about it. I'm really excited about these designs. :) As a funny side note,I had actually considered putting the spentness bitfield in the deltaLeafHeight = DLH_REQUIRED node's merkle hash... but quickly dismissed it since we were already were replacing the leafs w/ empties (which is a duplication of information). Your idea was the inspiration to switch from changing to empties to changing the spentness bits.

Humbled, Thanks,

Praxeology Guy

[praxeology_guy via bitcoin-dev]

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.

[Bram Cohen via bitcoin-dev]

On Sun, Apr 2, 2017 at 1:43 PM, praxeology_guy via bitcoin-dev <

Post by praxeology_guy via bitcoin-dev
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.

Yes the point of the txo bitfield is that the constant factors are so good
that it's entirely under control. Making the memory commitments smaller
requires that the proofs be kept up to date and increases CPU requirements
and proof size. It would be entirely reasonable to make an MMRs of the
bitfield or the insertion index data structure but they aren't needed
immediately if ever. For the insertion ordering structure it's reasonable
to require full nodes to cache the top bunch of layers to make the proofs
smaller, but a very expedient approximation of that is to make them simply
remember a root per block for all the insertions contained therein, and
have full nodes remember all of those.