Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 8F949F64 for ; Sat, 9 Jun 2018 10:35:33 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from newmail.dtrt.org (li1228-87.members.linode.com [45.79.129.87]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id ED9145E2 for ; Sat, 9 Jun 2018 10:35:32 +0000 (UTC) Received: from harding by newmail.dtrt.org with local (Exim 4.89) (envelope-from ) id 1fRbDX-000174-4r; Sat, 09 Jun 2018 10:35:31 +0000 Date: Sat, 9 Jun 2018 06:34:45 -0400 From: "David A. Harding" To: Olaoluwa Osuntokun , Bitcoin Protocol Discussion Message-ID: <20180609103445.alxrchjbbbxklkzt@email> References: <20180602124157.744x7j4u7dqtaa43@email> <343A3542-3103-42E9-95B7-640DFE958FFA@gmail.com> <37BECD1A-7515-4081-85AC-871B9FB57772@gmail.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="ydb33rmnn437oq7x" Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size 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, 09 Jun 2018 10:35:33 -0000 --ydb33rmnn437oq7x Content-Type: text/plain; charset=us-ascii Content-Disposition: inline On Fri, Jun 08, 2018 at 04:35:29PM -0700, Olaoluwa Osuntokun via bitcoin-dev wrote: > 2. Since the coinbase transaction is the first in a block, it has the > longest merkle proof path. As a result, it may be several hundred bytes > (and grows with future capacity increases) to present a proof to the > client. I'm not sure why commitment proof size is a significant issue. Doesn't the current BIP157 protocol have each filter commit to the filter for the previous block? If that's the case, shouldn't validating the commitment at the tip of the chain (or buried back whatever number of blocks that the SPV client trusts) obliviate the need to validate the commitments for any preceeding blocks in the SPV trust model? > Depending on the composition of blocks, this may outweigh the gains > had from taking advantage of the additional compression the prev outs > allow. I think those are unrelated points. The gain from using a more efficient filter is saved bytes. The gain from using block commitments is SPV-level security---that attacks have a definite cost in terms of generating proof of work instead of the variable cost of network compromise (which is effectively free in many situations). Comparing the extra bytes used by block commitments to the reduced bytes saved by prevout+output filters is like comparing the extra bytes used to download all blocks for full validation to the reduced bytes saved by only checking headers and merkle inclusion proofs in simplified validation. Yes, one uses more bytes than the other, but they're completely different security models and so there's no normative way for one to "outweigh the gains" from the other. > So should we optimize for the ability to validate in a particular > model (better security), or lower bandwidth in this case? It seems like you're claiming better security here without providing any evidence for it. The security model is "at least one of my peers is honest." In the case of outpoint+output filters, when a client receives advertisements for different filters from different peers, it: 1. Downloads the corresponding block 2. Locally generates the filter for that block 3. Kicks any peers that advertised a different filter than what it generated locally This ensures that as long as the client has at least one honest peer, it will see every transaction affecting its wallet. In the case of prevout+output filters, when a client receives advertisements for different filters from different peers, it: 1. Downloads the corresponding block and checks it for wallet transactions as if there had been a filter match This also ensures that as long as the client has at least one honest peer, it will see every transaction affecting its wallet. This is equivilant security. In the second case, it's possible for the client to eventually probabalistically determine which peer(s) are dishonest and kick them. The most space efficient of these protocols may disclose some bits of evidence for what output scripts the client is looking for, but a slightly less space-efficient protocol simply uses randomly-selected outputs saved from previous blocks to make the probabalistic determination (rather than the client's own outputs) and so I think should be quite private. Neither protocol seems significantly more complicated than keeping an associative array recording the number of false positive matches for each peer's filters. -Dave --ydb33rmnn437oq7x Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEEgxUkqkMp0LnoXjCr2dtBqWwiadMFAlsbrUUACgkQ2dtBqWwi adO0wA//Wlb2LhZxkp2OGtB+HrW4B110hUvWHBn7B5+WA1bEvgReu2sQt2WJWd3w bBRCja78yJw4573mAq7wkk57NO8Oob70Rg1fdfVx9Otld1ldKM51VpZh1Yk+JWMi Z2zsBk8Cd5VipjRQ3IUNn+YszOIcwwhen4bYQok8PBIslPbvbyaysd+UQi/WE8A9 Uj3QqDAfliqK+aX7BOeMzxhVQp1xjOOoOC9cYi84QxJKbtAGFuzAmRsnavRRicA3 sodsk+qk2M8P58D0dgwVowyOQh4h4uXmsqXKM5gFVyNnjT5lkrD51K6TH1ja3X1j fdFsX9A5A5uHlTepZiRWC2LeBPdmGdmLw9Hba9IuvRPVQ9Kyk4ww0oGo1SH7gPfZ aHq6yBTYp/QgKjxema2wzcvtpFyEJJaiSmnmD/VdVZYkiXFlAwE/uRW+Fpz/r7i+ YXNTs67Jz0HSaqKVJe6/o7CT/zCWtjBjXHHd8u5Kfel2QdkAAb+1HTRDaXLUTVwn 3KrOx6bNFh3QnJKAF7BSfwcagkYRRbV6Rq3qeLsNDftzF98DYE+Q6bmDF3mhC22j P/RivfsLaPcJiJ4rIelsKxIDWHcTzVmxEBctsnAtqxryNRewvpUe8yu8L/Uq9Ea3 hc8UgSlkpIerrwpu9M8XY+w/PzNeR5ikqzUrSP0iddhzlTzNeIw= =/c0/ -----END PGP SIGNATURE----- --ydb33rmnn437oq7x--