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 8016E892 for ; Fri, 18 May 2018 06:29:04 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mo.garage.hdemail.jp (mo.garage.hdemail.jp [46.51.242.127]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 42623B0 for ; Fri, 18 May 2018 06:29:03 +0000 (UTC) Received: from ip-10-217-1-36.ap-northeast-1.compute.internal (localhost.localdomain [127.0.0.1]) by mo.garage.hdemail.jp (hde-mf-postfix) with SMTP id D555114C0F1 for ; Fri, 18 May 2018 15:29:01 +0900 (JST) (envelope-from karljohan-alm@garage.co.jp) X-Received: from unknown (HELO mo.garage.hdemail.jp) (127.0.0.1) by 0 with SMTP; 18 May 2018 15:29:01 +0900 X-Received: from mo.garage.hdemail.jp (localhost.localdomain [127.0.0.1]) by mo.garage.hdemail.jp (hde-ma-postfix) with ESMTP id CC05D4C079 for ; Fri, 18 May 2018 15:29:01 +0900 (JST) (envelope-from karljohan-alm@garage.co.jp) Received: from gw27.oz.hdemail.jp (ip-10-126-140-29.ap-northeast-1.compute.internal [10.126.140.29]) by mo.garage.hdemail.jp (hde-mf-postfix) with ESMTP id BFEA314C0F1 for ; Fri, 18 May 2018 15:29:01 +0900 (JST) (envelope-from karljohan-alm@garage.co.jp) X-Received: from mail-qt0-f199.google.com (lb07.oz.hdemail.jp [54.238.57.67]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by gw27.oz.hdemail.jp (Postfix) with ESMTP id 61E31148C145 for ; Fri, 18 May 2018 15:29:01 +0900 (JST) X-Received: by mail-qt0-f199.google.com with SMTP id e8-v6so5947444qtj.0 for ; Thu, 17 May 2018 23:29:01 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=XjHClxWHn70CFG9yvQBZ2H7oy+1UdeSlgziwlT0lvWw=; b=XD+tmhETR1abpbPo9nKS1Q4HANC/dPtxghMonCpte3cXFZHNO+E20dOc7wfFNnhekD 4BWxWIAb1k8Y7VkwH5H+u7D4n4GVCbtxdZ1H53kpEBwqILkCftoupDNI4MWZ0yM7SYh3 7oGTrjXDI/qNQW11daswBORsAVWkjXGx6/aj4S+TOExSWc7Z1H91Jp1krkbJGTRvI4Xe NqBLg8PAbC+Hynagy4eptfcxaADUhS88GkLsBnOPnEEwXTvs3+ETMktfdza3RhJwS3Pk khhBQMNiiOPAY2owaVh1PpSAdP9jljvzVC9+QoYhh2sq8YzdajjHnM25dhcWzhLE8Qch NOgg== X-Gm-Message-State: ALKqPwe1CSoU6TKgACXkDy1kQIy0NCTiffxXLZSYRhi223vDp5m6v16n iAyr988A9IO/pM2VwpAgbUtN4shq/zo2XvLLcKU6WJeKmdSQD4owaclDlUkdqoMQJdtIxniOKp6 iT9c0Kb5x7QkpM8iEovwsQhyeXtWDSjO3Vpm3wd8ICgo3HMbnQeeZYAqDF/kG2s/FIwZI/zmxmP alqv5GH5n9pvbS3YfQEINn6qiK+t7HjN5nNmgWluueKk+VuPjO+41hAeFvzcpdpZhEUdicwrmAf CmD7EnqbXCIYzcjh6HyN6cGv2lNchuQvjbO0PIUDLWj1wnWViOl0MS5T4+6VsZZ3hlPuT1qAVDa r3noIYEzqhdI4wSkHCNcx04YWrg= X-Received: by 2002:a37:338f:: with SMTP id z137-v6mr7297040qkz.233.1526624939695; Thu, 17 May 2018 23:28:59 -0700 (PDT) X-Google-Smtp-Source: AB8JxZp3X4SrUvYbwaf8I2p18Om/1k79SX9kKZJp8a+NyWzDobSW/o5egv01woZhRTwshZM8IKIzHIsrH4uNDI3AT5Q= X-Received: by 2002:a37:338f:: with SMTP id z137-v6mr7297024qkz.233.1526624939358; Thu, 17 May 2018 23:28:59 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.12.208.90 with HTTP; Thu, 17 May 2018 23:28:39 -0700 (PDT) In-Reply-To: References: From: Karl-Johan Alm Date: Fri, 18 May 2018 15:28:39 +0900 Message-ID: To: Matt Corallo , Bitcoin Protocol Discussion Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_NONE 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: Fri, 18 May 2018 06:29:04 -0000 On Fri, May 18, 2018 at 12:25 AM, Matt Corallo via bitcoin-dev wrote: > In general, I'm concerned about the size of the filters making existing > SPV clients less willing to adopt BIP 158 instead of the existing bloom > filter garbage and would like to see a further exploration of ways to > split out filters to make them less bandwidth intensive. Some further > ideas we should probably play with before finalizing moving forward is > providing filters for certain script templates, eg being able to only > get outputs that are segwit version X or other similar ideas. There is also the idea of multi-block filters. The idea is that light clients would download a pair of filters for blocks X..X+255 and X+256..X+511, check if they have any matches and then grab pairs for any that matched, e.g. X..X+127 & X+128..X+255 if left matched, and iterate down until it ran out of hits-in-a-row or it got down to single-block level. This has an added benefit where you can accept a slightly higher false positive rate for bigger ranges, because the probability of a specific entry having a false positive in each filter is (empirically speaking) independent. I.e. with a FP probability of 1% in the 256 range block and a FP probability of 0.1% in the 128 range block would mean the probability is actually 0.001%. Wrote about this here: https://bc-2.jp/bfd-profile.pdf (but the filter type is different in my experiments)