Author: Bob McElrath 2016-05-11 20:29:33
Published on: 2016-05-11T20:29:33+00:00
The proposal of creating a Bloom Filter Digest for every block was discussed in the Bitcoin-dev mailing list. The filter size is determined by the number of elements it contains and false-positive rate, where an optimal filter is linear in the number of elements and logarithmic in the false-positive rate. A Cuckoo filter is faster than using Bloom filters as the data that would be put into the filter is already hashed. False-positive rate should be roughly less than 1/block height to prevent light clients from downloading more blocks than necessary. For today's block height (~410000) and false positive rate of 1e-6, this is about 20 bits per element. Thus the required size of the filter commitment is roughly N*log2H, where H is the block height. If Bitcoin had these filters from the beginning, a light client today would have to download about 12MB of data in filters, with personal SPV wallet using 31MB currently. It is not clear if this is a bandwidth win, though it's definitely a win for computing load on full nodes.
Updated on: 2023-06-11T05:00:38.988718+00:00