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
Built with Python programming language and QT library and Guess the number in three easy, medium and hard rolls

guess-the-numbers Built with Python programming language and QT library and Guess the number in three easy, medium and hard rolls Number guessing game

Amir Hussein Sharifnezhad 5 Oct 09, 2021
Demo code for "Logs in distributed systems" webinar

Hexlet Logs Demo Пререквизиты docker-compose python3 Учетка в DataDog Базовое понимание, что такое логи (можно почитать гайд

Anton Markelov 1 Dec 01, 2021
Improved version calculator, now using while True and etc

CalcuPython_2.0 Olá! Calculadora versão melhorada, agora usando while True e etc... melhorei o design e os carai tudo (rode no terminal, pra melhor ex

Scott 2 Jan 27, 2022
A lighweight screen color picker tool

tkpick A lighweigt screen color picker tool Availability Only GNU/Linux 🐧 Installing Install via pip (No auto-update): [sudo] pip install tkpick Usa

Adil Gürbüz 7 Aug 30, 2021
ABT aka Animated Background Tool is a windows only python program that makes it that you can have animated background.

ABT ABT aka Animated Background Tool is a windows only python program that makes it that you can have animated background. 𝓡𝓔𝓐𝓓 𝓜𝓔, An Important

Yeeterboi4 2 Jul 16, 2022
The LiberaPay archive module for the SeanPM life archive project.

By: Top README.md Read this article in a different language Sorted by: A-Z Sorting options unavailable ( af Afrikaans Afrikaans | sq Shqiptare Albania

Sean P. Myrick V19.1.7.2 1 Aug 26, 2022
Enhanced version of blender's bvh add-on with more settings supported. The bvh's rest pose should have the same handedness as the armature while could use a different up/forward definiton.

Enhanced bvh add-on (importer/exporter) for blender Enhanced bvh add-on (importer/exporter) for blender Enhanced bvh importer Enhanced bvh exporter Ho

James Zhao 16 Dec 20, 2022
Build Xmas cards with user inputs

Automatically build Xmas cards with user inputs

Anand 9 Jan 25, 2022
Simple Assembler with python

Assembler with python converts assembly source code to machine code Requirements Python 3 🐍 Usage python main.py [source] [output] [source] : Path t

Amir mohammad 1 Dec 24, 2021
PDX Code Guild Full Stack Python Bootcamp starting 2022/02/28

Class Liger Rough Timeline Weeks 1, 2, 3, 4: Python Weeks 5, 6, 7, 8: HTML/CSS/Flask Weeks 9, 10, 11: Javascript Weeks 12, 13, 14, 15: Django Weeks 16

PDX Code Guild 5 Jul 05, 2022
Open HW & SW for Scanning Electron Microscopes

OpenSEM Project Status: Preliminary The purpose of this project is to create a modern and open-source hardware and software platform for using vintage

Steven Lovegrove 7 Nov 01, 2022
A basic python project which replicates the functionalities on an 8 Ball.

Magic-8-Ball To the people who wish to make decisions using a Magic 8 Ball but can't get one? I gotchu. This is a basic python project which replicate

3 Jun 24, 2021
A general illumination correction method for optical microscopy.

CIDRE About CIDRE is a retrospective illumination correction method for optical microscopy. It is designed to correct collections of images by buildin

Kevin Smith 31 Sep 07, 2022
A inspector to be able to view and edit Qt style sheet while an application is running

Qt Style Sheet Inspector An inspector widget to view and modify the style sheet of a Qt app at runtime. Usage In order to use the inspector widget on

ESSS 46 Dec 10, 2022
inverted pendulum fuzzy control python code (python 2.7.18)

inverted-pendulum-fuzzy-control- inverted pendulum fuzzy control python code (python 2.7.18) We have 3 general functions for 3 main steps: fuzzificati

arian mottaghi 4 May 23, 2022
Aides to reduce a cheat file with a personal selection of the cheats you want to use.

Retroarch Cheat File Reducer Description Aides to reduce a cheat file with a personal selection of the cheats you want to use. Instructions Copy a sel

1 Jan 09, 2022
Python script for converting obsidian md-file to html (recursively adds all link/images)

ObsidianToHtmlConverter I made a small python script for converting obsidian md-file to static (local) html (recursively adds all link/images) I made

47 Jan 03, 2023
Model Quantization Benchmark

MQBench Update V0.0.2 Fix academic prepare setting. More deployable prepare process. Fix setup.py. Fix deploy on SNPE. Fix convert_deploy bug. Add Qua

500 Jan 06, 2023
This is some simple code to scrape vistbook's system to get an overview of the different cabins availability.

DNT_cabin_availability_system This is some simple code to scrape visbook's system to get an overview of the different cabins availability. The system

Andreas Lorentzen 1 Sep 25, 2022
Cairo-math-64x61 - Fixed point 64.61 math library for Cairo / Starknet

Cairo Math 64x61 A fixed point 64.61 math library for Cairo & Starknet Signed 64

Influence 63 Dec 05, 2022