A naive bloom filter implementation in Cairo.
A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either “possibly in set” or “definitely not in set”. Elements can be added to the set, but not removed (though this can be addressed with the counting Bloom filter variant); the more items added, the larger the probability of false positives.
Motivation from this blogpost that states a maxim for StarkNet:
Computation is cheap. Writes are expensive. That said, a bloom filter seems like it will be a fairly common tool to reach for when wanting to check membership of a set, without having to store that full set on chain.
Better implementations likely exist ? I used a full felt of storage for every bit in the bitarray. Probably should try to actually use the rest of the bits in each felt.
Start a new virtual environment:
[email protected]:~/dev/eth/starknet/cairo-bloom$ python3.7 -m venv venv [email protected]:~/dev/eth/starknet/cairo-bloom$ source venv/bin/activate
Install OpenZeppelin’s nile, then use it to install the StarkNet toolchain:
(venv) [email protected]:~/dev/eth/starknet/cairo-bloom$ python -m pip install cairo-nile (venv) [email protected]:~/dev/eth/starknet/cairo-bloom$ nile install
Run unit tests:
(venv) [email protected]:~/dev/eth/starknet/cairo-bloom$ make test pytest tests/ ==================== test session starts ===================== platform linux -- Python 3.7.12, pytest-7.0.0, pluggy-1.0.0 rootdir: /home/sam/dev/eth/starknet/cairo-bloom plugins: typeguard-2.13.3, asyncio-0.17.2, web3-5.27.0 asyncio: mode=legacy collected 1 item tests/test_bloom.py . [100%] =============== 1 passed, 2 warnings in 51.79s ===============