On May 19, 2016 01:53, "Peter Todd" <pete@petertodd.org> wrote:
tip of the tree.
> >
> > How expensive it is to update a leaf from this tree from unspent to spent?
>
> 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 "STXO")?
>
> Nope. The reason why this doesn't work is apparent when you ask how will the
> 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 need
> he entire thing, as the position of any new STXO that you need to add to the
> STXO tree is random.
>
> OTOH, if you index the STXO by txout creation order, with the first txout ever
> created having position #0, the second #1, etc. the data you may need to update
> the STXO later has predictable locality... but now you have something that's
> basically identical to my proposed insertion-ordered TXO commitment anyway.

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.