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 DB0BB273 for ; Sun, 28 Jun 2015 17:47:24 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wg0-f49.google.com (mail-wg0-f49.google.com [74.125.82.49]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 16B71A8 for ; Sun, 28 Jun 2015 17:47:24 +0000 (UTC) Received: by wgck11 with SMTP id k11so124181973wgc.0 for ; Sun, 28 Jun 2015 10:47:22 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to:cc :content-type:content-transfer-encoding; bh=Vl0l3KkP358Z4C5HrqrV2buAKT3EKnpCgIt06yogaVI=; b=GMTR/86F0CQ3ghoSKdHSkDLjznKS1Ny9pwRLb2KjAv5Gc2SGT4UCr0w69dJEh/7Wgr bDCaAC09CoVQsHkzDPGI8lT+CVSIKzjtsCru+17o1neQsLMw7g4CSxyla8fgt+2qPoZg xLdEzOEE6DeydF0zSSbhxLGinIQMl7of8mgf1FLuP1tDwi4SaZBGMry19+odmShlMNKC k5/LpzqcNboFMyE7Br7LvpWp3R/8GJJyPYp0UiCSUsCrKLdjoP4zN7t6AfEqVSPUcSuD 5zfpt/vn2GeLG20wPYWDeE4STM6yGlt2/Z9LdcUJ9Tluww91mKHccjTO0eMwA6KHT7DT 0Kew== X-Gm-Message-State: ALoCoQlG8ICaZZTElRy001SNZdJFDLyrQ1dWWdp/8cwp98tfLv916Xq3sfK0zEkSXQJ9mTU+b+Ed MIME-Version: 1.0 X-Received: by 10.180.88.201 with SMTP id bi9mr15426479wib.58.1435513642708; Sun, 28 Jun 2015 10:47:22 -0700 (PDT) Received: by 10.194.95.168 with HTTP; Sun, 28 Jun 2015 10:47:22 -0700 (PDT) Date: Sun, 28 Jun 2015 19:47:22 +0200 Message-ID: From: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= To: Mark Friedenbach Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW, URIBL_BLACK autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: bitcoin-dev@lists.linuxfoundation.org Subject: [bitcoin-dev] TXO + STXO vs UTXO Re: Original Vision X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 28 Jun 2015 17:47:25 -0000 On Sun, Jun 28, 2015 at 6:15 PM, Mark Friedenbach wr= ote: > Assuming randomly-picked outputs, it's actually worse. The slowdown facto= r > has to do with the depth of the tree, and TXO and STXO trees are always > growing. It's still complexity O(log N), but with TXO/STXO N is the size = of > the entire block chain history, whereas with UTXO it's just the set of > unspent transaction outputs. But you can prune them. > But it is not the case that TXO/STXO gives you constant time updates. The > append-only TXO tree might be close to that, but you'd still need the spe= nt > or unspent tree which is not insertion ordered. There are alternatives li= ke > updating the TXO tree and requiring blocks and transactions to carry proo= fs > with them (so validators can be stateless), but that pushes the same (wor= se, > actually) problem to whoever generated or assembled the proof. It may be = a > tradeoff worth making, but it's not an easy answer... No, no. You don't need a non-constant update of any spent flag (because there's none), that's the whole point of having 2 separated trees for everything on one side, and only spent outputs on the other side. This proposal is not useful for SPV wallets but it lets you build the UTXO at any height from the committed txo + stxo trees and update it yourself from there. You could have a fast synchronization mode in which you're not really a full node from the beginning but you end up validating the older blocks later, when you have time after synchronizing to the tip of the chain. For the SPV use case you would need a committed UTXO (or the TXO with a fIsSpent bit) but that seems to be more complicated and can be done separately later. > On Sun, Jun 28, 2015 at 8:51 AM, Jorge Tim=C3=B3n wrot= e: >> >> On Sun, Jun 28, 2015 at 5:23 PM, Mark Friedenbach >> wrote: >> > UTXO commitments are the nominal solution here. You commit the validat= or >> > state in each block, and then you can prove things like a negative by >> > referencing that state commitment. The trouble is this requires mainta= ining >> > a hash tree commitment over validator state, which turns out to be ins= anely >> > expensive. With the UTXO commitment scheme (the others are not better)= that >> > ends up requiring 15 - 22x more I/O during block validation. And I/O i= s >> > presently a limiter to block validation speed. So if you thought 8MB w= as >> > what bitcoin today could handle, and you also want this commitment sch= eme >> > for fraud proofs, then you should be arguing for a block size limit de= crease >> > (to 500kB), not increase. >> >> What about a TXO and a STXO O(1)-append commitment? That shouldn't >> cause that much overhead and you can build UTXO from TXO - STXO. >> I know it's not so efficient in some respects but it scales better I >> think. > >