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 0CFAD8755 for ; 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 ; Mon, 4 Feb 2019 11:41:24 +0000 (UTC) Received: by mail-wr1-f53.google.com with SMTP id v13so13996503wrw.5 for ; 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 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 , 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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=