public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed

* [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
@ 2019-02-04 11:41 Tamas Blummer
  2019-02-04 20:18 ` Jim Posen
  0 siblings, 1 reply; 14+ messages in thread
From: Tamas Blummer @ 2019-02-04 11:41 UTC (permalink / raw)
  To: bitcoin-dev, Olaoluwa Osuntokun, jimpo, alex

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’s 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’s 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. 

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:
	• Spent outpoints
	• The scriptPubKey of each output, aside from all OP_RETURN output scripts.

Tamas Blummer

^ permalink raw reply	[flat|nested] 14+ messages in thread

• * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
    2019-02-04 11:41 [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal Tamas Blummer
  @ 2019-02-04 20:18 ` Jim Posen
    2019-02-04 20:59   ` Tamas Blummer
    2021-10-03  9:53   ` Dustin Dettmer
    0 siblings, 2 replies; 14+ messages in thread
  From: Jim Posen @ 2019-02-04 20:18 UTC (permalink / raw)
    To: Tamas Blummer, Bitcoin Protocol Discussion; +Cc: Jim Posen
  
  [-- Attachment #1: Type: text/plain, Size: 6817 bytes --]
  
  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 given
  block (essentially the undo data in Core), and verify the scripts against
  the block by executing them. While this permits some forms of input script
  malleability (and thus cannot discriminate between all valid and invalid
  filters), it restricts what an attacker can do. This was proposed by Laolu
  AFAIK, and I believe this is how btcd is proceeding.
  2) Clients track multiple possible filter header chains and essentially
  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
  statistically unlikely, or 3) repeatedly serves filters that are
  significantly larger than the expected size (essentially padding the actual
  filters with garbage to waste bandwidth). I have not done the analysis yet,
  but we should be able to come up with some fairly simple banning heuristics
  using Chernoff 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.
  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 as
  currently written. (Though the recommended client protocol in the BIP 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
  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 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’s 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’s 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.
  >
  > 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:
  >         • Spent outpoints
  >         • The scriptPubKey of each output, aside from all OP_RETURN output
  > scripts.
  >
  > Tamas Blummer
  > _______________________________________________
  > bitcoin-dev mailing list
  > bitcoin-dev@lists•linuxfoundation.org
  > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
  >
  
  [-- Attachment #2: Type: text/html, Size: 7576 bytes --]
  
  ^ permalink raw reply	[flat|nested] 14+ messages in thread

• • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
      2019-02-04 20:18 ` Jim Posen
    @ 2019-02-04 20:59   ` Tamas Blummer
      2019-02-05  1:42     ` Olaoluwa Osuntokun
      2021-10-03  9:53   ` Dustin Dettmer
      1 sibling, 1 reply; 14+ messages in thread
    From: Tamas Blummer @ 2019-02-04 20:59 UTC (permalink / raw)
      To: Jim Posen; +Cc: Bitcoin Protocol Discussion, Jim Posen
    
    
    [-- Attachment #1.1: Type: text/plain, Size: 8884 bytes --]
    
    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 <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 reuse 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 thereby 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 given block (essentially the undo data in Core), and verify the scripts against the block by executing them. While this permits some forms of input script malleability (and thus cannot discriminate between all valid and invalid filters), it restricts what an attacker can do. This was proposed by Laolu AFAIK, and I believe this is how btcd is proceeding.
    > 2) Clients track multiple possible filter header chains and essentially 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 statistically unlikely, or 3) repeatedly serves filters that are significantly larger than the expected size (essentially padding the actual filters with garbage to waste bandwidth). I have not done the analysis yet, but we should be able to come up with some fairly simple banning heuristics using Chernoff 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.
    > 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 as currently written. (Though the recommended client protocol in the BIP 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 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 <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 <mailto: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 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’s 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’s 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.
    > 
    > 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:
    >         • Spent outpoints
    >         • The scriptPubKey of each output, aside from all OP_RETURN output scripts.
    > 
    > Tamas Blummer
    > _______________________________________________
    > bitcoin-dev mailing list
    > bitcoin-dev@lists•linuxfoundation.org <mailto:bitcoin-dev@lists•linuxfoundation.org>
    > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
    
    
    [-- Attachment #1.2: Type: text/html, Size: 10958 bytes --]
    
    [-- Attachment #2: Message signed with OpenPGP --]
    [-- Type: application/pgp-signature, Size: 488 bytes --]
    
    ^ permalink raw reply	[flat|nested] 14+ messages in thread

  • • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
        2019-02-04 20:59   ` Tamas Blummer
      @ 2019-02-05  1:42     ` Olaoluwa Osuntokun
        2019-02-05 12:21       ` Matt Corallo
        2019-02-05 20:10       ` Tamas Blummer
        0 siblings, 2 replies; 14+ messages in thread
      From: Olaoluwa Osuntokun @ 2019-02-05  1:42 UTC (permalink / raw)
        To: Tamas Blummer; +Cc: Jim Posen, Bitcoin Protocol Discussion
      
      [-- Attachment #1: Type: text/plain, Size: 9921 bytes --]
      
      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 the
      space savings (along with intra-block compression) were worthwhile, we
      weren't cutting off any anticipated application level use cases (at that
      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 reuse
      > 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 thereby
      > 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 given
      > block (essentially the undo data in Core), and verify the scripts against
      > the block by executing them. While this permits some forms of input script
      > malleability (and thus cannot discriminate between all valid and invalid
      > filters), it restricts what an attacker can do. This was proposed by Laolu
      > AFAIK, and I believe this is how btcd is proceeding.
      > 2) Clients track multiple possible filter header chains and essentially
      > 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
      > statistically unlikely, or 3) repeatedly serves filters that are
      > significantly larger than the expected size (essentially padding the actual
      > filters with garbage to waste bandwidth). I have not done the analysis yet,
      > but we should be able to come up with some fairly simple banning heuristics
      > using Chernoff 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.
      > 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 as
      > currently written. (Though the recommended client protocol in the BIP 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
      > 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 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’s 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’s 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.
      >>
      >> 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:
      >>         • Spent outpoints
      >>         • The scriptPubKey of each output, aside from all OP_RETURN
      >> output scripts.
      >>
      >> Tamas Blummer
      >> _______________________________________________
      >> bitcoin-dev mailing list
      >> bitcoin-dev@lists•linuxfoundation.org
      >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
      >>
      >
      >
      
      [-- Attachment #2: Type: text/html, Size: 11497 bytes --]
      
      ^ permalink raw reply	[flat|nested] 14+ messages in thread

    • • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
          2019-02-05  1:42     ` Olaoluwa Osuntokun
        @ 2019-02-05 12:21       ` Matt Corallo
          2019-02-06  0:05         ` Olaoluwa Osuntokun
          2019-02-05 20:10       ` Tamas Blummer
          1 sibling, 1 reply; 14+ messages in thread
        From: Matt Corallo @ 2019-02-05 12:21 UTC (permalink / raw)
          To: Olaoluwa Osuntokun, Bitcoin Protocol Discussion, Tamas Blummer; +Cc: Jim Posen
        
        
        On 2/4/19 8:18 PM, Jim Posen via bitcoin-dev wrote:
        - snip -
         > 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
         > against the block by executing them. While this permits some forms of
         > input script malleability (and thus cannot discriminate between all
         > valid and invalid filters), it restricts what an attacker can do. This
         > was proposed by Laolu AFAIK, and I believe this is how btcd is 
        proceeding.
        
        I'm somewhat confused by this - how does the undo data help you without 
        seeing the full (mistate compressed) transaction? In (the realistic) 
        thread model where an attacker is trying to blind you from some output, 
        they can simply give you "undo data" where scriptPubKeys are OP_TRUE 
        instead of the real script and you'd be none the wiser.
        
        On 2/5/19 1:42 AM, Olaoluwa Osuntokun via bitcoin-dev wrote:
        - snip -
        > 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.
        - snip -
        
        Huh? I don't think we should seriously consider 
        only-one-codebase-has-deployed-anything-with-very-limited-in-the-wild-use 
        as "too late into the current deployment"?
        
        Matt
        
        
        ^ permalink raw reply	[flat|nested] 14+ messages in thread

      • • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
            2019-02-05 12:21       ` Matt Corallo
          @ 2019-02-06  0:05         ` Olaoluwa Osuntokun
            0 siblings, 0 replies; 14+ messages in thread
          From: Olaoluwa Osuntokun @ 2019-02-06  0:05 UTC (permalink / raw)
            To: Matt Corallo; +Cc: Bitcoin Protocol Discussion, Jim Posen
          
          [-- Attachment #1: Type: text/plain, Size: 3408 bytes --]
          
          Hi Matt,
          
          > In (the realistic) thread model where an attacker is trying to blind you
          > from some output, they can simply give you "undo data" where scriptPubKeys
          > are OP_TRUE instead of the real script and you'd be none the wiser.
          
          It depends on the input. If I'm trying to verify an input that's P2WSH,
          since the witness script is included in the witness (the last element), I
          can easily verify that the pkScript given is the proper witness program.
          
          > Huh? I don't think we should seriously consider
          > only-one-codebase-has-deployed-anything-with-very-limited-in-the-wild-use
          as
          > "too late into the current deployment"?
          
          I'd wager that most developers reading this email right now are familiar
          with neutrino as a project. Many even routinely use "neutrino" to refer to
          BIP 157+158. There are several projects in the wild that have already
          deployed applications built on lnd+neutrino live on mainnet. lnd+neutrino is
          also the only project (as far as I'm aware) that has fully integrated the
          p2p BIP 157+158 into a wallet, and also uses the filters for higher level
          applications.
          
          I'm no stranger to this argument, as I made the exact same one 7 months ago
          when the change was originally discussed. Since then I realized that using
          input scripts can be even _more_ flexible as light clients can use them as
          set up or triggers for multi-party protocols such as atomic swaps. Using
          scripts also allows for faster rescans if one knows all their keys ahead of
          time, as the checks can be parallelized. Additionally, the current filter
          also lends better to an eventual commitment as you literally can't remove
          anything from it, and still have it be useful for the traditional wallet use
          case.
          
          As I mentioned in my last email, this can be added as an additional filter
          type, leaving it up the full node implementations that have deployed the
          base protocol to integrate it or not.
          
          -- Laolu
          
          
          On Tue, Feb 5, 2019 at 4:21 AM Matt Corallo <lf-lists@mattcorallo•com>
          wrote:
          
          >
          > On 2/4/19 8:18 PM, Jim Posen via bitcoin-dev wrote:
          > - snip -
          >  > 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
          >  > against the block by executing them. While this permits some forms of
          >  > input script malleability (and thus cannot discriminate between all
          >  > valid and invalid filters), it restricts what an attacker can do. This
          >  > was proposed by Laolu AFAIK, and I believe this is how btcd is
          > proceeding.
          >
          > I'm somewhat confused by this - how does the undo data help you without
          > seeing the full (mistate compressed) transaction? In (the realistic)
          > thread model where an attacker is trying to blind you from some output,
          > they can simply give you "undo data" where scriptPubKeys are OP_TRUE
          > instead of the real script and you'd be none the wiser.
          >
          > On 2/5/19 1:42 AM, Olaoluwa Osuntokun via bitcoin-dev wrote:
          > - snip -
          > > 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.
          > - snip -
          >
          > Huh? I don't think we should seriously consider
          > only-one-codebase-has-deployed-anything-with-very-limited-in-the-wild-use
          > as "too late into the current deployment"?
          >
          > Matt
          >
          
          [-- Attachment #2: Type: text/html, Size: 4334 bytes --]
          
          ^ permalink raw reply	[flat|nested] 14+ messages in thread

      • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
          2019-02-05  1:42     ` Olaoluwa Osuntokun
          2019-02-05 12:21       ` Matt Corallo
        @ 2019-02-05 20:10       ` Tamas Blummer
          2019-02-06  0:17         ` Olaoluwa Osuntokun
          1 sibling, 1 reply; 14+ messages in thread
        From: Tamas Blummer @ 2019-02-05 20:10 UTC (permalink / raw)
          To: Olaoluwa Osuntokun; +Cc: Jim Posen, Bitcoin Protocol Discussion
        
        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’s 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 the
        > space savings (along with intra-block compression) were worthwhile, we
        > weren't cutting off any anticipated application level use cases (at that
        > 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 reuse 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 thereby 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 given block (essentially the undo data in Core), and verify the scripts against the block by executing them. While this permits some forms of input script malleability (and thus cannot discriminate between all valid and invalid filters), it restricts what an attacker can do. This was proposed by Laolu AFAIK, and I believe this is how btcd is proceeding.
        >> 2) Clients track multiple possible filter header chains and essentially 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 statistically unlikely, or 3) repeatedly serves filters that are significantly larger than the expected size (essentially padding the actual filters with garbage to waste bandwidth). I have not done the analysis yet, but we should be able to come up with some fairly simple banning heuristics using Chernoff 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.
        >> 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 as currently written. (Though the recommended client protocol in the BIP 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 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 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’s 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’s 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. 
        >> 
        >> 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:
        >>         • Spent outpoints
        >>         • The scriptPubKey of each output, aside from all OP_RETURN output scripts.
        >> 
        >> Tamas Blummer
        >> _______________________________________________
        >> bitcoin-dev mailing list
        >> bitcoin-dev@lists•linuxfoundation.org
        >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
        > 
        
        
        
        ^ permalink raw reply	[flat|nested] 14+ messages in thread

      • • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
            2019-02-05 20:10       ` Tamas Blummer
          @ 2019-02-06  0:17         ` Olaoluwa Osuntokun
            2019-02-06  8:09           ` Tamas Blummer
            0 siblings, 1 reply; 14+ messages in thread
          From: Olaoluwa Osuntokun @ 2019-02-06  0:17 UTC (permalink / raw)
            To: Tamas Blummer; +Cc: Jim Posen, Bitcoin Protocol Discussion
          
          [-- Attachment #1: Type: text/plain, Size: 15098 bytes --]
          
          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’s 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 items
          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 all
          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 undo
          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’s 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 the
          > > space savings (along with intra-block compression) were worthwhile, we
          > > weren't cutting off any anticipated application level use cases (at that
          > > 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 reuse
          > 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 thereby
          > 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 given
          > block (essentially the undo data in Core), and verify the scripts against
          > the block by executing them. While this permits some forms of input script
          > malleability (and thus cannot discriminate between all valid and invalid
          > filters), it restricts what an attacker can do. This was proposed by Laolu
          > AFAIK, and I believe this is how btcd is proceeding.
          > >> 2) Clients track multiple possible filter header chains and essentially
          > 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
          > statistically unlikely, or 3) repeatedly serves filters that are
          > significantly larger than the expected size (essentially padding the actual
          > filters with garbage to waste bandwidth). I have not done the analysis yet,
          > but we should be able to come up with some fairly simple banning heuristics
          > using Chernoff 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.
          > >> 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 as
          > currently written. (Though the recommended client protocol in the BIP 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
          > 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 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’s 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’s 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.
          > >>
          > >> 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:
          > >>         • Spent outpoints
          > >>         • The scriptPubKey of each output, aside from all OP_RETURN
          > output scripts.
          > >>
          > >> Tamas Blummer
          > >> _______________________________________________
          > >> bitcoin-dev mailing list
          > >> bitcoin-dev@lists•linuxfoundation.org
          > >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
          > >
          >
          >
          
          [-- Attachment #2: Type: text/html, Size: 17214 bytes --]
          
          ^ permalink raw reply	[flat|nested] 14+ messages in thread

        • • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
              2019-02-06  0:17         ` Olaoluwa Osuntokun
            @ 2019-02-06  8:09           ` Tamas Blummer
              2019-02-06 18:17             ` Gregory Maxwell
              0 siblings, 1 reply; 14+ messages in thread
            From: Tamas Blummer @ 2019-02-06  8:09 UTC (permalink / raw)
              To: Olaoluwa Osuntokun; +Cc: Jim Posen, Bitcoin Protocol Discussion
            
            Hi Laolu,
            
            space savings come with the rather serious current disadvantage, that a light client is not 
            in the position to check the filter. Also the advanced uses you mention are subject to this, for now. 
            Building more on a shaky fundament does not make it look better.
            
            Now that we have seen advantages of both filters, what keeps us from offering both by Core?
            
            Computing the addional spent-outpoint output-script filter is cheaper than the current one as 
            it can be done with the block as only context, it does not need UTXO nor undo blocks no journals or 
            whatever else. I do not see how my statement regarding this was incorrect.
            
            There is a political issue though, why I favor better provable uncommitted filter:
            
            I am skeptical that commitment of any filter will come into Core soon.
            The reason of my skepticism is political, not technical.
            
            A committed filter makes light clients much more reliable and attractive, for some taste too much more.
            
            Clients that follow PoW are not significant on the current network. Core nodes enforce many more rules,
            some as important as miners' reward. A committed filter would strengthen light clients 
            significantly, such that perhabs too many were compelled using them instead of a Core node. 
            Would the remaining Core nodes be sufficient to enforce checks not covered? I see how this is a dilemma.
            
            Is this a dilemma because we think black-white? Light(er) clients might implement checks that are more 
            than blind PoW trust even if less than all Core checks. Has the time come to allow for this?
            
            Tamas Blummer
            
            
            
            
            > On Feb 6, 2019, at 01:17, Olaoluwa Osuntokun <laolu32@gmail•com> wrote:
            > 
            > 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’s 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 items
            > 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 all
            > 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 undo
            > 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’s 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 the
            > > space savings (along with intra-block compression) were worthwhile, we
            > > weren't cutting off any anticipated application level use cases (at that
            > > 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 reuse 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 thereby 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 given block (essentially the undo data in Core), and verify the scripts against the block by executing them. While this permits some forms of input script malleability (and thus cannot discriminate between all valid and invalid filters), it restricts what an attacker can do. This was proposed by Laolu AFAIK, and I believe this is how btcd is proceeding.
            > >> 2) Clients track multiple possible filter header chains and essentially 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 statistically unlikely, or 3) repeatedly serves filters that are significantly larger than the expected size (essentially padding the actual filters with garbage to waste bandwidth). I have not done the analysis yet, but we should be able to come up with some fairly simple banning heuristics using Chernoff 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.
            > >> 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 as currently written. (Though the recommended client protocol in the BIP 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 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 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’s 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’s 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. 
            > >> 
            > >> 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:
            > >>         • Spent outpoints
            > >>         • The scriptPubKey of each output, aside from all OP_RETURN output scripts.
            > >> 
            > >> Tamas Blummer
            > >> _______________________________________________
            > >> bitcoin-dev mailing list
            > >> bitcoin-dev@lists•linuxfoundation.org
            > >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
            > > 
            > 
            
            
            
            ^ permalink raw reply	[flat|nested] 14+ messages in thread

          • • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
                2019-02-06  8:09           ` Tamas Blummer
              @ 2019-02-06 18:17             ` Gregory Maxwell
                2019-02-06 19:48               ` Tamas Blummer
                0 siblings, 1 reply; 14+ messages in thread
              From: Gregory Maxwell @ 2019-02-06 18:17 UTC (permalink / raw)
                To: Tamas Blummer; +Cc: Jim Posen, Bitcoin Protocol Discussion
              
              On Wed, Feb 6, 2019 at 8:10 AM Tamas Blummer <tamas.blummer@gmail•com> wrote:
              > I am skeptical that commitment of any filter will come into Core soon. [...] A committed filter makes light clients much more reliable and attractive, for some taste too much more.
              
              You keep repeating this smear. Please stop.
              
              If you would actually bother reading the threads where this was
              discussed previously you will see that there was significant interest
              from bitcoin developers to eventually commit an output filter, and a
              significant investment of effort in improving the proposal to that
              end.  It is really disheartening to see you continue to repeat your
              negative assumptions about other people's wishes when you haven't even
              invested the time required to read their words.
              
              
              ^ permalink raw reply	[flat|nested] 14+ messages in thread

            • • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
                  2019-02-06 18:17             ` Gregory Maxwell
                @ 2019-02-06 19:48               ` Tamas Blummer
                       [not found]                 ` <CAAS2fgQX_02_Uwu0hCu91N_11N4C4Scm2FbAXQ-0YibroeqMYg@mail.gmail.com>
                  0 siblings, 1 reply; 14+ messages in thread
                From: Tamas Blummer @ 2019-02-06 19:48 UTC (permalink / raw)
                  To: Gregory Maxwell; +Cc: Jim Posen, Bitcoin Protocol Discussion
                
                [-- Attachment #1: Type: text/plain, Size: 1223 bytes --]
                
                I do not think this ad hominem attack of you on me was justified.
                
                I wrote code, gathered and shared data now and back in 2018. I showed
                understanding of non technical issues. Is there an actual action that
                defies my observation that a commitment is not yet in sight?
                
                Is there anything technically wrong in what I wrote?
                
                If not you should stop.
                
                Tamas Blummer
                
                
                On Wed, 6 Feb 2019, 18:17 Gregory Maxwell <greg@xiph•org wrote:
                
                > On Wed, Feb 6, 2019 at 8:10 AM Tamas Blummer <tamas.blummer@gmail•com>
                > wrote:
                > > I am skeptical that commitment of any filter will come into Core soon.
                > [...] A committed filter makes light clients much more reliable and
                > attractive, for some taste too much more.
                >
                > You keep repeating this smear. Please stop.
                >
                > If you would actually bother reading the threads where this was
                > discussed previously you will see that there was significant interest
                > from bitcoin developers to eventually commit an output filter, and a
                > significant investment of effort in improving the proposal to that
                > end.  It is really disheartening to see you continue to repeat your
                > negative assumptions about other people's wishes when you haven't even
                > invested the time required to read their words.
                >
                
                [-- Attachment #2: Type: text/html, Size: 1782 bytes --]
                
                ^ permalink raw reply	[flat|nested] 14+ messages in thread

              • • [parent not found: <CAAS2fgQX_02_Uwu0hCu91N_11N4C4Scm2FbAXQ-0YibroeqMYg@mail.gmail.com>]

                • • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
                           [not found]                 ` <CAAS2fgQX_02_Uwu0hCu91N_11N4C4Scm2FbAXQ-0YibroeqMYg@mail.gmail.com>
                    @ 2019-02-06 21:17                   ` Tamas Blummer
                      2019-02-07 20:36                     ` Pieter Wuille
                      0 siblings, 1 reply; 14+ messages in thread
                    From: Tamas Blummer @ 2019-02-06 21:17 UTC (permalink / raw)
                      To: Gregory Maxwell; +Cc: Jim Posen, Bitcoin Protocol Discussion
                    
                    [-- Attachment #1: Type: text/plain, Size: 1942 bytes --]
                    
                    The attack was in your implication that I would assume  ill intent of those
                    contributed to the proposal. That is not my position. I explained why, I
                    think, rolling out a commitment could face opposition. This foreseable
                    opposition, that must not come from you makes me prefer a provable
                    uncommitted filter for now.
                    
                    I am myself concerned of the implications if many nodes would blindly
                    follow POW.
                    
                    I did restart the discussion which I read and participated in at its first
                    instance because implementing the current proposal taught me how
                    problematic as is until not committed and because I have not seen a sign to
                    assume commitment was imminent.
                    
                    This is not just missing code. AFAIK we do not even have a consensus on how
                    any future soft fork would be activated.
                    
                    While trying to build a useful software I have to make assumtions on the
                    timeline of dependencies and in my personal evaluation commitment is not
                    yet to build on.
                    
                    I and others learned in this new discussion new arguments such as that of
                    atomic swaps by Laolu. If nothing else, this was worth of learning.
                    
                    It appears me that it is rather you assuming ill intent on my side, which
                    hurts given that I do contribute to the ecosystem since many years and have
                    not ever been caught of hurting the project.
                    
                    Tamas Blummer
                    
                    
                    On Wed, 6 Feb 2019, 20:16 Gregory Maxwell <gmaxwell@gmail•com wrote:
                    
                    > On Wed, Feb 6, 2019 at 7:48 PM Tamas Blummer <tamas.blummer@gmail•com>
                    > wrote:
                    > > I do not think this ad hominem attack of you on me was justified.
                    >
                    > I apologize if I have offended you, but I am at a loss to find in my
                    > words you found to be an attack. Can you help me out?
                    >
                    > On reread the only thing I'm saying is that you hadn't even read the
                    > prior discussion. Am I mistaken?  If so, why did you simply propose
                    > reverting prior improvements without addressing the arguments given
                    > the first time around or even acknowledging that you were rehashing an
                    > old discussion?
                    >
                    
                    [-- Attachment #2: Type: text/html, Size: 2657 bytes --]
                    
                    ^ permalink raw reply	[flat|nested] 14+ messages in thread

                  • • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
                        2019-02-06 21:17                   ` Tamas Blummer
                      @ 2019-02-07 20:36                     ` Pieter Wuille
                        0 siblings, 0 replies; 14+ messages in thread
                      From: Pieter Wuille @ 2019-02-07 20:36 UTC (permalink / raw)
                        To: Tamas Blummer, Bitcoin Protocol Discussion; +Cc: Gregory Maxwell, Jim Posen
                      
                      On Thu, 7 Feb 2019 at 12:19, Tamas Blummer via bitcoin-dev
                      <bitcoin-dev@lists•linuxfoundation.org> wrote:
                      > I did restart the discussion which I read and participated in at its first instance because implementing the current proposal taught me how problematic as is until not committed and because I have not seen a sign to assume commitment was imminent.
                      
                      Hi Tamas,
                      
                      I think you're confusing the lack of sign of imminent commitment for a
                      sign it isn't the end goal. Changes in consensus rules take a while,
                      and I think adoption of BIP157 in a limited setting where offered by
                      trusted nodes is necessary before we will see a big push for that.
                      
                      In my personal view (and I respect other opinions in this regard),
                      BIP157 as a public network-facing service offered by untrusted full
                      nodes is fair uninteresting. If the goal wasn't to have it eventually
                      as a commitment, I don't think I would be interested in helping
                      improving it. There are certainly heuristics that reduce the risk of
                      using it without, but they come at the cost of software complexity,
                      extra bandwidth, and a number of assumptions on the types of scripts
                      involved in the transactions. I appreciate work in exploring more
                      possibilities, but for a BIP157-that-eventually-becomes-a-commitment,
                      I think they're a distraction. Unless you feel that changes actually
                      benefit that end goal, I think the current BIP157 filter definition
                      should be kept.
                      
                      There is no problem however in optionally supporting other filters,
                      which make different trade-offs, which are intended to be offered by
                      (semi) trusted nodes. Still, for the reasons above I would very much
                      like to keep those discussions separate from the
                      to-be-committed-filter.
                      
                      Cheers,
                      
                      -- 
                      Pieter
                      
                      
                      ^ permalink raw reply	[flat|nested] 14+ messages in thread

  • * Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal
      2019-02-04 20:18 ` Jim Posen
      2019-02-04 20:59   ` Tamas Blummer
    @ 2021-10-03  9:53   ` Dustin Dettmer
      1 sibling, 0 replies; 14+ messages in thread
    From: Dustin Dettmer @ 2021-10-03  9:53 UTC (permalink / raw)
      To: Bitcoin Protocol Discussion, Jim Posen; +Cc: Jim Posen
    
    [-- Attachment #1: Type: text/plain, Size: 5477 bytes --]
    
    Jim Posen,
    
    A few years ago you mentioned roastbeef’s proposal of a P2P message to
    retrieve all prev-outputs for a given block:
    
    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 against
    > the block by executing them. While this permits some forms of input script
    > malleability (and thus cannot discriminate between all valid and invalid
    > filters), it restricts what an attacker can do. This was proposed by Laolu
    > AFAIK, and I believe this is how btcd is proceeding.
    >
    
    I’m trying to find the follow up on this. Was there discussion about it
    under another name (thread, PR, bip etc)? Apologies if I’m being obtuse and
    it’s easily found but for the life of me I can’t find any references.
    Bip157 seems to not make any mention of it.
    
    Thanks!
    Dustin
    
    >
    
    
    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 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’s 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’s 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.
    >>
    >> 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:
    >>         • Spent outpoints
    >>         • The scriptPubKey of each output, aside from all OP_RETURN
    >> output scripts.
    >>
    >> Tamas Blummer
    >> _______________________________________________
    >> bitcoin-dev mailing list
    >> bitcoin-dev@lists•linuxfoundation.org
    >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
    >>
    > _______________________________________________
    > bitcoin-dev mailing list
    > bitcoin-dev@lists•linuxfoundation.org
    > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
    >
    
    [-- Attachment #2: Type: text/html, Size: 7146 bytes --]
    
    ^ permalink raw reply	[flat|nested] 14+ messages in thread

end of thread, other threads:[~2021-10-03  9:53 UTC | newest]

Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-02-04 11:41 [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal Tamas Blummer
2019-02-04 20:18 ` Jim Posen
2019-02-04 20:59   ` Tamas Blummer
2019-02-05  1:42     ` Olaoluwa Osuntokun
2019-02-05 12:21       ` Matt Corallo
2019-02-06  0:05         ` Olaoluwa Osuntokun
2019-02-05 20:10       ` Tamas Blummer
2019-02-06  0:17         ` Olaoluwa Osuntokun
2019-02-06  8:09           ` Tamas Blummer
2019-02-06 18:17             ` Gregory Maxwell
2019-02-06 19:48               ` Tamas Blummer
     [not found]                 ` <CAAS2fgQX_02_Uwu0hCu91N_11N4C4Scm2FbAXQ-0YibroeqMYg@mail.gmail.com>
2019-02-06 21:17                   ` Tamas Blummer
2019-02-07 20:36                     ` Pieter Wuille
2021-10-03  9:53   ` Dustin Dettmer

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox