Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> An example of that cost is you arguing against specifying and supporting the > design that is closer to one that would be softforked, which increases the > time until we can make these filters secure because it > slows convergence on the design of what would get committed Agreed, since the

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> Doesn't the current BIP157 protocol have each filter commit to the filter > for the previous block? Yep! > If that's the case, shouldn't validating the commitment at the tip of the > chain (or buried back whatever number of blocks that the SPV client trusts) > obliviate the need to validate

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> So what's the cost in using > the current filter (as it lets the client verify the filter if they want to, An example of that cost is you arguing against specifying and supporting the design that is closer to one that would be softforked, which increases the time until we can make these filters

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Fri, Jun 08, 2018 at 04:35:29PM -0700, Olaoluwa Osuntokun via bitcoin-dev wrote: > 2. Since the coinbase transaction is the first in a block, it has the > longest merkle proof path. As a result, it may be several hundred bytes > (and grows with future capacity increases) to present

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> That in argument against adopting the inferior version, as that will > contribute more momentum to doing it in a way that doesn't make sense long > term. That was moreso an attempt at a disclosure, rather than may argument. But also as noted further up in the thread, both approaches have a

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Fri, Jun 8, 2018 at 5:03 AM, Olaoluwa Osuntokun via bitcoin-dev wrote: > As someone who's written and reviews code integrating the proposal all the > way up the stack (from node to wallet, to application), IMO, there's no > immediate cost to deferring the inclusion/creation of a filter that

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Hi sipa, > The advantage of (a) is that it can be verified against a full block without > access to the outputs being spent by it > > The advantage of (b) is that it is more compact (scriot reuse, and outputs > spent within the same block as they are created). Thanks for this breakdown. I think

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Sorry if I continue on the subject even if ​custom filter types are considered in BIP 157/158 . I am doing it because ​: 1)​ with a fixed target FP=2^-20 (or 1/784931) ​ and the multi layer filtering maybe it's reasonable to consider less than ~20 bits for the golomb encoding of the per-block

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

It isn't being discussed atm (but was discussed 1 year ago when the BIP draft was originally published), as we're in the process of removing items or filters that aren't absolutely necessary. We're now at the point where there're no longer any items we can remove w/o making the filters less

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Tue, Jun 5, 2018 at 1:08 AM, Jim Posen via bitcoin-dev wrote: > hesitant to make the complexity tradeoff for bandwidth savings due to a > behavior that is actively discouraged. As an important point of clarification here. If scripts are used to identify inputs and outputs, then no use is

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> > I don't understand this comment. The bandwidth gains are not from > address reuse, they are from the observed property that false > positives are independent between two filters. I.e. clients that > connect once a day will probably download 2-3 filters at most, if they > had nothing relevant

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Tue, Jun 5, 2018 at 10:08 AM, Jim Posen wrote: > It also derives all bandwidth gains from address reuse. So I'm > hesitant to make the complexity tradeoff for bandwidth savings due to a > behavior that is actively discouraged. I don't understand this comment. The bandwidth gains are not from

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> > I was wondering why this multi-layer multi-block filter proposal isn't > getting any comment, > is it because not asking all filters is leaking information? > It's an interesting idea, but it adds more complexity to the client and could be added later on if clients adopt BIP 157 and complain

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

I was wondering why this multi-layer multi-block filter proposal isn't getting any comment, is it because not asking all filters is leaking information? Thanks Il giorno ven 18 mag 2018 alle ore 08:29 Karl-Johan Alm via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> ha scritto: > On Fri,

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Correction: - Output script + spent script filters (Wuille’s (b)) have sizes of ca. 2% of block size. Tamas Blummer > On Jun 3, 2018, at 18:44, Tamas Blummer wrote: > > I processed bitcoin history assuming filters using with P=19 M=784931. > > Findings: > - Output script + spent script

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Sat, Jun 2, 2018, 22:56 Tamas Blummer via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Lighter but SPV secure nodes (filter committed) would help the network > (esp. Layer 2) to grow mesh like, but add more user that blindly follow POW. > > On longer term most users' security

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Lighter but SPV secure nodes (filter committed) would help the network (esp. Layer 2) to grow mesh like, but add more user that blindly follow POW. On longer term most users' security will be determined by either trusted hubs or POW. I do not know which is worse, but we should at least offer

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Sat, Jun 2, 2018 at 10:02 PM, Tamas Blummer via bitcoin-dev wrote: > Years of experience implementing wallets with BIP 37 pretty much us that all these filter things are a total waste of time. BIP37 use is nearly dead on the network-- monitor your own nodes to see the actual use of the

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Without block commitment mobiles would have to use trusted filter provider or implement a complex data hungry algorithm and still remain as insecure as with BIP 37. Years of experience implementing wallets with BIP 37 taught us that an outpoint + output script filter is useful. Committing such

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Fri, Jun 01, 2018 at 07:02:38PM -0700, Jim Posen via bitcoin-dev wrote: > Without the ability to verify filter validity, a client would have to stop > syncing altogether in the presence of just one malicious peer, which is > unacceptable. I'm confused about why this would be the case. If

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

To address the at-least-one-honest peer security assumption for light clients, I think this is a rather good security model for light clients. First it significantly reduces the chances that an attacker can eclipse a client just by chance, and clients can implement measures like ensuring

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Sat, Jun 2, 2018 at 12:01 AM, Olaoluwa Osuntokun wrote: >> A typical network attacker (e.g. someone on your lan or wifi segmet, or >> someone who has compromised or operates an upstream router) can be all of >> your peers. > > This is true, but it cannot make us accept any invalid filters

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> A typical network attacker (e.g. someone on your lan or wifi segmet, or > someone who has compromised or operates an upstream router) can be all of > your peers. This is true, but it cannot make us accept any invalid filters unless the attacker is also creating invalid blocks w/ valid PoW. >

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Fri, Jun 1, 2018 at 2:52 AM, Olaoluwa Osuntokun via bitcoin-dev wrote: > One notable thing that I left off is the proposed change to use the previous > output script rather than the outpoint. Modifying the filters in this > fashion would be a downgrade in the security model for light clients,

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Hi y'all, I've made a PR to the BIP repo to modify BIP 158 based on this thread, and other recent threads giving feedback on the current version of the BIP: * https://github.com/bitcoin/bips/pull/687 I've also updated the test vectors based on the current parameters (and filter format), and

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> The additional benefit of the input script/outpoint filter is to watch for > unexpected spends (coins getting stolen or spent from another wallet) or > transactions without a unique change or output address. I think this is a > reasonable implementation, and it would be nice to be able to

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> Is there an application that requires watching for output scripts that > doesn't also require watching for input scrips (or, less efficiently, > input outpoints)? > Certain wallets may be able to use only the output script filter by using output scripts to watch for confirmations on sent

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Tue, May 29, 2018 at 2:42 AM, Jim Posen wrote: > Certain wallets may be able to use only the output script filter by using > output scripts to watch for confirmations on sent transactions, assuming > that application is the only one with access to the private keys. The > additional benefit of

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Is there an application that requires watching for output scripts that doesn't also require watching for input scrips (or, less efficiently, input outpoints)? Any of the wallet application that I'm aware of need to see coins being spent as well as created, else they may try to spend already spent

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Forgot to mention: The link I sent is to a branch that is patched to produce the filter stats. This is the main project and the BIP158 implementation: https://github.com/rust-bitcoin/rust-bitcoin-spv/blob/master/src/blockfilter.rs Tamas Blummer > On May 28, 2018, at 20:18, Tamas Blummer

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Hi all, Jimpo, thanks for looking into those stats! I had always imagined that there would be a more significant savings in having all filters in one bundle, as opposed to separate. These results are interesting, to say the least, and definitely offer us some flexibility in options for filter

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Any chance you could add a graph of input-scripts (instead of input outpoints)? On Wed, May 23, 2018 at 7:38 AM, Jim Posen via bitcoin-dev wrote: > So I checked filter sizes (as a proportion of block size) for each of the > sub-filters. The graph is

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Thanks, Jimpo! This is very encouraging, I think. I sorta assumed that separating the elements into their own sub-filters would hurt the compression a lot more. Can the compression ratio/false positive rate be tweaked with the sub-filters in mind? With the total size of the separated filters

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> > My suggestion was to advertise a bitfield for each filter type the node > serves, > where the bitfield indicates what elements are part of the filters. This > essentially > removes the notion of decided filter types and instead leaves the decision > to > full-nodes. > I think it makes more

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Maybe I didn't make it clear, but the distinction is that the current track allocates one service bit for each "filter type", where it has to be agreed upon up front what elements such a filter type contains. My suggestion was to advertise a bitfield for each filter type the node serves, where

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> What if instead of trying to decide up front which subset of elements will > be most useful to include in the filters, and the size tradeoff, we let the > full-node decide which subsets of elements it serves filters for? This is already the case. The current "track" is to add new service bits

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Hi Y'all, The script finished a few days ago with the following results: reg-filter-prev-script total size: 161236078 bytes reg-filter-prev-script avg: 16123.6078 bytes reg-filter-prev-script median: 16584 bytes reg-filter-prev-script max: 59480 bytes Compared

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Hi all, Most light wallets will want to download the minimum amount of data required to operate, which means they would ideally download the smallest possible filters containing the subset of elements they need. What if instead of trying to decide up front which subset of elements will be most

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Thu, May 17, 2018 at 2:44 PM Jim Posen via bitcoin-dev Monitoring inputs by scriptPubkey vs input-txid also has a massive >> advantage for parallel filtering: You can usually known your pubkeys >> well in advance, but if you have to change what you're watching block >> N+1 for based on the

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Riccardo wrote: > The BIP recall some go code for how the parameter has been selected which > I can hardly understand and run The code you're linking to is for generating test vectors (to allow implementations to check the correctness of their gcs filters. The name of the file is

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Fri, May 18, 2018, 19:57 Olaoluwa Osuntokun via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Greg wrote: > > What about also making input prevouts filter based on the scriptpubkey > being > > _spent_? Layering wise in the processing it's a bit ugly, but if you > > validated

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Greg wrote: > What about also making input prevouts filter based on the scriptpubkey being > _spent_? Layering wise in the processing it's a bit ugly, but if you > validated the block you have the data needed. AFAICT, this would mean that in order for a new node to catch up the filter index

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Matt wrote: > I believe (1) could be skipped entirely - there is almost no reason why > you'd not be able to filter for, eg, the set of output scripts in a > transaction you know about Depending on the use-case, the txid is more precise than searching for the output script as it doesn't need to

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Another parameter which heavily affects filter size is the false positive rate which is empirically set to 2^-20 The BIP recall some go code

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Fri, May 18, 2018 at 12:25 AM, Matt Corallo via bitcoin-dev wrote: > In general, I'm concerned about the size of the filters making existing > SPV clients less willing to adopt BIP 158 instead of the existing bloom > filter garbage and would like to see a

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> > It isn't a question of 'some lite clients' -- I am aware of no > implementation of these kinds of measures in any cryptocurrency ever. > Doesn't mean there can't or shouldn't be a first. :-) > The same kind of comparison to the block could have been done with > BIP37 filtering, but no one

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Thu, May 17, 2018 at 8:19 PM, Jim Posen wrote: > In my opinion, it's overly pessimistic to design the protocol in an insecure > way because some light clients historically have taken shortcuts. Any non-commited form is inherently insecure. A nearby network attacker (or

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

> > I think lite clients cross checking is something which very likely > will never be implemented by anyone, and probably not stay working > (due to under-usage) if it is implemented. This thought is driven by > three things (1) the bandwidth overhead of performing the check, (2) > thinking

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Thu, May 17, 2018 at 4:59 PM, Matt Corallo wrote: > Yea I generally would really prefer something like that but it > significantly complicates the download logic - currently clients can > easily cross-check [...] Maybe > there is some other reasonable download logic

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Thu, May 17, 2018 at 4:59 PM, Matt Corallo wrote: > Yea I generally would really prefer something like that but it > significantly complicates the download logic - currently clients can > easily cross-check [...] Maybe > there is some other reasonable download logic

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

Yea I generally would really prefer something like that but it significantly complicates the download logic - currently clients can easily cross-check a filter in case they differ between providers by downloading the block. If we instead went with the script being spent they would have to be

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Thu, May 17, 2018 at 3:25 PM, Matt Corallo via bitcoin-dev wrote: > I believe (1) could be skipped entirely - there is almost no reason why > you'd not be able to filter for, eg, the set of output scripts in a > transaction you know about I think this is

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

(1) can be accomplished by filtering for the set of outputs in the transaction you created. I agree (2) would ideally be done to avoid issues with a copied wallet (theft or not), but I am worried about the size of the filters themselves, not just the size of the blocks downloaded after a match.

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

On Thu, May 17, 2018 at 11:25:12AM -0400, Matt Corallo via bitcoin-dev wrote: > BIP 158 currently includes the following in the "basic" filter: 1) > txids, 2) output scripts, 3) input prevouts. > > I believe (1) could be skipped entirely - there is almost no reason why > you'd not be able to

[bitcoin-dev] BIP 158 Flexibility and Filter Size

BIP 158 currently includes the following in the "basic" filter: 1) txids, 2) output scripts, 3) input prevouts. I believe (1) could be skipped entirely - there is almost no reason why you'd not be able to filter for, eg, the set of output scripts in a transaction you know about and (2) and (3)