Improve implementation of Bitfields

[lazzarello]

@cowlicks Thanks for the update on Replicator. Making this issue to track where we're going. I'll get some tests working for this and try and improve the bitfield implementation.

https://github.com/cowlicks/replicator/blob/master/bitfield/src/lib.rs

[louisgregg]

Hi @lazzarello,

I've been looking into this ticket too a bit. Maybe we can draw inspiration from how chunks of blobs are currently tracked in the iroh project. I include some notes on this ticket and possilbe approaches below. @cowlicks if I've misunderstood anything, please let me know.

(in other words I was asked to solve the problem and delivered this book report on trendy p2p projects instead. Hopefully this is useful information anyway?)

Ticket Goal: Improve the memory/space efficiency of the storage of Bitfields

The DumbBitField struct tracks which chunks of a specific hypercore are available from a specific peer. Currently the underlying datastructure in hypercore-rs is a BTree. A client interested in m hypercores, and aware of n peers must store m*n instances of DumbBitField[1]. For a large file/hypercore broken into many constituent chunks, the memory required to keep track of these chunks may become unwieldly. Hence the goal of this ticket is to minimize the memory required to store a DumbBitField.

Tracking chunks of blobs in the iroh-blobs crate

The iroh project addresses a similar problem in their iroh-blobs crate. For the purpose of this ticket, an iroh blob is a (possibly large) file broken into chunks which one or more peers wish to sync using a verified streaming protocol. In iroh-blobs, a peer does not track the availability of chunks on a per-peer basis. However, a Bitfield implementation is used to track which chunks of a blob are available in the local copy of a blob [2]. Under the hood, this contains an instance of the ChunkRanges type from the n0 bao-tree crate, which is itself derived from range_collections::RangeSet2. This is just a RangeSet with two indices. The RangeSet docs detail the time complexity of their implementation and claim it's fast. I'm hoping it would be sufficiently efficient space-wise for our purposes too. Could we base our solution on bao-tree::ChunkRanges or RangeSet2?

[1] For reference, in the original hypercore implementation, this functionality is achieved using the RemoteBitField class. Their replicator implementation seems to be under active development (recent commits in January 2026), so maybe we can steal politely borrow ideas from their project?

[2] To complete a blob, a peer determines what's missing from their local Bitfield and iteratively requests to stream the missing chunks from remote peers until the local bitfield is complete. Thus, a peer keeps no record of remote state, but a remote-peer-state discovery mechanism could be incorporated in future.

[louisgregg]

After some thought I'd like to use the range-set-blaze crate for the solution.

The main reason is that RangeSetBlaze implements get, insert and remove methods, which should directly satisfy the in-place unit tests for the DumbBitField with minimal glue code. That is my main motivation to use this instead of the range_collections::RangeSet class I suggested in my last comment - ease of implementation.

Under the hood, it uses a BTreeMap to store ranges of indices. I believe this should be more space efficient than the current implementation (which is a BTreeSet of the indices themselves) and thus satisfy the goal of this issue. All of the performance benchmarks they provide pertain to speed rather than space but they seem good too, fwiw: https://github.com/CarlKCarlK/range-set-blaze/blob/main/docs/bench.md