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 5E7D29D for ; 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 ; 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 To: Bram Cohen Message-ID: <20160618220929.GA24713@fedora-21-dvm> References: <20160616001040.GA5026@fedora-21-dvm> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="IS0zKkzwUGydFO0o" Content-Disposition: inline In-Reply-To: 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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--