Quotidien Fintech, Blocktech, DeFi, Blockchain
              


Lundi 21 Juin 2021

Bloom filters: How do they work?


A bloom filter is a data structure that is designed to describe a desired pattern without specifying it.



They are an efficient way of expressing a search pattern while ensuring privacy in the process. They are used by the Simplified Payment Verification (SPV) nodes to seek transactions that match their patterns from their "peers", without revealing the specific address keys, or the transactions they are looking for.

Bloom filters serve their functions to ensure that SPV nodes are able to specify a search pattern for transactions that can be tuned towards privacy and precision. Some bloom filters are more specific and they provide accurate results, but they do this at the expense of revealing the kind of pattern the SPV node is interested in. This inevitably reveals the address of the user's wallet. However, some bloom filters are less specific and will generate more data about the transactions, many of which are irrelevant to the node, but will ensure that the nodes maintain proper privacy.

How do the bloom filters work?

The bloom filters are employed as a series of X binary digits and a variable number of Y hash functions. These hash functions are specially designed to always generate an output that lies between 1 and X and this corresponds to the series of binary digits. The hash functions are deterministically created to ensure that every node employing a bloom filter will always adopt the same hash functions and will generate similar results for a certain input.

By selecting a different length (X) bloom filters and a different number (Y) of hash functions, tuning the bloom filters can be done, which ensures variations in the level of accuracy and allows privacy.

Initialization of the bloom filters is done to ensure that the series of bits are all zeros. To include a pattern to the bloom filter, the pattern must be hashed by every hash function. When the first hash function is applied to the input, the result lies between 1 and X. Then, the corresponding bit in the series is determined and set to 1, and in the process, record the output of the hash function. The next hash function is then used to set another bit and this goes on like that. Once every single Y hash function has been exhausted, the pattern is recorded in the bloom as Y bits that have been altered from 0 to 1.

Note: it is not a strange fact that Bloom filters are ideal for the Blockchain and it’s related services to perform more efficiently. This is best experienced when trading Bitcoins. When you visit some websites, you learn about how some platforms offer automated trading services to make transactions carried out more efficiently.

How does an SPV node use the bloom filter

One of the major importance of the bloom filters is that they are used to filter transactions that an SPV node receives from its peers and then, choosing just the transactions of interest to the SPV without sharing the addresses or keys that are associated with it.

When an SPV node initializes a bloom filter as empty, then the bloom filter ceases to match any patterns. The node will make a list of the keys, addresses, and hashes that are of interest. The node will propagate a "filterload" message to its peers, with the bloom filter to be used on the connection. The bloom filters are then checked against every incoming transaction.

The full node assesses different parts of the transaction against the bloom filters looking for a match such as
• The data from the scripts of the transaction outputs
• Transaction ID
• Transaction inputs
• Every single one of the signature data input components
After assessing against all these components for a match, the bloom filters can be used to match public key hashes, scripts, public keys, or any component of a smart contract.
Once a filter is set up, the transaction outputs will then be tested by the "peer" against the bloom filter. Transactions that match the filters are the only ones that are sent to the node.




Finyear: latest news, derniers articles


Inscription à la newsletter

Flux RSS