1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
Return-Path: <gmaxwell@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 9D778910
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 23 May 2018 17:28:31 +0000 (UTC)
Received: by mail-ua0-f182.google.com with SMTP id e8-v6so15272932uam.13
for <bitcoin-dev@lists.linuxfoundation.org>;
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: <CADZtCShYnM3A949H18V2+BArA-K9J+cDkd=rX8xRn0+0js5CwA@mail.gmail.com>
References: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com>
<CAAS2fgRF-MhOvpFY6c_qAPzNMo3GQ28RExdSbOV6Q6Oy2iWn1A@mail.gmail.com>
<22d375c7-a032-8691-98dc-0e6ee87a4b08@mattcorallo.com>
<CAAS2fgR3QRHeHEjjOS1ckEkL-h7=Na56G12hYW9Bmy9WEMduvg@mail.gmail.com>
<CADZtCShLmH_k-UssNWahUNHgHvWQQ1y638LwaOfnJEipwjbiYg@mail.gmail.com>
<CAAS2fgQLCN_cuZ-3QPjCLfYOtHfEk=SenTn5=y9LfGzJxLPR3Q@mail.gmail.com>
<CADZtCSjYr6VMBVQ=rx44SgRWcFSXhVXUZJB=rHMh4X78Z2eY1A@mail.gmail.com>
<CAO3Pvs9K3n=OzVQ06XGQvzNC+Aqp9S60kWM9VRPA8hWTJ3u9BQ@mail.gmail.com>
<c23a5346-9f99-44f0-abbf-d7e7979bf1d8@gmail.com>
<CAO3Pvs_MA4TtgCCu1NgCBjK2bZRN+rKnGQJN6m4yTrViBXRiPA@mail.gmail.com>
<CAD3i26BibcaMdbQv-j+Egz_1y0GuhzepBp5ATNpj=Qv8hi1TVA@mail.gmail.com>
<CADZtCShAYpbN=4qNoX5c8yd1j08+mEZzG8gZwcHrj2suY0mb9w@mail.gmail.com>
<CADZtCShYnM3A949H18V2+BArA-K9J+cDkd=rX8xRn0+0js5CwA@mail.gmail.com>
From: Gregory Maxwell <greg@xiph.org>
Date: Wed, 23 May 2018 17:28:29 +0000
X-Google-Sender-Auth: qnMYHLu0nb9-RtXPdgP4B5nd10M
Message-ID: <CAAS2fgTXS5Tains7dfe_Rc9JxR6M=NuFW9UtieRELm+6N2uNog@mail.gmail.com>
To: Jim Posen <jim.posen@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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
<bitcoin-dev@lists.linuxfoundation.org> 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 <jim.posen@gmail.com> 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
>
|
