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 9D137C75 for ; Tue, 5 Jun 2018 17:22:17 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-qt0-f178.google.com (mail-qt0-f178.google.com [209.85.216.178]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 296546EE for ; Tue, 5 Jun 2018 17:22:17 +0000 (UTC) Received: by mail-qt0-f178.google.com with SMTP id s9-v6so3267171qtg.2 for ; Tue, 05 Jun 2018 10:22:17 -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=5wpSKXqSBrjmir9m9BvTJrEFLOzcqCa+yTYdQ1pGXO8=; b=OfrgCcsg2cZMO3sVOCtLM8XHM8Jy9+pKFk3ApQvuxTp4SmYGzqTMkoaqehZCCdWCK5 Tp+Kj3RKnPiRlnwxxauo2HsDSw7/yl3TSKo64obqli1kpFDQ0+eyS49w7QX6rMggPqqK ZWlCeaPzseAb2tOc8VokyqLJUkSq+J83OW9tE86C4BvuV+yEZxfBAOs868iq/jUUx2wY Xv8nREV/k6r9EzHMgiK+sp0TOKAt0GyfP+luv+WcZm8D22+21CjCkdpmFL3Sr9tBu18S 2nlGftbgFYueaLVzbBqtEWRA4HefpIVZDQgw7SqrEDgEQmGu4uMnyXaV8iZ0a01KqLIi zt1A== 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=5wpSKXqSBrjmir9m9BvTJrEFLOzcqCa+yTYdQ1pGXO8=; b=JkQLHSd2+ogdnCgY0YwvjN3tm2Z3UZuWeyI44PrjYdAnI1I8U13iZawG5S9CpnRSrP tG3ag8YlA0Rxx9G9a9SiBdcuJ7/HmNGt4hIcCT2fZYbOUnjewJ36AQERtb0y6XxLsYtV 3He2uYoZOVNdJ/HFZUjXuD011jEX0gBEZJAEwkH0zP28fx5xFGdnUz3brk+kRL4J1SgX 2WeS7tQ0Zv5F4VYPZHhc3qQ4R0Q4e6GUfT5mZRow3THpN1IAmiNK2TRrKim1xBMrtCT8 JJ/qMtmS0/t8DTDoWhWdOdoMj1JB4CKQY6HHJ8MgOVvCO425PDTdwWBQdo9yAmMvYod1 AP2g== X-Gm-Message-State: APt69E0LGHNxK1OHBc3OaBNW+rl2dy2oEApTWIcDImPb55noxotUeKn3 gUcaHsKrzPRdNuRbNS4cP/HGfyaBbBVBqbpR4cM= X-Google-Smtp-Source: ADUXVKIMknoZQVYTkXo4j3qfal0v9qmSfKvoAN+gHkhhSPzSpTjqjFVkoxqeND7U8ZIdf4ETJFJ9L0mOYSy4ZUA+vcA= X-Received: by 2002:ac8:2f99:: with SMTP id l25-v6mr24540263qta.166.1528219336206; Tue, 05 Jun 2018 10:22:16 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Jim Posen Date: Tue, 5 Jun 2018 10:22:04 -0700 Message-ID: To: Karl Johan Alm Content-Type: multipart/alternative; boundary="000000000000ac700f056de84aa9" 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: Tue, 05 Jun 2018 17:38:31 +0000 Cc: Bitcoin Protocol Discussion 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: Tue, 05 Jun 2018 17:22:17 -0000 --000000000000ac700f056de84aa9 Content-Type: text/plain; charset="UTF-8" > > I don't understand this comment. The bandwidth gains are not from > address reuse, they are from the observed property that false > positives are independent between two filters. I.e. clients that > connect once a day will probably download 2-3 filters at most, if they > had nothing relevant in the last ~144 blocks. > Your multi-layer digest proposal (https://bc-2.jp/bfd-profile.pdf) uses a different type of filter which seems more like a compressed Bloom filter if I understand it correctly. Appendix A shows how the FP rate increases with the number of elements. With the Golomb-Coded Sets, the filter size increases linearly in the number of elements for a fixed FP rate. So currently we are targeting an ~1/2^20 rate (actually 1/784931 now), and filter sizes are ~20 bits * N for N elements. With a 1-layer digest covering let's say 16 blocks, you could drop the FP rate on the digest filters and the block filters each to ~10 bits per element, I think, to get the same FP rate for a given block by your argument of independence. But the digest is only half the size of the 16 combined filters and there's a high probability of downloading the other half anyway. So unless there is greater duplication of elements in the digest filters, it's not clear to me that there are great bandwidth savings. But maybe there are. Even so, I think we should just ship the block filters and consider multi-layer digests later. --000000000000ac700f056de84aa9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I don't understand this comment. The bandwidth gains= are not from
address reuse, they are from the observed property that false
positives are independent between two filters. I.e. clients that
connect once a day will probably download 2-3 filters at most, if they
had nothing relevant in the last ~144 blocks.

Your multi-layer digest proposal (https://bc-2.jp/bfd-profile.pdf) uses a different type of fil= ter which seems more like a compressed Bloom filter if I understand it corr= ectly. Appendix A shows how the FP rate increases with the number of elemen= ts.

With the Golomb-Coded Sets, the filter size in= creases linearly in the number of elements for a fixed FP rate. So currentl= y we are targeting an ~1/2^20 rate (actually 1/784931 no= w), and filter sizes are ~20 bits * N for N elements. With a 1-layer digest= covering let's say 16 blocks, you could drop the FP rate on the digest= filters and the block filters each to ~10 bits per element, I think, to ge= t the same FP rate for a given block by your argument of independence. But = the digest is only half the size of the 16 combined filters and there's= a high probability of downloading the other half anyway. So unless there i= s greater duplication of elements in the digest filters, it's not clear= to me that there are great bandwidth savings. But maybe there are. Even so= , I think we should just ship the block filters and consider multi-layer di= gests later.
--000000000000ac700f056de84aa9--