MIME-Version: 1.0
In-Reply-To: <CABm2gDp9N3ZEZcmF28ESv3V7v_HqU5e5KHY69cSxcVm0t7BeDQ@mail.gmail.com>
References: <20160517132311.GA21656@fedora-21-dvm>
	<CABm2gDoj=6CimHm2C0H_qa=o5SRqWr0ZTGamf-qT-kUjt5WXTA@mail.gmail.com>
	<CABm2gDqMQanaY0Eo4QAnx2MrKCSP+v31R6J80jSVx+jOwsVsVw@mail.gmail.com>
	<CABm2gDp9NLKS=+2BhtS3tT2aZjV0sGHUkVV-+n_90w4Ud9Aakw@mail.gmail.com>
	<20160518235336.GA1358@fedora-21-dvm>
	<CABm2gDrXjg_nSKr-ju0jdXxmMc4N=LQFRwaVU3ix1p-T8CVKdQ@mail.gmail.com>
	<CABm2gDrmRf9wjddiMb-TTDE0xkBJ6yMz-bW_aTpDuBvNqrnHzQ@mail.gmail.com>
	<CABm2gDqfZh0zOqJN5itVk8eP0nshBsydzT6uryrBdRTcYqyhyA@mail.gmail.com>
	<CABm2gDr4ZKvGt3qRPpV+iPgGbpQ5cO66M_bPn2HJPn-eYcQMOg@mail.gmail.com>
	<CABm2gDrijEMZW1dMjGTfG-32VGvLZvX-ujP1n5mxBeVLQSsL1Q@mail.gmail.com>
	<CABm2gDp9N3ZEZcmF28ESv3V7v_HqU5e5KHY69cSxcVm0t7BeDQ@mail.gmail.com>
Date: Thu, 19 May 2016 11:31:26 +0200
Message-ID: <CABm2gDqcURsug5C21A7dmAMCgU7easbCs=u5sFZy_G4MfyY8mw@mail.gmail.com>
From: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= <jtimon@jtimon.cc>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=94eb2c094e5669cbbc05332ea3c0
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With
 Low-Latency Delayed TXO Commitments
Precedence: list

--94eb2c094e5669cbbc05332ea3c0
Content-Type: text/plain; charset=UTF-8

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.

--94eb2c094e5669cbbc05332ea3c0
Content-Type: text/html; charset=UTF-8

<p dir="ltr"><br>
On May 19, 2016 01:53, &quot;Peter Todd&quot; &lt;<a href="mailto:pete@petertodd.org">pete@petertodd.org</a>&gt; wrote:<br>
 tip of the tree.<br>
&gt; &gt;<br>
&gt; &gt; How expensive it is to update a leaf from this tree from unspent to spent?<br>
&gt;<br>
&gt; log2(n) operations.</p>
<p dir="ltr">Updating a leaf is just as expensive as adding a new one?<br>
That&#39;s not what I expected.<br>
Or is adding a new one O (1) ?</p>
<p dir="ltr">Anyway, thanks, I&#39;ll read this in more detail.</p>
<p dir="ltr">&gt; &gt; Wouldn&#39;t it be better to have both an append-only TXO and an append-only<br>
&gt; &gt; STXO (with all spent outputs, not only the latest ones like in your &quot;STXO&quot;)?<br>
&gt;<br>
&gt; Nope. The reason why this doesn&#39;t work is apparent when you ask how will the<br>
&gt; STXO be indexed?</p>
<p dir="ltr">Just the same way the TXO is (you just stop updating the txo leafs from unspent to spent.</p>
<p dir="ltr">&gt; If it&#39;s indexed by outpoint - that is H(txid:n) - to update the STXO you need<br>
&gt; he entire thing, as the position of any new STXO that you need to add to the<br>
&gt; STXO tree is random.<br>
&gt;<br>
&gt; OTOH, if you index the STXO by txout creation order, with the first txout ever<br>
&gt; created having position #0, the second #1, etc. the data you may need to update<br>
&gt; the STXO later has predictable locality... but now you have something that&#39;s<br>
&gt; basically identical to my proposed insertion-ordered TXO commitment anyway.</p>
<p dir="ltr">Yeah, that&#39;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).</p>
<p dir="ltr">&gt; Incidentally, it&#39;s interesting how if a merbinner tree is insertion-order<br>
&gt; indexed you end up with a datastructure that&#39;s almost identical to a MMR.</p>
<p dir="ltr">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).</p>
<p dir="ltr">Maybe it doesn&#39;t make sense, but I would like to understand why.<br>
</p>

--94eb2c094e5669cbbc05332ea3c0--