bitcoin-core/minisketch

View on GitHub ↗ ★ 337 C++

Minisketch: an optimized library for BCH-based set reconciliation

22 mentions on Hacker News by 7 people: 2 stories, 20 comments · first 2018-12-10 · latest 2025-11-25

Mentions per year 22 mentions · busiest year 2020 (6)

20082026

All Stories Comments Newest Top Oldest

…I contributed to a fast implementation of the underlying algorithim: https://github.com/bitcoin-core/minisketch With it two peers could compare their BSSID environments and learn ~nothing about each other unless they were nearl
comment by nullc · 2025-11-25 · in Nearby peer discovery without GPS using environmental fingerprints
…reconciliation as a primitive. I helped create a library for reconciliation which might be useful: https://github.com/bitcoin-core/minisketch One notion would be to divide time in to periods small enough to keep messages relevant, but big…
comment by nullc · 2025-08-09 · in Testing Bitchat at the music festival
…and low failure rates (and on that note is only probabilistic in its success). We implemented https://github.com/bitcoin-core/minisketch which has optimal size efficiency-- N bits of state will always correctly recover when there are N or…
comment by nullc · 2025-07-18 · in Extending That XOR Trick to Billions of Rows
Generalizing an 'xor accumulator' support set difference of more than one element is interesting: https://github.com/bitcoin-core/minisketch
comment by nullc · 2025-07-03 · in That XOR Trick (2020)
…it or develop a better alternative, I did help create a primitive you should consider using: https://github.com/sipa/minisketch
comment by nullc · 2025-06-16 · in Start your own Internet Resiliency Club
…only works over small fields so it doesn't support many independent blocks/packets. Then there is https://github.com/bitcoin-core/minisketch which I am a coauthor of, which is a set corrector like IBLT which achieves perfect communications…
comment by nullc · 2025-05-03 · in Bloom Filters
…should also be aware of pinsketch and, particularly, our implementation of it: minisketch ( https://github.com/sipa/minisketch/ ). Our implementation communicates a difference of <=N b-bit entries with exactly N*b bits with 100% success.…
comment by nullc · 2023-07-13 · in Invertible Bloom Lookup Tables with Less Randomness and Memory
Since the protocol appears to use adhoc synchronization, the authors might be interested in https://github.com/sipa/minisketch/ which is a library that implements a data structure (pinsketch) that allows two parties to synchronize their…
comment by nullc · 2022-11-21 · in Briar: Peer-to-Peer Encrypted Messaging
…structures like the IBLT (Iterative Bloom Lookup Table) and BCH set digests like minisketch. https://github.com/sipa/minisketch Lets say you have a set of a billion items. Someone else has mostly the same set but they differ by 10 items.…
comment by api · 2022-07-22 · in Ask HN: What are some cool but obscure data structures you know about?
…for each power. The tricky part is decoding it. :P Here is an implementation I contributed to: https://github.com/sipa/minisketch/ There is a application related data-structure called an inverted bloom lookup table (IBLT) that accomplishes…
comment by nullc · 2022-07-22 · in Ask HN: What are some cool but obscure data structures you know about?
…would require 4MB of data be transferred to calculate the same thing. *(in particular pin sketch https://github.com/sipa/minisketch ).
comment by zbobet2012 · 2022-07-22 · in Ask HN: What are some cool but obscure data structures you know about?
…identifiers to gain privileged positions. Maybe this is a space where efficient reconciliation ( https://github.com/sipa/minisketch/ ) could help-- certainly if the goal were to flood messages to participants reconciliation can give almost…
comment by nullc · 2021-05-08 · in The Pinecone Overlay Network
…https://pncnmnp.github.io/blogs/spectral-bloom-filters.html [3] http://stevehanov.ca/blog/?id=115 [4] https://github.com/sipa/minisketch
comment by ignoramous · 2021-03-01 · in Show HN: Hackernews-Button – Bloom Filter-based, private HN browsing extension
…4. I just wrote a (slow) native Python re-implementation for demonstration/testing purpose: https://github.com/sipa/minisketch/pull/26 . The C++ code relies on many low-level optimizations that are hard to replicate in higher level…
comment by pwuille · 2020-12-03 · in Using Bloom filters to efficiently synchronise hash graphs
This sounds very interesting, so I tried reading some of the math in https://github.com/sipa/minisketch/blob/master/doc/math.md (I'm not great this kind of math). In my understanding, a Bloom filter, while being O(set_size), nonetheless…
comment by dochtman · 2020-12-03 · in Using Bloom filters to efficiently synchronise hash graphs
…via error correcting codes, for a high performance industrial implementation I contributed to, see: https://github.com/sipa/minisketch/ (I tried submitting this to HN a while back, but no joy--). For our paper on applying this to Bitcoin…
comment by nullc · 2020-12-03 · in Using Bloom filters to efficiently synchronise hash graphs
…in places where network coding is applicable. I worked on an efficient implementation of setrecon https://github.com/sipa/minisketch/ and an application of it to Bitcoin ( https://arxiv.org/abs/1905.10518 ).
comment by nullc · 2020-08-24 · in Network Coding in P2P Networks
…I recently had fun code golfing integer implementations of floor(106*log2(x)) and floor(log2(x!)): https://github.com/sipa/minisketch/blob/master/src/false_pos...
comment by nullc · 2020-06-29 · in Implementing the Exponential Function
…used for near optimal (in the sense of information leak) error correction for "set like" features: https://github.com/sipa/minisketch/ Our application is for communications efficient set reconciliation to convert Bitcoin's…
comment by nullc · 2020-04-27 · in How to generate keys from facial images and keep privacy at the same time (2018) [pdf]
…the Berlekamp–Massey algorithm as part of a greater explanation of some of our work that uses it ( https://github.com/sipa/minisketch/ ). It isn't terribly difficult to work through the algorithm mechanically and see that it solves the…
comment by nullc · 2019-04-11 · in Elwyn Berlekamp has died