From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 4E7DF83D for ; Thu, 19 May 2016 09:31:28 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-vk0-f44.google.com (mail-vk0-f44.google.com [209.85.213.44]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8BD52195 for ; Thu, 19 May 2016 09:31:27 +0000 (UTC) Received: by mail-vk0-f44.google.com with SMTP id y2so24594820vka.3 for ; Thu, 19 May 2016 02:31:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=jtimon-cc.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc; bh=9jL02jH43wRcaUVXTqiNiNmhy0+NeDinlhPP27X39VA=; b=LtibAq6gFLA22VkFgj1pP2oiF74JxWtENJdoEm0l6kqU/fC982G7ZGNmDmrqsxJl8K 72zN+wd/H2lYvGL3p1T0eRAuXhBqsux5ZSm0M6piiNCIFx95BTve5HrpPnOyOEjAfJ1J 7WV6LnK5OtouB/7F1otg6RhXgz5s6ig2VnWW7xtwODLSnrbqa9HRuNSyc1NymHQJNJPp UaqKMospviv3aGTbIPJso0Vp5t6/1joLEulPzM02Qsf+Fq0hq1aB+fKrC53GSsrMoP8T vrbAReUzxKLKTjWmsN3ozw/MrE4V4Ng34ORF+dIYG5VOGc+bgqPnnYWWIEb7uqwgkfip ArZA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc; bh=9jL02jH43wRcaUVXTqiNiNmhy0+NeDinlhPP27X39VA=; b=OSBmK3PVAkMyBhFGVHudJHFK+tsUf2Z48U/0o6TJZB1XG9siRgEA8pwOLM25pFdcoi 6eIhhwWpGPv5sXbsgvQvIil1N30a+pU9q5b5crSjEllgncbltHGJCcyEcWRkeK5/3yZt rJmG0J1ON8yVxTmGtEHF+A9EntGnEqM6tLLBLRbFgvXmyju3cEj7DVBjf36dt8XljN23 pBuHf+aC88seNYUSvoAPPSvQEIM5Z2aziTiPJKuACPxE7ZjiUT05GjqnzMQ70Ay5UoP0 kX79tQX4WhfJeyJVFurotsS2iFewWERkdYouShjLM41sKEWuFqb41aw8PfSt0tAs0o/j 24XQ== X-Gm-Message-State: AOPr4FVxxCPJCCiGPDVBrbVAe8dqLvFrjAUHQkoaviZ6NUvFkSUNl2Spljw870ciKUSf/hRifUi42DlGhfHr9Q== MIME-Version: 1.0 X-Received: by 10.31.230.197 with SMTP id d188mr6485183vkh.143.1463650286678; Thu, 19 May 2016 02:31:26 -0700 (PDT) Received: by 10.31.141.73 with HTTP; Thu, 19 May 2016 02:31:26 -0700 (PDT) Received: by 10.31.141.73 with HTTP; Thu, 19 May 2016 02:31:26 -0700 (PDT) In-Reply-To: References: <20160517132311.GA21656@fedora-21-dvm> <20160518235336.GA1358@fedora-21-dvm> Date: Thu, 19 May 2016 11:31:26 +0200 Message-ID: From: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= To: Peter Todd Content-Type: multipart/alternative; boundary=94eb2c094e5669cbbc05332ea3c0 X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,HTML_MESSAGE,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Dev Subject: Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 19 May 2016 09:31:28 -0000 --94eb2c094e5669cbbc05332ea3c0 Content-Type: text/plain; charset=UTF-8 On May 19, 2016 01:53, "Peter Todd" 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


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--