diff options
| author | Peter Todd <pete@petertodd.org> | 2017-02-23 18:51:05 -0500 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2017-02-23 23:51:12 +0000 |
| commit | 7f10fef2def088fb7bfb6d7d3aaf3f440a073aff (patch) | |
| tree | 237974ccebef8d0f51d8ded3f19cc119c92a080f | |
| parent | f3ec9192253c0cc4b830e5ebffd916809b89754e (diff) | |
| download | pi-bitcoindev-7f10fef2def088fb7bfb6d7d3aaf3f440a073aff.tar.gz pi-bitcoindev-7f10fef2def088fb7bfb6d7d3aaf3f440a073aff.zip | |
Re: [bitcoin-dev] A Better MMR Definition
| -rw-r--r-- | 5a/6bf5e7f55f732b0babdb3af4b16a2607074dd5 | 170 |
1 files changed, 170 insertions, 0 deletions
diff --git a/5a/6bf5e7f55f732b0babdb3af4b16a2607074dd5 b/5a/6bf5e7f55f732b0babdb3af4b16a2607074dd5 new file mode 100644 index 000000000..712eb52fa --- /dev/null +++ b/5a/6bf5e7f55f732b0babdb3af4b16a2607074dd5 @@ -0,0 +1,170 @@ +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 0663EC1D + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 23 Feb 2017 23:51:12 +0000 (UTC) +X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 +Received: from outmail148161.authsmtp.com (outmail148161.authsmtp.com + [62.13.148.161]) + by smtp1.linuxfoundation.org (Postfix) with ESMTP id E4ACD176 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 23 Feb 2017 23:51:10 +0000 (UTC) +Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232]) + by punt24.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1NNp8fC082001; + Thu, 23 Feb 2017 23:51:08 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 v1NNp711075267 + (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); + Thu, 23 Feb 2017 23:51:08 GMT +Received: from [127.0.0.1] (localhost [127.0.0.1]) + by petertodd.org (Postfix) with ESMTPSA id 8AFDB40576; + Thu, 23 Feb 2017 23:51:06 +0000 (UTC) +Received: by localhost (Postfix, from userid 1000) + id C6057204AB; Thu, 23 Feb 2017 18:51:05 -0500 (EST) +Date: Thu, 23 Feb 2017 18:51:05 -0500 +From: Peter Todd <pete@petertodd.org> +To: Bram Cohen <bram@bittorrent.com> +Message-ID: <20170223235105.GA28497@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> +MIME-Version: 1.0 +Content-Type: multipart/signed; micalg=pgp-sha256; + protocol="application/pgp-signature"; boundary="Dxnq1zWXvFF0Q93v" +Content-Disposition: inline +In-Reply-To: <CA+KqGkrUneGe4yORi=JAAWzoO0UftMUuJm3S-__W5sBh-+T1vQ@mail.gmail.com> +User-Agent: Mutt/1.5.23 (2014-03-12) +X-Server-Quench: f267c0ba-fa22-11e6-829f-00151795d556 +X-AuthReport-Spam: If SPAM / abuse - report it at: + http://www.authsmtp.com/abuse +X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR + aQdMdAEUHlAWAgsB AmEbWVdeVVx7WWs7 bghPaBtcak9QXgdq + T0pMXVMcUgQWf1wG Bx8eVRxwcQIIeXpx YUMsCHJdWxd6Jxdg + FB9WF3AHZDJmdWgd 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: Thu, 23 Feb 2017 23:51:12 -0000 + + +--Dxnq1zWXvFF0Q93v +Content-Type: text/plain; charset=us-ascii +Content-Disposition: inline +Content-Transfer-Encoding: quoted-printable + +On Thu, Feb 23, 2017 at 03:13:43PM -0800, Bram Cohen wrote: +> On Thu, Feb 23, 2017 at 9:53 AM, Chris Priest via bitcoin-dev < +> bitcoin-dev@lists.linuxfoundation.org> wrote: +>=20 +> > +> > What problem does this try to solve, and what does it have to do with +> > bitcoin? +> > +>=20 +> I can't speak to MMRs (they look a bit redundant with the actual blockcha= +in +> history to my eye) but circling back to utxo commitments, the benefits are + +In what way do you see MMRs as redundant? + +Remember that with UTXO commitments because access patterns are uniform, yo= +u'll +over time have a lot more "redundancy" in the form of lost-coins evenly spr= +ead +out across the whole keyspace. + +> that it enables actual proofs of non-fraud: You can prove the validity of= + a +> block based on just the previous block (and maybe some previous headers +> because of mining rewards) and can prove to a light node that a utxo hasn= +'t +> been spent yet. +> +> A major factor in the way of getting utxo commitments in blocks is +> performance. The txo set is of course vastly larger and more unwieldy. If + +That statement is incorrect with pruning: you can maintain a commitment to = +the +TXO set, without actually storing the entire TXO set, because you don't nee= +d to +store anything for nodes that have already been spent. + +Concretely, this can be done with nothing more than adding a FullySpent node +type to the MMR definition I published earlier, with the rule being that on= +ly a +left or right child of an inner node be a FullySpent node, not both; if both +sides are spent, the inner node itself becomes FullySpent. Equally, I think= + you +can re-use the Empty node for this, but I need to think a little about the +implications re: partial inner nodes. + +Regardless, with a generalized commitment scheme, the serialization/commitm= +ent +to an Empty node is simply '0', the encoding of an unspent txout surrounded= + by +spent txouts will be similar in size to a position integer followed by the +txout... + + +A subtlety of this construction is that you can only prove that a specific +txout # is unspent, but that's actually sufficient, as you can also prove w= +hat +# a txout txid corresponds too with a previous version of the MMR. + +> you make the utxo commitments trail by a small fixed number of blocks +> (between 2 and 5) their latency problems shouldn't be a big deal as long = +as +> the overall performance is good enough. My thesis is that with appropriate +> format and implementation tricks it's possible to get performance good +> enough to no longer be a gating factor to deployment. +>=20 +> Disappointingly there hasn't been any feedback about my implementation, +> just discussion about merkle sets generally. + +Well, I think at this point there's still discussion over whether or not a = +UTXO +set commitment is the right approach to begin with; if it's not your +implementation isn't relevant. + +--=20 +https://petertodd.org 'peter'[:-1]@petertodd.org + +--Dxnq1zWXvFF0Q93v +Content-Type: application/pgp-signature; name="signature.asc" +Content-Description: Digital signature + +-----BEGIN PGP SIGNATURE----- + +iQEcBAEBCAAGBQJYr3VmAAoJECSBQD2l8JH7+UIH/0SpeZNLujsPjE2iac/hXgM0 +0ba5XHB9aGEosO+Q/NpttNPswi3KpHfz251yWQ0nCPBA+8xL8V/nQZy1KfbxAFel +5KKVN0E9lymN7RF9KaTB4uv31/8HhfUomAS/RB6PTewKuy4lN1QMqkkI3KwmXh4O +oeBvdZRaR38Kx532KV1+XisuTpBOxZ0gL6kjsWWXk8UpZRA/1ZDbVz7hG03Hu/TO +9DzXli+bumuUZmcMxbVoGM7nvtz4Yt+32CEYDpwccgS+uOTO8gwod9UN4HpQPiNo +XMZbm2j3XsYp4LSiM98Oj5C917ExWp58QF4uUY7N9OArxE9T054iEbD4wCRUmyE= +=5VXW +-----END PGP SIGNATURE----- + +--Dxnq1zWXvFF0Q93v-- + |