[bitcoin-dev] Block Batch Filters for Light Clients

[bitcoin-dev] Block Batch Filters for Light Clients

[admin]

[-- Attachment #1: Type: text/plain, Size: 1764 bytes --]

Hello list, 

Here is a link for a draft of a BIP for  compact probabilistic block filters alternative of BIP 158

https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=sharing <https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=sharing>

Summary:

 - BIP 158  false positive rate is low, we can achieve lower bandwidth with higher false positive rate filter while sync blockchain

 - BIP 158 not do not support filter batching by design of used parameters for siphash and Golomb coding optimal parameters

 - Alternative compression with delta coding and splitting data to 2 bit string  sequences. First for data without prefixes, second one for information about  bit length written to first sequence.
   Second sequence have a lot of duplicates,  compressed with 2 round of Huffman algorithm. (Effectivity about 98% vs Golomb with optimal parameters)

 - Block filters batching reduce filter size significantly

- Separation of filters by address type allows lite client not to download redundant information without compromising privacy.

- Lite client filters download strategy: get biggest filter (smallest blocks/size rate) for blocks range, in case positive test  -> get medium filters to reduce blocks range ->  get block filters for affected range -> download affected blocks over TOR 

Implementation (python): https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py#L172 <https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py#L172>

Exactly information from mainnet  about size for separated filters by address types and batch size will be added within few days.

Thanks for any feedback.
      Aleksey Karpov


[-- Attachment #2: Type: text/html, Size: 2818 bytes --]

Re: [bitcoin-dev] Block Batch Filters for Light Clients

[Tamas Blummer]

[-- Attachment #1: Type: text/plain, Size: 3042 bytes --]

Hi Aleksey,

Yes, BIP158 uses the block hash to seed the hash function, which makes distinct block filters non-aggregatable 
for common values. Aggregate fiters on ranges of blocks would have to use some other seed and then 
achive significant savings using the same design.

I think that the most likely use of filters is to decide if a newly announced block should be downloaded and 
not scanning over the entire chain, where aggregate filters would help. I also suspect that whole chain 
scans would be better served with plain sequential reads in map-reduce style.

Typical clients do not care of filters for blocks before the birth date of their wallet’s keys, so they skip over the 
majority of history which is a bigger saving than any aggregate filter.

I wish we get a filter committed as commitment would unlock more utility than any marginal savings through
more elaborate design.

Tamas Blummer

> On Sep 19, 2019, at 19:20, admin--- via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> Hello list, 
> 
> Here is a link for a draft of a BIP for  compact probabilistic block filters alternative of BIP 158
> 
> https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=sharing <https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=sharing>
> 
> Summary:
> 
>  - BIP 158  false positive rate is low, we can achieve lower bandwidth with higher false positive rate filter while sync blockchain
> 
>  - BIP 158 not do not support filter batching by design of used parameters for siphash and Golomb coding optimal parameters
> 
>  - Alternative compression with delta coding and splitting data to 2 bit string  sequences. First for data without prefixes, second one for information about  bit length written to first sequence.
>    Second sequence have a lot of duplicates,  compressed with 2 round of Huffman algorithm. (Effectivity about 98% vs Golomb with optimal parameters)
> 
>  - Block filters batching reduce filter size significantly
> 
> - Separation of filters by address type allows lite client not to download redundant information without compromising privacy.
> 
> - Lite client filters download strategy: get biggest filter (smallest blocks/size rate) for blocks range, in case positive test  -> get medium filters to reduce blocks range ->  get block filters for affected range -> download affected blocks over TOR 
> 
> Implementation (python): https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py#L172 <https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py#L172>
> 
> Exactly information from mainnet  about size for separated filters by address types and batch size will be added within few days.
> 
> Thanks for any feedback.
>       Aleksey Karpov
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[-- Attachment #2: Type: text/html, Size: 4967 bytes --]

Re: [bitcoin-dev] Block Batch Filters for Light Clients

[nopara73]

[-- Attachment #1: Type: text/plain, Size: 3488 bytes --]

Please also take a look at "Applying Private Information Retrieval to
Lightweight Bitcoin Clients" Scaling Bitcoin talk. The academics were not
aware of BIP158 at all, yet came up with a similar scheme independently.

On Sat, Sep 21, 2019 at 11:40 PM Tamas Blummer via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Aleksey,
>
> Yes, BIP158 uses the block hash to seed the hash function, which makes
> distinct block filters non-aggregatable
> for common values. Aggregate fiters on ranges of blocks would have to use
> some other seed and then
> achive significant savings using the same design.
>
> I think that the most likely use of filters is to decide if a newly
> announced block should be downloaded and
> not scanning over the entire chain, where aggregate filters would help. I
> also suspect that whole chain
> scans would be better served with plain sequential reads in map-reduce
> style.
>
> Typical clients do not care of filters for blocks before the birth date of
> their wallet’s keys, so they skip over the
> majority of history which is a bigger saving than any aggregate filter.
>
> I wish we get a filter committed as commitment would unlock more utility
> than any marginal savings through
> more elaborate design.
>
> Tamas Blummer
>
> On Sep 19, 2019, at 19:20, admin--- via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> Hello list,
>
> Here is a link for a draft of a BIP for  compact probabilistic block
> filters alternative of BIP 158
>
>
> https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=sharing
>
> Summary:
>
>  - BIP 158  false positive rate is low, we can achieve lower bandwidth
> with higher false positive rate filter while sync blockchain
>
>  - BIP 158 not do not support filter batching by design of used parameters
> for siphash and Golomb coding optimal parameters
>
>  - Alternative compression with delta coding and splitting data to 2 bit
> string  sequences. First for data without prefixes, second one for
> information about  bit length written to first sequence.
>    Second sequence have a lot of duplicates,  compressed with 2 round of
> Huffman algorithm. (Effectivity about 98% vs Golomb with optimal parameters)
>
>  - Block filters batching reduce filter size significantly
>
> - Separation of filters by address type allows lite client not to download
> redundant information without compromising privacy.
>
> - Lite client filters download strategy: get biggest filter (smallest
> blocks/size rate) for blocks range, in case positive test  -> get medium
> filters to reduce blocks range ->  get block filters for affected range ->
> download affected blocks over TOR
>
> Implementation (python):
> https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py#L172
>
> Exactly information from mainnet  about size for separated filters by
> address types and batch size will be added within few days.
>
> Thanks for any feedback.
>       Aleksey Karpov
>
> _______________________________________________
> 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
>


-- 
Best,
Ádám

[-- Attachment #2: Type: text/html, Size: 5312 bytes --]

Re: [bitcoin-dev] Block Batch Filters for Light Clients

[admin]

[-- Attachment #1: Type: text/plain, Size: 1005 bytes --]

Last version updated draft

 https://github.com/bitaps-com/bips/blob/master/bip-block-batch-filters.mediawiki <https://github.com/bitaps-com/bips/blob/master/bip-block-batch-filters.mediawiki>

Summary changes:

- return back to Golomb coding 
- implemented more simple and effective shema
- Total filters size  is smaller then BIP 158 at all total estimated savings more than 20% (exactly info will be soon)
- filter is deterministic  and could be committed as commitment in coinbase transaction in future
- flexible GCS parameters to to maintain the necessary FPS
- spliting filter for 2 parts: unique elements and duplicated elements
- duplicated elements could be encoded more effective

Open questions:

- Optimal range for batch?
- Why we need sip has instead of just use first 64 bits from pub key/script hash?
- Downloading unique/duplicated elements separately? Just add filter types for these purposes?


Thanks for any feedback or discussions 
    Aleksey Karpov





[-- Attachment #2: Type: text/html, Size: 1663 bytes --]

Re: [bitcoin-dev] Block Batch Filters for Light Clients

[admin]

[-- Attachment #1: Type: text/plain, Size: 1339 bytes --]


Block Batch Filters draft :

https://github.com/bitaps-com/bips/blob/master/bip-block-batch-filters.mediawiki <https://github.com/bitaps-com/bips/blob/master/bip-block-batch-filters.mediawiki>

BIP 157 unlike BIP 37 not allow apply filters to mempool and check zero confirmation transactions.
Light client that refused to use BIP 37 due to privacy leaks can process unconfirmed transactions only one way and this is loading the entire mempool transaction flow.

Mempool Transaction Filters draft:

https://github.com/bitaps-com/bips/blob/master/bip-mempool-transactions-filters.mediawiki <https://github.com/bitaps-com/bips/blob/master/bip-mempool-transactions-filters.mediawiki>

Summary:
    - improved Block Batch Filters definition
    - unlocked ability to filter unconfirmed transaction for SPV nodes used BIP 157 instead of BIP 37 due privacy leak in BIP 37
    - more bandwidth consumption reduced in contrast with block filters and downloading full blocks for affected addresses
    - proposal for future consensus layer soft-fork to make block filters commitment one of the block validation rule to protect light nodes from payment hiding attack






> 23 сент. 2019 г., в 15:00, bitcoin-dev-request@lists.linuxfoundation.org написал(а):
> 
> Re: Block Batch Filters for Light Clients


[-- Attachment #2: Type: text/html, Size: 2581 bytes --]

Re: [bitcoin-dev] Block Batch Filters for Light Clients

[Jonas Schnelli]

[-- Attachment #1: Type: text/plain, Size: 1628 bytes --]

Hi Aleksey

> BIP 157 unlike BIP 37 not allow apply filters to mempool and check zero confirmation transactions.
> Light client that refused to use BIP 37 due to privacy leaks can process unconfirmed transactions only one way and this is loading the entire mempool transaction flow.
> 
> https://github.com/bitaps-com/bips/blob/master/bip-mempool-transactions-filters.mediawiki <https://github.com/bitaps-com/bips/blob/master/bip-mempool-transactions-filters.mediawiki>

Instead of using a per tx filter, would it be possible to allow retrieving a complete compact filter of the whole mempool (similar to BIP35)? Maybe using a maximum size of the filter (ordered by feerate).
In general, I guess the concerns are DOS and fingerprinting.

Maybe DOS could be mitigated via a dynamic filter construction (append elements during the time between blocks, though unsure if possible).
The update-interval of a such filter could also be timebases rather than on every new tx in the mempool.

Unsure about fingerprinting defence measures.

I would expect the following process:
* peer generates mempool filter
* [timespan A (say 3 seconds)]
* light client connects to peer
* light client requests mempool-filter
* peers sends mempool filter
* light client processes filter for relevant txns
* eventually, light client sends getdata of relevant txns

a) after the initial retrieve...
* light client inspects all new txns (inv/getdata) received from peers from this point on (filterless unconfirmed tx detection)

Of if a) is to bandwidth expansive, request the mempool filter again after a timeout

/jonas


[-- Attachment #2: Type: text/html, Size: 2166 bytes --]