summaryrefslogtreecommitdiff
path: root/e9/c6e416f70fcc5d8430b3c25c0b07eab8bee403
blob: 9fba75f6455a83198e0e8af24a7ea29158e46877 (plain)
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
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 C34A7AB18
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed,  6 Feb 2019 00:17:22 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-yw1-f52.google.com (mail-yw1-f52.google.com
	[209.85.161.52])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C3902762
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed,  6 Feb 2019 00:17:20 +0000 (UTC)
Received: by mail-yw1-f52.google.com with SMTP id f65so2462490ywc.8
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 05 Feb 2019 16:17:20 -0800 (PST)
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=CLN9HSPaPXMqcOHdYtFW7oaTSwkcX1uU1iBkCtK7qfc=;
	b=lf+k1A4kiGzpd11lJ0NQBv1o91fY80ORLX8CC1N0PIc9hcCOJonMA1Vf9uInuPtq2L
	/1rupDLtJ2A5+RH5D5q7dPe6yDXlGy7SwIxoHyLEtBg0m15Q6AVJJSGUQ1bbCmDO+Bmt
	u0DdpIeB2Rnh0cHggUpGMZoJ/QVBSsdJk4JRKOakMqkJPbC7WeRcQup7jFeNZnlHUQyA
	4Fa0uIH0W8bk1tbUwhb8BuBCDJr3w03tQ1kKLVZCeVVGyEhdShyEfbd36gKsYq0tVrq4
	HQwcFWcwCz5u2Qy8lY54l9lFH4B7ITye7Vxdu5HzRSccMM5ghuD1OLDHUoka4XDePAM6
	PUaw==
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=CLN9HSPaPXMqcOHdYtFW7oaTSwkcX1uU1iBkCtK7qfc=;
	b=ng/8JEa9SsjLkVP3z8oN0RdC26nUF4U1Ev/sk/aZkveo+GweTGf2+/FRkC1L2YFLwS
	bo/gg5VjhBE8MRgkwZSxdQYDQ/IfLgr5dGN5qBPUf0z+PARP1gU4PfpaNu8cJPrZqATP
	rm3c/eE/CfUuDfVKWa+66lAkzf1IqEFpXkFok9vFpAGdtpiP12msqOFcBg7Lpz0I6R2y
	7PZD1EX5YDFSuq8zWhwp4mdpJXOT4KCxpLUklr9fk7ctn2rlH615KBvvD9yjZzegIDSC
	ip+AtBfUfTPWrg4dn7CSxBjOXHfCwUAuLdTit05YZKetwx8RfiCsNIH05TY6nJYcyg0W
	SD2g==
X-Gm-Message-State: AHQUAube5bFus4tPdRnuCnU801iLWhPieApKPfs4Rt/jp5QyeLMYHs5f
	vXNiEwJGVR+1d9JiA+LGKPlymc9d0z8qORhTw10=
X-Google-Smtp-Source: AHgI3IZ/QLAzooCJBUoO2sqM2/WnYq2ugo7aIYzfRAMrZqtx+w9NpXWihPMMMyjPOLeLOs62ORqnHMSAHev7Fke0NIA=
X-Received: by 2002:a81:9b10:: with SMTP id s16mr6426581ywg.335.1549412239660; 
	Tue, 05 Feb 2019 16:17:19 -0800 (PST)
MIME-Version: 1.0
References: <6D57649F-0236-4FBA-8376-4815F5F39E8A@gmail.com>
	<CADZtCSgKu1LvjePNPT=0C0UYQvb47Ca0YN+B_AfgVNTpcOno4w@mail.gmail.com>
	<CDAFC2F7-A0AD-460B-B5B1-A717F7EC700E@gmail.com>
	<CAO3Pvs_gvYy99Bch=7RwVszM_0PFTKUyqDVok=xfm4OOcqwaaQ@mail.gmail.com>
	<6D36035C-A675-4845-9292-3BC16CD19B41@gmail.com>
In-Reply-To: <6D36035C-A675-4845-9292-3BC16CD19B41@gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Tue, 5 Feb 2019 16:17:05 -0800
Message-ID: <CAO3Pvs_Ai9d_uHC2a3ndGXhBoV-PDp2y_NShkbn=hRuzu=wNFw@mail.gmail.com>
To: Tamas Blummer <tamas.blummer@gmail.com>
Content-Type: multipart/alternative; boundary="00000000000027dc5d05812ea652"
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
X-Mailman-Approved-At: Wed, 06 Feb 2019 15:48:05 +0000
Cc: Jim Posen <jimpo@coinbase.com>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Interrogating a BIP157 server,
	BIP158 change proposal
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, 06 Feb 2019 00:17:22 -0000

--00000000000027dc5d05812ea652
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Tamas,

> The only advantage I see in the current design choice is filter size, but
> even that is less impressive in recent history and going forward, as
address
> re-use is much less frequent nowadays than it was Bitcoin=E2=80=99s early=
 days.

Gains aren't only had with address re-use, it's also the case that if an
input is spent in the same block as it was created, then only a single item=
s
is inserted into the filter. Filters spanning across several blocks would
also see savings due to the usage of input scripts.

Another advantage of using input scripts is that it allows rescans where al=
l
keys are known ahead of time to proceed in parallel, which can serve to
greatly speed up rescans in bitcoind. Additionally, it allows light clients
to participate in protocols like atomic swaps using the input scripts as
triggers for state transitions. If outpoints were used, then the party that
initiated the swap would need to send the cooperating party all possible
txid's that may be generated due to fee bumps (RBF or sighash single
tricks). Using the script, the light client simply waits for it to be
revealed in a block (P2WSH) and then it can carry on the protocol.

> Clear advantages of moving to spent outpoint + output script filter:

> 1. Filter correctness can be proven by downloading the block in question
only.

Yep, as is they can verify half the filter. With auxiliary data, they can
verify the entire thing. Once committed, they don't need to verify at all.
We're repeating a discussion that played out 7 months ago with no new
information or context.

> 2. Calculation of the filter on server side does not need UTXO.

This is incorrect. Filter calculation can use the spentness journal (or und=
o
blocks) that many full node implementations utilize.

> This certainly improves with a commitment, but that is not even on the
> roadmap yet, or is it?

I don't really know of any sort of roadmaps in Bitcoin development. However=
,
I think there's relatively strong support to adding a commitment, once the
current protocol gets more usage in the wild, which it already is today on
mainnet.

> Should a filter be committed that contains spent outpoints, then such
> filter would be even more useful

Indeed, this can be added as a new filter type, optionally adding created
outpoints as you referenced in your prior email.

> Since Bitcoin Core is not yet serving any filters, I do not think this
> discussion is too late.

See my reply to Matt on the current state of deployment. It's also the case
that bitcoind isn't the only full node implementation used in the wild.
Further changes would also serve to delay inclusion into bitcoind. The
individuals proposing these PRs to bitcoind has participated in this
discussion 7 months ago (along with many of the contributors to this
project). Based in this conversation 7 months ago, it's my understanding
that all parties are aware of the options and tradeoffs to be had.

-- Laolu


On Tue, Feb 5, 2019 at 12:10 PM Tamas Blummer <tamas.blummer@gmail.com>
wrote:

> Hi Laolu,
>
> The only advantage I see in the current design choice is filter size, but
> even that is less
> impressive in recent history and going forward, as address re-use is much
> less frequent nowadays
> than it was Bitcoin=E2=80=99s early days.
>
> I calculated total filter sizes since block 500,000:
>
> input script + output script (current BIP): 1.09 GB
> spent outpoint + output script: 1.26 GB
>
> Both filters are equally useful for a wallet to discover relevant
> transactions, but the current design
> choice seriously limits, practically disables a light client, to prove
> that the filter is correct.
>
> Clear advantages of moving to spent outpoint + output script filter:
>
> 1. Filter correctness can be proven by downloading the block in question
> only.
> 2. Calculation of the filter on server side does not need UTXO.
> 3. Spent outpoints in the filter enable light clients to do further
> probabilistic checks and even more if committed.
>
> The current design choice offers lower security than now attainable. This
> certainly improves with
> a commitment, but that is not even on the roadmap yet, or is it?
>
> Should a filter be committed that contains spent outpoints, then such
> filter would be even more useful:
> A client could decide on availability of spent coins of a transaction
> without maintaining the UTXO set, by
> checking the filters if the coin was spent after its origin proven in an
> SPV manner, evtl. eliminating false positives
> with a block download. This would be slower than having UTXO but require
> only immutable store, no unwinds and
> only download of a few blocks.
>
> Since Bitcoin Core is not yet serving any filters, I do not think this
> discussion is too late.
>
> Tamas Blummer
>
>
> > On Feb 5, 2019, at 02:42, Olaoluwa Osuntokun <laolu32@gmail.com> wrote:
> >
> > Hi Tamas,
> >
> > This is how the filter worked before the switch over to optimize for a
> > filter containing the minimal items needed for a regular wallet to
> function.
> > When this was proposed, I had already implemented the entire proposal
> from
> > wallet to full-node. At that point, we all more or less decided that th=
e
> > space savings (along with intra-block compression) were worthwhile, we
> > weren't cutting off any anticipated application level use cases (at tha=
t
> > point we had already comprehensively integrated both filters into lnd),
> and
> > that once committed the security loss would disappear.
> >
> > I think it's too late into the current deployment of the BIPs to change
> > things around yet again. Instead, the BIP already has measures in place
> for
> > adding _new_ filter types in the future. This along with a few other
> filter
> > types may be worthwhile additions as new filter types.
> >
> > -- Laolu
> >
> > On Mon, Feb 4, 2019 at 12:59 PM Tamas Blummer <tamas.blummer@gmail.com>
> wrote:
> > I participated in that discussion in 2018, but have not had the insight
> gathered by now though writing both client and server implementation of
> BIP157/158
> >
> > Pieter Wuille considered the design choice I am now suggesting here as
> alternative (a) in:
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016064.=
html
> > In his evaluation he recognized that a filter having spent output and
> output scripts would allow decision on filter correctness by knowing the
> block only.
> > He did not evaluate the usefulness in the context of checkpoints, which
> I think are an important shortcut here.
> >
> > Yes, a filter that is collecting input and output scripts is shorter if
> script re-use is frequent, but I showed back in 2018 in the same thread
> that this saving is not that significant in recent history as address reu=
se
> is no longer that frequent.
> >
> > A filter on spent outpoint is just as useful for wallets as is one on
> spent script, since they naturally scan the blockchain forward and thereb=
y
> learn about their coins by the output script before they need to check
> spends of those outpoints.
> >
> > It seems to me that implementing an interrogation by evtl. downloading
> blocks at checkpoints is much simpler than following multiple possible
> filter paths.
> >
> > A spent outpoint filter allows us to decide on coin availability based
> on immutable store, without updated and eventually rolled back UTXO store=
.
> The availability could be decided by following the filter path to current
> tip to genesis and
> > check is the outpoint was spent earlier. False positives can be sorted
> out with a block download. Murmel implements this if running in server
> mode, where blocks are already there.
> >
> > Therefore I ask for a BIP change based on better insight gained through
> implementation.
> >
> > Tamas Blummer
> >
> >> On Feb 4, 2019, at 21:18, Jim Posen <jim.posen@gmail.com> wrote:
> >>
> >> Please see the thread "BIP 158 Flexibility and Filter Size" from 2018
> regarding the decision to remove outpoints from the filter [1].
> >>
> >> Thanks for bringing this up though, because more discussion is needed
> on the client protocol given that clients cannot reliably determine the
> integrity of a block filter in a bandwidth-efficient manner (due to the
> inclusion of input scripts).
> >>
> >> I see three possibilities:
> >> 1) Introduce a new P2P message to retrieve all prev-outputs for a give=
n
> block (essentially the undo data in Core), and verify the scripts against
> the block by executing them. While this permits some forms of input scrip=
t
> malleability (and thus cannot discriminate between all valid and invalid
> filters), it restricts what an attacker can do. This was proposed by Laol=
u
> AFAIK, and I believe this is how btcd is proceeding.
> >> 2) Clients track multiple possible filter header chains and essentiall=
y
> consider the union of their matches. So if any filter received for a
> particular block header matches, the client downloads the block. The clie=
nt
> can ban a peer if they 1) ever return a filter omitting some data that is
> observed in the downloaded block, 2) repeatedly serve filters that trigge=
r
> false positive block downloads where such a number of false positives is
> statistically unlikely, or 3) repeatedly serves filters that are
> significantly larger than the expected size (essentially padding the actu=
al
> filters with garbage to waste bandwidth). I have not done the analysis ye=
t,
> but we should be able to come up with some fairly simple banning heuristi=
cs
> using Chernoff bounds. The main downside is that the client logic to trac=
k
> multiple possible filter chains and filters per block is more complex and
> bandwidth increases if connected to a malicious server. I first heard abo=
ut
> this idea from David Harding.
> >> 3) Rush straight to committing the filters into the chain (via witness
> reserved value or coinbase OP_RETURN) and give up on the pre-softfork BIP
> 157 P2P mode.
> >>
> >> I'm in favor of option #2 despite the downsides since it requires the
> smallest number of changes and is supported by the BIP 157 P2P protocol a=
s
> currently written. (Though the recommended client protocol in the BIP nee=
ds
> to be updated to account for this). Another benefit of it is that it
> removes some synchronicity assumptions where a peer with the correct
> filters keeps timing out and is assumed to be dishonest, while the
> dishonest peer is assumed to be OK because it is responsive.
> >>
> >> If anyone has other ideas, I'd love to hear them.
> >>
> >> -jimpo
> >>
> >> [1]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016057.=
html
> >>
> >>
> >>
> >> On Mon, Feb 4, 2019 at 10:53 AM Tamas Blummer via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> >> TLDR: a change to BIP158 would allow decision on which filter chain is
> correct at lower bandwith use
> >>
> >> Assume there is a BIP157 client that learned a filter header chain
> earlier and is now offered an alternate reality by a newly connected BIP1=
57
> server.
> >>
> >> The client notices the alternate reality by routinely asking for filte=
r
> chain checkpoints after connecting to a new BIP157 server. A divergence a=
t
> a checkpoint means that the server disagrees the client's history at or
> before the first diverging checkpoint. The client would then request the
> filter headers between the last matching and first divergent checkpoint,
> and quickly figure which block=E2=80=99s filter is the first that does no=
t match
> previous assumption, and request that filter from the server.
> >>
> >> The client downloads the corresponding block, checks that its header
> fits the PoW secured best header chain, re-calculates merkle root of its
> transaction list to know that it is complete and queries the filter to se=
e
> if every output script of every transaction is contained in there, if not
> the server is lying, the case is closed, the server disconnected.
> >>
> >> Having all output scripts in the filter does not however guarantee tha=
t
> the filter is correct since it might omit input scripts. Inputs scripts a=
re
> not part of the downloaded block, but are in some blocks before that.
> Checking those are out of reach for lightweight client with tools given b=
y
> the current BIP.
> >>
> >> A remedy here would be an other filter chain on created and spent
> outpoints as is implemented currently by Murmel. The outpoint filter chai=
n
> must offer a match for every spent output of the block with the divergent
> filter, otherwise the interrogated server is lying since a PoW secured
> block can not spend coins out of nowhere. Doing this check would already
> force the client to download the outpoint filter history up-to the point =
of
> divergence. Then the client would have to download and PoW check every
> block that shows a match in outpoints until it figures that one of the
> spent outputs has a script that was not in the server=E2=80=99s filter, i=
n which
> case the server is lying. If everything checks out then the previous
> assumption on filter history was incorrect and should be replaced by the
> history offered by the interrogated server.
> >>
> >> As you see the interrogation works with this added filter but is highl=
y
> ineffective. A really light client should not be forced to download lots =
of
> blocks just to uncover a lying filter server. This would actually be an
> easy DoS on light BIP157 clients.
> >>
> >> A better solution is a change to BIP158 such that the only filter
> contains created scripts and spent outpoints. It appears to me that this
> would serve well both wallets and interrogation of filter servers well:
> >>
> >> Wallets would recognize payments to their addresses by the filter as
> output scripts are included, spends from the wallet would be recognized a=
s
> a wallet already knows outpoints of its previously received coins, so it
> can query the filters for them.
> >>
> >> Interrogation of a filter server also simplifies, since the filter of
> the block can be checked entirely against the contents of the same block.
> The decision on filter correctness does not require more bandwith then
> download of a block at the mismatching checkpoint. The client could only =
be
> forced at max. to download 1/1000 th of the blockchain in addition to the
> filter header history.
> >>
> >> Therefore I suggest to change BIP158 to have a base filter, defined as=
:
> >>
> >> A basic filter MUST contain exactly the following items for each
> transaction in a block:
> >>         =E2=80=A2 Spent outpoints
> >>         =E2=80=A2 The scriptPubKey of each output, aside from all OP_R=
ETURN
> output scripts.
> >>
> >> Tamas Blummer
> >> _______________________________________________
> >> bitcoin-dev mailing list
> >> bitcoin-dev@lists.linuxfoundation.org
> >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
>
>

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

<div dir=3D"ltr"><div>Hi Tamas,=C2=A0</div><div><br></div><div>&gt; The onl=
y advantage I see in the current design choice is filter size, but</div><di=
v>&gt; even that is less impressive in recent history and going forward, as=
 address</div><div>&gt; re-use is much less frequent nowadays than it was B=
itcoin=E2=80=99s early days.</div><div><br></div><div>Gains aren&#39;t only=
 had with address re-use, it&#39;s also the case that if an</div><div>input=
 is spent in the same block as it was created, then only a single items</di=
v><div>is inserted into the filter. Filters spanning across several blocks =
would</div><div>also see savings due to the usage of input scripts.</div><d=
iv><br></div><div>Another advantage of using input scripts is that it allow=
s rescans where all</div><div>keys are known ahead of time to proceed in pa=
rallel, which can serve to</div><div>greatly speed up rescans in bitcoind. =
Additionally, it allows light clients</div><div>to participate in protocols=
 like atomic swaps using the input scripts as</div><div>triggers for state =
transitions. If outpoints were used, then the party that</div><div>initiate=
d the swap would need to send the cooperating party all possible</div><div>=
txid&#39;s that may be generated due to fee bumps (RBF or sighash single</d=
iv><div>tricks). Using the script, the light client simply waits for it to =
be</div><div>revealed in a block (P2WSH) and then it can carry on the proto=
col.</div><div><br></div><div>&gt; Clear advantages of moving to spent outp=
oint + output script filter:</div><div><br></div><div>&gt; 1. Filter correc=
tness can be proven by downloading the block in question only.</div><div><b=
r></div><div>Yep, as is they can verify half the filter. With auxiliary dat=
a, they can</div><div>verify the entire thing. Once committed, they don&#39=
;t need to verify at all.</div><div>We&#39;re repeating a discussion that p=
layed out 7 months ago with no new</div><div>information or context.</div><=
div><br></div><div>&gt; 2. Calculation of the filter on server side does no=
t need UTXO.</div><div><br></div><div>This is incorrect. Filter calculation=
 can use the spentness journal (or undo</div><div>blocks) that many full no=
de implementations utilize.</div><div><br></div><div>&gt; This certainly im=
proves with a commitment, but that is not even on the</div><div>&gt; roadma=
p yet, or is it?</div><div><br></div><div>I don&#39;t really know of any so=
rt of roadmaps in Bitcoin development. However,</div><div>I think there&#39=
;s relatively strong support to adding a commitment, once the</div><div>cur=
rent protocol gets more usage in the wild, which it already is today on</di=
v><div>mainnet.</div><div><br></div><div>&gt; Should a filter be committed =
that contains spent outpoints, then such</div><div>&gt; filter would be eve=
n more useful</div><div><br></div><div>Indeed, this can be added as a new f=
ilter type, optionally adding created</div><div>outpoints as you referenced=
 in your prior email.</div><div><br></div><div>&gt; Since Bitcoin Core is n=
ot yet serving any filters, I do not think this</div><div>&gt; discussion i=
s too late.</div><div><br></div><div>See my reply to Matt on the current st=
ate of deployment. It&#39;s also the case</div><div>that bitcoind isn&#39;t=
 the only full node implementation used in the wild.</div><div>Further chan=
ges would also serve to delay inclusion into bitcoind. The</div><div>indivi=
duals proposing these PRs to bitcoind has participated in this</div><div>di=
scussion 7 months ago (along with many of the contributors to this</div><di=
v>project). Based in this conversation 7 months ago, it&#39;s my understand=
ing</div><div>that all parties are aware of the options and tradeoffs to be=
 had.</div><div><br></div><div>-- Laolu</div><div><br></div><br><div class=
=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Tue, Feb 5, 2019 =
at 12:10 PM Tamas Blummer &lt;<a href=3D"mailto:tamas.blummer@gmail.com">ta=
mas.blummer@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_qu=
ote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex=
">Hi Laolu,<br>
<br>
The only advantage I see in the current design choice is filter size, but e=
ven that is less<br>
impressive in recent history and going forward, as address re-use is much l=
ess frequent nowadays<br>
than it was Bitcoin=E2=80=99s early days.<br>
<br>
I calculated total filter sizes since block 500,000:<br>
<br>
input script + output script (current BIP): 1.09 GB <br>
spent outpoint + output script: 1.26 GB<br>
<br>
Both filters are equally useful for a wallet to discover relevant transacti=
ons, but the current design<br>
choice seriously limits, practically disables a light client, to prove that=
 the filter is correct. <br>
<br>
Clear advantages of moving to spent outpoint + output script filter:<br>
<br>
1. Filter correctness can be proven by downloading the block in question on=
ly.<br>
2. Calculation of the filter on server side does not need UTXO.<br>
3. Spent outpoints in the filter enable light clients to do further probabi=
listic checks and even more if committed.<br>
<br>
The current design choice offers lower security than now attainable. This c=
ertainly improves with <br>
a commitment, but that is not even on the roadmap yet, or is it?<br>
<br>
Should a filter be committed that contains spent outpoints, then such filte=
r would be even more useful:<br>
A client could decide on availability of spent coins of a transaction witho=
ut maintaining the UTXO set, by <br>
checking the filters if the coin was spent after its origin proven in an SP=
V manner, evtl. eliminating false positives <br>
with a block download. This would be slower than having UTXO but require on=
ly immutable store, no unwinds and <br>
only download of a few blocks.<br>
<br>
Since Bitcoin Core is not yet serving any filters, I do not think this disc=
ussion is too late.<br>
<br>
Tamas Blummer<br>
<br>
<br>
&gt; On Feb 5, 2019, at 02:42, Olaoluwa Osuntokun &lt;<a href=3D"mailto:lao=
lu32@gmail.com" target=3D"_blank">laolu32@gmail.com</a>&gt; wrote:<br>
&gt; <br>
&gt; Hi Tamas, <br>
&gt; <br>
&gt; This is how the filter worked before the switch over to optimize for a=
<br>
&gt; filter containing the minimal items needed for a regular wallet to fun=
ction.<br>
&gt; When this was proposed, I had already implemented the entire proposal =
from<br>
&gt; wallet to full-node. At that point, we all more or less decided that t=
he<br>
&gt; space savings (along with intra-block compression) were worthwhile, we=
<br>
&gt; weren&#39;t cutting off any anticipated application level use cases (a=
t that<br>
&gt; point we had already comprehensively integrated both filters into lnd)=
, and<br>
&gt; that once committed the security loss would disappear.<br>
&gt; <br>
&gt; I think it&#39;s too late into the current deployment of the BIPs to c=
hange<br>
&gt; things around yet again. Instead, the BIP already has measures in plac=
e for<br>
&gt; adding _new_ filter types in the future. This along with a few other f=
ilter<br>
&gt; types may be worthwhile additions as new filter types.<br>
&gt; <br>
&gt; -- Laolu<br>
&gt; <br>
&gt; On Mon, Feb 4, 2019 at 12:59 PM Tamas Blummer &lt;<a href=3D"mailto:ta=
mas.blummer@gmail.com" target=3D"_blank">tamas.blummer@gmail.com</a>&gt; wr=
ote:<br>
&gt; I participated in that discussion in 2018, but have not had the insigh=
t gathered by now though writing both client and server implementation of B=
IP157/158<br>
&gt; <br>
&gt; Pieter Wuille considered the design choice I am now suggesting here as=
 alternative (a) in: <a href=3D"https://lists.linuxfoundation.org/pipermail=
/bitcoin-dev/2018-June/016064.html" rel=3D"noreferrer" target=3D"_blank">ht=
tps://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016064.html=
</a><br>
&gt; In his evaluation he recognized that a filter having spent output and =
output scripts would allow decision on filter correctness by knowing the bl=
ock only.<br>
&gt; He did not evaluate the usefulness in the context of checkpoints, whic=
h I think are an important shortcut here.<br>
&gt; <br>
&gt; Yes, a filter that is collecting input and output scripts is shorter i=
f script re-use is frequent, but I showed back in 2018 in the same thread t=
hat this saving is not that significant in recent history as address reuse =
is no longer that frequent.<br>
&gt; <br>
&gt; A filter on spent outpoint is just as useful for wallets as is one on =
spent script, since they naturally scan the blockchain forward and thereby =
learn about their coins by the output script before they need to check spen=
ds of those outpoints.<br>
&gt; <br>
&gt; It seems to me that implementing an interrogation by evtl. downloading=
 blocks at checkpoints is much simpler than following multiple possible fil=
ter paths.<br>
&gt; <br>
&gt; A spent outpoint filter allows us to decide on coin availability based=
 on immutable store, without updated and eventually rolled back UTXO store.=
 The availability could be decided by following the filter path to current =
tip to genesis and<br>
&gt; check is the outpoint was spent earlier. False positives can be sorted=
 out with a block download. Murmel implements this if running in server mod=
e, where blocks are already there.<br>
&gt; <br>
&gt; Therefore I ask for a BIP change based on better insight gained throug=
h implementation.<br>
&gt; <br>
&gt; Tamas Blummer<br>
&gt; <br>
&gt;&gt; On Feb 4, 2019, at 21:18, Jim Posen &lt;<a href=3D"mailto:jim.pose=
n@gmail.com" target=3D"_blank">jim.posen@gmail.com</a>&gt; wrote:<br>
&gt;&gt; <br>
&gt;&gt; Please see the thread &quot;BIP 158 Flexibility and Filter Size&qu=
ot; from 2018 regarding the decision to remove outpoints from the filter [1=
].<br>
&gt;&gt; <br>
&gt;&gt; Thanks for bringing this up though, because more discussion is nee=
ded on the client protocol given that clients cannot reliably determine the=
 integrity of a block filter in a bandwidth-efficient manner (due to the in=
clusion of input scripts).<br>
&gt;&gt; <br>
&gt;&gt; I see three possibilities:<br>
&gt;&gt; 1) Introduce a new P2P message to retrieve all prev-outputs for a =
given block (essentially the undo data in Core), and verify the scripts aga=
inst the block by executing them. While this permits some forms of input sc=
ript malleability (and thus cannot discriminate between all valid and inval=
id filters), it restricts what an attacker can do. This was proposed by Lao=
lu AFAIK, and I believe this is how btcd is proceeding.<br>
&gt;&gt; 2) Clients track multiple possible filter header chains and essent=
ially consider the union of their matches. So if any filter received for a =
particular block header matches, the client downloads the block. The client=
 can ban a peer if they 1) ever return a filter omitting some data that is =
observed in the downloaded block, 2) repeatedly serve filters that trigger =
false positive block downloads where such a number of false positives is st=
atistically unlikely, or 3) repeatedly serves filters that are significantl=
y larger than the expected size (essentially padding the actual filters wit=
h garbage to waste bandwidth). I have not done the analysis yet, but we sho=
uld be able to come up with some fairly simple banning heuristics using Che=
rnoff bounds. The main downside is that the client logic to track multiple =
possible filter chains and filters per block is more complex and bandwidth =
increases if connected to a malicious server. I first heard about this idea=
 from David Harding.<br>
&gt;&gt; 3) Rush straight to committing the filters into the chain (via wit=
ness reserved value or coinbase OP_RETURN) and give up on the pre-softfork =
BIP 157 P2P mode.<br>
&gt;&gt; <br>
&gt;&gt; I&#39;m in favor of option #2 despite the downsides since it requi=
res the smallest number of changes and is supported by the BIP 157 P2P prot=
ocol as currently written. (Though the recommended client protocol in the B=
IP needs to be updated to account for this). Another benefit of it is that =
it removes some synchronicity assumptions where a peer with the correct fil=
ters keeps timing out and is assumed to be dishonest, while the dishonest p=
eer is assumed to be OK because it is responsive.<br>
&gt;&gt; <br>
&gt;&gt; If anyone has other ideas, I&#39;d love to hear them.<br>
&gt;&gt; <br>
&gt;&gt; -jimpo<br>
&gt;&gt; <br>
&gt;&gt; [1] <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin=
-dev/2018-June/016057.html" rel=3D"noreferrer" target=3D"_blank">https://li=
sts.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016057.html</a><br>
&gt;&gt; <br>
&gt;&gt; <br>
&gt;&gt; <br>
&gt;&gt; On Mon, Feb 4, 2019 at 10:53 AM Tamas Blummer via bitcoin-dev &lt;=
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br>
&gt;&gt; TLDR: a change to BIP158 would allow decision on which filter chai=
n is correct at lower bandwith use<br>
&gt;&gt; <br>
&gt;&gt; Assume there is a BIP157 client that learned a filter header chain=
 earlier and is now offered an alternate reality by a newly connected BIP15=
7 server.<br>
&gt;&gt; <br>
&gt;&gt; The client notices the alternate reality by routinely asking for f=
ilter chain checkpoints after connecting to a new BIP157 server. A divergen=
ce at a checkpoint means that the server disagrees the client&#39;s history=
 at or before the first diverging checkpoint. The client would then request=
 the filter headers between the last matching and first divergent checkpoin=
t, and quickly figure which block=E2=80=99s filter is the first that does n=
ot match previous assumption, and request that filter from the server.<br>
&gt;&gt; <br>
&gt;&gt; The client downloads the corresponding block, checks that its head=
er fits the PoW secured best header chain, re-calculates merkle root of its=
 transaction list to know that it is complete and queries the filter to see=
 if every output script of every transaction is contained in there, if not =
the server is lying, the case is closed, the server disconnected.<br>
&gt;&gt; <br>
&gt;&gt; Having all output scripts in the filter does not however guarantee=
 that the filter is correct since it might omit input scripts. Inputs scrip=
ts are not part of the downloaded block, but are in some blocks before that=
. Checking those are out of reach for lightweight client with tools given b=
y the current BIP.<br>
&gt;&gt; <br>
&gt;&gt; A remedy here would be an other filter chain on created and spent =
outpoints as is implemented currently by Murmel. The outpoint filter chain =
must offer a match for every spent output of the block with the divergent f=
ilter, otherwise the interrogated server is lying since a PoW secured block=
 can not spend coins out of nowhere. Doing this check would already force t=
he client to download the outpoint filter history up-to the point of diverg=
ence. Then the client would have to download and PoW check every block that=
 shows a match in outpoints until it figures that one of the spent outputs =
has a script that was not in the server=E2=80=99s filter, in which case the=
 server is lying. If everything checks out then the previous assumption on =
filter history was incorrect and should be replaced by the history offered =
by the interrogated server. <br>
&gt;&gt; <br>
&gt;&gt; As you see the interrogation works with this added filter but is h=
ighly ineffective. A really light client should not be forced to download l=
ots of blocks just to uncover a lying filter server. This would actually be=
 an easy DoS on light BIP157 clients.<br>
&gt;&gt; <br>
&gt;&gt; A better solution is a change to BIP158 such that the only filter =
contains created scripts and spent outpoints. It appears to me that this wo=
uld serve well both wallets and interrogation of filter servers well:<br>
&gt;&gt; <br>
&gt;&gt; Wallets would recognize payments to their addresses by the filter =
as output scripts are included, spends from the wallet would be recognized =
as a wallet already knows outpoints of its previously received coins, so it=
 can query the filters for them.<br>
&gt;&gt; <br>
&gt;&gt; Interrogation of a filter server also simplifies, since the filter=
 of the block can be checked entirely against the contents of the same bloc=
k. The decision on filter correctness does not require more bandwith then d=
ownload of a block at the mismatching checkpoint. The client could only be =
forced at max. to download 1/1000 th of the blockchain in addition to the f=
ilter header history.<br>
&gt;&gt; <br>
&gt;&gt; Therefore I suggest to change BIP158 to have a base filter, define=
d as:<br>
&gt;&gt; <br>
&gt;&gt; A basic filter MUST contain exactly the following items for each t=
ransaction in a block:<br>
&gt;&gt;=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=E2=80=A2 Spent outpoints<br>
&gt;&gt;=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=E2=80=A2 The scriptPubKey of eac=
h output, aside from all OP_RETURN output scripts.<br>
&gt;&gt; <br>
&gt;&gt; Tamas Blummer<br>
&gt;&gt; _______________________________________________<br>
&gt;&gt; bitcoin-dev mailing list<br>
&gt;&gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D=
"_blank">bitcoin-dev@lists.linuxfoundation.org</a><br>
&gt;&gt; <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitc=
oin-dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation=
.org/mailman/listinfo/bitcoin-dev</a><br>
&gt; <br>
<br>
</blockquote></div></div>

--00000000000027dc5d05812ea652--