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
Process GPX files (adding sensor metrics, uploading to InfluxDB, etc.) exported from imxingzhe.com

Xingzhe GPX Processor 行者轨迹处理工具 Xingzhe sells cheap GPS bike meters with sensor support including cadence, heart rate and power. But the GPX files expo

Shengqi Chen 8 Sep 23, 2022
Simple card retirement plugin for Anki

Anki Retirement Addon Allow users to suspend, tag, delete, or move cards that reach a specific retirement interval Supports Anki version 2.1.45 Licens

3 Dec 23, 2022
Supercharge your NFTs with new behaviours and superpowers!

WrapX Supercharge your NFTs with new behaviours and superpowers! WrapX is a collection of Wrappers (currently one - WrapXSet) to decorate your NTFs ad

Emiliano Bonassi 9 Jun 13, 2022
MuMMI Core is the underlying infrastructure and generalizable component of the MuMMI framework

MuMMI Core is the underlying infrastructure and generalizable component of the MuMMI framework, which facilitates the coordination of massively parallel multiscale simulations.

4 Aug 17, 2022
A Non profit app built on top of Frappe framework & ERPNext

Non Profit A Non profit app built on top of Frappe framework & ERPNext. People who change the world need the tools to do it! The Non Profit Modules of

Frappe 16 Nov 17, 2022
A web application which you can search, buy or sell shares with current prices which provided by IEX.

CS50 - Stock Exchange A web application which you can search, buy or sell shares with current prices which provided by IEX. Table of Contents Setup St

1 May 28, 2022
Companion Web site for Fluent Python, Second Edition

Fluent Python, the site Source code and content for fluentpython.com. The site complements Fluent Python, Second Edition with extra content that did n

Fluent Python 49 Dec 08, 2022
A python library for writing parser-based interactive fiction.

About IntFicPy A python library for writing parser-based interactive fiction. Currently in early development. IntFicPy Docs Parser-based interactive f

Rita Lester 31 Nov 23, 2022
Pre-commit hook for upgrading type hints

This is a pre-commit hook configured to automatically upgrade your type hints to the new native types implemented in PEP 585.

snok 54 Nov 14, 2022
Decentralized intelligent voting application.

DiVA Decentralized intelligent voting application. Hack the North 2021. Inspiration Following the previous US election, many voters were fearful that

Ali Shariatmadari 4 Jun 05, 2022
Radiosonde Telemetry Decoders

Radiosonde Telemetry Frame Decoders This repository is an attempt to collate the various sources of information on how to decode radiosonde telemetry

Project Horus 3 Jan 04, 2022
A pomodoro app written in Python

Pomodoro It's a pomodoro app written in Python. You can minimize it while you're working if you want to, it'll pop up on your screen when the timer is

Yiğit 1 Dec 20, 2021
适用于HoshinoBot下的人生重来模拟器插件

LifeRestart for HoshinoBot 原作地址 python版原地址 本项目地址 安装方法 这是一个HoshinoBot的人生重来模拟器插件 这个项目使用的HoshinoBot的消息触发器,如果你了解其他机器人框架的api(比如nonebot)可以只修改消息触发器就将本项目移植到其他

黛笙笙 16 Sep 03, 2022
Python tools for working with Orbit Ephemeris Messages (OEMs).

Python Orbit Ephemeris Message tools Python tools for working with Orbit Ephemeris Messages (OEMs). Development Status Installation The oem package is

Brad Sease 4 Apr 06, 2022
A Python Based Utility for Processing GST-Return JSON Files to Multiple Formats

GSTR 1/2A Utility by Shan.tk Open Source GSTR 1/GSTR 2A JSON to Excel utility based on Python. Useful for Auditors in Verifying GSTR 1 Return Invoices

Sudharshan TK 1 Oct 08, 2022
Generalise Prometheus metrics. takes out server specific, replaces variables and such.

Generalise Prometheus metrics. takes out server specific, replaces variables and such. makes it easier to copy from Prometheus console straight to Grafana.

ziv 5 Mar 28, 2022
A place where the most basic, basic of python coding exists

python-basics A place where the most basic, basic of python coding exists As you can see, there are four folders and the best order to read is: appeti

Chuqin 2 Oct 05, 2022
Find habits that genuinely increase your productivity

BiProductive Description This repository contains the application BiProductive, which analyzes the habits of the person, tests his productivity, and d

Rizvan Iskaliev 43 Jun 11, 2022
Compile Binary Ninja's HLIL IR to LLVM, for purposes of compiling it back to a binary again.

Compiles BinaryNinja's HLIL to LLVM Approach Sweep binary for global variables, create them Sweep binary for (used?) external functions, declare those

Kyle Martin 31 Nov 10, 2022
A VirtualBox manager with interactive mode

A VirtualBox manager with interactive mode

Luis Gerardo 1 Nov 21, 2021