diff options
| author | Peter Todd <pete@petertodd.org> | 2016-06-18 18:09:29 -0400 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2016-06-18 22:09:36 +0000 |
| commit | 93290240f5e17a33e655fea24c44782726b704a0 (patch) | |
| tree | 747f35a229d50c6dd4f6dc09127ca31d0abcfb24 | |
| parent | 8ff019d95f751c5914cbe0d3c708b8f8319f31f4 (diff) | |
| download | pi-bitcoindev-93290240f5e17a33e655fea24c44782726b704a0.tar.gz pi-bitcoindev-93290240f5e17a33e655fea24c44782726b704a0.zip | |
Re: [bitcoin-dev] Merkle trees and mountain ranges
| -rw-r--r-- | e6/79f2c9622288cb7d9c9d63c6916c90337b577a | 172 |
1 files changed, 172 insertions, 0 deletions
diff --git a/e6/79f2c9622288cb7d9c9d63c6916c90337b577a b/e6/79f2c9622288cb7d9c9d63c6916c90337b577a new file mode 100644 index 000000000..e3f10343a --- /dev/null +++ b/e6/79f2c9622288cb7d9c9d63c6916c90337b577a @@ -0,0 +1,172 @@ +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 5E7D29D + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 18 Jun 2016 22:09:36 +0000 (UTC) +X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 +Received: from outmail149113.authsmtp.com (outmail149113.authsmtp.com + [62.13.149.113]) + by smtp1.linuxfoundation.org (Postfix) with ESMTP id 6A9E79C + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 18 Jun 2016 22:09:35 +0000 (UTC) +Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247]) + by punt24.authsmtp.com (8.14.2/8.14.2/) with ESMTP id u5IM9XuE074079; + Sat, 18 Jun 2016 23:09:33 +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 u5IM9UEX064633 + (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); + Sat, 18 Jun 2016 23:09:31 +0100 (BST) +Received: from [127.0.0.1] (localhost [127.0.0.1]) + by petertodd.org (Postfix) with ESMTPSA id 4B9DA400E9; + Sat, 18 Jun 2016 22:07:31 +0000 (UTC) +Received: by localhost (Postfix, from userid 1000) + id 8400820278; Sat, 18 Jun 2016 18:09:29 -0400 (EDT) +Date: Sat, 18 Jun 2016 18:09:29 -0400 +From: Peter Todd <pete@petertodd.org> +To: Bram Cohen <bram@bittorrent.com> +Message-ID: <20160618220929.GA24713@fedora-21-dvm> +References: <CA+KqGkosGrWQ2Lpg3Ptc+UyidK7H4_HLQ_QWx2DOAFRmLkv4zQ@mail.gmail.com> + <20160616001040.GA5026@fedora-21-dvm> + <CA+KqGko2jW9999A9vkkBrM3EPb5OXYe4OPu0_Ot=fGnc7Cge-Q@mail.gmail.com> +MIME-Version: 1.0 +Content-Type: multipart/signed; micalg=pgp-sha256; + protocol="application/pgp-signature"; boundary="IS0zKkzwUGydFO0o" +Content-Disposition: inline +In-Reply-To: <CA+KqGko2jW9999A9vkkBrM3EPb5OXYe4OPu0_Ot=fGnc7Cge-Q@mail.gmail.com> +User-Agent: Mutt/1.5.23 (2014-03-12) +X-Server-Quench: 5581974b-35a1-11e6-bcde-0015176ca198 +X-AuthReport-Spam: If SPAM / abuse - report it at: + http://www.authsmtp.com/abuse +X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR + aAdMdwoUEkAaAgsB AmAbWVdeUFR7WmE7 bghPaBtcak9QXgdq + T0pMXVMcUQARfBVk c3YeVB10dAYIeX5x ZkQsW3VTXU19cRRg + QUsFFHAHZDJmdTJM BBVFdwNVdQJNeEwU a1l3GhFYa3VsNCMk + FAgyOXU9MCtqYAFY WAIJIBoOW0sGBXY1 QRxKGDIyG1EMRiN7 NRUgJVMHdAAA +X-Authentic-SMTP: 61633532353630.1038: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] Merkle trees and mountain ranges +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: Sat, 18 Jun 2016 22:09:36 -0000 + + +--IS0zKkzwUGydFO0o +Content-Type: text/plain; charset=us-ascii +Content-Disposition: inline +Content-Transfer-Encoding: quoted-printable + +On Fri, Jun 17, 2016 at 08:22:04PM -0700, Bram Cohen wrote: +> On Wed, Jun 15, 2016 at 5:10 PM, Peter Todd <pete@petertodd.org> wrote: +> > Agreed - regardless of approach adding latency to commitment calculatio= +ns +> > of +> > all kinds is something I think we all agree can work in principle, alth= +ough +> > obviously it should be a last resort technique when optimization fails. +> > +>=20 +> An important point: Adding latency to utxo commitments does not imply +> latency to proofs of inclusion and exclusion! If roots of what's added and +> deleted in each block are added as well, then a proof of inclusion can be +> done by having a proof of inclusion of the trailing utxo set followed by a +> proof of exclusion from all the following deletion sets, or a proof of +> inclusion in one of the single block addition sets followed by proofs of +> exclusion from all the more recent deletion sets. Likewise a proof of +> exclusion can be a proof of exclusion from the utxo set followed by proofs +> of exclusion from all the more recent addition sets or a single proof of +> inclusion in a recent deletion set. +>=20 +> This does make proofs larger (except in the case of recent deletions and +> maybe recent additions) and adds complexity, so it shouldn't be done unle= +ss +> necessary. + +So, to be clear you're assuming that blocks commit to key:value maps of the +block contents, specifically a pre-block "UTXO deletion/things that this bl= +ock +spent" set? First of all, it's interesting how the much smaller dataset of a +pre-block key:value map would make L2/L3 caching optimizations much more li= +kely +to be relevant. :) + + +That type of solution would be very similar to the solutions treechains wou= +ld +need to prove coins haven't been doublespent. Basically, in treechains the +system as a whole is a datastructure indexed by time and prefix. So, if you +want to prove a valid spend you need to convince me of three things: + +1. The coin existed as of time t1 at prefix p + +2. At t2, p, a valid spend was published. + +3. Between t1 and t2 at prefix p no other valid spend was published. + +Paths to any prefix p as of time t, will have about log2(len(p)) size (beyo= +nd +the top-level chain), similar to your above suggestion. Of course, unlike y= +our +above suggestion, in treechains it's not clear if step #1 can be done witho= +ut +another n*log(N)-ish sized proof in a truly trustless environment! + +> But validation before block propagation needs to be extremely +> fast, so for utxo roots this trick is probably both necessary and +> sufficient. + +I'm _not_ of the optinion that validation before propagation needs to be do= +ne +at all - I think it's perfectly reasonable to propgate blocks that you have= + not +validated at all (beyond checking PoW as an anti-DoS measure). The time it +takes miners to start mining the next block - and collecting fees - is howe= +ver +very important. + +In practice, I think we're mostly in agreement here, but because I'm happy = +to +propagate prior to validating I'd be ok with protocol designs that required +miners to have relatively large amounts of RAM - say 32GB - dedicated to UT= +XO +lookup because that wouldn't require relay nodes to also have those kinds of +resources available to them once validationless propagation was implemented. + +--=20 +https://petertodd.org 'peter'[:-1]@petertodd.org + +--IS0zKkzwUGydFO0o +Content-Type: application/pgp-signature; name="signature.asc" +Content-Description: Digital signature + +-----BEGIN PGP SIGNATURE----- + +iQEcBAEBCAAGBQJXZcaWAAoJEGOZARBE6K+ytI4H/2ifzMFzewtKW97h6SVMVD7l +xfSKnAIErFsJYPwjpUXCAL2cdMDTzwCBTvuRcErcAMwYrHodExx+bGyuju7hQbWg +XN3aGcXGsdIsl7U4JXVcvb1gwjg7PPHjWRb8lu7Qk4ai9hlVLGV20AYZwV2IIe6t +WesU3SVBr39OO1sTp1GVTNhwjQpxmqQwsYeIsRhwLV2FJul/fvU7EynI4UN0b09f +tya1f8/Tfyi52SBiKnWL2+Yla165q5ZG532j6FPsZhAhqQhAV/8+B4g5kAHCPLDR +Oi0ucVLOQeGg7jidzIUzyzh51q608OrB8AUDJKxVcPM9BzqbYBkdxFEhdhEmgwg= +=hPgB +-----END PGP SIGNATURE----- + +--IS0zKkzwUGydFO0o-- + |