Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 842BFDA3 for ; Mon, 4 Jun 2018 08:42:23 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f53.google.com (mail-it0-f53.google.com [209.85.214.53]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 13B34136 for ; Mon, 4 Jun 2018 08:42:23 +0000 (UTC) Received: by mail-it0-f53.google.com with SMTP id j186-v6so9199034ita.5 for ; Mon, 04 Jun 2018 01:42:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=jTKO/ZM1/bIQ2vg/DOnIpOuDINM7/DKZolNZgLHA/pQ=; b=nrsyib+Np6idpTtJmJTFtGLnTubB6W0YdSiZIzYAHjsfIiJn5bHrC61g2Mezh7NRLi x1I+R3YZN07Ou5X98h0Bxg/vc6B3Dx+uxb3t5qVoxO9n+5ya3eeVNsbLdaoUBuAacVV/ W4Qu85l9dquckTzXYn4tCSvbPFaMzAVEGxW8nIDb852+TYvy93iq+UyAIGpgT3F1AONS wt5UtPa8E8REHAtDbPjKFIpDkKWaqwEtjHSCuLbH1yC7499olxV8vB3/8GlkDAYHDkbv 0ROxgnh1IuAtweM9lkQOJG4zEDoVPdBnNrMrPCdt5rxvBAIT6KmhFuaP2MpBEblN7M00 9a1g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=jTKO/ZM1/bIQ2vg/DOnIpOuDINM7/DKZolNZgLHA/pQ=; b=YcnmMjxQSXVTIRRRhPIWiMz1RM3E0YpZJxnoybzALzr+6ytqJ5qqS1oWQ8QjZGgxlb 3Bn1znxZpCfObczRAvcywe+wddeqBf1svwRG1ru60LUndk+6zGXVeT78Eb3Mv9cs7ECc Bt71jXq5pFQRkk20ijHDHrhZLsX1c5rl1jKa4UK/dHKzKdauVZDSWe9MxAeR2MOqOF/p +JUZfor5h5fX+8YKORQQMWkxX5XhPrgHC6aKbPnqi0+dLPGEnZHJpy6+e2nSTQJUzE5b HRVqT/79L2Y8b4iummQ8Zwb21SbVod+vQrJL5IXBCANIJQJZuNJ7ScmQA5W/OMis6hZs /vaA== X-Gm-Message-State: APt69E0ahc6ND7Vp+CXvO9++EfytYM4pWsaG6hAQy+zxi3ElDvamrU3l PTmP8RA+tPM+3mKG3Ni2LrmuP6IwKwQ+d13MmG0= X-Google-Smtp-Source: ADUXVKLtBQ8pKcZ8lCJmlLmSXcKe0Vn6aKfybQXHDc9fIjp65INDMCjCJN7jdpWU0UD+AW5tgCm5EalXfIVVHU/9MCo= X-Received: by 2002:a24:5112:: with SMTP id s18-v6mr10566062ita.151.1528101742343; Mon, 04 Jun 2018 01:42:22 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Riccardo Casatta Date: Mon, 4 Jun 2018 10:42:10 +0200 Message-ID: To: karljohan-alm@garage.co.jp, Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000887cf9056dcce976" X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,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, 04 Jun 2018 14:26:50 +0000 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: Mon, 04 Jun 2018 08:42:23 -0000 --000000000000887cf9056dcce976 Content-Type: text/plain; charset="UTF-8" I was wondering why this multi-layer multi-block filter proposal isn't getting any comment, is it because not asking all filters is leaking information? Thanks Il giorno ven 18 mag 2018 alle ore 08:29 Karl-Johan Alm via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> ha scritto: > 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) > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > -- Riccardo Casatta - @RCasatta --000000000000887cf9056dcce976 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I w= as wondering why this multi-layer multi-block filter proposal isn't get= ting any comment,
is it because not asking all filters is leaking information?

Thanks

Il giorno ven 18 mag 2018 alle ore 08:29 Karl= -Johan Alm via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> ha scritto:
<= /div>
On Fri, May 18, 2018 at 12:25 AM, Matt = Corallo via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> In general, I'm concerned about the size of the filters making exi= sting
> SPV clients less willing to adopt BIP 158 instead of the existing bloo= m
> filter garbage and would like to see a further exploration of ways to<= br> > split out filters to make them less bandwidth intensive. Some further<= br> > ideas we should probably play with before finalizing moving forward is=
> providing filters for certain script templates, eg being able to only<= br> > 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 f= ilter
type is different in my experiments)
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev


--
Riccardo Casatta - @RCasatta
--000000000000887cf9056dcce976--