path: root/be/7d78b5d793b8f0bc86e0b7e63570fab40c437f

Return-Path: <laolu32@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 500FFEB5
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  1 Jun 2018 02:53:02 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f67.google.com (mail-wm0-f67.google.com [74.125.82.67])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 67EA53CC
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  1 Jun 2018 02:53:01 +0000 (UTC)
Received: by mail-wm0-f67.google.com with SMTP id q4-v6so4854567wmq.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 31 May 2018 19:53:01 -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; 
	bh=dm0WiauHhBuf8IPGKYNBEHbC9I3crbZ8kIOllyN3bXE=;
	b=t8vEnEfT/ZW9bSb9Nwd+dwStiGPfk4n+uc1KnTWUoA1T1T9tlaHwoSvu9SwNhI8dnj
	V1SLlGcdUW9fDbsrbZ3yDFQ64fw2F4JRRJvbtqJb/1bDGwWy+IexaI7FarVrnUFQvpko
	Z23NEzUf3IllcWsW2Ji1FKriOMCCh7gbPSMBnRiUOg3jObUrZS1+rq4k6HczZcg0MdsO
	Gy7TfabA/Y3byGy80ekyaRkmd2FSOkENG19otfMjKJfb5+CxfZQhg2vhH1lh9pjeAN3z
	DbVq0nDwUpLrYXmAKW0F4iK05WCg4FbA/lb+IQ1AKfsU8C5lZXoRZjFjBT1yLdjHa3fp
	L1JQ==
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;
	bh=dm0WiauHhBuf8IPGKYNBEHbC9I3crbZ8kIOllyN3bXE=;
	b=sRWRlQD0F8939snFtG8ma5XSOHa4nOjOcJU52BZyebzl0QMYpKcl/AC4MPI1xCGwsu
	ofbrqLisrYMBR5AtaQjmJlpJzGD2oHyyxK2TM1pwnwdMMY4FCvJ8GqAoLZtc90lmtbaa
	e0hVCbzZHqXDAXoA45/EyGMoJ0y2pYePtvXshi+SPIPaMUfYeJCcimWels+tkej6Gur5
	j0y8XPxMz0bKBatlm3sGl+VZXzroej8pQkM/tB5vhqdIODsrOxlK8WKRJ2d0drlj6Z2k
	/zhVYCsdFL/bGQQYQl05z1vTEYQ5rlKecb5GXmZGdYgImpDaCdC19lQ6Mf4kB7u4tjus
	mzcg==
X-Gm-Message-State: ALKqPwfIG5h1p8xnOKtAKYEqnn8gCNLgt0AsmsQtmKpQCUil9JGzJRTX
	7aPEdWevZrBE3WjHLLm+4QbnvkG6KTcj1Tn8dS4=
X-Google-Smtp-Source: ADUXVKIvEuT1wtDj+4VPS/MYQ13Ye3hn7IZ7m/jfy2BE0VF78XDEAx+VGJvhK8Lfy+xNuFe69ymuWzLpfFSbsm57MuY=
X-Received: by 2002:a50:aba5:: with SMTP id
	u34-v6mr9854153edc.252.1527821579880; 
	Thu, 31 May 2018 19:52:59 -0700 (PDT)
MIME-Version: 1.0
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>
	<CAAS2fgTXS5Tains7dfe_Rc9JxR6M=NuFW9UtieRELm+6N2uNog@mail.gmail.com>
	<CAFfwr8F+ghYb2HYEgC7Lh7Z-ytNE7EABr6cxiVXYhWLk-TPO7A@mail.gmail.com>
	<CADZtCShDzPK_jqeOrK4XBoB2uriU9c9T8Dm7By-8ew3XOoAeQg@mail.gmail.com>
	<7E4FA664-BBAF-421F-8C37-D7CE3AA5310A@gmail.com>
	<F87D7069-0FDC-4572-B02B-398A2A455935@gmail.com>
	<CAAS2fgT716PiP0ucoASxryM9y+s9H2z06Z0ToaP1xT3BozAtNw@mail.gmail.com>
	<CADZtCSguto2z6Z9CykymxnCokqo1G=sW0Ov0ht+KcD+KMnYyow@mail.gmail.com>
	<CAO3Pvs-YDzfRqmyJ85wTH0ciccjCvkm5stGyP_tVGGna=PMv3A@mail.gmail.com>
In-Reply-To: <CAO3Pvs-YDzfRqmyJ85wTH0ciccjCvkm5stGyP_tVGGna=PMv3A@mail.gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Thu, 31 May 2018 19:52:48 -0700
Message-ID: <CAO3Pvs9p5COiS_7Jbj1r2iAKTEdXUcnVTRzL27c3=CeuB9WDTQ@mail.gmail.com>
To: Jim Posen <jim.posen@gmail.com>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000008c8ddb056d8bae06"
X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,
	HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no 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: Fri, 01 Jun 2018 02:53:02 -0000

--0000000000008c8ddb056d8bae06
Content-Type: text/plain; charset="UTF-8"

Hi y'all,

I've made a PR to the BIP repo to modify BIP 158 based on this thread, and
other recent threads giving feedback on the current version of the BIP:

  * https://github.com/bitcoin/bips/pull/687

I've also updated the test vectors based on the current parameters (and
filter format), and also the code used to generate the test vectors. Due to
the change in parametrization, the test vectors now target (P=19 M=784931),
and there're no longer any cases related to extended filters.

One notable thing that I left off is the proposed change to use the previous
output script rather than the outpoint. Modifying the filters in this
fashion would be a downgrade in the security model for light clients, as it
would allow full nodes to lie by omission, just as they can with BIP 37. As
is now, if nodes present conflicting information, then the light client can
download the target block, fully reconstruct the filter itself, then ban any
nodes which advertised the incorrect filter. The inclusion of the filter
header checkpoints make it rather straight forward for light clients to
bisect the state to find the conflicting advertisement, and it's strongly
recommended that they do so.

To get a feel for the level of impact these changes would have on existing
applications that depend on the txid being included in the filter, I've
implemented these changes across btcutil, btcd, btcwallet, and lnd (which
previously relied on the txid for confirmation notifications). For lnd at
least, the code impact was rather minimal, as we use the pkScript for
matching a block, but then still scan the block manually to find the precise
transaction (by txid) that we were interested in (if it's there).

-- Laolu


On Mon, May 28, 2018 at 9:01 PM Olaoluwa Osuntokun <laolu32@gmail.com>
wrote:

> > The additional benefit of the input script/outpoint filter is to watch
> for
> > unexpected spends (coins getting stolen or spent from another wallet) or
> > transactions without a unique change or output address. I think this is a
> > reasonable implementation, and it would be nice to be able to download
> that
> > filter without any input elements.
>
> As someone who's implemented a complete integration of the filtering
> technique into an existing wallet, and a higher application I disagree.
> There's not much gain to be had in splitting up the filters: it'll result
> in
> additional round trips (to fetch these distinct filter) during normal
> operation, complicate routine seed rescanning logic, and also is
> detrimental
> to privacy if one is fetching blocks from the same peer as they've
> downloaded the filters from.
>
> However, I'm now convinced that the savings had by including the prev
> output
> script (addr re-use and outputs spent in the same block as they're created)
> outweigh the additional booking keeping required in an implementation (when
> extracting the precise tx that matched) compared to using regular outpoint
> as we do currently. Combined with the recently proposed re-parametrization
> of the gcs parameters[1], the filter size should shrink by quite a bit!
>
> I'm very happy with the review the BIPs has been receiving as of late. It
> would've been nice to have this 1+ year ago when the draft was initially
> proposed, but better late that never!
>
> Based on this thread, [1], and discussions on various IRC channels, I plan
> to make the following modifications to the BIP:
>
>   1. use P=2^19 and M=784931 as gcs parameters, and also bind these to the
>      filter instance, so future filter types may use distinct parameters
>   2. use the prev output script rather than the prev input script in the
>      regular filter
>   3. remove the txid from the regular filter(as with some extra
> book-keeping
>      the output script is enough)
>   4. do away with the extended filter all together, as our original use
> case
>      for it has been nerfed as the filter size grew too large when doing
>      recursive parsing. instead we watch for the outpoint being spent and
>      extract the pre-image from it if it matches now
>
> The resulting changes should slash the size of the filters, yet still
> ensure
> that they're useful enough for our target use case.
>
> [1]:
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/016029.html
>
> -- Laolu
>

--0000000000008c8ddb056d8bae06
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Hi y&#39;all,=C2=A0</div><div><br></div><div>I&#39;ve=
 made a PR to the BIP repo to modify BIP 158 based on this thread, and</div=
><div>other recent threads giving feedback on the current version of the BI=
P:</div><div><br></div><div>=C2=A0 * <a href=3D"https://github.com/bitcoin/=
bips/pull/687">https://github.com/bitcoin/bips/pull/687</a></div><div><br><=
/div><div>I&#39;ve also updated the test vectors based on the current param=
eters (and</div><div>filter format), and also the code used to generate the=
 test vectors. Due to</div><div>the change in parametrization, the test vec=
tors now target (P=3D19 M=3D784931),</div><div>and there&#39;re no longer a=
ny cases related to extended filters.</div><div><br></div><div>One notable =
thing that I left off is the proposed change to use the previous</div><div>=
output script rather than the outpoint. Modifying the filters in this</div>=
<div>fashion would be a downgrade in the security model for light clients, =
as it</div><div>would allow full nodes to lie by omission, just as they can=
 with BIP 37. As</div><div>is now, if nodes present conflicting information=
, then the light client can</div><div>download the target block, fully reco=
nstruct the filter itself, then ban any</div><div>nodes which advertised th=
e incorrect filter. The inclusion of the filter</div><div>header checkpoint=
s make it rather straight forward for light clients to</div><div>bisect the=
 state to find the conflicting advertisement, and it&#39;s strongly</div><d=
iv>recommended that they do so.</div><div><br></div><div>To get a feel for =
the level of impact these changes would have on existing</div><div>applicat=
ions that depend on the txid being included in the filter, I&#39;ve</div><d=
iv>implemented these changes across btcutil, btcd, btcwallet, and lnd (whic=
h</div><div>previously relied on the txid for confirmation notifications). =
For lnd at</div><div>least, the code impact was rather minimal, as we use t=
he pkScript for</div><div>matching a block, but then still scan the block m=
anually to find the precise</div><div>transaction (by txid) that we were in=
terested in (if it&#39;s there).</div><div><br></div><div>-- Laolu</div><di=
v><br></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Mon, May 28,=
 2018 at 9:01 PM Olaoluwa Osuntokun &lt;<a href=3D"mailto:laolu32@gmail.com=
">laolu32@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">=
<div dir=3D"ltr"><div>&gt; The additional benefit of the input script/outpo=
int filter is to watch for<br></div></div><div dir=3D"ltr"><div><div>&gt; u=
nexpected spends (coins getting stolen or spent from another wallet) or</di=
v><div>&gt; transactions without a unique change or output address. I think=
 this is a</div><div>&gt; reasonable implementation, and it would be nice t=
o be able to download that</div><div>&gt; filter without any input elements=
.=C2=A0</div><div><br></div></div></div><div dir=3D"ltr"><div><div>As someo=
ne who&#39;s implemented a complete integration of the filtering</div><div>=
technique into an existing wallet, and a higher application I disagree.</di=
v><div>There&#39;s not much gain to be had in splitting up the filters: it&=
#39;ll result in</div><div>additional round trips (to fetch these distinct =
filter) during normal</div><div>operation, complicate routine seed rescanni=
ng logic, and also is detrimental</div><div>to privacy if one is fetching b=
locks from the same peer as they&#39;ve</div><div>downloaded the filters fr=
om.</div><div><br></div><div>However, I&#39;m now convinced that the saving=
s had by including the prev output</div><div>script (addr re-use and output=
s spent in the same block as they&#39;re created)</div><div>outweigh the ad=
ditional booking keeping required in an implementation (when</div><div>extr=
acting the precise tx that matched) compared to using regular outpoint</div=
><div>as we do currently. Combined with the recently proposed re-parametriz=
ation</div><div>of the gcs parameters[1], the filter size should shrink by =
quite a bit!</div><div><br></div><div>I&#39;m very happy with the review th=
e BIPs has been receiving as of late. It</div><div>would&#39;ve been nice t=
o have this 1+ year ago when the draft was initially</div><div>proposed, bu=
t better late that never!</div><div><br></div><div>Based on this thread, [1=
], and discussions on various IRC channels, I plan</div><div>to make the fo=
llowing modifications to the BIP:</div><div><br></div><div>=C2=A0 1. use P=
=3D2^19 and M=3D784931 as gcs parameters, and also bind these to the</div><=
div>=C2=A0 =C2=A0 =C2=A0filter instance, so future filter types may use dis=
tinct parameters</div><div>=C2=A0 2. use the prev output script rather than=
 the prev input script in the</div><div>=C2=A0 =C2=A0 =C2=A0regular filter<=
/div><div>=C2=A0 3. remove the txid from the regular filter(as with some ex=
tra book-keeping</div><div>=C2=A0 =C2=A0 =C2=A0the output script is enough)=
=C2=A0</div><div>=C2=A0 4. do away with the extended filter all together, a=
s our original use case</div><div>=C2=A0 =C2=A0 =C2=A0for it has been nerfe=
d as the filter size grew too large when doing</div><div>=C2=A0 =C2=A0 =C2=
=A0recursive parsing. instead we watch for the outpoint being spent and</di=
v><div>=C2=A0 =C2=A0 =C2=A0extract the pre-image from it if it matches now<=
/div><div><br></div><div>The resulting changes should slash the size of the=
 filters, yet still ensure</div><div>that they&#39;re useful enough for our=
 target use case.</div><div><br></div><div>[1]: <a href=3D"https://lists.li=
nuxfoundation.org/pipermail/bitcoin-dev/2018-May/016029.html" target=3D"_bl=
ank">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/01602=
9.html</a></div><div><br></div><div>-- Laolu</div></div></div></blockquote>=
</div></div>

--0000000000008c8ddb056d8bae06--