From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <pete@petertodd.org> Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id D982BB90 for <bitcoin-dev@lists.linuxfoundation.org>; Fri, 24 Feb 2017 02:58:17 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from outmail149056.authsmtp.com (outmail149056.authsmtp.com [62.13.149.56]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id 15988FC for <bitcoin-dev@lists.linuxfoundation.org>; Fri, 24 Feb 2017 02:58:16 +0000 (UTC) Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232]) by punt21.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1O2wElR023764; Fri, 24 Feb 2017 02:58:14 GMT Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com [52.5.185.120]) (authenticated bits=0) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1O2wCNw090019 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Fri, 24 Feb 2017 02:58:13 GMT Received: from [127.0.0.1] (localhost [127.0.0.1]) by petertodd.org (Postfix) with ESMTPSA id 598DA40576; Fri, 24 Feb 2017 02:58:12 +0000 (UTC) Received: by localhost (Postfix, from userid 1000) id B249A204AB; Thu, 23 Feb 2017 21:58:11 -0500 (EST) Date: Thu, 23 Feb 2017 21:58:11 -0500 From: Peter Todd <pete@petertodd.org> To: Bram Cohen <bram@bittorrent.com> Message-ID: <20170224025811.GA31911@savin.petertodd.org> References: <20170223011506.GC905@savin.petertodd.org> <CAAcC9ys5sUxVfOjogFiF3gzk51D_L=QQkOYevTH=qbh_RkA3Hw@mail.gmail.com> <CA+KqGkrUneGe4yORi=JAAWzoO0UftMUuJm3S-__W5sBh-+T1vQ@mail.gmail.com> <20170223235105.GA28497@savin.petertodd.org> <CA+KqGkowxEZeAFYa2JJchBDtRkg1p3YZNocivzu3fAtgRLDRBQ@mail.gmail.com> <20170224010943.GA29218@savin.petertodd.org> <CA+KqGkrOK76S3ffPJmpqYcBwtSeKESqN16yZsrwzDR6JZZmwFA@mail.gmail.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="HlL+5n6rz5pIUxbD" Content-Disposition: inline In-Reply-To: <CA+KqGkrOK76S3ffPJmpqYcBwtSeKESqN16yZsrwzDR6JZZmwFA@mail.gmail.com> User-Agent: Mutt/1.5.23 (2014-03-12) X-Server-Quench: 156fbad2-fa3d-11e6-829f-00151795d556 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aQdMdAYUHlAWAgsB AmEbW1ZeVVV7WGc7 bghPaBtcak9QXgdq T0pMXVMcUgQXA1ty eFkeWxlydgwIeX5z ZUMsX3VdChYrIURg FB9XQXAHZDJmdWgd WRZFdwNVdQJNdxoR b1V5GhFYa3VsNCMk FAgyOXU9MCtqYA0d aAwRMV8ICWMuJHYQ Sh4DGzQzHEoDLwAA X-Authentic-SMTP: 61633532353630.1037:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 52.5.185.120/25 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. 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 Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> Subject: Re: [bitcoin-dev] A Better MMR Definition X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> X-List-Received-Date: Fri, 24 Feb 2017 02:58:18 -0000 --HlL+5n6rz5pIUxbD Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Thu, Feb 23, 2017 at 06:50:10PM -0800, Bram Cohen wrote: > On Thu, Feb 23, 2017 at 5:09 PM, Peter Todd <pete@petertodd.org> wrote: >=20 > > I think you've misunderstood what TXO commitments are. From my article: > > > > "A merkle tree committing to the state of all transaction outputs, both > > spent > > and unspent, can provide a method of compactly proving the current state > > of an > > output." > > -https://petertodd.org/2016/delayed-txo-commitments#txo-commitments: > > >=20 > The proposal on that page is of a tree which does require random access > updates, it just positions entries in the order they happened to be added > instead of sorting by their hash. Once you start updating it to indicate > spent status all the exact same issues of TXO size and cache coherence on > updates show up again, but now you're using a more complex bespoke data > structure instead of a basic fundamental one. Sorry, but I was replying to your statement: > What you can't do with MMRs or the blockchain is make a compact proof that > something is still in the utxo set, which is the whole point of utxo > commitments. So to be clear, do you agree or disagree with me that you *can* extract a compact proof from a MMR that a given output is unspent? I just want to make sure we're on the same page here before we discuss performance characteristics. --=20 https://petertodd.org 'peter'[:-1]@petertodd.org --HlL+5n6rz5pIUxbD Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- iQEcBAEBCAAGBQJYr6FAAAoJECSBQD2l8JH7tmwIAK34ukxG2HFsKi7n1c87uam0 FcsxU1Kq7juomOxxVCdXuhvjspS32yx2yhMhQKZC8+fzICiPW4khfXAs4eqOUFDZ Rhi7K02c5qEMQocH7t+rY5LBjy93rvosFEP6gbme8ezfC1TZDkaKwVAJs09VeP5X MAJSdY5y7nIl1x5yC+bFhnnlajE0PyGoD0fZr/wuJ6YPaVFmEypBc5z5DK/oz5le 3UrV/VrjAtEhhpVbECjaWD2i/LpqcfB2r1973AYugkUpQQlv8z1xwwgIIeNqMHAc hJXpZeT+E6rpatKcbjidU9fCclWkLTsfyFQ0QLvXdUn0bofsBfID8kzTcqjCqwU= =0QRZ -----END PGP SIGNATURE----- --HlL+5n6rz5pIUxbD--