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 952DF26C for ; Mon, 9 May 2016 08:57:14 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-lf0-f52.google.com (mail-lf0-f52.google.com [209.85.215.52]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3C4CC174 for ; Mon, 9 May 2016 08:57:10 +0000 (UTC) Received: by mail-lf0-f52.google.com with SMTP id u64so192935696lff.3 for ; Mon, 09 May 2016 01:57:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc; bh=Qz3hKT6Xj8IHLZLm4c9xTV+oA3D1E/s1VfZApqVHCwA=; b=XC4S7dTb+UaenbIezFREZOnDYr8PKDXxjngr/ATCuzUp6pCoMg33u7wX4i+dlZl0+K i1XZ2eL+OBLlEUMLcsm0rjJGMMaoMvvWBPS9+XeGsJa6KqOvsB79U8iJ2pxiukWONCYa RKlvl4y34pc+NHnK8zmSo1waSh527VKn1h/GgkkH+gCEML30NJOzot2JHo8wM13/1ef8 LUFB1yOFH4lcGmfk5RY2gPDPOYV/CJuIboAbZa6d01TdytY5MSLD2HblCq0yy4H02gFc jFTnHkRGixEba11tb/WcEAjSk7dQO3wdUazn/VYKBNE9gvZ8gNtMGDJHVUOSsAen1uvy xZIw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:in-reply-to:references:date :message-id:subject:from:to:cc; bh=Qz3hKT6Xj8IHLZLm4c9xTV+oA3D1E/s1VfZApqVHCwA=; b=RYpnxpNoUbdSKte2wKrVr2iVe9bgSMpl0wROxqSj5xweG1E3g4BXoGLdsPp76MdNSG vgwqmSNhwXx9y+qeyJujOFX4D05FVdVhVM0hZrF2ztmg5zuvWXEL+FAY/eZIkkGLPI50 CEpFuo8g3e5SRX57DN2ai+Q3Yec6oOn66ltEs+dzkg5/z8WTc7W6q/OQI2SjsM1Kpi7/ 1XnLJOD4YtmvJIfT+GQRY7ZBFsyJxCKShRn0qhX4Un2W2DP5eOjMxWJ4xOxxYsb3K1q5 lJ6h/EBp3uG/NLVnqrnCHIALr6R+CScLoBe7HETFZGG5jJmPQSIDQykf6r7/ag8oVfx0 7BlQ== X-Gm-Message-State: AOPr4FXi1LNFmZe3AIBEVQFvb9V7bd5px5kouoR01O1YFIMw/09Z75KqDHp+2MPydAwrW4FS9NRSynzZiM6FPQ== MIME-Version: 1.0 X-Received: by 10.112.202.164 with SMTP id kj4mr14511365lbc.141.1462784228702; Mon, 09 May 2016 01:57:08 -0700 (PDT) Sender: gmaxwell@gmail.com Received: by 10.112.65.108 with HTTP; Mon, 9 May 2016 01:57:08 -0700 (PDT) In-Reply-To: <71d822e413ac457a530e1c367811cc24@cock.lu> References: <71d822e413ac457a530e1c367811cc24@cock.lu> Date: Mon, 9 May 2016 08:57:08 +0000 X-Google-Sender-Auth: PfbMDoFd7h9LnlewuYuIWnntc1E Message-ID: From: Gregory Maxwell To: bfd@cock.lu Content-Type: text/plain; charset=UTF-8 X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, 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 X-Mailman-Approved-At: Mon, 09 May 2016 09:11:33 +0000 Cc: Bitcoin Dev Subject: Re: [bitcoin-dev] Committed bloom filters for improved wallet performance and SPV security X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 09 May 2016 08:57:14 -0000 On Mon, May 9, 2016 at 8:26 AM, bfd--- via bitcoin-dev wrote: > We introduce several concepts that rework the lightweight Bitcoin > client model in a manner which is secure, efficient and privacy > compatible. [...] > A Bloom Filter Digest is deterministically created of every block I think this is a fantastic idea. Some napkin work shows that it has pretty good communications bandwidth so long as you assume that the wallet has many keys (e.g. more than the number of the outputs in the block)-- otherwise BIP37 uses less bandwidth, but you note its terrible privacy problems. You should be aware that when the filter is transmitted but not updated, as it is in these filtering applications, the bloom filter is not the most communication efficient data structure. The most efficient data structure is similar to a bloom filter, but you use more bits and only one hash function. The result will be mostly zero bits. Then you entropy code it using RLE+Rice coding or an optimal binomial packer (e.g. https://people.xiph.org/~greg/binomial_codec.c). This is about 45% more space efficient than a bloom filter. ... it's just a PITA to update, though that is inapplicable here. Entropy coding for this can be quite fast, if many lookups are done the decompression could even be faster than having to use two dozen hash functions for each lookup. The intuition is that this kind of simple hash-bitmap is great, but space inefficient if you don't have compression since most of the bits are 0 you end up spending a bit to send less than a bit of information. A bloom filter improve the situation by using the multiple filters to increase the ones density to 50%, but the increased collisions create overhead. This is important when its a in-memory data-structure that you're updating often, but not here. One thing to do with matching blocks is after finding the matches the node could potentially consult some PIR to get the blocks it cares about... thus preventing a leak of which blocks it was interested in, but not taking PIR costs for the whole chain or requiring the implementation of PIR tree search (which is theoretically simple but in practice hard to implement).