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 1EB28305 for ; Sun, 28 Jun 2015 15:51:57 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wi0-f175.google.com (mail-wi0-f175.google.com [209.85.212.175]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 69BE1A7 for ; Sun, 28 Jun 2015 15:51:55 +0000 (UTC) Received: by wiwl6 with SMTP id l6so80079869wiw.0 for ; Sun, 28 Jun 2015 08:51:54 -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:in-reply-to:references:date :message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=XUPfS9Rh7xnj1t8xtwkiVQ0zQAfR/XkQwHsWyK7AM6U=; b=UZ4huqZDs8IatkWbLoWjbP6j0fIfNK7m1uK7TUEdBPgDXMDTpDqa7hL03n2dWmQmGQ Q5Lq3IR4jv0LVAi60etnj2BRsNpl9TrGBQWkXRtlO+4EHdMgJWZCbqb8/XBFYqRT7eC+ f+i6i+XnF2HSkAC9H27p5prYFBWAJVDmXeCO2e/jvQzTDqCfLuSzIBethoUCk6KBawho JZeXmgTrckAl4pge7lxwZV78r39/a/NKSvWowFYEGhHpJ+KqbMzTxplg1/AWef+0gfbg XMBBvtDR+lmzBaIxWezR2XEFxGLjzQJlrO9S8xIdMC54exzz+r3QQB482k1qrUm0OF+9 L48Q== X-Gm-Message-State: ALoCoQluAngHJxU6BXIWs6cZyBMM2hdz3CCdDO0wMrOPkuwFrdfSaO2/0Z3mbvzqW+vah8/A5G3I MIME-Version: 1.0 X-Received: by 10.194.58.7 with SMTP id m7mr20353272wjq.109.1435506714190; Sun, 28 Jun 2015 08:51:54 -0700 (PDT) Received: by 10.194.95.168 with HTTP; Sun, 28 Jun 2015 08:51:54 -0700 (PDT) In-Reply-To: References: <1164261435450448@web14h.yandex.ru> <558F583C.1000500@gmail.com> <2A94BDF7-F265-4D36-B438-DC4F432E1C67@gmail.com> <558F8634.90904@gmail.com> <38C2E2A1-EB6C-48EB-8FA1-7FAA97B3E911@gmail.com> Date: Sun, 28 Jun 2015 17:51:54 +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=-2.6 required=5.0 tests=BAYES_00,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@lists.linuxfoundation.org Subject: Re: [bitcoin-dev] 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 15:51:57 -0000 On Sun, Jun 28, 2015 at 5:23 PM, Mark Friedenbach wr= ote: > UTXO commitments are the nominal solution here. You commit the validator = state in each block, and then you can prove things like a negative by refer= encing that state commitment. The trouble is this requires maintaining a ha= sh tree commitment over validator state, which turns out to be insanely exp= ensive. With the UTXO commitment scheme (the others are not better) that en= ds up requiring 15 - 22x more I/O during block validation. And I/O is prese= ntly a limiter to block validation speed. So if you thought 8MB was what bi= tcoin today could handle, and you also want this commitment scheme for frau= d proofs, then you should be arguing for a block size limit decrease (to 50= 0kB), 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.