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 E693694B for ; Tue, 16 May 2017 18:17:22 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f50.google.com (mail-wm0-f50.google.com [74.125.82.50]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 881EE212 for ; Tue, 16 May 2017 18:17:21 +0000 (UTC) Received: by mail-wm0-f50.google.com with SMTP id b84so142364094wmh.0 for ; Tue, 16 May 2017 11:17:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=axSiGFBKpMTC8PS597wVvmwqRJGMUMObePKurV/NBy4=; b=iBKxXfs7fNd+iEVpGEKZ+hHJk6BmAP8d18fNLzSqNntxUxI7lyFU/vu7odLO9KPf56 B50t3iwYTlAUp6D8SR6rd+dWfHLmiyyMReA18UZRaqAJm/InXayiQEOzTFoKQWnrHF0D GdGKzbFZtVuVR+hCdRL2beo+AyyEIEoExB4MbcF6U1q3ObVelf9kez1IdLkmfj2toaxG HN7v1DFeKjEUDyQ/KBalUylVXVZcayFOqMtcxZa8QTE01xOejSejBqXsWWE0KMIJqc/o bjKOlPjopyFyfNQWbwKY/Hb6XcV7aNpOOG8TDezK+x6XcsX9QtHO1HgwA6VUOShst7kR LSTQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=axSiGFBKpMTC8PS597wVvmwqRJGMUMObePKurV/NBy4=; b=CYlC37wEUgulU+DFa47TCTthd2Z2RJjtzUNCoc4h1pL67ZxLCjD+Af8PN1xfhXKLDo 1cMUJjvK4PBBbaRcDSjNyfC2k1hcF3o3C98Lo1Zucx3w64+Bz12bmgI3kjJwv3gaX5L4 Ad5rp8crd8unHOEI9JD7wm+tDz5V1wYyrZ+BC7+Nl8ai+UDKEJuwwMKgpdj6KpSTzmZp RmCiEDLYCVf3jZMg9ewIyaFCArIZGyV8gLnJmW3FUFFPcp5r9xbmsnEu0INMKmESw2nr yr3vR8EL8Gl+AbFZhW/hhzp5ZaB7ej5IPNGAWIIqY2zQNZPyfWz/uy9dASA09Hzv3D7H hDyQ== X-Gm-Message-State: AODbwcBcVFJuCfmkWTiQEXX7B/KmCUAjqm6c7KIh91OoOYuhA5eavUky RhGieaDDplavaKusREUE6uj+Q4yeqFCP X-Received: by 10.80.180.229 with SMTP id x34mr98299edd.91.1494958640098; Tue, 16 May 2017 11:17:20 -0700 (PDT) MIME-Version: 1.0 Received: by 10.80.135.79 with HTTP; Tue, 16 May 2017 11:17:19 -0700 (PDT) In-Reply-To: <20170516110104.GA5564@fedora-23-dvm> References: <20170516110104.GA5564@fedora-23-dvm> From: Pieter Wuille Date: Tue, 16 May 2017 11:17:19 -0700 Message-ID: To: Peter Todd Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Tue, 16 May 2017 18:18:34 +0000 Cc: Bitcoin Dev Subject: Re: [bitcoin-dev] Rolling UTXO set hashes 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: Tue, 16 May 2017 18:17:23 -0000 On Tue, May 16, 2017 at 4:01 AM, Peter Todd via bitcoin-dev wrote: > To be clear, *none* of the previous (U)TXO commitment schemes require *miners* > to participate in generating a commitment. While that was previously thought to > be true by many, I've seen no counter-arguments to the argument I published I > few months ago(1) that (U)TXO commitments did not require a soft-fork to > deploy. > > 1) "[bitcoin-dev] TXO commitments do not need a soft-fork to be useful", > Peter Todd, Feb 23 2017, > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013591.html I'm aware, I agree, and I even referenced that mail in my original post. However, all of those approaches still require a network wide choice to be useful. A validating node that does not maintain a UTXO X must get a proof of its unspentness from somewhere for at least the block which contains a spend of X. In a world where such a model is deployed network-wide, that proof information is generated by the wallet and relayed wherever needed. In a partial deployment however, you need nodes that can produce the proof for other nodes, and the ability to produce a proof is significantly more expensive than running either an old or a new full node. This ability to produce proofs becomes even harder when there are different models deployed at once. Even just having a different criterion for which UTXOs need a proof (eg. "only outputs created more than 1000 blocks ago") may already cause compatibility issues. Combine that with the multitude of ideas about this (insertion-ordered TXO trees, txid-ordered UTXO Patricia tries, AVL+ trees, append-only bitfield, ...) with different trade-offs (in CPU, RAM for validators, complexity for wallets/index services, ...), I don't think we're quite ready to make that choice. To be clear: I'm very much in favor of moving to a model where the responsibilities of full nodes are reduced in the long term. But before that can happen there will need to be implementations, experiments, analysis, ... Because of that, I think it is worthwhile to investigate solutions to the "how can we efficiently compare UTXO sets" problem separately from the "how do we reduce full node costs by sending proofs instead of it maintaining the data". And rolling UTXO set hashes are a solution for just the first - and one that has very low costs and no normative datastructures at all. -- Pieter