[bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments
jtimon at jtimon.cc
Thu May 19 09:31:26 UTC 2016
On May 19, 2016 01:53, "Peter Todd" <pete at petertodd.org> wrote:
tip of the tree.
> > How expensive it is to update a leaf from this tree from unspent to
> log2(n) operations.
Updating a leaf is just as expensive as adding a new one?
That's not what I expected.
Or is adding a new one O (1) ?
Anyway, thanks, I'll read this in more detail.
> > Wouldn't it be better to have both an append-only TXO and an append-only
> > STXO (with all spent outputs, not only the latest ones like in your
> Nope. The reason why this doesn't work is apparent when you ask how will
> STXO be indexed?
Just the same way the TXO is (you just stop updating the txo leafs from
unspent to spent.
> If it's indexed by outpoint - that is H(txid:n) - to update the STXO you
> he entire thing, as the position of any new STXO that you need to add to
> STXO tree is random.
> OTOH, if you index the STXO by txout creation order, with the first txout
> created having position #0, the second #1, etc. the data you may need to
> the STXO later has predictable locality... but now you have something
> basically identical to my proposed insertion-ordered TXO commitment
Yeah, that's what I want. Like your append only TXO but for STXO (that way
we avoid ever updating leafs in the TXO, and I suspect there are other
advantages for fraud proofs).
> Incidentally, it's interesting how if a merbinner tree is insertion-order
> indexed you end up with a datastructure that's almost identical to a MMR.
No complain with MMR. My point is having 2 of them separated: one for the
TXO (entries unmutable) and one for the STXO (again, entries unmutable).
Maybe it doesn't make sense, but I would like to understand why.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the bitcoin-dev