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 B115E722 for ; Wed, 18 May 2016 23:53:43 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from outmail149043.authsmtp.co.uk (outmail149043.authsmtp.co.uk [62.13.149.43]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id 66A78152 for ; Wed, 18 May 2016 23:53:42 +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 u4INre74068777; Thu, 19 May 2016 00:53:40 +0100 (BST) 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 u4INrcEd006888 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 19 May 2016 00:53:39 +0100 (BST) Received: from [127.0.0.1] (localhost [127.0.0.1]) by petertodd.org (Postfix) with ESMTPSA id 4691C400A9; Wed, 18 May 2016 23:52:11 +0000 (UTC) Received: by localhost (Postfix, from userid 1000) id 8505820583; Wed, 18 May 2016 19:53:36 -0400 (EDT) Date: Wed, 18 May 2016 19:53:36 -0400 From: Peter Todd To: Jorge =?iso-8859-1?Q?Tim=F3n?= Message-ID: <20160518235336.GA1358@fedora-21-dvm> References: <20160517132311.GA21656@fedora-21-dvm> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="FCuugMFkClbJLl1L" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) X-Server-Quench: be538d99-1d53-11e6-829e-00151795d556 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdwsUFVQNAgsB AmAbW1ReVV57Wmo7 bghPaBtcak9QXgdq T0pMXVMcUQERf15S c0oeUh96fw0IeXx0 bE4sDCVeX0wufE9g QxpRFnAHZDJmdWgd WRVFdwNVdQJNdxoR b1V5GhFYa3VsNCMk FAgyOXU9MCtqYAFc QQALIhovfXYsVgUx W1gtBzIwAU1NZj8p IhgrNFcaAA4uM1ky eX8mRhc8OgMfDAZP fQlhDStQNlQNDxYb KktxWksbESFYTCFA GXUA 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 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: Wed, 18 May 2016 23:53:43 -0000 --FCuugMFkClbJLl1L Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, May 18, 2016 at 01:14:59PM +0200, Jorge Tim=F3n wrote: > On May 17, 2016 15:23, "Peter Todd via bitcoin-dev" < > bitcoin-dev@lists.linuxfoundation.org> wrote: > > # TXO Commitments > > >=20 > > Specifically TXO commitments proposes a Merkle Mountain Range=B9 (MMR),= a > > type of deterministic, indexable, insertion ordered merkle tree, which > allows > > new items to be cheaply appended to the tree with minimal storage > requirements, > > just log2(n) "mountain tips". Once an output is added to the TXO MMR it= is > > never removed; if an output is spent its status is updated in place. Bo= th > the > > state of a specific item in the MMR, as well the validity of changes to > items > > in the MMR, can be proven with log2(n) sized proofs consisting of a > merkle path > > to the tip of the tree. >=20 > How expensive it is to update a leaf from this tree from unspent to spent? log2(n) operations. I wrote a full MMR implementation with pruning support as part of my proofchains work: https://github.com/proofchains/python-proofmarshal/blob/master/proofmarshal= /mmr.py Documentation is a bit lacking, but I'd suggest reading the above source co= de and the unit tests(1) to understand what's going on. As of writing item retrieval by index is implemented(2), and if you follow how that works you'= ll see it's log2(n) operations; changing elements in-place isn't yet implemented(3) but would be a fun homework problem. I'll bet anyone a beer = that you'll find it can be done in k*log2(n) operations, with a reasonably small= k. :) Additionally, I also have a merkelized key:value prefix tree implementation called a "merbinner tree" in the same library, again with pruning support. = It does implement changing elements in place(4) with log2(n) operations. Incidentally, something I probably should have made more clear in my TXO commitments post is that the original MMR scheme I developed for OpenTimest= amps (and independently reinvented for Certificate Transparency) is insufficient: while you can easily extract a proof that an element is present in the MMR, that inclusion proof doesn't do a good job of proving the position in the t= ree very well. OpenTimestamps didn't need that kind of proof, and I don't think Certificate Transparency needs it either. However many other MMR applicatio= ns do, including many types of TXO commitments. My proofchains MMR scheme fixes this problem by making each inner node in t= he MMR commit to the total number of elements under it(5) - basically it's a merkle-sum-tree with the size of the tree being what's summed. There may be more efficient ways to do this, but a committed sum-length is easy to implement, and the space overhead is only 25% even in the least optimised implementation possible. 1) https://github.com/proofchains/python-proofmarshal/blob/3f0ba0a9d46f3637= 7ad6c1901de19273604e6fbc/proofmarshal/test/test_mmr.py 2) https://github.com/proofchains/python-proofmarshal/blob/3f0ba0a9d46f3637= 7ad6c1901de19273604e6fbc/proofmarshal/mmr.py#L294 3) https://github.com/proofchains/python-proofmarshal/blob/3f0ba0a9d46f3637= 7ad6c1901de19273604e6fbc/proofmarshal/mmr.py#L230 4) https://github.com/proofchains/python-proofmarshal/blob/3f0ba0a9d46f3637= 7ad6c1901de19273604e6fbc/proofmarshal/merbinnertree.py#L140 5) https://github.com/proofchains/python-proofmarshal/blob/3f0ba0a9d46f3637= 7ad6c1901de19273604e6fbc/proofmarshal/mmr.py#L139 > 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? If it's indexed by outpoint - that is H(txid:n) - to update the STXO you ne= ed 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 e= ver created having position #0, the second #1, etc. the data you may need to up= date the STXO later has predictable locality... but now you have something that's basically identical to my proposed insertion-ordered TXO commitment anyway. 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. --=20 https://petertodd.org 'peter'[:-1]@petertodd.org --FCuugMFkClbJLl1L Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- iQEcBAEBCAAGBQJXPQB9AAoJEGOZARBE6K+yW9kIAIHSFg32zHnSRYvcM13SdJnY jb2CLaDaXf+oRM8Klq2UwZH0R5265zZPGrwCJ5nxwcsO7ypl9yBqkLWUrIeBbvN4 21irs8eydxRGvaa6Wud9xlGZI25loB789j34DJMNDSA8ZTN80g2Te2RB8l3ltlMx 9W52sQW6FjlW/ICy9+EdDeRAx3K8Uc3FVVlyww3zhatZO5uk7kNHRIJ2SoXsjNRM hy7/apBwHZSXUfCNUIpkvlZ0p2+e9dNb8aArzEnsB4V8F/8P8OwVupjC+E7HPwq3 CRXimQgEzS7enZJEtTsVB7vI6wOyvgQWkCmICFIgpBxnKbWJGa5UuOVR82ZvLjc= =NlTI -----END PGP SIGNATURE----- --FCuugMFkClbJLl1L--