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 9D778910 for ; Wed, 23 May 2018 17:28:32 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ua0-f182.google.com (mail-ua0-f182.google.com [209.85.217.182]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 408256C8 for ; Wed, 23 May 2018 17:28:31 +0000 (UTC) Received: by mail-ua0-f182.google.com with SMTP id e8-v6so15272932uam.13 for ; Wed, 23 May 2018 10:28:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=qUo2PMyPh3dn7O3fG8fZdcPPR5sdcvG/jiEEbu4YHyQ=; b=l6eYS+YVo/oyWvQ2WpRM970FhurcQAuh2DtaEN6CZ+whBmQ8NRB67JqQJyYLZfezmj IRBlm9fEmKnAgHsqu6UGGcGRfc2dlz06Apf8+3oPD86ypeR2Pt6MnSX77voyluYc96ya Rq7VgREifL3rnDvKm1Df7j2JvW/Wt4tz2P23B8j1M7aHSKbNvjPM1P9CpCkEBxdEkj/6 spHgBn0WiEz8fwhyFlrizFW6ahMPvd5B/8bCtqjRLljgGQRHawAryMDFP3hvtTBepHvX 5ve8aLE4+qskaLW0pWlwsv+XcJMdLKgcwIRM4nDlVg/z/SRBlAjJPuId3nzeAV6cGKOG a9+w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=qUo2PMyPh3dn7O3fG8fZdcPPR5sdcvG/jiEEbu4YHyQ=; b=OflIzUUkQ4sNdKXWukcolAXDnmEtrX2haK1wrhdi4b3M4jue8U3SHo+ajmdgyzx5xN IQnTzVReUbC3ovf3DX4+auVXLwfOvV/8cgmGdpykHUZ+BsnUC1SLLTpb8V5YZk2lY8zi UaBANg6or0plH9Bhwtq32VTSsFVzm0lpuU9RHH3A81JiLbzCpBzDgMib0g7vom8Ge7IF 456ENvD/wtMG2jXuORjN8mt+2z++dsYYPM12EE7JeclTD1TikvzV80NKuT1sOT3MkfwD j2TKWjhKwILzGT5SpdH/8tAd9v7Kc3YSF/XTyRL81qKPZHmXB9St+TNhj3d0s6RmaQXq +lQQ== X-Gm-Message-State: ALKqPweH/vZ3+Px5uGI5c/9DYI9dFhNYR0czlOWIkIBaFWUE88mznvay n+kf1U5YMKzUhT8rlhyMxXjItfsbd4tj1hGubNY= X-Google-Smtp-Source: AB8JxZpC6XIgsSDBrgnal/USYQro1aXLVYgIHB+7ByJzb++GThTeWomixMBw/HjDWsEuFjtK+zJNdltqAHYQ+959h08= X-Received: by 2002:ab0:1c16:: with SMTP id a22-v6mr2563127uaj.27.1527096510289; Wed, 23 May 2018 10:28:30 -0700 (PDT) MIME-Version: 1.0 Sender: gmaxwell@gmail.com Received: by 2002:a67:5184:0:0:0:0:0 with HTTP; Wed, 23 May 2018 10:28:29 -0700 (PDT) In-Reply-To: References: <22d375c7-a032-8691-98dc-0e6ee87a4b08@mattcorallo.com> From: Gregory Maxwell Date: Wed, 23 May 2018 17:28:29 +0000 X-Google-Sender-Auth: qnMYHLu0nb9-RtXPdgP4B5nd10M Message-ID: To: Jim Posen , Bitcoin Protocol Discussion Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, 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: Wed, 23 May 2018 17:28:32 -0000 Any chance you could add a graph of input-scripts (instead of input outpoints)? On Wed, May 23, 2018 at 7:38 AM, Jim Posen via bitcoin-dev wrote: > So I checked filter sizes (as a proportion of block size) for each of the > sub-filters. The graph is attached. > > As interpretation, the first ~120,000 blocks are so small that the > Golomb-Rice coding can't compress the filters that well, which is why the > filter sizes are so high proportional to the block size. Except for the > input filter, because the coinbase input is skipped, so many of them have 0 > elements. But after block 120,000 or so, the filter compression converges > pretty quickly to near the optimal value. The encouraging thing here is that > if you look at the ratio of the combined size of the separated filters vs > the size of a filter containing all of them (currently known as the basic > filter), they are pretty much the same size. The mean of the ratio between > them after block 150,000 is 99.4%. So basically, not much compression > efficiently is lost by separating the basic filter into sub-filters. > > On Tue, May 22, 2018 at 5:42 PM, Jim Posen wrote: >>> >>> My suggestion was to advertise a bitfield for each filter type the node >>> serves, >>> where the bitfield indicates what elements are part of the filters. This >>> essentially >>> removes the notion of decided filter types and instead leaves the >>> decision to >>> full-nodes. >> >> >> I think it makes more sense to construct entirely separate filters for the >> different types of elements and allow clients to download only the ones they >> care about. If there are enough elements per filter, the compression ratio >> shouldn't be much worse by splitting them up. This prevents the exponential >> blowup in the number of filters that you mention, Johan, and it works nicely >> with service bits for advertising different filter types independently. >> >> So if we created three separate filter types, one for output scripts, one >> for input outpoints, and one for TXIDs, each signaled with a separate >> service bit, are people good with that? Or do you think there shouldn't be a >> TXID filter at all, Matt? I didn't include the option of a prev output >> script filter or rolling that into the block output script filter because it >> changes the security model (cannot be proven to be correct/incorrect >> succinctly). >> >> Then there's the question of whether to separate or combine the headers. >> I'd lean towards keeping them separate because it's simpler that way. > > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >