Struct BitMap 

pub struct BitMap<H: CHasher, const N: usize> { /* private fields */ }

A bitmap supporting inclusion proofs through Merkelization.

Merkelization of the bitmap is performed over chunks of N bytes. If the goal is to minimize proof sizes, choose an N that is equal to the size or double the size of the hasher’s digest.

Warning

Even though we use u64 identifiers for bits, on 32-bit machines, the maximum addressable bit is limited to (u32::MAX * N * 8).

Implementations

impl<H: CHasher, const N: usize> BitMap<H, N>

pub const CHUNK_SIZE_BITS: u64 = PrunableBitMap<N>::CHUNK_SIZE_BITS

The size of a chunk in bits.

pub fn new() -> Self

Return a new empty bitmap.

pub fn size(&self) -> Position

pub fn get_node(&self, position: Position) -> Option<H::Digest>

pub async fn restore_pruned<C: RStorage + Metrics + Clock>( context: C, partition: &str, pool: Option<ThreadPool>, ) -> Result<Self, Error>

Restore the fully pruned state of a bitmap from the metadata in the given partition. (The caller must still replay retained elements to restore its full state.)

The metadata must store the number of pruned chunks and the pinned digests corresponding to that pruning boundary.

Returns an error if the bitmap could not be restored, e.g. because of data corruption or underlying storage error.

pub async fn write_pruned<C: RStorage + Metrics + Clock>( &self, context: C, partition: &str, ) -> Result<(), Error>

Write the information necessary to restore the bitmap in its fully pruned state at its last pruning boundary. Restoring the entire bitmap state is then possible by replaying the retained elements.

pub fn len(&self) -> u64

Return the number of bits currently stored in the bitmap, irrespective of any pruning.

pub fn is_empty(&self) -> bool

Returns true if the bitmap is empty.

pub fn pruned_bits(&self) -> u64

Return the number of bits that have been pruned from this bitmap.

pub fn prune_to_bit(&mut self, bit: u64) -> Result<(), Error>

Prune all complete chunks before the chunk containing the given bit.

The chunk containing bit and all subsequent chunks are retained. All chunks before it are pruned from the bitmap and the underlying MMR.

If bit equals the bitmap length, this prunes all complete chunks while retaining the empty trailing chunk, preparing the bitmap for appending new data.

Warning

• Returns Error::DirtyState if there are unmerkleized updates.

pub fn last_chunk(&self) -> (&[u8; N], u64)

Return the last chunk of the bitmap and its size in bits. The size can be 0 (meaning the last chunk is empty).

pub fn get_chunk_containing(&self, bit: u64) -> &[u8; N]

Returns the bitmap chunk containing the specified bit.

Warning

Panics if the bit doesn’t exist or has been pruned.

pub fn push(&mut self, bit: bool)

Add a single bit to the end of the bitmap.

Warning

The update will not affect the root until merkleize is called.

pub fn get_bit(&self, bit: u64) -> bool

Get the value of a bit.

Warning

Panics if the bit doesn’t exist or has been pruned.

pub fn get_bit_from_chunk(chunk: &[u8; N], bit: u64) -> bool

Get the value of a bit from its chunk. bit is an index into the entire bitmap, not just the chunk.

pub fn set_bit(&mut self, bit: u64, value: bool)

Set the value of the given bit.

Warning

The update will not impact the root until merkleize is called.

pub fn is_dirty(&self) -> bool

Whether there are any updates that are not yet reflected in this bitmap’s root.

pub fn dirty_chunks(&self) -> Vec<Location>

The chunks that have been modified or added since the last call to merkleize.

pub async fn merkleize( &mut self, hasher: &mut impl Hasher<H>, ) -> Result<(), Error>

Merkleize all updates not yet reflected in the bitmap’s root.

pub async fn root( &self, hasher: &mut impl Hasher<H>, ) -> Result<H::Digest, Error>

Return the root digest against which inclusion proofs can be verified.

Format

The root digest is simply that of the underlying MMR whenever the bit count falls on a chunk boundary. Otherwise, the root is computed as follows in order to capture the bits that are not yet part of the MMR:

hash(mmr_root || next_bit as u64 be_bytes || last_chunk_digest)

Warning

Panics if there are unmerkleized updates.

pub fn partial_chunk_root( hasher: &mut H, mmr_root: &H::Digest, next_bit: u64, last_chunk_digest: &H::Digest, ) -> H::Digest

Returns a root digest that incorporates bits that aren’t part of the MMR yet because they belong to the last (unfilled) chunk.

pub async fn proof( &self, hasher: &mut impl Hasher<H>, bit: u64, ) -> Result<(Proof<H::Digest>, [u8; N]), Error>

Return an inclusion proof for the specified bit, along with the chunk of the bitmap containing that bit. The proof can be used to prove any bit in the chunk.

The bitmap proof stores the number of bits in the bitmap within the size field of the proof instead of MMR size since the underlying MMR’s size does not reflect the number of bits in any partial chunk. The underlying MMR size can be derived from the number of bits as leaf_num_to_pos(proof.size / Bitmap<_, N>::CHUNK_SIZE_BITS).

Errors

Returns Error::BitOutOfBounds if bit is out of bounds. Returns Error::DirtyState if there are unmerkleized updates.

pub fn verify_bit_inclusion( hasher: &mut impl Hasher<H>, proof: &Proof<H::Digest>, chunk: &[u8; N], bit: u64, root: &H::Digest, ) -> bool

Verify whether proof proves that the chunk containing the given bit belongs to the bitmap corresponding to root.

pub async fn destroy<C: RStorage + Metrics + Clock>( context: C, partition: &str, ) -> Result<(), Error>

Destroy the bitmap metadata from disk.

Trait Implementations

impl<H: CHasher, const N: usize> Default for BitMap<H, N>

fn default() -> Self

Returns the “default value” for a type.

impl<H: CHasher, const N: usize> Storage<<H as Hasher>::Digest> for BitMap<H, N>

fn size(&self) -> Position

Return the number of elements in the MMR.

async fn get_node(&self, position: Position) -> Result<Option<H::Digest>, Error>

Return the specified node of the MMR if it exists & hasn’t been pruned.