Cairo-bloom - A naive bloom filter implementation in Cairo

Overview

🥀 cairo-bloom

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. Optimized a little bit, now stores 64 bits per felt of storage.

Development

Start a new virtual environment:

[email protected]:~/dev/eth/starknet/cairo-bloom$ python3.7 -m venv venv
s[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 ===============
Owner
Sam Barnes
Sam Barnes
HatAsm - a HatSploit native powerful assembler and disassembler that provides support for all common architectures

HatAsm - a HatSploit native powerful assembler and disassembler that provides support for all common architectures.

EntySec 8 Nov 09, 2022
A weekly dive into commonly used modules in the Rust ecosystem, with story flavor!

The goal of this project is to bring the same concept as PyMOTW to the Rust world. PyMOTW was an invaluable resource for me when I was learning Python years ago, and I hope that I can help someone in

Scott Lyons 20 Aug 26, 2022
Pipenv-local-deps-repro - Reproduction of a local transitive dependency on pipenv

Reproduction of the pipenv bug with transitive local dependencies. Clone this re

Lucas Duailibe 2 Jan 11, 2022
The Python agent for Apache SkyWalking

SkyWalking Python Agent SkyWalking-Python: The Python Agent for Apache SkyWalking, which provides the native tracing abilities for Python project. Sky

The Apache Software Foundation 149 Dec 12, 2022
PyDateWaiter helps waiting special day & calculating remain days till that day with Python code.

PyDateWaiter (v.Beta) PyDateWaiter helps waiting special day(aniversary) & calculating remain days till that day with Python code. Made by wallga gith

wallga 1 Jan 14, 2022
An extension for Arma 3 that lets you write extensions in Python 3

An Arma 3 extension that lets you to write python extensions for Arma 3. And it's really simple and straightforward to use!

Lukasz Taczuk 48 Dec 18, 2022
monster hunter world randomizer project

mhw_randomizer monster hunter world randomizer project Settings are in rando_config.py Current script for attack randomization is n mytest.py There ar

2 Jan 24, 2022
Project 2 for Microsoft Azure on WUT

azure-proj2 Project 2 for Microsoft Azure on WUT Table of contents Team Tematyka projektu Architektura Opis rozwiązania Demo dzałania The Team Krzyszt

1 Dec 07, 2021
Analyzes crypto candles over a set time period and then trades based on winning patterns found

patternstrade Analyzes crypto candles over a set time period and then trades based on winning patterns found. Heavily customizable. Warning: This was

ConnorCreate 14 May 29, 2022
Team Hash Brown Science4Cast Submission

Team Hash Brown Science4Cast Submission This code reproduces Team Hash Brown's (@princengoc, @Xieyangxinyu) best submission (ee5a) for the competition

3 Feb 02, 2022
A simply program to find active jackbox.tv game codes

PeepingJack A simply program to find active jackbox.tv game codes How does this work? It uses a threadpool to loop through all possible codes in a ran

3 Mar 20, 2022
Integration of CCURE access control system with automation HVAC of a commercial building

API-CCURE-Automation-Quantity-Floor Integration of CCURE access control system with automation HVAC of a commercial building CCURE is an access contro

Alexandre Edson Silva Pereira 1 Nov 24, 2021
Um Script De Mensagem anonimas Para linux e Termux Feito em python

Um Script De Mensagem anonimas Para linux e Termux Feito em python feito em um celular

6 Sep 09, 2021
Q-Tracker is originally a High School Project created by Admins of Cirus Lab.

Q-Tracker is originally a High School Project created by Admins of Cirus Lab. It's completly coded in python along with mysql.(Tkinter For GUI)

Adithya Krishnan 2 Nov 14, 2022
Programming labs for 6.S060 (Foundations of Computer Security).

6.S060 Labs This git repository contains the code for the labs in 6.S060. In these labs, you will add a series of security features to a photo-sharing

MIT PDOS 10 Nov 02, 2022
Basic code and description for GoBigger challenge 2021.

GoBigger Challenge 2021 en / 中文 Challenge Description 2021.11.13 We are holding a competition —— Go-Bigger: Multi-Agent Decision Intelligence Challeng

OpenDILab 183 Dec 29, 2022
Convert your Gyrosco.pe travels to GPX files

gyroscope2gpx This little python joint will do you a favor of taking your "Travel" export from Gyroscope (https://gyrosco.pe) and turn it into a bunch

nick g 4 Oct 02, 2022
Reactjs web app written entirely in python, using transcrypt compiler.

Reactjs web app written entirely in python, using transcrypt compiler.

Dan Shai 22 Nov 27, 2022
MODeflattener deobfuscates control flow flattened functions obfuscated by OLLVM using Miasm.

MODeflattener deobfuscates control flow flattened functions obfuscated by OLLVM using Miasm.

Suraj Malhotra 138 Jan 07, 2023
Practice10 - Operasi String With Python

Operasi String MY SOSIAL MEDIA : Apa itu Python String ? String adalah urutan si

Maulana Reza Badrudin 1 Jan 05, 2022