path: root/3f/87c8afcb7be7f757bdb6a3dcbef01d3fa86b4b

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 B115E722
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	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 <pete@petertodd.org>
To: Jorge =?iso-8859-1?Q?Tim=F3n?= <jtimon@jtimon.cc>
Message-ID: <20160518235336.GA1358@fedora-21-dvm>
References: <20160517132311.GA21656@fedora-21-dvm>
	<CABm2gDoj=6CimHm2C0H_qa=o5SRqWr0ZTGamf-qT-kUjt5WXTA@mail.gmail.com>
	<CABm2gDqMQanaY0Eo4QAnx2MrKCSP+v31R6J80jSVx+jOwsVsVw@mail.gmail.com>
	<CABm2gDp9NLKS=+2BhtS3tT2aZjV0sGHUkVV-+n_90w4Ud9Aakw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="FCuugMFkClbJLl1L"
Content-Disposition: inline
In-Reply-To: <CABm2gDp9NLKS=+2BhtS3tT2aZjV0sGHUkVV-+n_90w4Ud9Aakw@mail.gmail.com>
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 <bitcoin-dev@lists.linuxfoundation.org>
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 <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: 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--