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
|
Return-Path: <tamas.blummer@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 0CFAD8755
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 4 Feb 2019 11:41:25 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f53.google.com (mail-wr1-f53.google.com
[209.85.221.53])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5EA00A8
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 4 Feb 2019 11:41:24 +0000 (UTC)
Received: by mail-wr1-f53.google.com with SMTP id v13so13996503wrw.5
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 04 Feb 2019 03:41:24 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=from:content-transfer-encoding:mime-version:subject:message-id:date
:to; bh=XtWGKeEoSM1sIzmqsERo/ODQ+obuI1NsIMMuDvTDgnU=;
b=hl/nmRGZA5TGQ2AOKPZA/yYmGufdkAzxObEP6Cs6E89ThVzvtofxtJ8su6uorrJSvj
SjTuPFblZCYwU2j3q+GlQ1bjkP2IioiPYRLL1d1qwMIKw9Uhcs90FwCd1rkT8Aetl4fz
OsntMQ0VzFTNZOfv1n1qcCfsCMuLgv4QQEtO0dZuLyfisQogjxcsh/gY9FJgmNgYPpWh
1NlKexLSNQs993MtXzTlq/bEbVKEh8oeW5fiQtSyGpEscfS3J0aOKT1JKWlCAHzAbyFT
00KgG2NikuaV9jRSw4OQ5CdPpPKxkZxNDj7Pir8Q6yXu5kYNivk/c6PXy3K/1kI0OMIe
iwEg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:from:content-transfer-encoding:mime-version
:subject:message-id:date:to;
bh=XtWGKeEoSM1sIzmqsERo/ODQ+obuI1NsIMMuDvTDgnU=;
b=j6RVAj7EXM3zbF72arPH2G+72jwWqbMZ/4x8U3KZ0u6rKbGZ4mzVsQXyCvLOJfSGxp
o8eFBBXzolPbwvby38cEgzknzDgM/SrWlFb/nA8dbqnQpG14NY9ifdSHuCoIngw0EGBD
eIREaea7T5zfeQPujQYS+5Bwo0ARbrTWkIgweABE2SnsxEoutqmJLgKm1Qqkh3ZIlQN/
E1LtUz41xDhuJkmQUpm4sgnjGSEOF7bCsPzF/ux0Axnh+1kebuj4z3PvyacDxBVo3Sbh
PZmDr0Qyj5q4zR4cZPn1xtdNEqJaojjHRXCLzTvoNbxy+bCQ0GEiQKW7rSi0BN4UZNyT
AC0g==
X-Gm-Message-State: AHQUAuZFjtUFEzZhWLxvoIJyYALbUz4GiTzs6OwzqoAbEloIczZi+4/c
Yq3Teo8+K8sS0px2eDGrDN5BLo9A
X-Google-Smtp-Source: AHgI3IZwybTWr1ZssLoqI3bTayNwtqKOzgFot6qDa9PL3lcJJgqLRgxQiDooboaFDT/d+34C/DznNg==
X-Received: by 2002:a5d:4486:: with SMTP id j6mr4333720wrq.41.1549280482679;
Mon, 04 Feb 2019 03:41:22 -0800 (PST)
Received: from p200300dd672d1a81ec526fc0218d83dc.dip0.t-ipconnect.de
(p200300DD672D1A81EC526FC0218D83DC.dip0.t-ipconnect.de.
[2003:dd:672d:1a81:ec52:6fc0:218d:83dc])
by smtp.gmail.com with ESMTPSA id
d16sm4728051wrx.11.2019.02.04.03.41.21
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Mon, 04 Feb 2019 03:41:21 -0800 (PST)
From: Tamas Blummer <tamas.blummer@gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Message-Id: <6D57649F-0236-4FBA-8376-4815F5F39E8A@gmail.com>
Date: Mon, 4 Feb 2019 12:41:20 +0100
To: bitcoin-dev@lists.linuxfoundation.org,
Olaoluwa Osuntokun <laolu32@gmail.com>, jimpo@coinbase.com,
alex@akselrod.org
X-Mailer: Apple Mail (2.3273)
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, 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
X-Mailman-Approved-At: Mon, 04 Feb 2019 18:49:05 +0000
Subject: [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: Mon, 04 Feb 2019 11:41:25 -0000
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 =
BIP157 server.
The client notices the alternate reality by routinely asking for filter =
chain checkpoints after connecting to a new BIP157 server. A divergence =
at 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 not 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 =
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.
Having all output scripts in the filter does not however guarantee that =
the filter is correct since it might omit input scripts. Inputs scripts =
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 by 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 =
chain 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, 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.=20
As you see the interrogation works with this added filter but is highly =
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 =
as 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_RETURN output scripts.
Tamas Blummer=
|
